chapters/Background.tex

   1 \chapter{Literature Review}\label{Background}
   2
   3 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}.
   4
   5 \rephrase{TODO: If I want to link to the Paper by Paper summary it will need a bit of rewriting}.
   6
   7 \rephrase{TODO: Actually (re)write this entire chapter}.
   8
   9 \rephrase{TODO: Un dot point ify}
  10
  11 \rephrase{TODO: Citations}
  12
  13 \rephrase{TODO: Make less terrible}
  14
  15
  16 \rephrase{TODO: Reconsider sections (do I really want to make this go down to} \verb/\subsubsection/?)
  17
  18 \rephrase{TODO: :-(}
  19
  20
  21
  22 \section{Vector Graphics vs Raster Graphics}
  23
  24 \newlength\imageheight
  25 \newlength\imagewidth
  26 \settoheight\imageheight{\includegraphics{figures/fox-raster.png}}
  27 \settowidth\imagewidth{\includegraphics{figures/fox-raster.png}}
  28
  29 %Height: \the\imageheight
  30 %Width: \the\imagewidth
  31
  32 \rephrase{TODO: Distinguish between Raster Formats and the Rasterisation of an image (which may or may not be in a raster format)}
  33
  34
  35 \subsubsection{Raster Graphics}
  36 \begin{itemize}
  37         \item Bitmap --- array of colour information for pixels
  38         \item Exact pixels in a similar format to how they would appear on a (modern) display device.
  39         \begin{itemize}
  40                 \item Also similar to how they would be stored by a camera or scanner
  41                 \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}
  42                 \item \rephrase{For that matter, should it described as 3D (3rd dimension = colour)?}
  43         \end{itemize}
  44         \item Lowest level representation of a document
  45         \item Issues with scaling; values of extra pixels must be calculated
  46         \item Not convenient to edit; ill suited to text
  47 \end{itemize}
  48
  49
  50 \subsubsection{Vector Graphics}
  51 \begin{itemize}
  52         \item Stores relative position of primitives - scales better
  53         \item In particular, \emph{edges} of lines can be zoomed without becomming jagged; sometimes (somewhat misleadingly) described as ``infinitely sharp''
  54         \item Vector Graphics must be rasterised before being drawn on most display devices.
  55         \item Still can't scale forever due to use of fixed size floats
  56 \end{itemize}
  57
  58 \subsubsection{Resolution and Raster Graphics}
  59 \begin{itemize}
  60         \item DPI = dots (pixels) per inch differs per display device - a rastered image looks different on different display devices
  61         \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.
  62         \item Tex uses 72.27 points per inch (?)
  63         \item The vector image was rastered at 96 points per inch
  64         \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
  65 \end{itemize}
  66
  67
  68
  69 \begin{figure}[H]
  70         \centering
  71
  72         \includegraphics[scale=0.7528125]{figures/fox-vector.pdf}
  73         \includegraphics[scale=0.7528125]{figures/fox-raster.png}
  74         \includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{figures/fox-vector.pdf}
  75         \includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{figures/fox-raster.png}
  76         \caption{Scaling of vector and Raster Graphics}\label{vector-vs-raster}
  77 \end{figure}
  78
  79
  80
  81 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\%$}.
  82
  83 Various ways to end this section:
  84 \begin{enumerate}
  85         \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}.
  86         \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.}
  87         \item \rephrase{You can't have infinite precision in raster graphics by definition, therefore we no longer care about them in this report.}
  88         \item \rephrase{This report being in a vector format is a clue that we only care about vector formats}.
  89 \end{enumerate}
  90
  91 \section{Primitives in Vector Graphics Formats (and how they are Rendered)}
  92
  93 \subsection{Bezier Curves}
  94 \rephrase{I did an ipython notebook on this in February, but I forgot all of it}
  95
  96 \subsection{Text}
  97 Text is just Bezier Curves
  98
  99 \subsection{Shapes}
 100 Shapes are just bezier curves joined together.
 101
 102 \subsection{Other Things}
 103 We don't really care about other things (ie: Colour gradients etc) in this report.
 104
 105 \section{Document Representations}
 106
 107 \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.}
 108
 109
 110
 111 \subsection{Interpreted Model}
 112
 113 \rephrase{Did I just invent that terminology or did I read it in a paper? Is there actually existing terminology for this that sounds similar enough to ``Document Object Model'' for me to compare them side by side?}
 114
 115 \begin{itemize}
 116         \item This model treats a document as the source code program which produces graphics
 117         \item Arose from the desire to produce printed documents using computers (which were still limited to text only displays).
 118         \item Typed by hand or (later) generated by a GUI program
 119         \item PostScript --- largely supersceded by PDF on the desktop but still used by printers\footnote{Desktop pdf viewers can still cope with PS, but I wonder if a smartphone pdf viewer would implement it?}
 120         \item \TeX --- Predates PostScript! {\LaTeX } is being used to create this very document and until now I didn't even have it here!
 121         \begin{itemize}
 122                 \item I don't really want to go down the path of investigating the billion steps involved in getting \LaTeX into an actually viewable format
 123                 \item There are interpreters (usually WYSIWYG editors) for \LaTeX though
 124                 \item Maybe if \LaTeX were more popular there would be desktop viewers that converted \LaTeX directly into graphics
 125         \end{itemize}
 126         \item Potential for dynamic content, interactivity; dynamic PostScript, enhanced Postscript
 127
 128         \item Scientific Computing --- Mathematica, Matlab, IPython Notebook --- The document and the code that produces it are stored together
 129         \item Problems with security --- Turing complete, can be exploited easily
 130 \end{itemize}
 131
 132 \subsection{Crippled Interpreted Model}
 133
 134 \rephrase{I'm pretty sure I made that one up}
 135
 136 \begin{itemize}
 137         \item PDF is PostScript but without the Turing Completeness
 138         \item Solves security issues, more efficient
 139 \end{itemize}
 140
 141 \subsection{Document Object Model}
 142
 143 \begin{itemize}
 144         \item DOM = Tree of nodes; node may have attributes, children, data
 145         \item XML (SGML) is the standard language used to represent documents in the DOM
 146         \item XML is plain text
 147         \item SVG is a standard for a vector graphics language conforming to XML (ie: a DOM format)
 148 \end{itemize}
 149
 150 \subsection{Blurring the Line --- Javascript}
 151
 152 \begin{itemize}
 153         \item The document is expressed in DOM format using XML/HTML/SVG
 154         \item A Javascript program is run which can modify the DOM
 155         \item At a high level this may be simply changing attributes of elements dynamically
 156         \item For low level control there is canvas2D and even WebGL which gives direct access to OpenGL functions
 157         \item Javascript can be used to make a HTML/SVG interactive
 158         \begin{itemize}
 159                 \item Overlooking the fact that the SVG standard already allows for interactive elements...
 160         \end{itemize}
 161         \item Javascript is now becoming used even in desktop environments and programs (Windows 8, GNOME 3, Cinnamon, Game Maker Studio) ({\bf shudder})
 162         \item There are also a range of papers about including Javascript in PDF ``Pixels or Perish'' being the only one we have actually read\cite{hayes2012pixels}
 163         \begin{itemize}
 164                 \item I have no idea how this works; PDF is based on PostScript... it seems very circular to be using a programming language to modify a document that is modelled on being a (non turing complete) program
 165                 \item This is yet more proof that people will converge towards solutions that ``work'' rather than those that are optimal or elegant
 166                 \item I guess it's too much effort to make HTML look like PDF (or vice versa) so we could phase one out
 167         \end{itemize}
 168 \end{itemize}
 169
 170
 171
 172
 173 \section{Precision Limitations of Modern Documents}
 174
 175 \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}.
 176
 177 \subsection{Limitations Imposed By Standards}
 178 \begin{itemize}
 179         \item Implementations of PostScript and PDF must by definition restrict themselves to IEEE binary32 ``single precision'' floating point number representations in order to conform to the standards\cite{plrm, pdfref17}.
 180         \item Implementations of SVG are by definition required to use IEEE binary32 as a {\bf minimum}. ``High Quality'' SVG viewers are required to use at least IEEE binary64.\cite{svg2011-1.1}
 181 \end{itemize}
 182
 183
 184 \subsection{Limitations Imposed By Graphics APIs and/or GPUs}
 185
 186 It's not really the standard's fault (although they could specify double); they specify IEEE because underlying hardware must use IEEE.
 187
 188 \begin{itemize}
 189         \item Internal representations are GPU dependent\cite{hillesland2004paranoia}
 190         \item OpenGL standards specify: binary16, binary32, binary64
 191         \item OpenVG aims to become a standard API for SVG viewers but it uses binary32 and may be {\bf worse} internally\cite{rice2008openvg}
 192 \end{itemize}
 193
 194 \subsection{Limitations Imposed By CPU}
 195
 196 Even if we don't use the GPU, CPU's are restricted in their representation of floating point numbers by the IEEE standard.
 197
 198 \rephrase{AND THUS WE FINALLY GET TO THE POINT}
 199
 200 \section{Representation of Numbers}
 201
 202 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.
 203
 204 Whilst David Gow will be focusing on structures \rephrase{and the use of multiple coordinate systems} to represent a document so as to avoid or reduce these limitations\cite{proposalGow}, the focus of our own research will be \rephrase{increased precision in the representation of real numbers so as to get away with using a single global coordinate system}.
 205
 206 \subsection{The IEEE Standard}
 207
 208 \subsection{Floating Point Number Representations}
 209
 210 \begin{align*}
 211         x &= (-1)^{s} \times m \times B^{e}
 212 \end{align*}
 213
 214 $B = 2$, although IEEE also defines decimal representations for $B = 10$ --- these are useful in financial software\cite{ieee2008-754}.
 215
 216 \rephrase{Aside: Are decimal representations for a document format eg: CAD also useful because you can then use metric coordinate systems?}
 217
 218 \subsubsection{Precision}
 219
 220 The floats map an infinite set of real numbers onto a discrete set of representations.
 221
 222 \rephrase{Figure: 8 bit ``minifloats'' (all 255 of them) clearly showing the ``precision vs range'' issue}
 223
 224 The most a result can be rounded in conversion to a floating point number is the units in last place; $m_{N} \times B^{e}$.
 225
 226 \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}
 227
 228 \subsection{Examples of Precision Related Errors in Floating Point Arithmetic}
 229
 230 \subsection{Relate This to the Sorts of Maths Done By Document Formats}
 231
 232 \subsection{Techniques for Arbitrary Precision Arithmetic}
 233
 234 \begin{itemize}
 235         \item Fast2SUM for summation (and multiplication).
 236         \item Guard digits.
 237         \item Other techniques
 238         \item Hardware techniques that improve speed (which may be beneficial because you can get away with higher precision in hardware)
 239         \item Anything you can do in hardware you can do in software but it will be slower and have more segmentation faults
 240 \end{itemize}
 241
 242 \subsection{Alternate Number Representations}
 243
 244 \rephrase{They exist\cite{HFP}}.
 245
 246