LitReviewDavid.tex

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