XGitUrl: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LitReviewDavid.tex;h=5cde5c65ade51a6f11b9a5882cb456c3217eac4b;hp=da4d5d8a4bec732cfb579bb6949f657e1b3a3922;hb=41db8b8b500eab8e280aa71c4073c1f3dbdb36d8;hpb=12f72f4023ed26652874c68a5211fdee16ceb359
diff git a/LitReviewDavid.tex b/LitReviewDavid.tex
index da4d5d8..5cde5c6 100644
 a/LitReviewDavid.tex
+++ b/LitReviewDavid.tex
@@ 21,7 +21,7 @@ could be passed on from person to person without them ever meeting.
And thus the document was born.
Traditionally, documents have been static: just marks on paper, but with the advent of computers many more possibilities open up.
+Traditionally, documents have been static: just marks on rock, parchment or paper, but with the advent of computers many more possibilities open up.
\section{Rendering}
@@ 37,8 +37,8 @@ and match how cameras, printers and monitors work.
\end{figure}
However, bitmap devices do not handle zooming beyond their ``native'' resolution  the resolution where one document pixel maps
to one display pixel , exhibiting an artefact called pixelation where the pixel structure becomes evident. Attempts to use
+However, bitmap devices do not handle zooming beyond their ``native'' resolution (the resolution where one document pixel maps
+to one display pixel), exhibiting an artefact called pixelation where the pixel structure becomes evident. Attempts to use
interpolation to hide this effect are never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly affected.
Vector graphics avoid many of these problems: the representation is independent of the output resolution, and rather
@@ 87,6 +87,7 @@ different shapes.
A B\'ezier curve is a smooth (i.e.\ infinitely differentiable) curve between two points, represented by a Bernstein polynomial.
The coefficients of this Bernstein polynomial are known as the ``control points.''
+ B\'ezier curves are typically rasterized using De Casteljau's algorithm\cite{foley1996computer}
Line Segments are a firstorder B\'ezier curve.
\item[B\'ezier Spline]
@@ 103,16 +104,21 @@ different shapes.
%for rendering lines\cite{bresenham1965algorithm}, triangles\cite{giesen2013triangle}, polygons\cite{pineda1988parallel} and B\'ezier
%Curves\cite{goldman_thefractal}.
+\subsection{GPU Rendering}
While traditionally, rasterization was done entirely in software, modern computers and mobile devices have hardware support for rasterizing
lines and triangles designed for use rendering 3D scenes. This hardware is usually programmed with an
API like \texttt{OpenGL}\cite{openglspec}.
More complex shapes like B\'ezier curves can be rendered by combining the use of bitmapped textures (possibly using signeddistance
fields\cite{leymarie1992fast}\cite{frisken2000adaptively}\cite{green2007improved}) with polygons approximating the curve's shape\cite{loop2005resolution}\cite{loop2007rendering}.
+fields\cite{leymarie1992fast}\cite{frisken2000adaptively}\cite{green2007improved}) strtched over a triangle mesh
+approximating the curve's shape\cite{loop2005resolution}\cite{loop2007rendering}.
Indeed, there are several implementations of entire vector graphics systems using OpenGL: OpenVG\cite{robart2009openvg} on top of OpenGL ES\cite{oh2007implementation};
the Cairo\cite{worth2003xr} library, based around the PostScript/PDF rendering model, has the ``Glitz'' OpenGL backend\cite{nilsson2004glitz} and the SVG/PostScript GPU
renderer by nVidia\cite{kilgard2012gpu} as an OpenGL extension\cite{kilgard300programming}.
+Indeed, there are several implementations of entire vector graphics systems using OpenGL:
+\begin{itemize}
+ \item The OpenVG standard\cite{robart2009openvg} has been implemented on top of OpenGL ES\cite{oh2007implementation};
+ \item the Cairo\cite{worth2003xr} library, based around the PostScript/PDF rendering model, has the ``Glitz'' OpenGL backend\cite{nilsson2004glitz}
+ \item and the SVG/PostScript GPU renderer by nVidia\cite{kilgard2012gpu} as an OpenGL extension\cite{kilgard300programming}.
+\end{itemize}
\section{Numeric formats}
@@ 171,13 +177,6 @@ These types are typically built from several native data types such as integers
paired with custom routines implementing arithmetic primitives.\cite{priest1991algorithms}
These, therefore, are likely slower than the native types they are built on.
While traditionally, GPUs have supported some approximation of IEEE 754's 32bit floats,
modern graphics processors also support 16bit\cite{nv_half_float} and 64bit\cite{arb_gpu_shader_fp64}
IEEE floats. Note, however, that some parts of the GPU are only able to use some formats,
so precision will likely be truncated at some point before display.
Higher precision numeric types can be implemented or used on the GPU, but are
slow.\cite{emmart2010high}

Pairs of integers $(a \in \mathbb{Z},b \in \mathbb{Z}\setminus 0)$ can be used to represent rationals. This allows
values such as $\frac{1}{3}$ to be represented exactly, whereas in fixed or floatingpoint formats,
this would have a recurring representation:
@@ 188,6 +187,15 @@ Whereas with a rational type, this is simply $\frac{1}{3}$.
Rationals do not have a unique representation for each value, typically the reduced fraction is used
as a characteristic element.
+While traditionally, GPUs have supported some approximation of IEEE 754's 32bit floats,
+modern graphics processors also support 16bit\cite{nv_half_float} and 64bit\cite{arb_gpu_shader_fp64}
+IEEE floats, though some features of IEEE floats, like denormals and NaNs are not always supported.
+Note, however, that some parts of the GPU are only able to use some formats,
+so precision will likely be truncated at some point before display.
+Higher precision numeric types can be implemented or used on the GPU, but are
+slow.\cite{emmart2010high}
+
+
\section{Document Formats}
Most existing document formats  such as the venerable PostScript and PDF  are, however, designed to imitate
@@ 203,7 +211,7 @@ renderer.
The process of creating and displaying a document is a rather universal one (\ref{documenttimeline}), though
different document formats approach it slightly differently. A document often begins as raw content: text and images
(be they raster or vector) and it must end up as a set of photons flying towards the reader's eyes.
+(be they raster or vector) and it must end up as a stream of photons flying towards the reader's eyes.
\begin{figure}
\label{documenttimeline}
@@ 274,7 +282,7 @@ which already have their elements placed.
PDF documents represent a particular layout, and must be rasterized before display.
\item[SVG]
 Scalable Vector Graphics (SVG) is a vector graphics document format\cite{svg2011} which uses the Document Object Model. It consists of a tree of matrix transforms,
+ Scalable Vector Graphics (SVG) is a vector graphics document format\cite{svg20111.1} which uses the Document Object Model. It consists of a tree of matrix transforms,
with objects such as vector paths (made up of B\'ezier curves) and text at the leaves.
\end{description}
@@ 307,7 +315,7 @@ representable with the \emph{real} type have been specified differently: the lar
$\pm1.175 \times 10^{38}$ with approximately $5$ decimal digits of precision \emph{in the fractional part}.
Adobe's implementation of PDF uses both IEEE 754 single precision floatingpoint numbers and (for some calculations, and in previous versions) 16.16 bit fixedpoint values.
The SVG specification\cite{svg2011} specifies numbers as strings with a decimal representation of the number.
+The SVG specification\cite{svg20111.1} specifies numbers as strings with a decimal representation of the number.
It is stated that a ``Conforming SVG Viewer'' must have ``all visual rendering accurate to within one device pixel to the mathematically correct result at the initial 1:1
zoom ratio'' and that ``it is suggested that viewers attempt to keep a high degree of accuracy when zooming.''
A ``Conforming HighQuality SVG Viewer'' must use ``doubleprecision floating point\footnote{Presumably the 64bit IEEE 754 ``double'' type.}'' for computations involving
@@ 324,11 +332,16 @@ only processs  or \emph{cull}  parts of the document which are not onscre
The quadtree\cite{finkel1974quad}is a data structure  one of a family of \emph{spatial}
data structures  which recursively breaks down space into smaller subregions
which can be processed independently. Points (or other objects) are added to a single
node, which if certain criteria are met  typically the number of points in a node
exceeding a maximum, though in our case likely the level of precision required exceeding
that supported by the data type in use  is split into four equalsized subregions, and
+node which (if certain criteria are met) is split into four equalsized subregions, and
points attached to the region which contains them.
+Quadtrees have been used in computer graphics for both culling  excluding objects in
+nodes which are not visible  and ``level of detail'', where different levels of the quadtree store
+different quality versions of objects or data\cite{zerbst2004game}.
+Typically the number of points in a node
+exceeding a maximum triggers this split, though in our case likely the level of precision required exceeding
+that supported by the data type in use.
+
In this project, we will be experimenting with a form of quadtree in which each
node has its own independent coordinate system, allowing us to store some spatial
information\footnote{One bit percoordinate, perlevel of the quadtree} within the