XGitUrl: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LitReviewDavid.tex;h=edd8b2b01b6e5be1dfa0eef4b1f16584fd79eba6;hp=e84b6f54d20b345798197381a0f4806f99bf03bd;hb=22d90ae18c3f51d42e646b8a5880aa3675c8c545;hpb=66a3095577df07859b7ef9e8378238a4ef56d278
diff git a/LitReviewDavid.tex b/LitReviewDavid.tex
index e84b6f5..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.
@@ 36,132 +40,65 @@ to issues with numeric precision.
\section{Rendering}
As existing displays (and printers) are bitmapped devices, one of the core problems which must be solved when
designing a document format is how it is to be \emph{rasterized} into a bitmap at a given resolution.

\subsection{Compositing Digital Images\cite{porter1984compositing}}



Perter and Duff's classic paper "Compositing Digital Images" lays the
foundation for digital compositing today. By providing an "alpha channel,"
images of arbitrary shapes â and images with soft edges or subpixel coverage
information â can be overlayed digitally, allowing separate objects to be
rasterized separately without a loss in quality.

Pixels in digital images are usually represented as 3tuples containing
(red component, green component, blue component). Nominally these values are in
the [01] range. In the PorterDuff paper, pixels are stored as $(R,G,B,\alpha)$
4tuples, where alpha is the fractional coverage of each pixel. If the image
only covers half of a given pixel, for example, its alpha value would be 0.5.

To improve compositing performance, albeit at a possible loss of precision in
some implementations, the red, green and blue channels are premultiplied by the
alpha channel. This also simplifies the resulting arithmetic by having the
colour channels and alpha channels use the same compositing equations.

Several binary compositing operations are defined:
\begin{itemize}
\item over
\item in
\item out
\item atop
\item xor
\item plus
\end{itemize}

The paper further provides some additional operations for implementing fades and
dissolves, as well as for changing the opacity of individual elements in a
scene.

The method outlined in this paper is still the standard system for compositing
and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL}. It is
all but guaranteed that this is the method we will be using for compositing
document elements in our project.

\subsection{Bresenham's Algorithm: Algorithm for computer control of a digital plotter\cite{bresenham1965algorithm}}
Bresenham's line drawing algorithm is a fast, high quality line rasterization
algorithm which is still the basis for most (aliased) line drawing today. The
paper, while originally written to describe how to control a particular plotter,
is uniquely suited to rasterizing lines for display on a pixel grid.
+Computer graphics comes in two forms: bitmapped (or raster) graphics, which is defined by an array of pixel colours,
+and \emph{vector} graphics, defined by mathematical descriptions of objects. Bitmapped graphics are well suited to photographs
+and are match how cameras, printers and monitors work. 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 effected.
Lines drawn with Bresenham's algorithm must begin and end at integer pixel
coordinates, though one can round or truncate the fractional part. In order to
avoid multiplication or division in the algorithm's inner loop,
+Vector graphics lack many of these problems: the representation is independent of the output resolution, and rather
+an abstract description of what it is being rendered, typically as a combination of simple geometric shapes like lines,
+arcs and ``B\'ezier curves''.
+As existing displays (and printers) are bitmapped devices, vector documents must be \emph{rasterized} into a bitmap at
+a given resolution. This bitmap is then displayed or printed. The resulting bitmap is then an approximation of the vector image
+at that resolution.
The algorithm works by scanning along the long axis of the line, moving along
the short axis when the error along that axis exceeds 0.5px. Because error
accumulates linearly, this can be achieved by simply adding the perpixel
error (equal to (short axis/long axis)) until it exceeds 0.5, then incrementing
the position along the short axis and subtracting 1 from the error accumulator.
+This project will be based around vector graphics, as these properties make it more suited to experimenting with zoom
+quality.
As this requires nothing but addition, it is very fast, particularly on the
older CPUs used in Bresenham's time. Modern graphics systems will often use Wu's
linedrawing algorithm instead, as it produces antialiased lines, taking
subpixel coverage into account. Bresenham himself extended this algorithm to
produce Bresenham's circle algorithm. The principles behind the algorithm have
also been used to rasterize other shapes, including B\'{e}zier curves.
\emph{GPU Rendering}\cite{loop2005resolution}, OpenVG implementation on GLES: \cite{oh2007implementation},
\cite{robart2009openvg}
+The rasterization process typically operates on an individual ``object'' or ``shape'' at a time: there are special algorithms
+for rendering lines\cite{bresenham1965algorithm}, triangles\cite{giesen2013triangle}, polygons\cite{pineda1988parallel} and B\'ezier
+Curves\cite{goldman_thefractal}. Typically, these are rasterized independently and composited in the bitmap domain using PorterDuff
+compositing\cite{porter1984compositing} into a single image. This allows complex images to be formed from many simple pieces, as well
+as allowing for layered translucent objects, which would otherwise require the solution of some very complex constructive geometry problems.
\emph{Existing implementations of document format rendering}
+While traditionally, rasterization was done entirely in software, modern computers and mobile devices have hardware support for rasterizing
+some basic primitives  typically lines and triangles , designed for use rendering 3D scenes. This hardware is usually programmed with an
+API like \texttt{OpenGL}\cite{openglspec}.
\subsection{Xr: Crossdevice Rendering for Vector Graphics\cite{worth2003xr}}
+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}.
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.
+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 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.

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}
@@ 175,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}