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.}
   4
   5 \rephrase{TODO: Decide exactly what figures to make, then go make them; so far I have some ideas for a few about Floating Point operations, but none about the other stuff}.
   6
   7 \rephrase{TODO: Actually (re)write this entire chapter}.
   8 \rephrase{????: Do I really want to make this go down to} \verb/\subsubsection/
   9
  10 A paper by paper summary of the literature is also available at: \\ \url{http://szmoore.net/ipdf/documents/LiteratureNotes.pdf}.
  11
  12
  13 \rephrase{TODO: Actually make that readable or just remove the link}.
  14
  15 \section{Document Formats}
  16
  17 Since mankind climbed down from the trees... \rephrase{plagiarism alert!}
  18
  19 \subsection{Vector Graphics vs Raster Graphics}
  20
  21 Raster Graphics: Stores the exact pixels as they would appear on a device. Causes obvious issues with scaling. Lowest level representation of a document.
  22
  23
  24 Vector Graphics: Stores relative position of primitives - scales better. BUT still can't scale forever. Vector Graphics must be rasterised before being drawn on most display devices.
  25
  26 Vector Graphics formats may contain more information than is shown on the display device; Raster Graphics always contain as much or less pixel information than is shown.
  27
  28 \rephrase{Captain Obvious strikes again!} \\
  29 Figure \ref{fox} shows an example of scaling. The top image is a vector graphics drawing which has been scaled. The bottom image was a raster image of the original drawing which has then been scaled by the same amount. Scaling in = interpolation/antialiasing/just scale the pixels depending on the viewer and scale; scaling out = blurring of pixels by averaging of neighbours. If you are viewing this document in a PDF viewer you can try it yourself! Otherwise, welcome to the 21st century.
  30
  31
  32 \begin{figure}[H]
  33         \centering
  34         \includegraphics[width=0.5\textwidth]{figures/fox.pdf}
  35         \includegraphics[width=0.5\textwidth]{figures/fox.png}
  36         \caption{Scaling of Vector and Raster Graphics}\label{fox}
  37 \end{figure}
  38 \rephrase{I am torn as to whether to use a Fox or Rabbit or Rox here}.
  39
  40
  41 \subsection{Document Format Categories}
  42
  43 Main reference: Pixels or Perish\cite{hayes2012pixels}
  44
  45 \begin{enumerate}
  46         \item DOM - eg: HTML/XMLish - defined in terms of elements that can contain other elements
  47         \item Programming Language - eg: PostScript - programmer (or program) produces a program that is interpreted
  48         \item Combination - eg: Javascript with HTML/XML - Program is interpreted that modifies the DOM.
  49         \begin{itemize}
  50                 \item The lines are becomming increasingly blurred between 1. and 2.
  51                 \item In the case of Javascript/HTML, a special DOM element \verb/<canvas>/ allows even lower level manipulation of graphics.
  52         \end{itemize}
  53 \end{enumerate}
  54
  55 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}
  56
  57 \subsection{Modern Graphics Formats}
  58
  59 PostScript: Not actually widely used now, but PDF is basically the same thing.
  60 PDF: A way for adobe to make money
  61 SVG: Based on the DOM model, vector format
  62 BMP,PNG,GIF: Are these even worth mentioning?
  63
  64 HTML: With the evolution of JavaScript and CSS, this has actually become a competitive document format; it can display much more complex dynamic content than eg: PDF.
  65
  66 Web based documents still suffer from precision issues (JavaScript is notorious for its representation of everything, even integers, as floats, so you get rounding errors even with integer maths), and it also has other limitations (requires reasonably skilled programmer to create Javascript and/or a disgusting GUI tool that auto generates 10000 lines to display a button (I have seen one of these)). \rephrase{Hate on javascript a bit less maybe.}
  67
  68 \subsection{Precision Limitations}
  69
  70 \section{Representation of Numbers}
  71
  72 Although this project has been motivated by a desire for more flexible document formats, the fundamental source of limited precision in vector document formats such as PDF and PostScript is the use of floating point numbers to represent the coordinates of vertex positions. In particular, 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}.
  73
  74 Whilst David Gow will be focusing on how to structure a document format so as to avoid or reduce these limitations\cite{proposalGow}, the focus of our own research will be \rephrase{NUMBERS}.
  75
  76 \subsection{Floating Point Number Representations}
  77
  78 \begin{align*}
  79         x &= (-1)^{s} \times m \times B^{e}
  80 \end{align*}
  81
  82 $B = 2$, although IEEE also defines decimal representations for $B = 10$ --- these are useful in financial software\cite{ieee2008-754}.
  83
  84 \rephrase{Aside: Are decimal representations for a document format eg: CAD also useful because you can then use metric coordinate systems?}
  85
  86 \subsubsection{Precision}
  87
  88 The floats map an infinite set of real numbers onto a discrete set of representations.
  89
  90 \rephrase{Figure: 8 bit ``minifloats'' (all 255 of them) clearly showing the ``precision vs range'' issue}
  91
  92 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}$.
  93
  94 \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}
  95
  96
  97 \subsection{Alternate Number Representations}
  98
  99 \rephrase{They exist\cite{HFP}}.
 100
 101