Literally more Literature
authorSam Moore <>
Fri, 2 May 2014 15:32:15 +0000 (23:32 +0800)
committerSam Moore <>
Fri, 2 May 2014 15:32:15 +0000 (23:32 +0800)
Extended that damn fox example even more

Put in markers for the sections as described in the previous commit.
They don't match the current sections. This is sort of a clusterfuck.

Keep wanting to go into more detail on things that probably don't matter.

figures/bezier-goldman.png [new file with mode: 0644]
figures/g3636-8.png [new file with mode: 0644]
figures/rasteraster.png [new file with mode: 0644]

index 4bedb57..8a94f02 100644 (file)
@@ -1,25 +1,38 @@
 \chapter{Literature Review}\label{Background}
-This chapter will \rephrase{review the literature. It will also include some figures created by us from our test programs to aid with conceptual understanding of the literature.} A paper by paper summary of the literature is also available at: \\ \url{}.
+\rephrase{0. Here is a brilliant summary of the sections below}
-\rephrase{TODO: If I want to link to the Paper by Paper summary it will need a bit of rewriting}.
+This chapter provides an overview of relevant literature. The areas of interest can be broadly grouped into two largely seperate categories; Documents and Number Representations.
-\rephrase{TODO: Actually (re)write this entire chapter}.
+The first half of this chapter will be devoted to documents themselves, including: the representation and rendering of low level graphics primitives, how collections of these primitives are represented in document formats, and the various standards for documents in use today. 
-\rephrase{TODO: Un dot point ify}
+We will find that although there has been a great deal of research into the rendering, storing, editing, manipulation, and extension of document formats, all popular document standards are content to specify at best a single precision IEEE-754 floating point number representations. 
-\rephrase{TODO: Citations}
+The research on arbitrary precision arithmetic applied to documents is very sparse; however arbitrary precision arithmetic itself is a very active field of research. Therefore, the second half of this chapter will be devoted to considering the IEEE-754 standard, its advantages and limitations, and possible alternative number representations to allow for arbitrary precision arithmetic.
-\rephrase{TODO: Make less terrible}
+In Chapter \ref{Progress}, we will discuss our findings so far with regards to arbitrary precision arithmetic applied to document formats.
-\rephrase{TODO: Reconsider sections (do I really want to make this go down to} \verb/\subsubsection/?)
-\rephrase{TODO: :-(}
+\section{Raster and Vector Graphics}\label{vector-vs-raster-graphics}
+\rephrase{1. Here are the fundamentals of graphics (raster and vector, rendering)}
+At a fundamental level everything that is seen on a display device is represented as either a vector or raster image. These images can be stored as stand alone documents or embedded in a much more complex document format capable of containing many other types of information.
-\section{Vector Graphics vs Raster Graphics}
+A raster image's structure closely matches it's representation as shown on modern display hardware; the image is represented as a grid of filled square ``pixels''. Each pixel is the same size and contains information describing its colour. This representation is simple and also well suited to storing images as produced by cameras and scanners\cite{citationneeded}.
+The drawback of raster images is that by their very nature there can only be one level of detail. Figures \ref{vector-vs-raster} and \ref{vector-vs-raster-scaled} attempt to illustrate this by comparing raster images to vector images in a similar way to Worth and Packard\cite{worth2003xr}.
+Consider the right side of Figure \ref{vector-vs-raster}. This is a raster image which should be recognisable as an animal defined by fairly sharp edges. Figure \ref{vector-vs-raster-scaled} shows that zooming on the animal's face causes these edges to appear jagged. There is no information in the original image as to what should be displayed at a larger size, so each square shaped pixel is simply increased in size. A blurring effect will probably be visible in most PDF viewers; the software has attempted to make the ``edge'' appear more realistic using a technique called ``antialiasing'' which averages neighbouring pixels in the original image in order to generate extra pixels in the scaled image\cite{citationneeded}.\footnote{The exact appearance of the images at different zoom levels will depend greatly on the PDF viewer or printer used to display this report. On the author's display using the Atril (1.6.0) viewer, the top images appear to be pixel perfect mirror images at a 100\% scale. In the bottom raster image, antialiasing is not applied at zoom levels above $125\%$ and the effect of scaling is quite noticable.}
+%\footnote{\noindent This behaviour may be configured in some PDF viewers (Adobe Reader) whilst others (Evince, Atril, Okular) will choose whether or not to bother with antialiasing based on the zoom level. For best results experiment with changing the zoom level in your PDF viewer.\footnotemark}\footnotetext{On the author's hardware, the animals in the vector and raster images should appear mirrored pixel for pixel; but they may vary slightly on other PDF viewers or display devices.}
+In contrast, the left sides of Figures \ref{vector-vs-raster} and \ref{vector-vs-raster-scaled} are a vector image. A vector image contains information about a number of geometric shapes. To display this image on modern display hardware, the coordinates are transformed according to the view and \emph{then} the image is converted into a raster like representation. Whilst the raster image merely appears to contain edges, the vector image actually contains information about these edges, meaning they can be displayed ``infinitely sharply'' at any level of detail\cite{citationneeded} --- or they could be if the coordinates are stored with enough precision (see Section \ref{}). Thus, vector images are well suited to high quality digital art\footnote{Figure \ref{vector-vs-raster} is not to be taken as an example of this.} and text\cite{citationneeded}.
+\rephrase{Woah, an entire page with only one citation ham fisted in after I had written the rest... and the ``actually writing it'' phase of the Lit Review is off to a great start.}
@@ -29,84 +42,82 @@ This chapter will \rephrase{review the literature. It will also include some fig
 %Height: \the\imageheight
 %Width: \the\imagewidth
-\rephrase{TODO: Distinguish between Raster Formats and the Rasterisation of an image (which may or may not be in a raster format)}
+       \centering
+       \includegraphics[scale=0.7528125]{figures/fox-vector.pdf}
+       \includegraphics[scale=0.7528125]{figures/fox-raster.png}
+       \caption{Original Vector and Raster Images}\label{vector-vs-raster}
+\end{figure} % As much as I hate to break up the party, these fit best over the page (at the moment)
+       \centering
+       \includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{figures/fox-vector.pdf}
+       \includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{figures/fox-raster.png}
+       \caption{Scaled Vector and Raster Images}\label{vector-vs-raster-scaled}
-\subsubsection{Raster Graphics}
-       \item Bitmap --- array of colour information for pixels
-       \item Exact pixels in a similar format to how they would appear on a (modern) display device.
-       \begin{itemize}
-               \item Also similar to how they would be stored by a camera or scanner
-               \item \rephrase{Is it misleading to say 2D array? Pixels are actually stored in a 1D array, but conceptually it's nicer to say 2D}
-               \item \rephrase{For that matter, should it described as 3D (3rd dimension = colour)?}
-       \end{itemize}
-       \item Lowest level representation of a document
-       \item Issues with scaling; values of extra pixels must be calculated
-       \item Not convenient to edit; ill suited to text
+\section{Rendering Vector Images}
+Throughout Section \ref{vector-vs-raster-graphics} we were careful to refer to ``modern'' display devices, which are raster based. It is of some historical significance that vector display devices were popular during the 70s and 80s, and so algorithms for drawing a vector image directly without rasterisation exist. An example is the shading of polygons which is somewhat more complicated on a vector display than a raster display\cite{brassel1979analgorithm, lane1983analgorithm}.
-\subsubsection{Vector Graphics}
-       \item Stores relative position of primitives - scales better
-       \item In particular, \emph{edges} of lines can be zoomed without becomming jagged; sometimes (somewhat misleadingly) described as ``infinitely sharp''
-       \item Vector Graphics must be rasterised before being drawn on most display devices.
-       \item Still can't scale forever due to use of fixed size floats
+All modern displays of practical interest are raster based. In this section we explore the structure of vector graphics in more detail, and how different primitives are rendered.
+\rephrase{After the wall of citationless text in Section \ref{vector-vs-raster-graphics} we should probably redeem ourselves a bit here}
-\subsubsection{Resolution and Raster Graphics}
+\subsection{Bezier Curves}
+The bezier curve is of vital importance in vector graphics.
+\rephrase{Things this section lacks}
-       \item DPI = dots (pixels) per inch differs per display device - a rastered image looks different on different display devices
-       \item PostScript/PDF use 72 points per inch; this means a rasterised image will look the same in all pdf viewers regardless of the display.
-       \item Tex uses 72.27 points per inch (?)
-       \item The vector image was rastered at 96 points per inch
-       \item Hence, have to scale by 72.27/96 = 0.7528125 to get the vector and rastered version to look exactly the same in the pdf
+       \item Who came up with them (presumably it was a guy named Bezier)
+       \item Flesh out how they evolved or came into use?
+       \item Naive algorithm
+       \item De Casteljau Algorithm
+Recently, Goldman presented an argument that Bezier's could be considered as fractal in nature, a fractal being the fixed point of an iterated function system\cite{goldman_thefractal}. Goldman's proof depends upon a modification to the De Casteljau Subdivision algorithm. Whilst we will not go the details of the proof, or attempt comment on its theoretical value, it is interesting to note that Goldman's algorithm is not only worse than the De Casteljau algorithm upon which it was based, but it also performs worse than a naive Bezier rendering algorithm. Figure \ref{bezier-goldman} shows our results using implementations of the various algorithms in python.
+       \includegraphics[width=0.7\textwidth]{figures/bezier-goldman.png}
+       \caption{Performance of Bezier Subdivision Algorithms}\label{bezier-goldman}
-       \includegraphics[scale=0.7528125]{figures/fox-vector.pdf}
-       \includegraphics[scale=0.7528125]{figures/fox-raster.png}
-       \includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{figures/fox-vector.pdf}
-       \includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{figures/fox-raster.png}
-       \caption{Scaling of vector and Raster Graphics}\label{vector-vs-raster}
+\rephrase{Does the Goldman bit need to be here? Probably NOT. Do I need to check very very carefully that I haven't made a mistake before saying this? YES. Will I have made a mistake? Probably.}
+Shapes are just bezier curves joined together.
-Figure \ref{vector-vs-raster} shows a vector image (left) which has been rasterised (right). At the original scale the two foxes should appear to be mirror images\footnote{If I've worked out the scaling to account for dpi differences between inkscape and latex/pdf correctly}. When the scale is increased, the edges of the vector image remain sharp, whilst the raster image begins to appear jagged. PDF viewers will typically use antialiasing to smooth the edges of a scaled bitmap, causing the image to appear blurred.\footnote{In the Atril Document Viewer 1.6.0 this image will only be antialiased at zoom levels $\leq 125\%$}.
+\subsubsection{Approximating a Circle Using Cubic Beziers}
-Various ways to end this section:
-       \item \rephrase{It should be obvious that documents containing text must use the vector graphics format, and so the remainder of this chapter will concentrate on the latter}.
-       \item \rephrase{As can be seen in Figure \ref{fox}, if we were to decide to pursue ``infinite precision'' in raster graphics we would be shooting ourselves in both feet and then the face before we even started. The rest of this chapter will concentrate on vector graphics.}
-       \item \rephrase{You can't have infinite precision in raster graphics by definition, therefore we no longer care about them in this report.}
-       \item \rephrase{This report being in a vector format is a clue that we only care about vector formats}.
+An example of a shape is a circle. We used some algorithm on wikipedia that I'm sure is in Literature somewhere
+\cite{citationneeded} and made a circle. It's in my magical ipython notebook with the De Casteljau stuff.
-\section{Primitives in Vector Graphics Formats (and how they are Rendered)}
+Text is just Bezier Curves, I think we proved out point with the circle, but maybe find some papers to cite\cite{citationneeded}
-\subsection{Bezier Curves}
-\rephrase{I did an ipython notebook on this in February, but I forgot all of it}
-Text is just Bezier Curves
-Shapes are just bezier curves joined together.
+Shading is actually extremely complicated! \cite{brassel1979analgorithm, lane1983analgorithm}
+\rephrase{Sure, but do we care enough to talk about it? We will run out of space at this rate}
 \subsection{Other Things}
-We don't really care about other things (ie: Colour gradients etc) in this report.
+We don't really care about other things in this report.
-\section{Document Representations}
+\rephrase{6. Sort of starts here... or at least background does}
-\rephrase{The file format can be either human readable\footnote{For some definition of human and some definition of readable} or binary\footnote{So, our viewer is basically a DOM style but stored in a binary format}. Can also be compressed or not. Here we are interested in how the document is interpreted or traversed in order to produce graphics output.}
+\subsection{Rendering Vector Graphics on the GPU}
+Traditionally, vector graphics have been rasterized by the CPU before being sent to the GPU for drawing\cite{kilgard2012gpu}. Lots of people would like to change this \cite{worth2003xr, loop2007rendering, rice2008openvg, kilgard2012gpu, green2007improved} ... \rephrase{All of these are things David found except kilgard which I thought I found and then realised David already had it :S}
+\rephrase{2. Here are the ways documents are structured ... we got here eventually}
+\section{Document Representations}
+\rephrase{The file format can be either human readable\footnote{For some definition of human and some definition of readable} or binary\footnote{So, our viewer is basically a DOM style but stored in a binary format}. Can also be compressed or not. Here we are interested in how the document is interpreted or traversed in order to produce graphics output.}
 \subsection{Interpreted Model}
@@ -181,10 +192,11 @@ Despite their limitations, we still use static, boring old PDFs. Particularly in
        \item Once you complicate a PDF by adding Javascript, it becomes more complicated to create; it is simply easier to use a series of static figures than to embed a shader in your document. Even for people that know WebGL.
+\rephrase{3. Here are the ways document standards specify precision (or don't)}
 \section{Precision in Modern Document Formats}
-\rephrase{All this is very interesting and provides important context, but it is not actually directly related to the problem of infinite precision which we are going to try and solve}.
+\rephrase{All the above is very interesting and provides important context, but it is not actually directly related to the problem of infinite precision which we are going to try and solve. Sorry to make you read it all.}
@@ -202,6 +214,8 @@ Despite their limitations, we still use static, boring old PDFs. Particularly in
 The use of IEEE binary32 floats in the PostScript and PDF standards is not surprising if we consider that these documents are oriented towards representing static pages. They don't actually need higher precision to do this; 32 bits is more than sufficient for A4 paper.
+\rephrase{4. Here is IEEE-754 which is what these standards use}
 \section{Representation of Numbers}
 Although this project has been motivated by a desire for more flexible document formats, the fundamental source of limited precision in vector document formats is the restriction to IEEE floating point numbers for representation of coordinates.
@@ -220,6 +234,7 @@ $B = 2$, although IEEE also defines decimal representations for $B = 10$ --- the
 \rephrase{Aside: Are decimal representations for a document format eg: CAD also useful because you can then use metric coordinate systems?}
 The floats map an infinite set of real numbers onto a discrete set of representations.
@@ -230,6 +245,9 @@ The most a result can be rounded in conversion to a floating point number is the
 \rephrase{Even though that paper that claims double is the best you will ever need because the error can be as much as the size of a bacterium relative to the distance to the moon}\cite{} \rephrase{there are many cases where increased number of bits will not save you}.\cite{HFP}
+\rephrase{5. Here are limitations of IEEE-754 floating point numbers on compatible hardware}
 \subsection{Limitations Imposed By CPU}
 CPU's are restricted in their representation of floating point numbers by the IEEE standard.
@@ -240,6 +258,8 @@ CPU's are restricted in their representation of floating point numbers by the IE
 Traditionally algorithms for drawing vector graphics are performed on the CPU; the image is rasterised and then sent to the GPU for rendering\cite{}. Recently there has been a great deal of literature relating to implementation of algorithms such as bezier curve rendering\cite{} or shading\cite{} on the GPU. As it seems the trend is to move towards GPU 
+\rephrase{6. Here are ways GPU might not be IEEE-754 --- This goes *somewhere* in here but not sure yet}
        \item Internal representations are GPU dependent and may not match IEEE\cite{hillesland2004paranoia}
        \item OpenGL standards specify: binary16, binary32, binary64
@@ -249,25 +269,17 @@ Traditionally algorithms for drawing vector graphics are performed on the CPU; t
-\subsection{Examples of Precision Related Errors in Floating Point Arithmetic}
-\subsection{Relate This to the Sorts of Maths Done By Document Formats}
-\subsection{Techniques for Arbitrary Precision Arithmetic}
-       \item Fast2SUM for summation (and multiplication).
-       \item Guard digits.
-       \item Other techniques
-       \item Hardware techniques that improve speed (which may be beneficial because you can get away with higher precision in hardware)
-       \item Anything you can do in hardware you can do in software but it will be slower and have more segmentation faults
+\rephrase{7. Sod all that, let's just use an arbitrary precision library (AND THUS WE FINALLY GET TO THE POINT)}
 \subsection{Alternate Number Representations}
 \rephrase{They exist\cite{HFP}}.
+Do it all using MFPR\cite{}, she'll be right.
+\rephrase{8. Here is a brilliant summary of sections 7- above}
+Dear reader, thankyou for your persistance in reading this mangled excuse for a Literature Review.
+Hopefully we have brought together the radically different areas of interest together in some sort of coherant fashion.
+In the next chapter we will talk about how we have succeeded in rendering a rectangle. It will be fun. I am looking forward to it.
index 6383224..ade601b 100644 (file)
@@ -16,15 +16,19 @@ We are now seeing a widespread use of mobile computing devices with touch screen
 In this project, we will explore the state of the art of current document formats including PDF, PostScript, SVG, HTML, and the limitations of each in terms of precision.
 We will consider designs for a document format allowing graphics primitives at an arbitrary level of zoom with no loss of detail. We will refer to such a document format as ``infinite precision''. A viewer and editor will be implemented as a proof of concept; we adopt a low level, ground up approach to designing this viewer so as to not become restricted by any single existing document format.
-\rephrase{New bit} \\
-It is necessary to clarify what we mean by ``infinite'' precision. We do not propose to be able to contain an infinite amount of information within a document. The goal is to be able to render a primitive at the same level of detail it is specified by a document format. For example, the precision of coordinates of primitives drawn in a graphical editor will always be limited by the resolution of the display on which they are drawn, but not by the viewer.
 There are many possible applications for documents in which precision is unlimited. Several areas of use include: visualisation of extremely large or infinite data sets; visualisation of high precision numerical computations; digital artwork; computer aided design; and maps.
+\subsection{Clarification of Terms}
+It may be necessary to clarify what we mean by the terms ``infinite precision'' and ``document formats''. Regarding the latter, we consider a document format to be any representation of visual information which is capable of being stored indefinitely. Regarding the former, we do not propose to be able to contain an infinite amount of information within such a document. The goal is to be able to render a primitive at the same level of detail it is specified by a document format, regardless of how precise this level is. For example, the precision of coordinates of primitives drawn in a graphical document editor will always be limited by the resolution of the display on which they are drawn, but not by the viewer.
 Initial research and software development is being conducted in collaboration with David Gow\cite{proposalGow}. Once a simple testbed application has been developed, we will individually explore approaches for introducing arbitrary levels of precision; these approaches will be implemented as alternate versions of the same software. The focus will be on drawing simple primitives (lines, polygons, circles). However, if time permits we will explore adding more complicated primitives (font glyphs, bezier curves, embedded bitmaps). 
+The process of rendering a document will be considered as a common area of research, whilst individual research will be conducted on means for allowing infinite precision.
 At this stage we have identified two possible areas for individual research:
diff --git a/figures/bezier-goldman.png b/figures/bezier-goldman.png
new file mode 100644 (file)
index 0000000..11e8311
Binary files /dev/null and b/figures/bezier-goldman.png differ
diff --git a/figures/g3636-8.png b/figures/g3636-8.png
new file mode 100644 (file)
index 0000000..363802f
Binary files /dev/null and b/figures/g3636-8.png differ
diff --git a/figures/rasteraster.png b/figures/rasteraster.png
new file mode 100644 (file)
index 0000000..b58d003
Binary files /dev/null and b/figures/rasteraster.png differ
index e5afcca..4ab4ffd 100644 (file)
Binary files a/thesis.pdf and b/thesis.pdf differ

UCC git Repository ::