From: David Gow Date: Sun, 18 May 2014 17:08:20 +0000 (+0800) Subject: I should be ashamed, but at least my shame is safe X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=commitdiff_plain;h=e60efee9befb1708f4928bc62504b337db9d6813 I should be ashamed, but at least my shame is safe Looking at the diff shows me how I've deleted more than I've added, and that this still isn't even a first-order approximation to a literature review. --- diff --git a/LitReviewDavid.pdf b/LitReviewDavid.pdf index a04c7b2..f3510f8 100644 Binary files a/LitReviewDavid.pdf and b/LitReviewDavid.pdf differ 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 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}} - -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 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} @@ -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} diff --git a/figures/quadtree_example.pdf b/figures/quadtree_example.pdf new file mode 100644 index 0000000..61cc76e Binary files /dev/null and b/figures/quadtree_example.pdf differ diff --git a/papers.bib b/papers.bib index d8d2f5a..4796a0b 100644 --- a/papers.bib +++ b/papers.bib @@ -104,6 +104,22 @@ Goldberg:1991:CSK:103162.103163, organization={IEEE} } +@article{ieee754std1985, + journal={{ANSI}/{IEEE} Std 754-1985}, + title={{IEEE} Standard for Binary Floating-Point Arithmetic}, + year={1985}, +} + +@article{ieee754std2008, + journal={{IEEE} Std 754-2008}, + title={{IEEE} Standard for Floating-Point Arithmetic}, + year={2008}, + month={Aug}, + pages={1-70}, +} + + + %%%%%%%%%%%%%%%%%%%%%%%% % GPU-y Stuff %%%%%%%%%%%%%%%%%%%%%%%% @@ -112,7 +128,7 @@ Goldberg:1991:CSK:103162.103163, % The latest OpenGL spec. % See: http://www.opengl.org/registry/doc/glspec44.core.pdf @book{openglspec, - title={The OpenGL\textregistered Graphics System: A Specification}, + title={The {OpenGL}\textregistered Graphics System: A Specification}, author={Segal, Mark and Akely, Kurt and Leech, Jon}, year={2014}, publisher={The Kronos Group, Inc}, @@ -126,7 +142,7 @@ Goldberg:1991:CSK:103162.103163, @inproceedings{green2007improved, title={Improved alpha-tested magnification for vector textures and special effects}, author={Green, Chris}, - booktitle={ACM SIGGRAPH 2007 courses}, + booktitle={{ACM} {SIGGRAPH} 2007 courses}, pages={9--18}, year={2007}, organization={ACM} @@ -158,7 +174,7 @@ Goldberg:1991:CSK:103162.103163, % Split texture into a grid/quadtree, have each element represented by a set of cubic equations, combined CSG style. % Need to read this further to understand some of the nuance, though I expect GLyphy does this better? @techreport{ray2005vector, - title={Vector texture maps on the GPU}, + title={Vector texture maps on the {GPU}}, author={Ray, Nicolas and Cavin, Xavier and L{\'e}vy, Bruno}, year={2005}, institution={Technical Report ALICE-TR-05-003} @@ -206,7 +222,7 @@ Goldberg:1991:CSK:103162.103163, @article{loop2007rendering, title={Rendering vector art on the GPU}, author={Loop, Charles and Blinn, Jim}, - journal={GPU gems}, + journal={{GPU} gems}, volume={3}, pages={543--562}, year={2007} @@ -219,9 +235,9 @@ Goldberg:1991:CSK:103162.103163, % See Zach Rusin's blog post comparing it to Qt's SVG renderer. % http://zrusin.blogspot.com.au/2011/09/nv-path-rendering.html @article{kilgard2012gpu, - title={GPU-accelerated path rendering}, + title={{GPU}-accelerated path rendering}, author={Kilgard, Mark J and Bolz, Jeff}, - journal={ACM Transactions on Graphics (TOG)}, + journal={{ACM} Transactions on Graphics (TOG)}, volume={31}, number={6}, pages={172}, @@ -230,7 +246,7 @@ Goldberg:1991:CSK:103162.103163, } % An extension to the above, detailing the use of the extension, rather than the way it is implemented. @article{kilgard300programming, - title={Programming with NV path rendering: An Annex to the SIGGRAPH paper GPU-accelerated Path Rendering}, + title={Programming with {NV} path rendering: An Annex to the {SIGGRAPH} paper {GPU}-accelerated Path Rendering}, author={Kilgard, Mark J}, journal={heart}, volume={300}, @@ -247,7 +263,7 @@ Goldberg:1991:CSK:103162.103163, % OpenVG is an opengl-ish API for vector graphics. % More based around SVG than postscript, but not bad. @article{rice2008openvg, - title={OpenVG Specification, version 1.1}, + title={{OpenVG} Specification, version 1.1}, author={Rice, Daniel and Simpson, RJ}, journal={Khronos Group}, year={2008} @@ -257,7 +273,7 @@ Goldberg:1991:CSK:103162.103163, % Implementing OpenVG using OpenGL ES 1. Pretty high-level overview. % Basically boiled down to "we tesselated to get curves, and then used textures for fill" @inproceedings{oh2007implementation, - title={Implementation of OpenVG 1.0 using OpenGL ES}, + title={Implementation of {OpenVG} 1.0 using {OpenGL} {ES}}, author={Oh, Aekyung and Sung, Hyunchan and Lee, Hwanyong and Kim, Kujin and Baek, Nakhoon}, booktitle={Proceedings of the 9th international conference on Human computer interaction with mobile devices and services}, pages={326--328}, @@ -268,7 +284,7 @@ Goldberg:1991:CSK:103162.103163, % Implementing the OpenVG paint modes using GLES2 shaders. % This is all pretty simple stuff. @inproceedings{robart2009openvg, - title={OpenVG paint subsystem over openGL ES shaders}, + title={{OpenVG} paint subsystem over {OpenGL} {ES} shaders}, author={Robart, Mathieu}, booktitle={Consumer Electronics, 2009. ICCE'09. Digest of Technical Papers International Conference on}, pages={1--2}, @@ -301,7 +317,7 @@ Goldberg:1991:CSK:103162.103163, Keywords = {PDF (Computer file format), FILE organization (Computer science), ELECTRONIC data processing}, Number = {1}, Pages = {59 - 63}, - Title = {Portable Document Format (PDF) -- Finally, a Universal Document Exchange Technology.}, + Title = {Portable Document Format ({PDF}) -- Finally, a Universal Document Exchange Technology.}, Volume = {28}, URL = {http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=11512377&site=ehost-live}, Year = {2002},