Tidy up a bit

Still need that entire second half of the lit review.
It'll just have to be smaller I think.

diff --git a/chapters/Background.tex b/chapters/Background.tex
index bde2b7c..ee8da21 100644 (file)
--- a/chapters/Background.tex
+++ b/chapters/Background.tex
@@ -2,7 +2,7 @@
 
 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}.
 
 
 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}.
 

-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.
+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.

 
 The research on arbitrary precision arithmetic applied to documents is rather 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.
 
 
 The research on arbitrary precision arithmetic applied to documents is rather 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.
 


@@ -52,7 +52,7 @@ The PostScript and PDF standards, as well as the OpenGL API also use a painter's
 
 Traditionally, vector images have been rasterized by the CPU before being sent to a specialised Graphics Processing Unit (GPU) for drawing\cite{computergraphics2}. Rasterisation of simple primitives such as lines and triangles have been supported directly by GPUs for some time through the OpenGL standard\cite{openglspec}. However complex shapes (including those based on B{\'e}zier curves such as font glyphs) must either be rasterised entirely by the CPU or decomposed into simpler primitives that the GPU itself can directly rasterise. There is a significant body of research devoted to improving the performance of rendering such primitives using the latter approach, mostly based around the OpenGL API\cite{robart2009openvg, leymarie1992fast, frisken2000adaptively, green2007improved, loop2005resolution, loop2007rendering}. Recently Mark Kilgard of the NVIDIA Corporation described an extension to OpenGL for NVIDIA GPUs capable of drawing and shading vector paths\cite{kilgard2012gpu,kilgard300programming}. From this development it seems that rasterization of vector graphics may eventually become possible upon the GPU.openglspec
 
 
 Traditionally, vector images have been rasterized by the CPU before being sent to a specialised Graphics Processing Unit (GPU) for drawing\cite{computergraphics2}. Rasterisation of simple primitives such as lines and triangles have been supported directly by GPUs for some time through the OpenGL standard\cite{openglspec}. However complex shapes (including those based on B{\'e}zier curves such as font glyphs) must either be rasterised entirely by the CPU or decomposed into simpler primitives that the GPU itself can directly rasterise. There is a significant body of research devoted to improving the performance of rendering such primitives using the latter approach, mostly based around the OpenGL API\cite{robart2009openvg, leymarie1992fast, frisken2000adaptively, green2007improved, loop2005resolution, loop2007rendering}. Recently Mark Kilgard of the NVIDIA Corporation described an extension to OpenGL for NVIDIA GPUs capable of drawing and shading vector paths\cite{kilgard2012gpu,kilgard300programming}. From this development it seems that rasterization of vector graphics may eventually become possible upon the GPU.openglspec
 

-It is not entirely clear how well supported the IEEE-754 standard for floating point computation (which we will discuss in Section \ref{}) is amongst GPUs. Although the OpenGL API does use IEEE-754 number representations, research by Hillesland and Lastra in 2004 suggested that many GPUs were not internally compliant with the standard\cite{hillesland2004paranoia}. Arbitrary precision arithmetic, whilst provided by many libraries for CPU based calculations, is virtually unheard of in the context of GPU rendering.
+It is not entirely clear how well supported the IEEE-754 standard for floating point computation (which we will discuss in Section \ref{}) is amongst GPUs\footnote{Informal technical articles are prevelant on the internet --- Eg: Regarding the Dolphin Wii GPU Emulator: \url{https://dolphin-emu.org/blog} (accessed 2014-05-22)}. Although the OpenGL API does use IEEE-754 number representations, research by Hillesland and Lastra in 2004 suggested that many GPUs were not internally compliant with the standard\cite{hillesland2004paranoia}. %Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations

 
  \pagebreak
 \section{Document Representations}\label{Document Representations}
 
  \pagebreak
 \section{Document Representations}\label{Document Representations}


@@ -90,7 +90,7 @@ PDF defines ``Real'' objects in a similar way to PostScript, but suggests a rang
 
 \subsection{\TeX and METAFONT}
 
 
 \subsection{\TeX and METAFONT}
 

-In ``The METAFONT book'' Knuth appears to describe coordinates as fixed point numbers: ``The computer works internally with coordinates that are integer multiples of $\frac{1}{65536} \approx 0.00002$ of the width of a pixel''\cite{knuth1983metafont}. There is no mention of precision in ``The \TeX book''. In 2007 Beebe claimed this was due to the lack of standardised floating point arithmetic on computers at the time; a problem that the IEEE-754 was designed to solve\cite{beebe2007extending}. Beebe also suggests that \TeX and METAFONT could now be modified to use IEEE-754 arithmetic.
+In ``The METAFONT book'' Knuth appears to describe coordinates as fixed point numbers: ``The computer works internally with coordinates that are integer multiples of $\frac{1}{65536} \approx 0.00002$ of the width of a pixel''\cite{knuth1983metafont}. There is no mention of precision in ``The \TeX book''. In 2007 Beebe claimed that {\TeX} uses a $14.16$ fixed point encoding, and that this was due to the lack of standardised floating point arithmetic on computers at the time; a problem that the IEEE-754 was designed to solve\cite{beebe2007extending}. Beebe also suggests that \TeX and METAFONT could now be modified to use IEEE-754 arithmetic.

 
 \subsection{SVG}
 
 
 \subsection{SVG}
 


@@ -98,46 +98,44 @@ The SVG standard specifies a minimum precision equivelant to that of ``single pr
 coordinate system transformations to provide the best possible precision and to prevent round-off errors.''\cite{svg2011-1.1} An SVG Viewer may refer to itself as ``High Quality'' if it uses a minimum of ``double precision'' floats.
 
 \subsection{Javascript}
 coordinate system transformations to provide the best possible precision and to prevent round-off errors.''\cite{svg2011-1.1} An SVG Viewer may refer to itself as ``High Quality'' if it uses a minimum of ``double precision'' floats.
 
 \subsection{Javascript}

-Although Javascript is not a stand alone document format, we include it here due to its relation with the SVG, HTML5 and PDF standards.
-
+We include Javascript here due to its relation with the SVG, HTML5 and PDF standards.

 
 According to the EMCA-262 standard, ``The Number type has exactly 18437736874454810627 (that is, $2^64-^53+3$) values, 
 representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic''\cite{ecma-262}. 
 The Number type does differ slightly from IEEE-754 in that there is only a single valid representation of ``Not a Number'' (NaN). The EMCA-262 does not define an ``integer'' representation.
        
 
 
 According to the EMCA-262 standard, ``The Number type has exactly 18437736874454810627 (that is, $2^64-^53+3$) values, 
 representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic''\cite{ecma-262}. 
 The Number type does differ slightly from IEEE-754 in that there is only a single valid representation of ``Not a Number'' (NaN). The EMCA-262 does not define an ``integer'' representation.
        
 

-\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.
+\section{Number Representations}

 
 

-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}

 
 

-\rephrase{Reorder to start with Integers, General Floats, then go to IEEE, then other things}
+\subsection{Integers and Fixed Point Numbers}

 
 

-\subsection{IEEE Floating Points}

 
 

-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 original IEEE-754 standard specified the encoding, number of bits, rounding methods, and maximum acceptable errors for the basic floating point operations for base $B = 2$ floats. It also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero\footnote{Kahan has argued that exceptions in IEEE-754 are conceptually different to Exceptions as defined in several programming languages including C++ and Java. An IEEE exception is intended to prevent an error by its detection, whilst an exception in those languages is used to indicate an error has already occurred\cite{}}. We will restrict ourselves to considering $B = 2$, since it was found that this base in general gives the smallest rounding errors\cite{HFP}, although it is worth noting that different choices of base had been used historically\cite{goldman1991whatevery}, and the IEEE-854 and later the revised IEEE-754 standard specify a decimal representation $B = 10$ intended for use in financial applications.

 
 

-\subsection{Floating Point Definition}
+\subsection{Floating Points}

 
 

-A floating point number $x$ is commonly represented by a tuple of integers $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}:
+A floating point number $x$ is commonly represented by a tuple of values $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}:

 
 \begin{align*}
        x &= (-1)^{s} \times m \times B^{e}
 \end{align*}
 
 
 \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.
+Where $s$ is the sign and may be zero or one, $m$ is commonly called the ``mantissa'' and $e$ is the exponent. Whilst $e$ is an integer in some range $\pm e_max$, the mantissa $m$ is actually a fixed point value in the range $0 < m < B$. The name ``floating point'' refers to the equivelance of the $\times B^e$ operation to a shifting of the ``fixed point'' along the mantissa.

 
 

-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}.
+For example, the value $7.25$ can be expressed as:
+\begin{enumerate}
+       \item 
+       
+\end{enumerate}

 
 

+The choice of base $B = 2$, closely matches the nature of modern hardware. It has also been found that this base in general gives the smallest rounding errors\cite{HFP}. Early computers had in fact used a variety of representations including $B=3$ or even $B=7$\cite{goldman1991whatevery}, and the revised IEEE-754 standard specifies a decimal representation $B = 10$ intended for use in financial applications\cite{ieee754std2008}. From now on we will restrict ourselves to considering base 2 floats.

 
 

-\subsection{Precision and Rounding}
+Figure \ref{minifloat.pdf} shows the positive real numbers which can be represented exactly by an 8 bit floating point number encoded in the IEEE-754 format, and the distance between successive floating point numbers. We show two encodings using (1,2,5) and (1,3,4) bits to encode (sign, exponent, mantissa) respectively.

 
 

-Real values which cannot be represented exactly in a floating point representation must be rounded. The results of a floating point operation will in general 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 in 2008, a textbook ``Handbook Of Floating Point Arithmetic'' has been published which provides a thourough review of literature relating to floating point arithmetic in both software and hardware\cite{HFP}.
+For each distinct value of the exponent, the successive floating point representations lie on a straight line with constant slope. As the exponent increases, larger values are represented, but the distance between successive values increases\footnote{A plot of fixed point numbers or integers (which we omit for space considerations) would show points lying on a straight line with a constant slope between points}.

 
 

+In the graph of the difference between representations, a single isolated point should be visible; this is not an error, but due to the greater discontinuity between the denormalised and normalised values ($e = 0$ and $1$ respectively). 

 
 

-Figure \ref{minifloat.pdf} shows the positive 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^7 = 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 2 and 5 bits to encode $e$ and $m$ whilst the second set of points corresponds to a 3 and 4 bit encoding. This allows us to see the trade off between the precision and range of real values represented. 

 
 \begin{figure}[H]
        \centering
 
 \begin{figure}[H]
        \centering


@@ -148,45 +146,20 @@ Figure \ref{minifloat.pdf} shows the positive real numbers which can be represen
 
 \subsection{Floating Point Operations}
 
 
 \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{Some sort of Example(s) or Floating Point Mayhem}
-
-\rephrase{Eg: $f(x) = |x|$ calculated from sqrt and squaring}
+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{kelley1997acmos}. 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 briefly describe the algorithms for floating point operations without focusing on the hardware implementation of these algorithms.

 
 

-\rephrase{Eg: Massive rounding errors from calculatepi}

 
 

-\rephrase{Eg: Actual graphics things :S}
+\subsection{Precision and Rounding} 

 
 

+Real values which cannot be represented exactly in a floating point representation must be rounded to the nearest floating point value. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Referring to Figure \ref{minifloat.pdf} it can be seen that the largest possible rounding error, or ``units in last place'' (ulp) is half the distance between successive floats; this means that rounding errors increase as the value to be represented increases. The IEEE-754 standard specifies the rounding conventions for floating point arithmetic\cite{ieee754std2008}.

 
 

-\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 B{\'e}zier curve rendering\cite{} or shading\cite{} on the GPU. As it seems the trend is to move towards GPU 
+Goldberg's assertively titled 1991 paper ``What Every Computer Scientist Needs to Know about Floating Point Arithmetic''\cite{goldberg1991whatevery} provides a comprehensive overview of issues in floating point arithmetic and relates these to requirements of the IEEE-754 1985 standard\cite{ieee754std1985}. More recently, after the release of the revised IEEE-754 standard in 2008\cite{ieee754std2008}, a textbook ``Handbook Of Floating Point Arithmetic'' has been published which provides a thourough review of literature relating to floating point arithmetic in both software and hardware\cite{HFP}.

 
 

-\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. 
-       \item \rephrase{Blog post alert} \url{https://dolphin-emu.org/blog/2014/03/15/pixel-processing-problems/}
-\end{itemize}
-
-
-
-\rephrase{7. Sod all that, let's just use an arbitrary precision library (AND THUS WE FINALLY GET TO THE POINT)}
+William Kahan, one of the architects of the IEEE-754 standard in 1984 and a contributor to its revision in 2010, has also published many articles on his website explaining the more obscure features of the IEEE-754 standard and calling out software which fails to conform to the standard\footnote{In addition to encodings and acceptable rounding errors, the standard also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero --- which are sometimes neglected, as in the ECMA-256}\cite{kahanweb, kahan1996ieee754}, as well as examples of the limitations of floating point computations\cite{kahan2007wrong}. 

 
 \subsection{Arbitrary Precision Floating Point Numbers}
 
 
 \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.
+Fouse described 

 
 

-\rephrase{Oh dear this is not going well}

 
 

diff --git a/chapters/Introduction.tex b/chapters/Introduction.tex
index 311b406..808b70a 100644 (file)
--- a/chapters/Introduction.tex
+++ b/chapters/Introduction.tex
@@ -12,4 +12,4 @@ We are now seeing a widespread use of mobile computing devices with touch screen
 
 \section{Overview}
 
 
 \section{Overview}
 

-The remainder of this document will be organised as follows: In Chapter \ref{Proposal} we give an overview of the current state of the research in document formats, and the motivation for implementing ``infinite precision'' in a document format. We will outline our approach to research in collaboration with David Gow\cite{}. In Chapter \ref{Background} we provide more detailed background examining the literature related to rendering, interpreting, and creating document formats, as well as possible techniques for increased and possibly infinite precision. In Chapter \ref{Progress} gives the current state of our research and the progress towards the goals outlined in Chapter \ref{Introduction}. In Chapter \ref{Conclusion} we will conclude with a summary of our findings and goals.
+The remainder of this document will be organised as follows: In Chapter \ref{Proposal} we give an overview of the current state of the research in document formats, and the motivation for implementing ``infinite precision'' in a document format. We will outline our approach to research in collaboration with David Gow\cite{}. In Chapter \ref{Background} we provide more detailed background examining the literature related to rendering, interpreting, and creating document formats, as well as possible techniques for increased and possibly infinite precision. In Chapter \ref{Progress} gives the current state of our research and the progress towards the goals outlined in Chapter \ref{Introduction}.

diff --git a/chapters/Progress.tex b/chapters/Progress.tex
index 1aa5f1b..a88e002 100644 (file)
--- a/chapters/Progress.tex
+++ b/chapters/Progress.tex
@@ -1,73 +1,84 @@
-\chapter{Progress Report}\label{Progress Report}
+\chapter{Progress Report}\label{Progress}

 
 

-This chapter outlines the current state of our research in relation to the aims outlined in Chapter \ref{Introduction}.
+We describe the current state of our research in relation to the aims outlined in Chapter \ref{Introduction}.

 
 \section{Literature Review}
 
 
 \section{Literature Review}
 

-We have examined a range of literature that can be broadly classed into three different areas:
+We have examined a range of literature that can be broadly classed into three different areas (with major references indicated):

 \begin{enumerate}
 \begin{enumerate}

-       \item Rendering Vector Graphics
-       \item Representations of Vector Documents
-       \item Floating Point number representations
+       \item Rendering Vector Graphics \cite{computergraphics2, knuth1983metafont, kilgard2012gpu}
+       \begin{itemize}
+               \item Rasterisation of Vector Graphics is non-trivial but well understood
+               \item Traditionally most rasterisation has been performed on the CPU and drawing on a dedicated GPU; current interest is in techniques for utilising the GPU directly to rasterise vector graphics
+       \end{itemize}
+       \item Representations of Vector Documents \cite{hayes2012pixels, plrm, knuth1984texbook, svg2011-1.1, pdfref17}
+       \begin{itemize}
+               \item Traditional approaches are be based on a programmatic model (PostScript, {\TeX}, DVI)
+               \item The Document Object Model (DOM) used by web technologies is a powerful way to produce dynamic documents (HTML5, SVG, Javascript)
+               \item These approaches can overlap (PDF)
+       \end{itemize}
+       \item Number Representations \cite{ieee754std2008, HFP, goldberg1991whatevery, fousse2007mpfr}
+       \begin{itemize}
+               \item Most document standards either specify, suggest, or imply a IEEE-754 floating point representation ({\TeX} is an exception)
+               \item IEEE-754 is widely used, although there are instances of languages or processors which do not conform exactly to the standard
+               \item Some GPUs in particular may not conform to IEEE-754, possibly trading some accuracy for performance
+       \end{itemize}

 \end{enumerate}
 
 \end{enumerate}
 

-In summary, we have found:
-\begin{itemize}
-       \item Rasterisation of Vector Graphics is non-trivial but well understood
-       \item Traditionally rasterisation has been performed on the CPU and rendering on a dedicated GPU; current interest is in techniques for utilising the GPU directly to rasterise vector graphics.
-       \item The popular standards for document formats including PostScript, PDF, HTML, SVG require IEEE-754 binary32 precision
-       \item Fixed precision floating point numbers make a trade off between precision and range
-       \item IEEE-754 is widely used although there are instances of languages or processors which do not conform exactly to the standard
-       \item GPUs in particular may not conform to IEEE-754, trading some accuracy of operations for performance
-\end{itemize}
+To improve the Literature Review we could consider the following topics in more detail:
+\begin{enumerate}
+       \item Additional approaches to arbitrary or infinite precision, possibly including symbolic computation
+       \item Floating point errors in the context of computing B\'{e}zier Curves or similar
+       \item How well GPUs conform or do not conform to IEEE-754 in more detail
+       \item Additional aspects of rendering vector documents including shading
+\end{enumerate}

 
 \section{Development of Testbed Software}
 
 
 \section{Development of Testbed Software}
 

-We have produced a basic Document Viewer capable of rendering simple primitives under translation and scaling. OpenGL 3.1 is used to interface with graphics hardware. This software has the following features:
+We have produced a basic Document Viewer capable of rendering simple primitives under translation and scaling. The OpenGL 3.1 API is used to interface with graphics hardware. This software has the following features:

 \begin{enumerate}
        \item A type name \verb/Real/ is used in place of the standard floating point types \verb/float/, \verb/double/ or \verb/long double/. This type name can be redefined to refer to one of the standard types or a custom real number representation, allowing us to easily recompile and test our software for different representations.
        \item Screenshots can be overlaid on top of each other to get a pixel comparison of the graphical output of different versions of the program
        \item Test documents can be loaded and saved so that we can compare different versions of the program on identical inputs
 \begin{enumerate}
        \item A type name \verb/Real/ is used in place of the standard floating point types \verb/float/, \verb/double/ or \verb/long double/. This type name can be redefined to refer to one of the standard types or a custom real number representation, allowing us to easily recompile and test our software for different representations.
        \item Screenshots can be overlaid on top of each other to get a pixel comparison of the graphical output of different versions of the program
        \item Test documents can be loaded and saved so that we can compare different versions of the program on identical inputs

-       \item Transformations can be performed on either the GPU or CPU
-       \item Performance of rendering can be measured
+       \item The time for rendering can be measured
+       \item Coordinate transformations may be performed on either the GPU or CPU 

 \end{enumerate}
 
 \end{enumerate}
 

-We have found the performance of coordinate transforms on the GPU to be far superior to the CPU. However, at large enough scales it becomes apparent that the GPU is performing operations at a lower precision than the CPU. See Figure \ref{}.
-
-
+We have noticed the CPU produces more precise coordinate transformations at large ``zoom'' levels, but is significantly slower than the GPU. We have yet to quantitatively measure this difference.

 
 

-\section{Floating Point Precision}
+\section{Floating Point Arithmetic}

 
 Algorithms for floating point arithmetic may be implemented in software (CPU) or on dedicated hardware (FPU). We have made progress towards both approaches. 
 
 An open source Virtual FPU implemented in the VHDL language has been successfully compiled and can be substituted into our testbed software in place of native arithmetic running on the CPU. The timing diagram for this FPU throughout the execution of test programs can be extracted. Currently the virtual FPU is restricted to 32 bit floats and the square root operation is unimplemented.
 
 
 Algorithms for floating point arithmetic may be implemented in software (CPU) or on dedicated hardware (FPU). We have made progress towards both approaches. 
 
 An open source Virtual FPU implemented in the VHDL language has been successfully compiled and can be substituted into our testbed software in place of native arithmetic running on the CPU. The timing diagram for this FPU throughout the execution of test programs can be extracted. Currently the virtual FPU is restricted to 32 bit floats and the square root operation is unimplemented.
 

-Mainly motivated by producing Figure \ref{minifloat.pdf} we have also implemented functions to convert arbitrary real numbers (which may themselves be IEEE-754 floats) to and from a fixed size floating point representation of our choosing. We have not implemented any operations for floating point arithmetic using these representations.
+Mainly motivated by producing Figure \ref{minifloat.pdf} we have also implemented functions to convert an arbitrary \verb/Real/ type (which may be IEEE-754 floats) to and from a fixed size floating point representation of our choosing. We have not implemented any operations for floating point arithmetic using these representations.

 
 By using the functions to convert real numbers to variable precision floats as an interface for the virtual FPU, we hope to illustrate the limitations of floating point arithmetic more clearly than would be possible using IEEE-754 binary32 as is native to the C and C++ languages.
 
 
 By using the functions to convert real numbers to variable precision floats as an interface for the virtual FPU, we hope to illustrate the limitations of floating point arithmetic more clearly than would be possible using IEEE-754 binary32 as is native to the C and C++ languages.
 

-\subsection{Prototype Document Formats}
+\section{Prototype Document Formats}

 
 

-Our testbed software is capable of reading primitive attributes from either a binary file or XML plain text file. Our format is closest to the Document Object Model, although there is currently only one generation in the tree as no primitives can contain other elements as of yet.
+Our testbed software is capable of reading primitive attributes from either a binary file or XML plain text file. Our format is conceptually similar to the Document Object Model, although there is currently only one generation in the tree as no primitives can contain other elements as of yet.

 
 If time permits, we plan to extend our XML format to cover a subset of the SVG standard. This may allow us to compare the rasterisation of an SVG using our own software and traditional software relying on IEEE-754 floats.
 
 
 If time permits, we plan to extend our XML format to cover a subset of the SVG standard. This may allow us to compare the rasterisation of an SVG using our own software and traditional software relying on IEEE-754 floats.
 

+Some of the figures produced for Chapter \ref{Background} may prove useful as standard test images for comparing the qualitative performance of versions of our software.

 
 \section{Version Control and Backup of Work}
 
 
 \section{Version Control and Backup of Work}
 

-Git is a distributed version control system widely used in the development of open source software\cite{}. All rescources created for or used by this project have been placed in git repositories on several servers. The repositories are publically accessable at \url{http://git.ucc.asn.au}, \url{http://szmoore.net/ipdf} and \url{david's website probably I guess}\footnote{These are all actually on the same filesystem but it sounds impressive anyway}
+Git is a distributed version control system widely used in the development of open source software. All rescources created for or used by this project have been placed in git repositories on several servers. The repositories are publically accessable at \url{http://git.ucc.asn.au}, \url{http://szmoore.net/ipdf}.

 
 \section{Timeline}
 
 
 \section{Timeline}
 

-Deadlines enforced by the faculty of Engineering Computing and Mathematics are \emph{italicised}. Tasks completed as of the submission of this report are struck through. \footnote{David Gow is being assessed under the 2014 rules for a BEng (Software) Final Year Project, whilst the author is being assessed under the 2014 rules for a BEng (Mechatronics) Final Year Project; deadlines and requirements as shown in Gow's proposal\cite{proposalGow} may differ}.
+Deadlines enforced by the faculty of Engineering Computing and Mathematics are \emph{italicised}.\footnote{David Gow is being assessed under the 2014 rules for a BEng (Software) Final Year Project, whilst the author is being assessed under the 2014 rules for a BEng (Mechatronics) Final Year Project; deadlines and requirements as shown in Gow's proposal\cite{proposalGow} may differ}.

 
 \begin{center}
 \begin{tabular}{l|p{0.5\textwidth}}
 
 \begin{center}
 \begin{tabular}{l|p{0.5\textwidth}}

-       {\bf Date} & {\bf Milestone}\\
+       {\bf Date} & {\bf Milestone} \\

        \hline
        $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
        \hline
        \hline
        $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
        \hline

-       ? May & Draft Progress Report and Literature Review \\
+       $17^{\text{th}}$ May & Draft Progress Report and Literature Review \\

        \hline
        $26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\
        \hline
        \hline
        $26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\
        \hline

diff --git a/meta/Abstract.tex b/meta/Abstract.tex
index 467ee0e..31289eb 100644 (file)
--- a/meta/Abstract.tex
+++ b/meta/Abstract.tex
@@ -2,4 +2,9 @@
 
 At the fundamental level, a document is a means to convey information. The limitations on a digital document format therefore restrict the types and quality of information that can be communicated. Whilst modern document formats are now able to include increasingly complex dynamic content, they still suffer from early views of a document as a static page; to be viewed at a fixed scale and position. In this report, we focus on the limitations of modern document formats (including PDF, PostScript, SVG) with regards to the level of detail, or precision at which primatives can be drawn. We propose a research project to investigate whether it is possible to obtain an ``infinite precision'' document format, capable of including primitives created at an arbitrary level of zoom.
 
 
 At the fundamental level, a document is a means to convey information. The limitations on a digital document format therefore restrict the types and quality of information that can be communicated. Whilst modern document formats are now able to include increasingly complex dynamic content, they still suffer from early views of a document as a static page; to be viewed at a fixed scale and position. In this report, we focus on the limitations of modern document formats (including PDF, PostScript, SVG) with regards to the level of detail, or precision at which primatives can be drawn. We propose a research project to investigate whether it is possible to obtain an ``infinite precision'' document format, capable of including primitives created at an arbitrary level of zoom.
 

-{\bf Keywords:} \emph{document formats, precision, floating point, graphics, OpenGL, VHDL, PostScript, PDF, bootstraps}
+{\bf Keywords:} \emph{document formats, precision, floating point, vector images, graphics, OpenGL, VHDL, PostScript, PDF, {\TeX}, SVG, HTML5, Javascript }
+
+{\bf Note:} This report is best viewed digitally as a PDF. The digital version is available at \url{http://szmoore.net/ipdf/documents/LitReviewSam.pdf}
+
+% Oh dear...
+\quad \\ \quad \\ \quad \\ \quad

diff --git a/thesis.pdf b/thesis.pdf
index e2ea4d9..b6e93a1 100644 (file)
Binary files a/thesis.pdf and b/thesis.pdf differ

diff --git a/thesis.tex b/thesis.tex
index 5e7b1ea..5a31a3b 100644 (file)
--- a/thesis.tex
+++ b/thesis.tex
@@ -6,7 +6,7 @@
  %\renewcommand{\baselinestretch}{1.5}         % Uncomment for 1.5 spacing between lines
  %\parindent 0pt                 % sets leading space for paragraphs
 \usepackage{mathrsfs}
  %\renewcommand{\baselinestretch}{1.5}         % Uncomment for 1.5 spacing between lines
  %\parindent 0pt                 % sets leading space for paragraphs
 \usepackage{mathrsfs}

-\usepackage{ulem}
+%\usepackage{ulem}

 %\usepackage{natbib}
 \usepackage{makeidx}
 \usepackage{graphicx}
 %\usepackage{natbib}
 \usepackage{makeidx}
 \usepackage{graphicx}


@@ -127,14 +127,20 @@
 
 
 \pagenumbering{roman}
 
 
 \pagenumbering{roman}

-\newpage
+%\newpage

 %---------------------------------------------------------
 % Do the table of Contents and lists of figures and tables
 %---------------------------------------------------------
 %---------------------------------------------------------
 % Do the table of Contents and lists of figures and tables
 %---------------------------------------------------------

+
+\begingroup
+\let\cleardoublepage\relax
+\let\clearpage\relax

 \linespread{0.3}
 {\small\tableofcontents}
 \linespread{0.3}
 {\small\tableofcontents}

-\listoffigures
+\vspace*{6\baselineskip} % sigh
+{\small\listoffigures}

 \markboth{}{}
 \markboth{}{}

+\endgroup

 \linespread{1.5}
 \newpage
 
 \linespread{1.5}
 \newpage
 


@@ -147,7 +153,7 @@
 \include{chapters/Proposal}
 \include{chapters/Background}
 \include{chapters/Progress}
 \include{chapters/Proposal}
 \include{chapters/Background}
 \include{chapters/Progress}

-\include{chapters/Conclusion}
+%\include{chapters/Conclusion}

 %\newpage
 %---------------------------------------------------------
 \renewcommand{\bibname}{References}
 %\newpage
 %---------------------------------------------------------
 \renewcommand{\bibname}{References}