XGitUrl: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LitReviewDavid.tex;h=edd8b2b01b6e5be1dfa0eef4b1f16584fd79eba6;hp=e5ad1fe679ee6112f81e5ad99bf1e11174f3827e;hb=22d90ae18c3f51d42e646b8a5880aa3675c8c545;hpb=24e6b793cd84df7f985fe006623f8dc7fcbdb5d1
diff git a/LitReviewDavid.tex b/LitReviewDavid.tex
index e5ad1fe..edd8b2b 100644
 a/LitReviewDavid.tex
+++ b/LitReviewDavid.tex
@@ 1,6 +1,7 @@
\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
+\usepackage{graphicx}
%opening
\title{Literature Review}
@@ 19,6 +20,9 @@ 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.
+
+\section{Document Formats}
+
Most existing document formats  such as the venerable PostScript and PDF  are, however, designed to imitate
existing paper documents, largely to allow for easy printing. In order to truly take advantage of the possibilities operating in the digital
domain opens up to us, we must look to new formats.
@@ 67,68 +71,34 @@ 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}.
Indeed, there are several implementations of these vector graphics

\emph{GPU Rendering}\cite{loop2005resolution}, OpenVG implementation on GLES: \cite{oh2007implementation},
\cite{robart2009openvg}

\emph{Existing implementations of document format rendering}

\subsection{Xr: Crossdevice Rendering for Vector Graphics\cite{worth2003xr}}

Xr (now known as Cairo) is an implementation of the PDF v1.4 rendering model,
independent of the PDF or PostScript file formats, and is now widely used
as a rendering API. In this paper, Worth and Packard describe the PDF v1.4 rendering
model, and their PostScriptderived API for it.

The PDF v1.4 rendering model is based on the original PostScript model, based around
a set of \emph{paths} (and other objects, such as raster images) each made up of lines
and B\'{e}zier curves, which are transformed by the ``Current Transformation Matrix.''
Paths can be \emph{filled} in a number of ways, allowing for different handling of selfintersecting
paths, or can have their outlines \emph{stroked}.
Furthermore, paths can be painted with RGB colours and/or patterns derived from either
previously rendered objects or external raster images.
PDF v1.4 extends this to provide, amongst other features, support for layering paths and
objects using PorterDuff compositing\cite{porter1984compositing}, giving each painted path
the option of having an $\alpha$ value and a choice of any of the PorterDuff compositing
methods.

The Cairo library approximates the rendering of some objects (particularly curved objects
such as splines) with a set of polygons. An \texttt{XrSetTolerance} function allows the user
of the library to set an upper bound on the approximation error in fractions of device pixels,
providing a tradeoff between rendering quality and performance. The library developers found
that setting the tolerance to greater than $0.1$ device pixels resulted in errors visible to the
user.

\subsection{Glitz: Hardware Accelerated Image Compositing using OpenGL\cite{nilsson2004glitz}}

This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
the \texttt{Cairo} library.
+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}.
The paper describes how OpenGL's PorterDuff compositing is easily suited to the Cairo/PDF v1.4
rendering model. Similarly, traditional OpenGL (preversion 3.0 core) support a matrix stack
of the same form as Cairo.

The ``Glitz'' backend will emulate support for tiled, nonpoweroftwo patterns/textures if
the hardware does not support it.

Glitz can render both triangles and trapezoids (which are formed from pairs of triangles).
However, it cannot guarantee that the rasterization is pixelprecise, as OpenGL does not proveide
this consistently.

Glitz also supports multisample antialiasing, convolution filters for raster image reads (implemented
with shaders).

Performance was much improved over the software rasterization and over XRender accellerated rendering
on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when
some transformations were applied.



\textbf{Also look at \texttt{NV\_path\_rendering}} \cite{kilgard2012gpu}
\section{FloatingPoint Precision}
+On modern computer architectures, there are two basic number formats supported:
+fixedwidth integers and \emph{floatingpoint} numbers. Typically, computers
+natively support integers of up to 64 bits, capable of representing all integers
+between $0$ and $2^{64}  1$\footnote{Most machines also support \emph{signed} integers,
+which have the same cardinality as their \emph{unsigned} counterparts, but which
+represent integers between $(2^{63})$ and $2^{63}  1$}.
+
+Floatingpoint numbers\cite{goldberg1991whatevery} are the binary equivalent of scientific notation:
+each number consisting of an exponent ($e$) and a mantissa $(m)$ such that a number is given by
+\begin{equation}
+ n = 2^{e} \times m
+\end{equation}
+
+The IEEE 754 standard\cite{ieee754std1985} defines several floatingpoint data types
+which are used\footnote{Many systems' implement the IEEE 754 standard's storage formats,
+but do not implement arithmetic operations in accordance with this standard.} by most
+computer systems. The standard defines 32bit (8bit exponent, 23bit mantissa) and
+64bit (11bit exponent, 53bit mantissa) formats\footnote{The 2008
+revision to this standard\cite{ieee754std2008} adds some additional formats, but is
+less widely supported in hardware.}
+
How floatingpoint works and what its behaviour is w/r/t range and precision
\cite{goldberg1991whatevery}
\cite{goldberg1992thedesign}
@@ 142,9 +112,13 @@ slow.
\section{Quadtrees}
The quadtree is a data structure which
+The quadtree is a data structure which keeps
\cite{finkel1974quad}
+\begin{figure}[h]
+ \includegraphics[width=0.4\linewidth]{figures/quadtree_example}
+\end{figure}
+
\bibliographystyle{unsrt}
\bibliography{papers}