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}
\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
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 first-order B\'ezier curve.
\item[B\'ezier Spline]
%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 signed-distance
-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}
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 32-bit floats,
-modern graphics processors also support 16-bit\cite{nv_half_float} and 64-bit\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 floating-point formats,
this would have a recurring representation:
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 32-bit floats,
+modern graphics processors also support 16-bit\cite{nv_half_float} and 64-bit\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
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}
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{svg2011-1.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}
$\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 floating-point numbers and (for some calculations, and in previous versions) 16.16 bit fixed-point values.
-The SVG specification\cite{svg2011} specifies numbers as strings with a decimal representation of the number.
+The SVG specification\cite{svg2011-1.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 High-Quality SVG Viewer'' must use ``double-precision floating point\footnote{Presumably the 64-bit IEEE 754 ``double'' type.}'' for computations involving
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
+node which (if certain criteria are met) is split into four equal-sized 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 per-coordinate, per-level of the quadtree} within the
git.ucc.asn.au / ipdf / documents.git / blobdiff
UCC git Repository :: git.ucc.asn.au