\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
+\usepackage{graphicx}
%opening
\title{Literature Review}
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.
However, these data-driven formats typically do not support fixed layouts, and the display differs from renderer to
renderer.
+Ultimately, there are two fundamental stages by which all documents --- digital or otherwise --- are produced and displayed:
+\emph{layout} and \emph{display}. The \emph{layout} stage is where the positions and sizes of text and other graphics are
+determined, while the \emph{display} stage actually produces the final output, whether as ink on paper or pixels on a computer monitor.
+
Existing document formats, due to being designed to model paper,
have limited precision (8 decimal digits for PostScript\cite{plrm}, 5 decimal digits for PDF\cite{pdfref17}).
This matches the limited resolution of printers and ink, but is limited when compared to what aught to be possible
More complex shapes like B\'ezier curves can be rendered by combining the use of bitmapped textures (possibly using signed-distance
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: Cross-device 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 PostScript-derived 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 self-intersecting
-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 Porter-Duff compositing\cite{porter1984compositing}, giving each painted path
-the option of having an $\alpha$ value and a choice of any of the Porter-Duff 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 trade-off 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}}
+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}.
-This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
-the \texttt{Cairo} library.
-
-The paper describes how OpenGL's Porter-Duff compositing is easily suited to the Cairo/PDF v1.4
-rendering model. Similarly, traditional OpenGL (pre-version 3.0 core) support a matrix stack
-of the same form as Cairo.
-
-The ``Glitz'' backend will emulate support for tiled, non-power-of-two 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 pixel-precise, as OpenGL does not proveide
-this consistently.
-
-Glitz also supports multi-sample anti-aliasing, 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{Floating-Point Precision}
+On modern computer architectures, there are two basic number formats supported:
+fixed-width integers and \emph{floating-point} 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$}.
+
+Floating-point 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 floating-point 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 32-bit (8-bit exponent, 23-bit mantissa) and
+64-bit (11-bit exponent, 53-bit mantissa) formats\footnote{The 2008
+revision to this standard\cite{ieee754std2008} adds some additional formats, but is
+less widely supported in hardware.}
+
How floating-point works and what its behaviour is w/r/t range and precision
\cite{goldberg1991whatevery}
\cite{goldberg1992thedesign}
\section{Quadtrees}
-The quadtree is a data structure which
-\cite{finkel1974quad}
-
+When viewing or processing a small part of a large document, it may be helpful to
+only processs --- or \emph{cull} --- parts of the document which are not on-screen.
+
+\begin{figure}[h]
+ \centering \includegraphics[width=0.4\linewidth]{figures/quadtree_example}
+ \caption{A simple quadtree.}
+\end{figure}
+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 equal-sized subregions, and
+points attached to the region which contains them.
+
+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 per-coordinate, per-level of the quadtree} within the
+quadtree structure, eliminating redundancy in the coordinates of nearby objects.
+
+Other spatial data structures exist, such as the KD-tree\cite{bentley1975multidimensional},
+which partitions the space on any axis-aligned line; or the BSP tree\cite{fuchs1980onvisible},
+which splits along an arbitrary line which need not be axis aligned. We believe, however,
+that the simpler conversion from binary coordinates to the quadtree's binary split make
+it a better avenue for initial research to explore.
\bibliographystyle{unsrt}
\bibliography{papers}
git.ucc.asn.au / ipdf / documents.git / blobdiff
UCC git Repository :: git.ucc.asn.au