LitReviewDavid.tex

   1 \documentclass[a4paper,10pt]{article}
   2 \usepackage[utf8]{inputenc}
   3 \usepackage{hyperref}
   4 \usepackage{graphicx}
   5 \usepackage{amsmath}
   6
   7 %opening
   8 \title{Literature Review}
   9 \author{David Gow}
  10
  11 \begin{document}
  12
  13 \maketitle
  14
  15 \section{Introduction}
  16
  17 Since mankind first climbed down from the trees, it is our ability to communicate that has made us unique.
  18 Once ideas could be passed from person to person, it made sense to have a permanent record of them; one which
  19 could be passed on from person to person without them ever meeting.
  20
  21 And thus the document was born.
  22
  23 Traditionally, documents have been static: just marks on paper, but with the advent of computers many more possibilities open up.
  24
  25 \section{Document Formats}
  26
  27 Most existing document formats --- such as the venerable PostScript and PDF --- are, however, designed to imitate
  28 existing paper documents, largely to allow for easy printing. In order to truly take advantage of the possibilities operating in the digital
  29 domain opens up to us, we must look to new formats.
  30
  31 Formats such as \texttt{HTML} allow for a greater scope of interactivity and for a more data-driven model, allowing
  32 the content of the document to be explored in ways that perhaps the author had not anticipated.\cite{hayes2012pixels}
  33 However, these data-driven formats typically do not support fixed layouts, and the display differs from renderer to
  34 renderer.
  35
  36 Ultimately, there are two fundamental stages by which all documents --- digital or otherwise --- are produced and displayed:
  37 \emph{layout} and \emph{display}. The \emph{layout} stage is where the positions and sizes of text and other graphics are
  38 determined, while the \emph{display} stage actually produces the final output, whether as ink on paper or pixels on a computer monitor.
  39
  40 Different document formats approach these stages in different ways. Some treat the document as a program, written in
  41 a turing complete document language with instructions which emit shapes to be displayed. These shapes are either displayed
  42 immediately, as in PostScript, or stored in another file, such as with \TeX or \LaTeX, which emit a \texttt{DVI} file. Most other
  43 forms of document use a \emph{Document Object Model}, being a list or tree of objects to be rendered. \texttt{DVI}, \texttt{PDF},
  44 \texttt{HTML}\footnote{Some of these formats --- most notably \texttt{HTML} --- implement a scripting lanugage such as JavaScript,
  45 which permit the DOM to be modified while the document is being viewed.} and SVG. Of these, only \texttt{HTML} and \TeX typically
  46 store documents in pre-layout stages, whereas even turing complete document formats such as PostScript typically encode documents
  47 which already have their elements placed.
  48
  49 Existing document formats, due to being designed to model paper,
  50 have limited precision (8 decimal digits for PostScript\cite{plrm}, 5 decimal digits for PDF\cite{pdfref17}).
  51 This matches the limited resolution of printers and ink, but is limited when compared to what aught to be possible
  52 with ``zoom'' functionality, which is prevent from working beyond a limited scale factor, lest artefacts appear due
  53 to issues with numeric precision.
  54
  55 \section{Rendering}
  56
  57 Computer graphics comes in two forms: bit-mapped (or raster) graphics, which is defined by an array of pixel colours;
  58 and \emph{vector} graphics, defined by mathematical descriptions of objects. Bit-mapped graphics are well suited to photographs
  59 and are match how cameras, printers and monitors work. However, bitmap devices do not handle zooming beyond their
  60 ``native'' resolution --- the resolution where one document pixel maps to one display pixel ---, exhibiting an artefact
  61 called pixelation where the pixel structure becomes evident. Attempts to use interpolation to hide this effect are
  62 never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly effected.
  63
  64 \begin{figure}[h]
  65         \centering \includegraphics[width=0.8\linewidth]{figures/vectorraster_example}
  66         \caption{A circle as a vector image and a $32 \times 32$ pixel raster image}
  67 \end{figure}
  68
  69
  70 Vector graphics lack many of these problems: the representation is independent of the output resolution, and rather
  71 an abstract description of what it is being rendered, typically as a combination of simple geometric shapes like lines,
  72 arcs and ``B\'ezier curves''.
  73 As existing displays (and printers) are bit-mapped devices, vector documents must be \emph{rasterized} into a bitmap at
  74 a given resolution. This bitmap is then displayed or printed. The resulting bitmap is then an approximation of the vector image
  75 at that resolution.
  76
  77 This project will be based around vector graphics, as these properties make it more suited to experimenting with zoom
  78 quality.
  79
  80
  81 The rasterization process typically operates on an individual ``object'' or ``shape'' at a time: there are special algorithms
  82 for rendering lines\cite{bresenham1965algorithm}, triangles\cite{giesen2013triangle}, polygons\cite{pineda1988parallel} and B\'ezier
  83 Curves\cite{goldman_thefractal}. Typically, these are rasterized independently and composited in the bitmap domain using Porter-Duff
  84 compositing\cite{porter1984compositing} into a single image. This allows complex images to be formed from many simple pieces, as well
  85 as allowing for layered translucent objects, which would otherwise require the solution of some very complex constructive geometry problems.
  86
  87 While traditionally, rasterization was done entirely in software, modern computers and mobile devices have hardware support for rasterizing
  88 some basic primitives --- typically lines and triangles ---, designed for use rendering 3D scenes. This hardware is usually programmed with an
  89 API like \texttt{OpenGL}\cite{openglspec}.
  90
  91 More complex shapes like B\'ezier curves can be rendered by combining the use of bitmapped textures (possibly using signed-distance
  92 fields\cite{leymarie1992fast}\cite{frisken2000adaptively}\cite{green2007improved}) with polygons approximating the curve's shape\cite{loop2005resolution}\cite{loop2007rendering}.
  93
  94 Indeed, there are several implementations of entire vector graphics systems using OpenGL: OpenVG\cite{robart2009openvg} on top of OpenGL ES\cite{oh2007implementation};
  95 the Cairo\cite{worth2003xr} library, based around the PostScript/PDF rendering model, has the ``Glitz'' OpenGL backend\cite{nilsson2004glitz} and the SVG/PostScript GPU
  96 renderer by nVidia\cite{kilgard2012gpu} as an OpenGL extension\cite{kilgard300programming}.
  97
  98
  99 \section{Floating-Point Precision}
 100
 101 On modern computer architectures, there are two basic number formats supported:
 102 fixed-width integers and \emph{floating-point} numbers. Typically, computers
 103 natively support integers of up to 64 bits, capable of representing all integers
 104 between $0$ and $2^{64} - 1$\footnote{Most machines also support \emph{signed} integers,
 105 which have the same cardinality as their \emph{unsigned} counterparts, but which
 106 represent integers between $-(2^{63})$ and $2^{63} - 1$}.
 107
 108 By introducing a fractional component (analogous to a decimal point), we can convert
 109 integers to \emph{fixed-point} numbers, which have a more limited range, but a fixed, greater
 110 precision. For example, a number in 4.4 fixed-point format would have four bits representing the integer
 111 component, and four bits representing the fractional component:
 112 \begin{equation}
 113         \underbrace{0101}_\text{integer component}.\underbrace{1100}_\text{fractional component} = 5.75
 114 \end{equation}
 115
 116
 117 Floating-point numbers\cite{goldberg1992thedesign} are the binary equivalent of scientific notation:
 118 each number consisting of an exponent ($e$) and a mantissa ($m$) such that a number is given by
 119 \begin{equation}
 120         n = 2^{e} \times m
 121 \end{equation}
 122
 123 The IEEE 754 standard\cite{ieee754std1985} defines several floating-point data types
 124 which are used\footnote{Many systems' implement the IEEE 754 standard's storage formats,
 125 but do not implement arithmetic operations in accordance with this standard.} by most
 126 computer systems. The standard defines 32-bit (8-bit exponent, 23-bit mantissa, 1 sign bit) and
 127 64-bit (11-bit exponent, 53-bit mantissa, 1 sign bit) formats\footnote{The 2008
 128 revision to this standard\cite{ieee754std2008} adds some additional formats, but is
 129 less widely supported in hardware.}, which can store approximately 7 and 15 decimal digits
 130 of precision respectively.
 131
 132 Floating-point numbers behave quite differently to integers or fixed-point numbers, as
 133 the representable numbers are not evenly distributed. Large numbers are stored to a lesser
 134 precision than numbers close to zero. This can present problems in documents when zooming in
 135 on objects far from the origin.
 136
 137 IEEE floating-point has some interesting features as well, including values for negative zero,
 138 positive and negative infinity and the ``Not a Number'' (NaN) value. Indeed, with these values,
 139 IEEE 754 floating-point equality does not form an equivalence relation, which can cause issues
 140 when not considered carefully.\cite{goldberg1991whatevery}
 141
 142 Arb. precision exists
 143
 144 Higher precision numeric types can be implemented or used on the GPU, but are
 145 slow.
 146 \cite{emmart2010high}
 147
 148
 149
 150 \section{Quadtrees}
 151 When viewing or processing a small part of a large document, it may be helpful to
 152 only processs --- or \emph{cull} --- parts of the document which are not on-screen.
 153
 154 \begin{figure}[h]
 155         \centering \includegraphics[width=0.4\linewidth]{figures/quadtree_example}
 156         \caption{A simple quadtree.}
 157 \end{figure}
 158 The quadtree\cite{finkel1974quad}is a data structure --- one of a family of \emph{spatial}
 159 data structures --- which recursively breaks down space into smaller subregions
 160 which can be processed independently. Points (or other objects) are added to a single
 161 node, which if certain criteria are met --- typically the number of points in a node
 162 exceeding a maximum, though in our case likely the level of precision required exceeding
 163 that supported by the data type in use --- is split into four equal-sized subregions, and
 164 points attached to the region which contains them.
 165
 166 In this project, we will be experimenting with a form of quadtree in which each
 167 node has its own independent coordinate system, allowing us to store some spatial
 168 information\footnote{One bit per-coordinate, per-level of the quadtree} within the
 169 quadtree structure, eliminating redundancy in the coordinates of nearby objects.
 170
 171 Other spatial data structures exist, such as the KD-tree\cite{bentley1975multidimensional},
 172 which partitions the space on any axis-aligned line; or the BSP tree\cite{fuchs1980onvisible},
 173 which splits along an arbitrary line which need not be axis aligned. We believe, however,
 174 that the simpler conversion from binary coordinates to the quadtree's binary split make
 175 it a better avenue for initial research to explore.
 176
 177 \bibliographystyle{unsrt}
 178 \bibliography{papers}
 179
 180 \end{document}