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 Computer graphics comes in two forms: bit-mapped (or raster) graphics, which is defined by an array of pixel colours,
  40 and \emph{vector} graphics, defined by mathematical descriptions of objects. Bit-mapped graphics are well suited to photographs
  41 and are match how cameras, printers and monitors work. However, bitmap devices do not handle zooming beyond their
  42 ``native'' resolution --- the resolution where one document pixel maps to one display pixel ---, exhibiting an artefact
  43 called pixelation where the pixel structure becomes evident. Attempts to use interpolation to hide this effect are
  44 never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly effected.
  45
  46 Vector graphics lack many of these problems: the representation is independent of the output resolution, and rather
  47 an abstract description of what it is being rendered, typically as a combination of simple geometric shapes like lines,
  48 arcs and ``B\'ezier curves''.
  49 As existing displays (and printers) are bit-mapped devices, vector documents must be \emph{rasterized} into a bitmap at
  50 a given resolution. This bitmap is then displayed or printed. The resulting bitmap is then an approximation of the vector image
  51 at that resolution.
  52
  53 This project will be based around vector graphics, as these properties make it more suited to experimenting with zoom
  54 quality.
  55
  56
  57 The rasterization process typically operates on an individual ``object'' or ``shape'' at a time: there are special algorithms
  58 for rendering lines\cite{bresenham1965algorithm}, triangles\cite{giesen2013triangle}, polygons\cite{pineda1988parallel} and B\'ezier
  59 Curves\cite{goldman_thefractal}. Typically, these are rasterized independently and composited in the bitmap domain using Porter-Duff
  60 compositing\cite{porter1984compositing} into a single image. This allows complex images to be formed from many simple pieces, as well
  61 as allowing for layered translucent objects, which would otherwise require the solution of some very complex constructive geometry problems.
  62
  63 While traditionally, rasterization was done entirely in software, modern computers and mobile devices have hardware support for rasterizing
  64 some basic primitives --- typically lines and triangles ---, designed for use rendering 3D scenes. This hardware is usually programmed with an
  65 API like \texttt{OpenGL}\cite{openglspec}.
  66
  67 More complex shapes like B\'ezier curves can be rendered by combining the use of bitmapped textures (possibly using signed-distance
  68 fields\cite{leymarie1992fast}\cite{frisken2000adaptively}\cite{green2007improved}) with polygons approximating the curve's shape\cite{loop2005resolution}\cite{loop2007rendering}.
  69
  70 Indeed, there are several implementations of these vector graphics
  71
  72 \emph{GPU Rendering}\cite{loop2005resolution}, OpenVG implementation on GLES: \cite{oh2007implementation},
  73 \cite{robart2009openvg}
  74
  75 \emph{Existing implementations of document format rendering}
  76
  77 \subsection{Xr: Cross-device Rendering for Vector Graphics\cite{worth2003xr}}
  78
  79 Xr (now known as Cairo) is an implementation of the PDF v1.4 rendering model,
  80 independent of the PDF or PostScript file formats, and is now widely used
  81 as a rendering API. In this paper, Worth and Packard describe the PDF v1.4 rendering
  82 model, and their PostScript-derived API for it.
  83
  84 The PDF v1.4 rendering model is based on the original PostScript model, based around
  85 a set of \emph{paths} (and other objects, such as raster images) each made up of lines
  86 and B\'{e}zier curves, which are transformed by the ``Current Transformation Matrix.''
  87 Paths can be \emph{filled} in a number of ways, allowing for different handling of self-intersecting
  88 paths, or can have their outlines \emph{stroked}.
  89 Furthermore, paths can be painted with RGB colours and/or patterns derived from either
  90 previously rendered objects or external raster images.
  91 PDF v1.4 extends this to provide, amongst other features, support for layering paths and
  92 objects using Porter-Duff compositing\cite{porter1984compositing}, giving each painted path
  93 the option of having an $\alpha$ value and a choice of any of the Porter-Duff compositing
  94 methods.
  95
  96 The Cairo library approximates the rendering of some objects (particularly curved objects
  97 such as splines) with a set of polygons. An \texttt{XrSetTolerance} function allows the user
  98 of the library to set an upper bound on the approximation error in fractions of device pixels,
  99 providing a trade-off between rendering quality and performance. The library developers found
 100 that setting the tolerance to greater than $0.1$ device pixels resulted in errors visible to the
 101 user.
 102
 103 \subsection{Glitz: Hardware Accelerated Image Compositing using OpenGL\cite{nilsson2004glitz}}
 104
 105 This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
 106 the \texttt{Cairo} library.
 107
 108 The paper describes how OpenGL's Porter-Duff compositing is easily suited to the Cairo/PDF v1.4
 109 rendering model. Similarly, traditional OpenGL (pre-version 3.0 core) support a matrix stack
 110 of the same form as Cairo.
 111
 112 The ``Glitz'' backend will emulate support for tiled, non-power-of-two patterns/textures if
 113 the hardware does not support it.
 114
 115 Glitz can render both triangles and trapezoids (which are formed from pairs of triangles).
 116 However, it cannot guarantee that the rasterization is pixel-precise, as OpenGL does not proveide
 117 this consistently.
 118
 119 Glitz also supports multi-sample anti-aliasing, convolution filters for raster image reads (implemented
 120 with shaders).
 121
 122 Performance was much improved over the software rasterization and over XRender accellerated rendering
 123 on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when
 124 some transformations were applied.
 125
 126
 127
 128 \textbf{Also look at \texttt{NV\_path\_rendering}} \cite{kilgard2012gpu}
 129
 130 \section{Floating-Point Precision}
 131
 132 How floating-point works and what its behaviour is w/r/t range and precision
 133 \cite{goldberg1991whatevery}
 134 \cite{goldberg1992thedesign}
 135
 136 Arb. precision exists
 137
 138 Higher precision numeric types can be implemented or used on the GPU, but are
 139 slow.
 140 \cite{emmart2010high}
 141
 142
 143
 144 \section{Quadtrees}
 145 The quadtree is a data structure which
 146 \cite{finkel1974quad}
 147
 148
 149 \bibliographystyle{unsrt}
 150 \bibliography{papers}
 151
 152 \end{document}