\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{http://szmoore.net/ipdf/documents/LiteratureNotes.pdf}.
+\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/?)
+\pagebreak
-\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.}
\newlength\imageheight
\newlength\imagewidth
%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)}
+\begin{figure}[H]
+ \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)
+\begin{figure}[H]
+ \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}
+\end{figure}
-\subsubsection{Raster Graphics}
-\begin{itemize}
- \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
-\end{itemize}
+\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}
-\begin{itemize}
- \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
-\end{itemize}
+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}
\begin{itemize}
- \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
\end{itemize}
-
+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.
\begin{figure}[H]
\centering
+ \includegraphics[width=0.7\textwidth]{figures/bezier-goldman.png}
+ \caption{Performance of Bezier Subdivision Algorithms}\label{bezier-goldman}
+\end{figure}
- \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}
-\end{figure}
+\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.}
+\subsection{Shapes}
+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:
-\begin{enumerate}
- \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}.
-\end{enumerate}
+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)}
+\subsection{Text}
+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}
-\subsection{Text}
-Text is just Bezier Curves
+\subsection{Shading}
-\subsection{Shapes}
-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}
\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.
\end{itemize}
+\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.}
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.
\rephrase{Aside: Are decimal representations for a document format eg: CAD also useful because you can then use metric coordinate systems?}
+
\subsubsection{Precision}
The floats map an infinite set of real numbers onto a discrete set of representations.
\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.
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}
+
\begin{itemize}
\item Internal representations are GPU dependent and may not match IEEE\cite{hillesland2004paranoia}
\item OpenGL standards specify: binary16, binary32, binary64
-\rephrase{AND THUS WE FINALLY GET TO THE POINT}
-
-
-\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}
-
-\begin{itemize}
- \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
-\end{itemize}
+\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.
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au