\chapter{Literature Review}\label{Background}
-The first half of this chapter will be devoted to documents themselves, including: the representation and displaying of graphics primitives\cite{computergraphics2}, and how collections of these primitives are represented in document formats, focusing on widely used standards\cite{plrm, pdfref17, svg2011-1.1}.
+%\section{Overview}
+\input{chapters/Background/Overview}
+\section{Raster and Vector Graphics}
+\input{chapters/Background/RasterAndVectorGraphics}
+\section{Rendering Vector Primitives}
+\input{chapters/Background/Rendering}
+\section{Coordinate Systems and Transformations}
+\input{chapters/Background/CoordinateSystems}
+\section{Precision Specified by Document Standards}
-We will find that although there has been a great deal of research into the rendering, storing, editing, manipulation, and extension of document formats, modern standards are content to specify at best single precision IEEE-754 floating point arithmetic.
+\input{chapters/Background/Standards}
-The research on arbitrary precision arithmetic applied to documents is very sparse; however arbitrary precision arithmetic itself is a very active field of research. Therefore, the second half of this chapter will be devoted to considering fixed precision floating point numbers as specified by the IEEE-754 standard, possible limitations in precision, and alternative number representations for increased or arbitrary precision arithmetic.
-In Chapter \ref{Progress}, we will discuss our findings so far with regards to arbitrary precision arithmetic applied to document formats, and expand upon the goals outlined in Chapture \ref{Proposal}.
-\section{Raster and Vector Images}\label{Raster and Vector Images}
-\input{chapters/Background_Raster-vs-Vector}
-\section{Rasterising Vector Images}\label{Rasterising Vector Images}
+\section{Fixed Point and Integer Number Representations}
+\input{chapters/Background/FixedPoint}
+\section{Floating Point Number Representations}
+\input{chapters/Background/Floats}
+\section{Rational Number Representations}
+\input{chapters/Background/Rationals}
-Throughout Section \ref{vector-vs-raster-graphics} we were careful to refer to ``modern'' display devices, which are raster based. It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}.
-Hearn and Baker's textbook ``Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in ``Computer Graphics'' and the relevant literature. Informal tutorials are abundant on the internet\cite{elias2000graphics}. This section is by no means a comprehensive survey of the literature but intends to provide some idea computations which are required to render a document.
+\section{Floating Point Operations on the CPU and GPU}\label{FloatingPointOnTheGPU}
+\input{chapters/Background/FloatingPointOnTheGPU}
-\subsection{Straight Lines}\label{Straight Lines}
-\input{chapters/Background_Lines}
-\subsection{Spline Curves}\label{Spline Curves}
-Splines are continuous curves formed from piecewise polynomial segments. A polynomial of $n$th degree is defined by $n$ constants $\{a_0, a_1, ... a_n\}$ and:
-\begin{align}
- y(x) &= \displaystyle\sum_{k=0}^n a_k x^k
-\end{align}
-A straight line is simply a polynomial of $0$th degree. Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and rendering straight lines between $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}. More direct algorithms for drawing splines based upon Brasenham and Wu's algorithms also exist\cite{citationneeded}.
-
-There are many different ways to define a spline. One approach is to specify ``knots'' on the spline and solve for the cooefficients to generate a cubic spline ($n = 3$) passing through the points. Alternatively, there are many ways to specify a spline using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors.
-
-\subsubsection{Bezier Curves}
-\input{chapters/Background_Bezier}
-
-\subsection{Shading}
-
-Algorithms for shading on vector displays involved drawing equally spaced lines in the region with endpoints defined by the boundaries of the region\cite{brassel1979analgorithm}. Apart from being unrealistic, these techniques required a computationally expensive sorting of vertices\cite{lane1983analgorithm}.
-
-On raster displays, shading is typically based upon Lane's algorithm of 1983\cite{lane1983analgorithm}. Lane's algorithm relies on the ability to ``subtract'' fill from a region. This algorithm is now implemented in the GPU \rephrase{stencil buffer-y and... stuff} \cite{kilgard2012gpu}
-
-\subsection{Compositing}
-\input{chapters/Background_Compositing}
-
-Traditionally, vector graphics have been rasterized by the CPU before being sent to the GPU for drawing\cite{kilgard2012gpu}. Lots of people would like to change this \cite{worth2003xr, loop2007rendering, rice2008openvg, kilgard2012gpu, green2007improved}.
-
-\rephrase{2. Here are the ways documents are structured ... we got here eventually}
-
-\section{Document Representations}
-
-The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper referenced earlier has been produced on a mechanical type writer. Although the paper discusses an algorithm for shading on computer displays, the figures illustrating this algorithm have not been generated by a computer, but drawn by Brassel's assistant\cite{brassel1979analgorithm}. In contrast, modern papers such as Barnes et. al's recent paper on embedding 3d images in PDF documents\cite{barnes2013embeddding} can themselves be an interactive proof of concept.
-
-Hayes' 2012 article ``Pixels or Perish'' discusses the recent history and current state of the art in documents for scientific publications\cite{hayes2012pixels}. Hayes argued that there are currently two different approaches to representing documents although the line between these two philosophies is being blurred. We shall restrict ourselves to considering the standards discussed by Hayes.
-
-\subsection{Interpreted Model}
-
-\begin{itemize}
- \item This model treats a document as the source code program which produces graphics
- \item Arose from the desire to produce printed documents using computers (which were still limited to text only displays).
- \item Typed by hand or (later) generated by a GUI program
- \item PostScript --- largely supersceded by PDF on the desktop but still used by printers\footnote{Desktop pdf viewers can still cope with PS, but I wonder if a smartphone pdf viewer would implement it?}
- \item \TeX --- Predates PostScript, similar idea
- \begin{itemize}
- \item Maybe if \LaTeX were more popular there would be desktop viewers that converted \LaTeX directly into graphics
- \end{itemize}
- \item Potential for dynamic content, interactivity; dynamic PostScript, enhanced Postscript
-
- \item Problems with security --- Turing complete, can be exploited easily
-\end{itemize}
-
-\subsection{Crippled Interpreted Model}
-
-\rephrase{I'm pretty sure I made that one up}
-
-\begin{itemize}
- \item PDF is PostScript but without the Turing Completeness
- \item Solves security issues, more efficient
-\end{itemize}
-
-\subsection{Document Object Model}
-
-The Document Object Model (DOM) represents a document as a tree like data structure with the document as a root node. The elements of the document are represented as children of either this root node or of a parent element. In addition, elements may have attributes which contain information about that particular element.
-
-The DOM is described by the W3C XML (extensible markup language) standard\cite{citationneeded}. XML itself is a general language which is intended for representing any tree-like structure using the DOM, whilst languages such as HTML\cite{citationneeded} and SVG\cite{citationneeded} are specific XML based languages for representing visual information.
-
-The HyperText Markup Language (HTML) was, as its name implies, originally intended mostly for text. When combined with Cascading Style Sheets (CSS) control over the positioning and style of the text can be acheived. Images stored in some other format can be rendered within a HTML document, but HTML does not include ways to specify graphics primitives or their coordinates.
-
-The Scalable Vector Graphics (SVG) standard was designed to represent a vector image. In the SVG standard, each graphics primitive is an element in the DOM, whilst attributes of the element give information about how the primitive is to be drawn, such as path coordinates, line thickness, mitre styles and fill colours.
-
-\subsubsection{Modifying the DOM --- Javascript}
-
-Javascript is now ubiquitous in web based documents, and is essentially used to make the DOM interactive. This can be done by altering the attributes of elements, or adding and removing elements from the DOM, in response to some event such as user input or communication with a HTTP server. In the HTML5 standard, it is also possible to draw directly to a region of the document defined by the \verb/<canvas>/ tag; as Hayes points out, this is similar to the use of PostScript in specifying the appearance of a document using low level drawing operators which are read by an interpreter.
-
-\subsection{Scientific Computation Packages}
-
-The document and the code that produces it are one and the same.
-
-\begin{itemize}
- \item Numerical computation packages such as Mathematica and Maple use arbitrary precision floats
- \begin{itemize}
- \item Mathematica is not open source which is an issue when publishing scientific research (because people who do not fork out money for Mathematica cannot verify results)
- \item What about Maple? \cite{HFP} and \cite{fousse2007mpfr} both mention it being buggy.
- \item Octave and Matlab use fixed precision doubles
- \end{itemize}
- \item IPython is pretty cool guys
-\end{itemize}
-
-\section{Precision in Modern Document Formats}
-
-We briefly summarise the requirements of standard document formats in regards to the precision of number representations:
-\begin{itemize}
- \item {\bf PostScript} predates the IEEE-754 standard and originally specified a floating point representation with ? bits of exponent and ? bits of mantissa. Version ? of the PostScript standard changed to specify IEEE-754 binary32 ``single precision'' floats.
- \item {\bf PDF} has also specified IEEE-754 binary32 since version ?. Importantly, the standard states that this is a \emph{maximum} precision; documents created with higher precision would not be viewable in Adobe Reader.
- \item {\bf SVG} specifies a minimum of IEEE-754 binary32 but recommends more bits be used internally
- \item {\bf Javascript} uses binary32 floats for all operations, and does not distinguish between integers and floats.
-\end{itemize}
-
-\rephrase{4. Here is IEEE-754 which is what these standards use}
-
-\section{Real Number Representations}
-
-We have found that PostScript, PDF, and SVG document standards all restrict themselves to IEEE floating point number representations of coordinates. This is unsurprising as the IEEE standard has been successfully adopted almost universally by hardware manufactures and programming language standards since the early 1990s. In the traditional view of a document as a static, finite sheet of paper, there is little motivation for enhanced precision.
-
-In this section we will begin by investigating floating point numbers as defined in the IEEE standard and their limitations. We will then consider alternative number representations including fixed point numbers, arbitrary precision floats, rational numbers, p-adic numbers and symbolic representations. \rephrase{Oh god I am still writing about IEEE floats let alone all those other things}
-
-\subsection{Floating Point}
-
-A floating point number $x$ is commonly represented by a tuple of integers $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}:
-
-\begin{align*}
- x &= (-1)^{s} \times m \times B^{e}
-\end{align*}
-
-Where $s$ is the sign and may be zero or one, $m$ is commonly called the ``mantissa'' and $e$ is the exponent.
-The name ``floating point'' refers to the equivelance of the $\times B^e$ operation to a shifting of a decimal point along the mantissa. This contrasts with a ``fixed point'' representation where $x$ is the sum of two fixed size numbers representing the integer and fractional part.
-
-
-
-\subsection{The IEEE-754 Standard}
-
-Although the concept of a floating point representation has been attributed to various early computer scientists including Charles Babbage\cite{citationneeded}, it is widely accepted that William Kahan and his colleagues working on the IEEE-754 standard in the 1980s are the ``fathers of modern floating point computation''\cite{citationneeded}. The IEEE standard specifies the encoding, number of bits, rounding methods, and maximum acceptable errors for the basic floating point operations. It also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero.
-
-In the IEEE-754 standard, for a base of $B = 2$, numbers are encoded in continuous memory by a fixed number of bits, with $s$ occupying 1 bit, followed by $e$ and $m$ occupying a number of bits specified by the precision; 5 and 10 for a binary16 or ``half precision'' float, 8 and 23 for a binary32 or ``single precision'' and 15 and 52 for a binary64 or ``double precision'' float\cite{HFP, ieee2008-754}. The IEEE-754 standard also specifies a base 10 encoding (useful in financial software\cite{citationneeded}), but since this is subject to similar limitations, we will restrict ourselves to the simpler base 2 encodings.
-
-
-\subsection{Precision and Rounding}
-
-Real values which cannot be represented exactly in a floating point representation must be rounded. The results of a floating point operation may be such values and thus there is a rounding error possible in any floating point operation. Goldberg's assertively titled 1991 paper ``What Every Computer Scientist Needs to Know about Floating Point Arithmetic'' provides a comprehensive overview of issues in floating point arithmetic and relates these to the 1984 version of the IEEE-754 standard\cite{goldberg1991whatevery}. More recently, after the release of the revised IEEE-754 standard,
-
-Figure \ref{minifloat.pdf} shows the real numbers which can be represented exactly by an 8 bit base $B = 2$ floating point number; and illustrates that a set of fixed precision floating point numbers forms a discrete approximation of the reals. There are only $2^8 = 256$ numbers in this set, which means it is easier to see some of the properties of floats that would be unclear using one of the IEEE-754 encodings. The first set of points corresponds to using $(1,2,5)$ to encode $(s,e,m)$ whilst the second set of points corresponds to a $(1,3,4)$ encoding. This allows us to see the trade off between the precision and range of real values represented.
-
-
-\subsection{Floating Point Operations}
-
-Floating point operations can in principle be performed using integer operations, but specialised Floating Point Units (FPUs) are an almost universal component of modern processors\cite{citationneeded}. The improvement of FPUs remains highly active in several areas including: efficiency\cite{seidel2001onthe}; accuracy of operations\cite{dieter2007lowcost}; and even the adaptation of algorithms originally used in software for reducing the overal error of a sequence of operations\cite{kadric2013accurate}. In this section we will consider the algorithms for floating point operations without focusing on the hardware implementation of these algorithms.
-
-
-\subsection{Limitations Imposed By CPU}
-
-CPU's are restricted in their representation of floating point numbers by the IEEE standard.
-
-
-
-\subsection{Limitations Imposed By Graphics APIs and/or GPUs}
-
-Traditionally algorithms for drawing vector graphics are performed on the CPU; the image is rasterised and then sent to the GPU for rendering\cite{}. Recently there has been a great deal of literature relating to implementation of algorithms such as bezier curve rendering\cite{} or shading\cite{} on the GPU. As it seems the trend is to move towards GPU
-
-\rephrase{6. Here are ways GPU might not be IEEE-754 --- This goes *somewhere* in here but not sure yet}
-
-\begin{itemize}
- \item Internal representations are GPU dependent and may not match IEEE\cite{hillesland2004paranoia}
- \item OpenGL standards specify: binary16, binary32, binary64
- \item OpenVG aims to become a standard API for SVG viewers but the API only uses binary32 and hardware implementations may use less than this internally\cite{rice2008openvg}
- \item It seems that IEEE has not been entirely successful; although all modern CPUs and GPUs are able to read and write IEEE floating point types, many do not conform to the IEEE standard in how they represent floating point numbers internally.
-\end{itemize}
-
-
-
-\rephrase{7. Sod all that, let's just use an arbitrary precision library (AND THUS WE FINALLY GET TO THE POINT)}
-
-\subsection{Arbitrary Precision Floating Point Numbers}
-
-An arbitrary precision floating point number simply uses extra bits to store extra precision. Do it all using MFPR\cite{fousse2007mpfr}, she'll be right.
-
-\rephrase{8. Here is a brilliant summary of sections 7- above}
-
-Dear reader, thankyou for your persistance in reading this mangled excuse for a Literature Review.
-Hopefully we have brought together the radically different areas of interest together in some sort of coherant fashion.
-In the next chapter we will talk about how we have succeeded in rendering a rectangle. It will be fun. I am looking forward to it.
-
-\rephrase{Oh dear this is not going well}
-
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au