LitReviewDavid.tex

   1 \documentclass[a4paper,10pt]{article}
   2 \usepackage[utf8]{inputenc}
   3 \usepackage{hyperref}
   4
   5 %opening
   6 \title{Literature Review}
   7 \author{David Gow}
   8
   9 \begin{document}
  10
  11 \maketitle
  12
  13 \section{Introduction}
  14
  15 Since mankind first climbed down from the trees, it is our ability to communicate that has made us unique.
  16 Once ideas could be passed from person to person, it made sense to have a permanent record of them; one which
  17 could be passed on from person to person without them ever meeting.
  18
  19 And thus the document was born.
  20
  21 Traditionally, documents have been static: just marks on paper, but with the advent of computers many more possibilities open up.
  22 Most existing document formats --- such as the venerable PostScript and PDF --- are, however, designed to imitate
  23 existing paper documents, largely to allow for easy printing. In order to truly take advantage of the possibilities operating in the digital
  24 domain opens up to us, we must look to new formats.
  25
  26 Formats such as \texttt{HTML} allow for a greater scope of interactivity and for a more data-driven model, allowing
  27 the content of the document to be explored in ways that perhaps the author had not anticipated.\cite{hayes2012pixels}
  28 However, these data-driven formats typically do not support fixed layouts, and the display differs from renderer to
  29 renderer.
  30
  31 Existing document formats, due to being designed to model paper,
  32 have limited precision (8 decimal digits for PostScript\cite{plrm}, 5 decimal digits for PDF\cite{pdfref17}).
  33 This matches the limited resolution of printers and ink, but is limited when compared to what aught to be possible
  34 with ``zoom'' functionality, which is prevent from working beyond a limited scale factor, lest artefacts appear due
  35 to issues with numeric precision.
  36
  37 \section{Rendering}
  38
  39 As existing displays (and printers) are bit-mapped devices, one of the core problems which must be solved when
  40 designing a document format is how it is to be \emph{rasterized} into a bitmap at a given resolution.
  41
  42 \subsection{Compositing Digital Images\cite{porter1984compositing}}
  43
  44
  45
  46 Perter and Duff's classic paper "Compositing Digital Images" lays the
  47 foundation for digital compositing today. By providing an "alpha channel,"
  48 images of arbitrary shapes — and images with soft edges or sub-pixel coverage
  49 information — can be overlayed digitally, allowing separate objects to be
  50 rasterized separately without a loss in quality.
  51
  52 Pixels in digital images are usually represented as 3-tuples containing
  53 (red component, green component, blue component). Nominally these values are in
  54 the [0-1] range. In the Porter-Duff paper, pixels are stored as $(R,G,B,\alpha)$
  55 4-tuples, where alpha is the fractional coverage of each pixel. If the image
  56 only covers half of a given pixel, for example, its alpha value would be 0.5.
  57
  58 To improve compositing performance, albeit at a possible loss of precision in
  59 some implementations, the red, green and blue channels are premultiplied by the
  60 alpha channel. This also simplifies the resulting arithmetic by having the
  61 colour channels and alpha channels use the same compositing equations.
  62
  63 Several binary compositing operations are defined:
  64 \begin{itemize}
  65 \item over
  66 \item in
  67 \item out
  68 \item atop
  69 \item xor
  70 \item plus
  71 \end{itemize}
  72
  73 The paper further provides some additional operations for implementing fades and
  74 dissolves, as well as for changing the opacity of individual elements in a
  75 scene.
  76
  77 The method outlined in this paper is still the standard system for compositing
  78 and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL}. It is
  79 all but guaranteed that this is the method we will be using for compositing
  80 document elements in our project.
  81
  82 \subsection{Bresenham's Algorithm: Algorithm for computer control of a digital plotter\cite{bresenham1965algorithm}}
  83 Bresenham's line drawing algorithm is a fast, high quality line rasterization
  84 algorithm which is still the basis for most (aliased) line drawing today. The
  85 paper, while originally written to describe how to control a particular plotter,
  86 is uniquely suited to rasterizing lines for display on a pixel grid.
  87
  88 Lines drawn with Bresenham's algorithm must begin and end at integer pixel
  89 coordinates, though one can round or truncate the fractional part. In order to
  90 avoid multiplication or division in the algorithm's inner loop,
  91
  92 The algorithm works by scanning along the long axis of the line, moving along
  93 the short axis when the error along that axis exceeds 0.5px. Because error
  94 accumulates linearly, this can be achieved by simply adding the per-pixel
  95 error (equal to (short axis/long axis)) until it exceeds 0.5, then incrementing
  96 the position along the short axis and subtracting 1 from the error accumulator.
  97
  98 As this requires nothing but addition, it is very fast, particularly on the
  99 older CPUs used in Bresenham's time. Modern graphics systems will often use Wu's
 100 line-drawing algorithm instead, as it produces antialiased lines, taking
 101 sub-pixel coverage into account. Bresenham himself extended this algorithm to
 102 produce Bresenham's circle algorithm. The principles behind the algorithm have
 103 also been used to rasterize other shapes, including B\'{e}zier curves.
 104
 105 \emph{GPU Rendering}\cite{loop2005resolution}, OpenVG implementation on GLES: \cite{oh2007implementation},
 106 \cite{robart2009openvg}
 107
 108 \emph{Existing implementations of document format rendering}
 109
 110 \subsection{Xr: Cross-device Rendering for Vector Graphics\cite{worth2003xr}}
 111
 112 Xr (now known as Cairo) is an implementation of the PDF v1.4 rendering model,
 113 independent of the PDF or PostScript file formats, and is now widely used
 114 as a rendering API. In this paper, Worth and Packard describe the PDF v1.4 rendering
 115 model, and their PostScript-derived API for it.
 116
 117 The PDF v1.4 rendering model is based on the original PostScript model, based around
 118 a set of \emph{paths} (and other objects, such as raster images) each made up of lines
 119 and B\'{e}zier curves, which are transformed by the ``Current Transformation Matrix.''
 120 Paths can be \emph{filled} in a number of ways, allowing for different handling of self-intersecting
 121 paths, or can have their outlines \emph{stroked}.
 122 Furthermore, paths can be painted with RGB colours and/or patterns derived from either
 123 previously rendered objects or external raster images.
 124 PDF v1.4 extends this to provide, amongst other features, support for layering paths and
 125 objects using Porter-Duff compositing\cite{porter1984compositing}, giving each painted path
 126 the option of having an $\alpha$ value and a choice of any of the Porter-Duff compositing
 127 methods.
 128
 129 The Cairo library approximates the rendering of some objects (particularly curved objects
 130 such as splines) with a set of polygons. An \texttt{XrSetTolerance} function allows the user
 131 of the library to set an upper bound on the approximation error in fractions of device pixels,
 132 providing a trade-off between rendering quality and performance. The library developers found
 133 that setting the tolerance to greater than $0.1$ device pixels resulted in errors visible to the
 134 user.
 135
 136 \subsection{Glitz: Hardware Accelerated Image Compositing using OpenGL\cite{nilsson2004glitz}}
 137
 138 This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
 139 the \texttt{Cairo} library.
 140
 141 The paper describes how OpenGL's Porter-Duff compositing is easily suited to the Cairo/PDF v1.4
 142 rendering model. Similarly, traditional OpenGL (pre-version 3.0 core) support a matrix stack
 143 of the same form as Cairo.
 144
 145 The ``Glitz'' backend will emulate support for tiled, non-power-of-two patterns/textures if
 146 the hardware does not support it.
 147
 148 Glitz can render both triangles and trapezoids (which are formed from pairs of triangles).
 149 However, it cannot guarantee that the rasterization is pixel-precise, as OpenGL does not proveide
 150 this consistently.
 151
 152 Glitz also supports multi-sample anti-aliasing, convolution filters for raster image reads (implemented
 153 with shaders).
 154
 155 Performance was much improved over the software rasterization and over XRender accellerated rendering
 156 on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when
 157 some transformations were applied.
 158
 159
 160
 161 \textbf{Also look at \texttt{NV\_path\_rendering}} \cite{kilgard2012gpu}
 162
 163 \section{Floating-Point Precision}
 164
 165 How floating-point works and what its behaviour is w/r/t range and precision
 166 \cite{goldberg1991whatevery}
 167 \cite{goldberg1992thedesign}
 168
 169 Arb. precision exists
 170
 171 Higher precision numeric types can be implemented or used on the GPU, but are
 172 slow.
 173 \cite{emmart2010high}
 174
 175
 176
 177 \section{Quadtrees}
 178 The quadtree is a data structure which
 179 \cite{finkel1974quad}
 180
 181
 182 \bibliographystyle{unsrt}
 183 \bibliography{papers}
 184
 185 \end{document}