LitReviewDavid.tex

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