Penultimate draft
authorSam Moore <matches@ucc.asn.au>
Sun, 26 Oct 2014 07:49:02 +0000 (15:49 +0800)
committerSam Moore <matches@ucc.asn.au>
Sun, 26 Oct 2014 07:49:02 +0000 (15:49 +0800)
Depending on how much I can be bothered reading through it again.

34 files changed:
chapters/Background.tex
chapters/Background/CoordinateSystems.tex
chapters/Background/FixedPoint.tex
chapters/Background/FloatingPointOnTheGPU.tex
chapters/Background/Floats.tex
chapters/Background/Floats/Operations.tex
chapters/Background/Floats/Visualisation.tex
chapters/Background/RasterAndVectorGraphics.tex
chapters/Background/Rationals.tex
chapters/Background/Rendering.tex
chapters/Background/Rendering/BezierSplines.tex
chapters/Background/Rendering/StraightLines.tex
chapters/Background/Standards.tex
chapters/Background/Standards/DOM.tex
chapters/Background/Standards/Interpreted.tex
chapters/Background/Standards/Precision.tex
chapters/Conclusion.tex
chapters/Introduction.tex
chapters/Process.tex
chapters/Results.tex
figures/github.png [new file with mode: 0644]
figures/memory.svg [new file with mode: 0644]
figures/naive_gmprat_is_slow.pdf [new file with mode: 0644]
figures/naive_mpfr_is_also_slow.pdf [new file with mode: 0644]
figures/time.svg [new file with mode: 0644]
figures/turtle.pdf [new file with mode: 0644]
meta/Abstract.tex
meta/Acknowledgements.tex
meta/Letter.tex [new file with mode: 0644]
meta/Titlepage.tex
meta/abstract.pdf [new file with mode: 0644]
meta/letter.pdf [new file with mode: 0644]
thesis.pdf
thesis.tex

index 8a1c83c..fa9de22 100644 (file)
@@ -1,4 +1,5 @@
-\chapter{Literature Review}\label{Background}
+\chapter{Background}\label{Background}
+
 
 %\section{Overview}
 \input{chapters/Background/Overview}
@@ -6,24 +7,25 @@
 \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}
-
-\input{chapters/Background/Standards}
+%\section{Coordinate Systems and Transformations}
+%\input{chapters/Background/CoordinateSystems}
+\section{Precision Specified by Document Standards} \label{Precision Specified by Document Standards}
+In this section we will overview the statements made about the precision with which an object can be stored by various vector graphics and document standards. A more detailed description of the standards discussed here can be found in Appendix \ref{An Overview of Document Standards}.
+\input{chapters/Background/Standards/Precision}
 
 
 
 
 \section{Fixed Point and Integer Number Representations}
 \input{chapters/Background/FixedPoint}
-\section{Floating Point Number Representations}
+\section{Floating Point Number Representations}\label{Floating Point Number Representations}
 \input{chapters/Background/Floats}
 \section{Rational Number Representations}
-\input{chapters/Background/Rationals}
+\input{chapters/Background/Rationals} \label{Rational Number Representations}
 
 
-\section{Floating Point Operations on the CPU and GPU}\label{FloatingPointOnTheGPU}
+\section{Floating Point Operations on the CPU and GPU}
+\label{FloatingPointOnTheGPU}
 \input{chapters/Background/FloatingPointOnTheGPU}
 
 
index 65baecf..c28b45b 100644 (file)
@@ -1,4 +1,4 @@
-Basic vector primitives composed of B{\'e}ziers may be rendered using only integer operations, once the starting and ending positions are rounded to the nearest pixel.
+The literature discussed in Chapter \ref{Background} is primarily concerned with the rendering process for graphical primitives, namely outlines defined by B\'{e}zier curves. We have seen that basic vector primitives composed of B{\'e}ziers may be rendered using only integer operations, once the starting and ending positions are rounded to the nearest pixel.
 
 However, a complete document will contain many such primitives which in general cannot all be shown on a display at once. A ``View'' rectangle can be defined to represent the size of the display relative to the document. To interact with the document a user can change this view through scaling or translating with the mouse.
 
@@ -20,6 +20,7 @@ The transformation may also be written as a 3x3 matrix $\matx{V}$ if we introduc
        \left( \begin{array}{c} X \\ Y \\ 1 \end{array}\right)\label{view-transformation-matrix}
 \end{align}
 
+This transformation can be used not just for the view, but in any mapping of points from one coordinate system to another one which is defined by some bounds rectangle. In particular, our implementations of B\'{e}zier rendering use this transformation to re-express control points relative to the bounding rectangle (whilst in the SVG standard, control points are specified relative to the document).
 
 \begin{figure}[H]
        \centering
@@ -29,18 +30,15 @@ The transformation may also be written as a 3x3 matrix $\matx{V}$ if we introduc
 
 \subsection{View Transformations}
 
-Moving the mouse\footnote{or on a touch screen, swiping the screen} by a distance $(\Delta x, \Delta y)$ relative to the size of the view should translate it by the same amount\cite{}:
+Moving the mouse (or on a touch screen, swiping the screen) by a distance $(\Delta x, \Delta y)$ relative to the size of the view should translate it by the same amount:
 \begin{align}
-       V_x \to V_x + \Delta x \\
-       V_y \to V_y + \Delta y
+       V_x \to V_x + \Delta x &\quad \quad V_y \to V_y + \Delta y
 \end{align}
 
-The document can be scaled by a factor of $s$ about a point $(x_0,y_0)$ specified relative to the view (such as the position of the mouse cursor)\cite{}:
+The document can be scaled by a factor of $s$ about a point $(x_0,y_0)$ specified relative to the view (such as the position of the mouse cursor):
 \begin{align}
-       V_x \to V_x + x_0 V_w(1 - s) \\
-       V_y \to V_y + y_0 V_h(1 - s) \\
-       V_w \to s V_w \\
-       V_h \to s V_h
+       V_x \to V_x + x_0 V_w(1 - s) &\quad \quad V_y \to V_y + y_0 V_h(1 - s) \\
+       V_w \to s V_w &\quad \quad V_h \to s V_h
 \end{align}
 
 The effect of this transformation is that, measured relative to the view rectangle, the distance of primitives with coordinates $(x, y)$ to the point $(x_0, y_0)$ will decrease by a factor of $s$. For $s < 1$ the operation is ``zooming out'' and for $s > 1$, ``zooming in''.
index bb1dea3..15e005a 100644 (file)
@@ -7,12 +7,33 @@ A seperate sign '-' can be used to represent negative reals using equation \eqre
 
 To express a real number using equation \eqref{fixedpointZ} in practice we are limited to a finite number of terms between $i = -m$ and $i = n$. Fixed point representations are capable of representing a discrete set of numbers $0 \leq |z| \leq \beta^{n+1}-\beta^{-m}$ seperated by $\Delta z = \beta^{-m} \leq 1$. In the case $m = 0$, only integers can be represented.
 
+
 Example integer representation in base 10 (decimal) and base 2 (binary):
 \begin{align*}
        5682_{10} &= 5\times10^3 + 6\times10^2 + 8\times10^1 + 2\times10^0 \\
        1011000110010_2 &= 1\times2^{12} + 0\times2^{11} + \text{ ...} + 0\times2^0
 \end{align*}
 
+\subsection{Big Integers} \label{Big Integers}
+Computer hardware implements operations for fixed size integers. The base is $\beta = 2$ and the digits
+are {0, 1}. The most significant bit can be reserved for the sign instead of a digit.
+We can construct larger size integers by considering some sequence of fixed size integers to be
+individual digits. In practice we will still be limited by the memory and processing time required
+1for ``big'' integers.
+
+For example, we can represent $5682_{10}$ as a single 16 bit digit or as the sum of two 8 bit digits. Each
+digit is being written in base 2 or 10 because there is not a universal base with $\ge 2^8$ unique symbols.
+\begin{align*}
+       5682_{10} &= 1011000110010_2 = 10110_2 \times 2^{8} + 110010_{2} \times 2^{0}
+\end{align*}
+
+When performing an operation involving two $m$ digit integers, the result will in general require at most $2m$ digits. A straight forward big integer implementation merely needs to allocate memory for leading zeroes 
+
+Big Integers are implemented on the CPU as part of the standard for several languages including Python\cite{python_pep0237} and Java\cite{java_bigint}. Most implementations are based on the GNU Multiple Precision library (GMP) \cite{gmp2014}. There have also been implementations of Big Integer arithmetic for GPUs\cite{zhao2010GPUMP}.
+
+ During this project a custom Big Integer type was implemented, but was found to be vastly inferior to the GMP implementation\cite{documentsArbitraryIntegers}.
+
+
 %{\bf FIXME} Add Maths reference (Cantor's Diagonal argument) without going into all the Pure maths details
 
 
index 33357a6..7598e73 100644 (file)
@@ -4,10 +4,14 @@ Traditionally, vector images have been rasterized by the CPU before being sent t
 
 It is not entirely clear how well supported the IEEE-754 standard for floating point computation is amongst GPUs\footnote{Informal technical articles are abundant 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}.
 
-Figure \ref{gpufloats.pdf} shows the rendering of a circle through evaluation of $x^2 + y^2 < 1$ in an early version of the IPDF software (Chapter \ref{Process}) using an x86-64 CPU and various GPU models respectively. If we assume the x86-64 is IEEE-754 compliant performing the default rounding behaviour (to nearest) the GPUs are using different rounding behaviours which may not be IEEE-754 compliant.
+To test this assertion, Figure \ref{gpufloats.pdf} was produced with an early version of the IPDF software which will be discussed in Chapter \ref{Process}. The Figure was created jointly with Gow and is also discussed in their work \cite{thesisGow}.
+
 \begin{figure}[H]
        \centering
-       \includegraphics[width=0.9\textwidth]{figures/gpufloats.pdf}\label{gpufloats.pdf}
-       \caption{CPU and GPU evaluation of $x^2 + y^2 < 1$ at $\approx 10^6$ magnification}
+       \includegraphics[width=0.6\textwidth]{figures/gpufloats.pdf}
+       \caption{CPU and GPU evaluation of $x^2 + y^2 < 1$ (black) at $\approx 10^6$ magnification} \label{gpufloats.pdf}
 \end{figure}
+
+
+Figure \ref{gpufloats.pdf} shows the rendering of a the edge of circle through evaluation of $x^2 + y^2 < 1$ using an x86-64 CPU and various GPU models. If we assume the x86-64 is IEEE-754 compliant performing the default rounding behaviour (to nearest) the GPUs are using different rounding behaviours which may not be IEEE-754 compliant. Whilst outside the scope of this project, consistency of floating point arithmetic on GPUs could be an interesting area for further investigation, particularly given the recent interest in use of GPUs for parallelisable numerical computing.
 %Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations
index 1be1113..17ec51c 100644 (file)
@@ -3,12 +3,12 @@
 \input{chapters/Background/Floats/Visualisation}
 
 
-\subsection{Floating Point Operations}
-\input{chapters/Background/Floats/Operations}
+%\subsection{Floating Point Operations}
+%\input{chapters/Background/Floats/Operations}
 
 
-\subsection{Arbitrary Precision Floating Point Numbers}
+\section{Arbitrary Precision Floating Point Numbers}\label{Arbitrary Precision Floating Point Numbers}
 
-Arbitrary precision floating point numbers are implemented in a variety of software libraries which will dynamically allocate extra bits for the exponent or mantissa as required. An example is the GNU MPFR library discussed by Fousse in 2007\cite{fousse2007mpfr}. Although many arbitrary precision libraries already existed, MPFR intends to be fully compliant with some of the more obscure IEEE-754 requirements such as rounding rules and exceptions. 
+Arbitrary precision floating point numbers are implemented in a variety of software libraries which will allocate extra bits for the exponent or mantissa as required. An example is the GNU MPFR library discussed by Fousse in 2007\cite{fousse2007mpfr}. Although many arbitrary precision libraries already existed, MPFR intends to be fully compliant with some of the more obscure IEEE-754 requirements such as rounding rules and exceptions. 
 
-It is trivial to find real numbers that would require an infinite number of bits to represent exactly (for example, $\frac{1}{3} = 0.333333\text{...}$). The GMP and MPFR libraries require a fixed (but arbitrarily large) precision be set; although it is possible to increase or decrease the precision of individual numbers as desired.
+It is trivial to find real numbers that would require an infinite number of bits to represent exactly (for example, $\frac{1}{3} = 0.333333\text{...}$). The GMP and MPFR libraries require a fixed but arbitrarily large precision (size of the mantissa) be set; although it is possible to increase or decrease the precision of individual numbers as desired.
index a527c39..befb9e7 100644 (file)
@@ -1,10 +1,13 @@
 
-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\cite{HFP}. 
+
+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\cite{HFP,ieee754std2008, goldberg1991whatevery}. 
 
 Referring to Figure \ref{floats.pdf} it can be seen that the largest possible rounding error is half the distance between successive floats; this means that rounding errors increase as the value to be represented increases. For the result of a particular operation, the maximum possible rounding error can be determined and is commonly expressed in ``units in the last place'' (ulp), with 1 ulp equivelant to half the distance between successive floats\cite{goldberg1991whatevery}.
 
 
+
 \begin{comment}
+
 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, such as Kahan's Fast2Sum algorithm\cite{kadric2013accurate}. 
 
 
index 41bbda3..90b30b5 100644 (file)
@@ -1,5 +1,7 @@
 
-Figure \ref{floats.pdf} shows the positive real numbers which can be represented exactly by an 8 bit floating point number encoded in the IEEE-754 format. We show two encodings using (1,2,5) and (1,3,4) bits to encode (sign, exponent, mantissa) respectively. 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; this can be seen in Figure\ref{}. The marked single point discontinuity at \verb/0x10/ and \verb/0x20/ occur when $e$ leaves the denormalised region and the encoding of $m$ changes. We have also plotted a fixed point representation for comparison; fixed point and integer representations appear on straight lines.
+To assist with understanding the limitations of floating point representations, we have produced a plot of the positive real numbers which can be represented exactly by an 8 bit floating point number encoded in the IEEE-754 format. We could not find any similar visualisations in the literature.
+
+In Figure \ref{floats.pdf} we show two encodings using (1,2,5) and (1,3,4) bits to encode (sign, exponent, mantissa) respectively. 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; this can be seen in Figure \ref{floats_diff.pdf}. The marked single point discontinuity at \verb/0x10/ and \verb/0x20/ occur when $e$ leaves the denormalised region and the encoding of $m$ changes. We have also plotted a fixed point representation for comparison; fixed point and integer representations appear on straight lines.
 
 \begin{comment}
 The earlier example $7.25$ would be converted to a (1,3,4) floating point representation as follows:
@@ -15,20 +17,21 @@ The earlier example $7.25$ would be converted to a (1,3,4) floating point repres
 This particular example can be encoded exactly; however as there are an infinite number of real values and only a finite number of floats, in general a value must be $7.26$ must be rounded or truncated at Step 3. 
 \end{comment}
 
+\input{chapters/Background/Floats/Operations}
 %\begin{figure}[H]
 %      \centering
 %\begin{minipage}[t]{0.45\textwidth}
        \begin{figure}[H]
                \centering
-               \includegraphics[width=0.8\textwidth]{figures/floats.pdf}\label{floats.pdf}
-               \caption{Positive 8-Bit Number Representations}
+               \includegraphics[width=0.8\textwidth]{figures/floats.pdf} 
+               \caption{Positive 8-Bit Number Representations} \label{floats.pdf}
        \end{figure}
 %\end{minipage}
 %\begin{minipage}[t]{0.45\textwidth}
        \begin{figure}[H]
                \centering
-               \includegraphics[width=0.8\textwidth]{figures/floats_diff.pdf}\label{floats_diff.pdf}
-               \caption{Difference between successive numbers}
+               \includegraphics[width=0.8\textwidth]{figures/floats_diff.pdf} 
+               \caption{Difference between successive numbers} \label{floats_diff.pdf}
        \end{figure}
 %\end{minipage}
 %      \caption{8 bit float and fixed point representations a) As mapped to real values b) The distance between each representation}\label{floats.pdf}
index f729ece..e2301dd 100644 (file)
@@ -2,7 +2,7 @@ At a fundamental level everything that is seen on a display device is represente
 
 A raster image's structure closely matches it's representation as shown on modern display hardware; the image is represented as a grid of filled square ``pixels''. Each pixel is considered to be a filled square of the same size and contains information describing its colour. This representation is simple and also well suited to storing images as produced by cameras and scanners. The drawback of raster images is that by their very nature there can only be one level of detail; this is illustrated in Figures \ref{vector-vs-raster} and \ref{vector-vs-raster-scaled}.
 
-A vector image contains information about the positioning and shading of geometric shapes. To display this image on modern display hardware, coordinates are transformed according to the view and then the image is converted into a raster like representation. Whilst the raster image merely appears to contain edges, the vector image actually contains information about these edges, meaning they can be displayed ``infinitely sharply'' at any level of detail --- or they could be if the coordinates are stored with enough precision (see Section \ref{Precision and Rounding})
+A vector image contains information about the positioning and shading of geometric shapes. To display this image on modern display hardware, coordinates are transformed according to the view and then the image is converted into a raster like representation. Whilst the raster image merely appears to contain edges, the vector image actually contains information about these edges, meaning they can be displayed ``infinitely sharply'' at any level of detail --- or they could be if the coordinates are stored with enough precision. 
 
 Figures \ref{vector-vs-raster} and \ref{vector-vs-raster-scaled} illustrate the advantage of vector formats by comparing raster and vector images in a similar way to Worth and Packard\cite{worth2003xr}. On the right is a raster image which should be recognisable as an animal defined by fairly sharp edges. Figure \ref{vector-vs-raster-scaled} shows how these edges appear jagged when scaled. There is no information in the original image as to what should be displayed at a larger size, so each square shaped pixel is simply increased in size. A blurring effect will probably be visible in most PDF viewers; the software has attempted to make the ``edge'' appear more realistic using a technique called ``antialiasing''\footnote{We recommend disabling this if your PDF viewer supports it}. 
 
index da4f77a..5a55198 100644 (file)
@@ -1,15 +1,13 @@
+A rational number $Q$ may be represented by two integers $N$ the numerator and $D$ the denominator.
+
+\begin{align}
+       Q &= \frac{N}{D} 
+\end{align}                    
+
+Compared to floating point arithmetic which is generally inexact, rational arithmetic including the division operation is always exactly representable as another rational number. However, a \emph{fixed size} rational representation is of rather limited use as $D$ will always grow after repeated operations and overflow. Use of arbitrary sized integers as described in section \ref{Big Integers} and implemented by GMP\cite{granlund2004GMP} overcomes this issue; however as we will see in Chapter \ref{Results and Discussion} there can be a significant performance cost associated with Rationals.
+  
        \begin{align}
-               Q &= \frac{N}{D} 
-       \end{align}                     
-       \begin{itemize}
-               \item $N$ and $D$ are arbitrary precision integers
-       \end{itemize}
-       \begin{align}
-               N &= \sum_{i=0}^{S} d_i \beta^{i}
+               N = \sum_{i=0}^{S} n_i \beta^{i} & \text{ and }
+               D = \sum_{i=0}^{S} d_i \beta^{i} \text{ where $S$ grows as needed}
        \end{align}     
-       \begin{itemize}
-               \item $d_i$ are fixed size integers, $\beta = 2^{64}$
-               \item Size $S$ grows as needed
-               \item Operations are always exact
-               \item Implemented by GNU Multiple Precision Library
-       \end{itemize}
+       
index ce9d13a..7080410 100644 (file)
@@ -1,9 +1,9 @@
 %\subsection{Overview}
 \input{chapters/Background/Rendering/Overview}
 \subsection{Straight Lines}
-\input{chapters/Background/Rendering/StraightLines}
-\subsection{B\'{e}zier Splines}
+\input{chapters/Background/Rendering/StraightLines} \label{Straight Lines}
+\subsection{B\'{e}zier Splines} \label{Bezier Splines}
 \input{chapters/Background/Rendering/BezierSplines}
-\subsection{Fonts}
+\subsection{Fonts} \label{Fonts}
 \input{chapters/Background/Rendering/Fonts}
 
index fd0ec01..cf936ef 100644 (file)
@@ -10,7 +10,7 @@ Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and
 There are many different ways to define a spline.One approach is to specify ``knots'' on the curve and choosing a fixed $n$ ($n = 3$ for ``cubic'' splines) solve for the cooefficients to generate polynomials passing through the points. Alternatively, special polynomials may be defined using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors.\end{co B{\'e}zier splines are the most straight forward way to define a curve in the standards considered in Section \ref{Document Representations}. A spline defined from two cubic B{\'e}ziers is shown in Figure \ref{spline.pdf}
 \end{comment}
 
-Cubic and Quadratic B{\'e}zier Splines are used to define curved paths in the PostScript\cite{plrm}, PDF\cite{pdfref17} and SVG\cite{svg2011-1.1} standards which we will discuss in Section \ref{Document Representations}.  Cubic B{\'e}ziers are also used to define vector fonts for rendering text in these standards and the {\TeX}  typesetting language \cite{knuth1983metafont, knuth1984texbook}. Although he did not derive the mathematics, the usefulness of B{\'e}zier curves was realised by Pierre B{\'e}zier who used them in the 1960s for the computer aided design of automobile bodies\cite{bezier1986apersonal}. 
+Cubic and Quadratic B{\'e}zier Splines are used to define curved paths in the PostScript\cite{plrm}, PDF\cite{pdfref17} and SVG\cite{svg2011-1.1} standards.  Cubic B{\'e}ziers are also used to define vector fonts for rendering text in these standards and the {\TeX}  typesetting language \cite{knuth1983metafont, knuth1984texbook}. Although he did not derive the mathematics, the usefulness of B{\'e}zier curves was realised by Pierre B{\'e}zier who used them in the 1960s for the computer aided design of automobile bodies\cite{bezier1986apersonal}. 
 
 A B{\'e}zier Curve of degree $n$ is defined by $n$ ``control points'' $\left\{P_0, ... P_n\right\}$. 
 Points $P(t) = (x(t), y(t))$ along the curve are defined by:
@@ -65,5 +65,5 @@ De Casteljau's algorithm of 1959 is often used for decomposing B{\'e}ziers into
        \includegraphics[width=0.7\textwidth]{figures/spline.pdf}
 \end{figure}
 \end{minipage}
-       \caption{Constructing a Spline from two cubic B{\'e}ziers \\ (a) Showing the Control Points (b) Representations in SVG and PostScript (c) Rendered Spline}\label{spline.pdf}
+       \caption{Constructing a Spline from two cubic B{\'e}ziers \\ (a) Showing the Control Points (b) Representations in SVG and PostScript (c) Rendered Spline} \label{spline.pdf}
 \end{figure}
index a1a1393..69faa45 100644 (file)
@@ -5,7 +5,7 @@ It is well known that in cartesian coordinates, a line between points $(x_1, y_1
        \text{ and } c = y_1 - m x_1
 \end{align}
 
-On a raster display, only points $(x,y)$ with integer coordinates can be displayed; however $m$ will generally not be an integer. Thus a straight forward use of Equation \ref{eqn_line} will require costly floating point operations and rounding (See Section\ref{Precision and Rounding}). Modifications based on computing steps $\Delta x$ and $\Delta y$ eliminate the multiplication but are still less than ideal in terms of performance\cite{computergraphics2}.
+On a raster display, only points $(x,y)$ with integer coordinates can be displayed; however $m$ will generally not be an integer. Thus a straight forward use of Equation \ref{eqn_line} will require floating point operations and therefore rounding (See Section \ref{Floating Point Number Representations}). Modifications based on computing steps $\Delta x$ and $\Delta y$ eliminate the multiplication but are still less than ideal in terms of performance\cite{computergraphics2}.
 
 It should be noted that algorithms for drawing lines can be based upon sampling $y(x)$ only if $|m| \leq 1$; otherwise sampling at every integer $x$ coordinate would leave gaps in the line because $\Delta y > 1$. Line drawing algorithms can be trivially adopted to sample $x(y)$ if $|m| > 1$.
 
index 3532410..1bb99cf 100644 (file)
@@ -1,12 +1,12 @@
 %\subsection{Overview}
-{\bf FIXME: Most of this stuff should probably be appendicised}
+%{\bf FIXME: Most of this stuff should probably be appendicised}
 
 \input{chapters/Background/Standards/Overview}
-\subsection{Interpreted Models: PostScript and PDF}
+\section{Interpreted Models}
 \input{chapters/Background/Standards/Interpreted}
-\subsection{The Document Object Model: SVG}
+\section{The Document Object Model}
 \input{chapters/Background/Standards/DOM}
-\subsection{Precision Specified By Standards}
+%\subsection{Precision Specified By Standards}
 
 %{\bf TODO: Keep this subsection, appendicise rest of this section}
-\input{chapters/Background/Standards/Precision}
+%\input{chapters/Background/Standards/Precision}
index dc033ca..a7dc00a 100644 (file)
@@ -6,12 +6,12 @@ Version 5 of the Hypertext Markup Language (HTML5) is currently a candidate reco
 
 The Scalable Vector Graphics (SVG) recommendation defines a language for representing vector images using the DOM. This is intended not only for stand alone images, but also for inclusion within HTML documents. 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.
 
-In the SVG representation, general shapes can be specified by locations of enclosed curves using B\'{e}zier splines (Section \ref{}) - the construction of these curves is very similar to PostScript (refer to Figure \ref{}). Again, text is created using vector fonts as described in Section \ref{}.
+In the SVG representation, general shapes can be specified by locations of enclosed curves using B\'{e}zier splines (Section \ref{Bezier Splines}) - the construction of these curves is very similar to PostScript (refer to Figure \ref{spline.pdf}). Again, text is created using vector fonts as described in Section \ref{Fonts}.
 
 Figure \ref{SVG} shows an example of an SVG image as rendered (left) and represented as text. The textual representation is syntactically a subset of XML and is similar to HTML.\footnote{The details of distinctions between these languages are beyond the scope of this report.} Here we have used \verb/<rect>/ elements to position rectangles and \verb/<path>/ elements to define a straight line and a filled region bounded by a cubic bezier spline; note that the points and type of curves are defined as a data attribute.
 
 %\begin{comment}
-\subsubsection{Javascript and the DOM}
+\subsection{Javascript and the DOM}
 
 Using Javascript, an element in the DOM can be selected by its type, class, name, or unique identifier, each of which may be specified as an attribute in the original DOM. Once an element is selected Javascript can be used to modify its attributes, add children below it in the DOM, or remove it from the DOM entirely.
 
@@ -69,7 +69,7 @@ In HTML5, Javascript is not restricted to merely manipulating the DOM to alter t
        \includegraphics[width=1\textwidth]{figures/shape.pdf}
        \end{figure}
 \end{minipage}
-       \caption{Vector image and a possible SVG representation}\label{SVG}
+       \caption{Vector image and a possible SVG representation} \label{SVG}
 \end{figure}
 
 \begin{figure}[H]
index bb11062..8febeb4 100644 (file)
@@ -1,4 +1,4 @@
-Adobe's PostScript Language Reference Manual defines a turing complete language for producing graphics output on an abstract ``output device''\cite{plrm}. A PostScript document is treated as a procedural program; an interpreter executes instructions in the order they are written by the programmer. In particular, the document specifies the locations of enclosed curves using B\'{e}zier splines (Section \ref{}), whilst text is treated as vector fonts described in Section \ref{}.
+Adobe's PostScript Language Reference Manual defines a turing complete language for producing graphics output on an abstract ``output device''\cite{plrm}. A PostScript document is treated as a procedural program; an interpreter executes instructions in the order they are written by the programmer. In particular, the document specifies the locations of enclosed curves using B\'{e}zier splines (Section \ref{Bezier Splines}), whilst text is treated as vector fonts described in Section \ref{Fonts}.
 \begin{comment}
 Each symbol is pushed onto a stack as it is read. Special symbols called ``operators'' can act upon this stack and/or the output device. An internal ``graphics state'' stack can be constructed to store styling information (such as colour, line thickness, the current cursor position). It is possible for the language to define new operators.\end{comment} 
 PostScript was and is still widely used in printing of documents onto paper; many printers execute postscript directly, and newer formats including PDF must still be converted into PostScript by printer drivers\cite{pdfref17, cheng2002portable}.
index 3acacbd..2d2a3b4 100644 (file)
@@ -1,4 +1,4 @@
-In this section we will overview the statements made about the precision with which an object can be stored by various vector graphics and document standards.
+
 
 
 \subsection{PostScript}
index 57724b9..eb4fbe2 100644 (file)
@@ -1,5 +1,27 @@
 \chapter{Conclusion}\label{Conclusion}
 
+\section{Work Achieved}
+
+In this project we have explored and identified the issues limiting precision in vector graphics formats.
+A primitive such as a B\'{e}zier curve can be decomposed into straight lines and rendered on a display to sub-pixel accuracy using IEEE-754 floating point representations, but creating a document using coordinates specified with a floating point representation limits the locations at which detail can be included. 
+
+By implementing a proof of concept SVG viewer, we have shown how the approach to applying coordinate transformations affects the accuracy of rendering. Using arbitrary precision GMP rationals to form the coordinates of SVG path elements, expressing B\'{e}zier bounds relative to the paths, we have demonstrated the ability to reduce rendering error and include detail accross an extremely large scale. Performance tests show that this implementation is comparable to a straight forward implementation for a very large number of B\'{e}zier's in the document.
+
+
+
+\section{Limitations and Future Work}
+
+As seen in Figure \ref{cumulative_error_grid.pdf} the error for an implementation based on GMP rationals and path coordinates still increases very slowly with scaling, as the final transformation requires conversion to IEEE-754 floats. Our tests have typically been limited to ranges of values represented by IEEE-754 double precision floats, due to time constraints. Future work should address this gradual accumulation of error, particularly outside the range of IEEE-754 values.
+
+Another limitation of our implementation is that only straight lines with starting and ending coordinates in the display will be rendered accurately using Bresenham's algorithm. When ``zooming in'' to a point within a path, the size of lines increases beyond that of the display, and a rounding error is present. This may be a minor problem unless the view is scaled to an intersection point of lines, in which case the intersection may move. Future work should explore this issue.
+
+The MPFR arbitrary precision floating point implementation allows for individually altering the precision of a number. As an alternative to GMP rationals, which automatically increase in size as needed, algorithms for dynamically increasing the precision of MPFR floats could be explored.
+
+Gow has been exploring a spatial approach to constructing a document, which allows detail to be scaled indefinitely whilst using only IEEE-754 single precision floating point representations \cite{thesisGow}. This implementation could be compared to ours in more detail. It may be possible to apply the Quad tree approach to perform sub division of the path based coordinate systems to overcome some of the limitations of both approaches.
+
+Arbitrary precision arithmetic is well understood, but from our review of the literature we have found little evidence of it's application to vector graphics. The well known graphics standards mention precision in passing, if at all. Ideally this work would motivate future document standards which can include detail at potentially arbitrary precision.
+
+\begin{comment}
 \begin{itemize}
        \item What we have done?
        \begin{itemize}
@@ -17,4 +39,4 @@
                \item Compare with David's Quadtree
        \end{itemize}
 \end{itemize}
-
+\end{comment}
index 9a431ba..a9f3850 100644 (file)
@@ -1,11 +1,19 @@
 \chapter{Introduction}\label{Introduction}
 
-Early electronic document formats such as PostScript were motivated by a need to print documents onto a paper medium. In the PostScript standard, this lead to a model of the document as a program; a series of instructions to be executed by an interpreter which would result in ``ink'' being placed on ``pages'' of a fixed size\cite{plrm}. The ubiquitous Portable Document Format (PDF) standard provides many enhancements to PostScript taking into account desktop publishing requirements\cite{cheng2002portable}, but it is still fundamentally based on the same imaging model\cite{pdfref17}. This idea of a document as a static ``page'' has lead to limitations on what could be achieved with a digital document viewers \cite{hayes2012pixels}.
+Early electronic document formats such as PostScript were motivated by a need to print documents onto a paper medium. In the PostScript standard, this lead to a model of the document as a program; a series of instructions to be executed by an interpreter which would result in ``ink'' being placed on ``pages'' of a fixed size\cite{plrm}. 
 
-The emergence of the internet, web browsers, XML/HTML, JavaScript and related technologies has seen a revolution in the ways in which information can be presented digitally, and the PDF standard itself has begun to move beyond static text and figures\cite{hayes2012pixels, barnes2013embedding}. However, the popular document formats are still designed with the intention of showing information at either a single, fixed level of detail, or a small range of levels.
+The ubiquitous Portable Document Format (PDF) standard provides many enhancements to PostScript taking into account desktop publishing requirements \cite{cheng2002portable}, but it is still fundamentally based on the same imaging model \cite{pdfref17}. This idea of a document as a static ``page'' has lead to limitations on what could be achieved with a digital document viewers \cite{hayes2012pixels}.
 
-As most digital display devices are smaller than physical paper medium, all useful viewers are able to ``zoom'' to a subset of the document. Vector graphics formats including PostScript, PDF and SVG support rasterisation at different zoom levels\cite{plrm, pdfref17, svg2011-1.1}, but the use of fixed precision floating point numbers causes problems due to imprecision either far from the origin, or at a high level of detail\cite{goldberg1991whatevery, goldberg1992thedesign}.
+The emergence of the internet, web browsers, XML/HTML, JavaScript and related technologies has seen a revolution in the ways in which information can be presented digitally, and the PDF standard itself has begun to move beyond static text and figures \cite{hayes2012pixels, barnes2013embedding}. However, the popular document formats are still designed with the intention of showing information at either a single, fixed level of detail, or a small range of levels.
+
+As most digital display devices are smaller than physical paper medium, all useful viewers are able to ``zoom'' to a subset of the document. Vector graphics formats including PostScript, PDF and SVG support rasterisation at different zoom levels \cite{plrm, pdfref17, svg2011-1.1}, but the use of fixed precision floating point numbers causes problems due to imprecision either far from the origin, or at a high level of detail \cite{goldberg1991whatevery, goldberg1992thedesign}.
 
 There are many possible applications for documents in which precision is unlimited. Several areas of use include: visualisation of extremely large or infinite data sets; visualisation of high precision numerical computations; digital artwork; computer aided design; and maps.
 
-In collaboration with Gow\cite{} we have implemented a proof of concept document viewer compatable with a subset of the SVG standard, which has allowed us to explore the limitations of floating point arithmetic and possible approaches to achieving arbitrary precision document formats. Using the Rational representation of the GNU Multiple Precision (GMP) library\cite{granlund2004GMP} we are able to implement correct rendering of SVG test images seperated by arbitrary distances. We present measurements of rendering accuracy and performance for our implementation. An alternative implementation based on a spatial approach to constructing the document is discussed by Gow\cite{}.
+The goal of this work is to explore to explore the limitations of floating point arithmetic and possible approaches to achieving arbitrary precision document formats. In collaboration with Gow \cite{thesisGow} we have implemented a proof of concept document viewer compatable with a subset of the SVG standard as a starting point for our research.
+
+With the aim of being able to correctly insert and render ``detail'' (constructed by importing test SVG images) seperated by arbitrary distance, this work explores the limitations in floating point arithmetic and how these may be mitigated
+
+Using the Rational representation of the GNU Multiple Precision (GMP) library \cite{granlund2004GMP} we are able to implement correct rendering of SVG test images seperated by extremely large distances. We will present measurements of rendering accuracy and performance for our implementation. 
+
+An alternative implementation based on a spatial approach to constructing the document is discussed by Gow \cite{thesisGow}.
index 1b24726..db56861 100644 (file)
@@ -1,40 +1,75 @@
-\chapter{Methods and Design}\label{Process}
+\chapter{Implementation of an SVG Viewer}\label{Process}
 
+To better understand the calculations required to represent and render a vector document, whilst allowing maximum flexibility in approaches to arbitrary precision, a custom vector graphics viewer called IPDF\footnote{The original name ``Infinite Precision Document Format'' stuck, although the use of the word ``infinite'' is highly misleading} was implemented for this project in collaboration with Gow \cite{thesisGow}. This chapter gives a brief overview of the features and limitations of this software.
 
-\section{Structure of Software}
+\section{Software Overview}
 
-A custom vector graphics viewer called IPDF\footnote{The original name ``Infinite Precision Document Format'' stuck, although the use of the word ``infinite'' is highly misleading} was implemented for this project in collaboration with David Gow\cite{}. We will give a brief overview of the features and limitations of this software.
+The IPDF software has been written using the C++ programming language for x86-64 Debian GNU/Linux machines. The use of C++ offers low level control over CPU and (through the OpenGL API) GPU memory whilst allowing an Object Orientated approach. The choice of C++ was agreed on with Gow \cite{thesisGow}.
 
-\subsection{Document Structure}
+IPDF has been tested on a set of SVG images\footnote{These can be found at \url{http://szmoore.net/ipdf/code/src/svg-tests}} prepared by the author. Figure \ref{fox-rendering} shows the rendering of the same vector image used in Figure \ref{vector-vs-raster-scaled} in the IPDF software.
 
-IPDF is built around Objects which can be rendered either on the CPU (directly altering a bitmap and then uploading to the GPU) or the GPU (via the use of OpenGL GLSL shader programs).
 
-Initially only very simple shapes (Rectangles and Circles) were supported, but in order to produce a meaningful demonstration of arbitrary precision viewing, Paths formed from Quadratic or Cubic B\'{e}ziers as specified by the SVG standard were added. Shading of paths is partially implemented.
+ The software is capable of importing SVG images scaled to the current view location, and stores a DOM like representation of the document (for discussion of the Document Object Model (DOM) compared to the PostScript style Interpreted Model, refer to Appendix \ref{An Overview of Document Standards}).
+ \begin{figure}[H]
+       \centering
+       \includegraphics[width=0.45\textwidth]{figures/fox-vector_face_with_bezbounds.png}
+       \includegraphics[width=0.45\textwidth]{figures/shady-the-fox.png}
+       \caption{Rendering of Figure \ref{vector-vs-raster-scaled} in the IPDF software \\ a) Outline with individual B\'{e}ziers highlighted in rectangles b) With shading enabled} \label{fox-rendering}
+\end{figure}
 
-\subsection{Rendering Process}
+\section{Document Structure}
 
-As discussed in Section \ref{FloatingPointOnTheGPU
-} it is not clear to what extend GPUs comply with the IEEE-754 standard, and arbitrary precision arithmetic is most easily implemented on the CPU; for this reason a CPU renderer and GPU renderer were implemented.
+IPDF is built around Objects which are internally represented by bounding rectangles, a type, and any additional coordinates and other data required for rendering the object.
 
-All Objects are represented by their bounding rectangles; in the case of B\'{e}zier curves the control points are stored relative to the bounding rectangle. The rendering process involves converting the bounding rectangle coordinates from Document to Screen space as discussed in Section \ref{}. For both GPU and CPU rendering a B\'{e}zier in screen space is decomposed into straight lines; the CPU renders these lines using Bresenham's algorithm.
+Initially only very simple shapes (Rectangles and Circles) were supported, but in order to produce a meaningful demonstration of arbitrary precision viewing, Paths formed from Quadratic or Cubic B\'{e}ziers as specified by the SVG standard were added. Shading of paths is partially implemented but detailed discussion is beyond the scope of this report.
 
+\section{CPU and GPU Renderering}
 
+As discussed in Section \ref{FloatingPointOnTheGPU} it is not clear to what extend GPUs comply with the IEEE-754 standard. In addition, arbitrary precision arithmetic is most easily implemented on the CPU and well supported through libraries such as GMP. For these reasons both a CPU and GPU renderer were implemented.
 
-\subsection{Interactivity}
+To render an object on the GPU its bounding rectangle and additional data are provided to a series of OpenGL shader programs. In the case of B\'{e}zier curves, a Geometry shader performs the subdivision on the GPU and the resultant points are drawn with lines.
 
-There are two ways to control the IPDF software; manually through use of keyboard and mouse and a Qt4\cite{} based control panel, or automatically through a script containing a sequence of commands to transform the view or insert SVGs. In both cases SVGs can be inserted scaled to the current View rectangle. 
+The CPU renderer behaves similarly, with the exception that a custom ``Renderer'' class performs the function of all three shader programs. A bitmap is directly modified by the CPU and then uploaded to the GPU as a texture for displaying.
 
-\subsection{Version Control}
+Figure \ref{gpufloats.pdf} shows a comparison between the renderering of a circle performed by an x86-64 (CPU) and several GPUs in the IPDF software.
+
+\section{Coordinate Systems and Transformations} \label{Coordinate Systems and Transformations}
+\input{chapters/Background/CoordinateSystems}
+
+
+\section{Interactivity and Obtaining Results}
+
+There are two basic ways to control the IPDF software; manually through use of keyboard and mouse and a Qt4 \cite{Qt4} based control panel, or automatically by reading a script containing a sequence of commands to transform the view or insert test SVGs. More complex control can be obtained by using the Python \texttt{subprocess} module to produce the commands and analyse performance results.
+
+All results presented in Chapter \ref{Results and Discussion} were obtained on a conventional Debian GNU/Linux laptop with an AMD/ATI Radeon series GPU. An attempt was made to cross compile the software for the Windows operating system, but at the time of publication there were difficulties with the Windows 7 OpenGL drivers on the author's system.
+
+\begin{figure}[H]
+       \centering
+       \includegraphics[width=0.3\textwidth]{figures/controlpanel_screenshot.png}
+       \caption{The Qt4 Control Panel provides basic interactivity} \label{controlpanel_screenshot.png}
+\end{figure}
+
+
+\section{Version Control}
+
+The Git version control system was used to collaborate and back up work on this project; the main repository may be viewed at \url{http://git.ucc.asn.au/?p=ipdf/code.git} or on Github at \url{http://github.com/szmoore/ipdf-code}.
+
+\begin{figure}[H]
+       \centering
+       \includegraphics[width=\textwidth]{figures/github.png}
+       \caption{Commit statistics from the repository at Github (this author is ``szmoore'')} \label{github.png}
+\end{figure}
 
-The Git version control system was used to collaborate on this project; the main repository may be viewed at \url{http://git.ucc.asn.au/?p=ipdf/code.git}
 
 \section{Approaches to Arbitrary Precision}
 
-\subsection{Na\"{i}ve Approach}
+\subsection{Na\"{i}ve Approach} \label{Naive Approach}
 
 A na\"{i}ve approach would be to replace all floating point operations with arbitrary precision operations, and this was in fact tried in early experiments. This approach requires use of the CPU renderer, as GLSL is restricted to floating point representations. A type definition \texttt{Real} on the CPU can be selected at compile time.
 
-Unfortunately truly arbitrary precision number representations were found to be far too inefficient for practical purposes --- for example, rendering a frame with GMP Rationals could take up to 60 seconds at the default view.
+Unfortunately truly arbitrary precision number representations (including custom implementations of Rationals, and the GMP library's rationals) were found to be far too inefficient for practical purposes, and indeed unnecessary. The results shown in Chapter \ref{Results and Discussion} were produced using the GPU renderer, since this na\"{i}ve approach was discarded.
 
 
 \begin{comment}
@@ -54,32 +89,30 @@ Unfortunately truly arbitrary precision number representations were found to be
 \subsection{Intermediate Coordinate Systems}
 
 When an object is visible on the screen it is only necessary to render it accurately to within the nearest pixel.
-As shown in the Results Section \ref{}, introducing an intermediate coordinate system for a large number of objects and applying transformations to this coordinate system instead of individual objects produces the best results both in terms of reduced rounding errors using floating point arithmetic, and reduced number of required arbitrary precision operations.
+As shown in Chapter \ref{Results and Discussion}, introducing an intermediate coordinate system for a large number of objects and applying transformations to this coordinate system instead of individual objects produces the best results both in terms of reduced rounding errors using floating point arithmetic, and reduced number of required arbitrary precision operations.
 
 \subsection{Quadtree Document Division}
 
-An approach identified by Gow\cite{} is to construct intermediate coordinate systems as the user manipulates the view. 
-
+An approach identified by Gow\cite{thesisGow} is to construct intermediate coordinate systems as the user manipulates the view in a spatial structure called a ``Quadtree''. This involves dividing the initial view into four quadrants when the document is scaled by a required amount, and only rendering those quadrant(s) that are visible. The process repeats with additional scaling. With each division objects must be added to the appropriate quadrant, or in the case of objects which span a boundary, clipped. The advantages and disadvantages of this implementation will be explored by Gow\cite{thesisGow}.
 
 
 \section{Libraries Used}
-
-The libraries used to compile the IPDF software are:
 \begin{itemize}
        \item SDL2 - Simple Direct media Library
-       \begin{itemize}
-               \item Used for window management and to obtain an OpenGL context
-               \item Provides Bitmap handling functions
-       \end{itemize}
+       
+       SDL2 is a cross-platform library commonly used in games for window management and to obtain an OpenGL context.
+       We have also made some use of the SDL2 bitmap handling functions to save screenshots.
+               
        \item Qt4 (optional) --- Open source toolkit for Dialog based applications
+       
+       The control panel shown in Figure \ref{controlpanel_screenshot.png} was created using Qt4. Use of Qt4 can cause difficulties in compiling the software, so it can be disabled at compile time.
        \item OpenGL (4.4) --- The standard API for controlling GPUs
        \item PugiXML --- Open source XML parsing library used to implement parsing of SVGs
        \item GNU Multiple Precision (GMP)
-       \begin{itemize}
-               \item Implements arbitrary precision integers, floats, and rationals
-               \item Highly optimised using CPU specific assembly instructions
-       \end{itemize}
-       \item MPFR --- built on GMP but ensures IEEE-754 consistent rounding behaviour
-\end{itemize}
+       
+       As discussed in Sections \ref{Big Integers}, \ref{Arbitrary Precision Floating Point Numbers}, \ref{Rational Number Representations} GMP implements arbitrary precision integers, floats, and rationals. Although we did explore these representations by producing custom implementations, examining the GMP source code reveals that it is highly optimised using CPU specific assembly instructions, and vastly outperformed straight forward C++ implementations of Big Integers and Rationals.
 
+       \item MPFR --- Arbitrary precision floats built on GMP but ensures IEEE-754 consistent rounding behaviour.
+       The IPDF software may be compiled with MPFR floats in place of IEEE-754 floats. The precision (size of mantissa) must be set to an arbitrary large but fixed size at compile time.
+\end{itemize}
 
index 1d9df1a..47b46fa 100644 (file)
@@ -5,10 +5,19 @@
 Our ultimate goal is to be able to insert detail at an arbitrary point in the document. Therefore, we are interested in how the same test SVG would appear when scaled to the view coordinates, as the view coordinates are varied. 
 
 
+Throughout this section we will use IEEE-754 single precision (binary32) floats unless otherwise stated. Although double precision (binary64) would allow for greater precision, one could still choose coordinates for which similar results can be obtained.
+
+
 \subsection{Applying the view transformation directly}\label{direct_transform}
 
-Figure \ref{qualitative-rendering-fox} shows the rendering of a vector image\footnote{Unfortunately, since a rendered vector image is a raster image and this figure must be scaled to fit the PDF, the figure as seen here is not a pixel perfect representation of the actual rendering. Most notably, antialiasing effects will be apparent}. Transformation \eqref{view-transformation} is applied to object coordinates with default IEEE-754 rounding behaviour (to nearest). The loss of precision in the second figure is obvious. This is because division by $10^{-6}$ increases the rounding error in $x - v_x$, by $10^{6}$, so the total error is of the order $10^6$ ulp which is of the order $0.25$
+Figure \ref{qualitative-rendering-fox} shows the rendering of a vector image\footnote{Unfortunately, since a rendered vector image is a raster image and this figure must be scaled to fit the PDF, the figure as seen here is not a pixel perfect representation of the actual rendering. Most notably, antialiasing effects will be apparent}. Transformation \eqref{view-transformation} is applied to the coordinates of B\'{e}zier bounds, with default IEEE-754 rounding behaviour (to nearest). The loss of precision in the second figure is obvious. 
 
+In this case, the precision loss occurs when the test SVG is added to the document; the inverse of \eqref{view-transformation} must be applied. That is (for the $x$ coordinate, with the same equations applying for the $y$ coordinate):
+\begin{align*}
+       X = V_{w} \times \text{SVG}_x + V_{x}
+\end{align*}
+
+Where $V$ represents the view, $X$ is the coordinate in the document, and $\text{SVG}_x$ is the coordinate in the test SVG at original scale. In Figure \ref{qualitative-rendering-fox}, the multiplication $V_{w} \times \text{SVG}_x$ has a smaller exponent than $V_{x}$. The error of the addition operation is comparable to one ulp, ie: $\frac{V_{x}}{2}$. In this case, the rounding error is dominating the calculation. The division by $V_{w} = 10^{6}$ in \eqref{view-transformation} is merely increasing this rounding error.
 
 \begin{figure}[H]
        \centering
@@ -19,7 +28,7 @@ Figure \ref{qualitative-rendering-fox} shows the rendering of a vector image\foo
 
 \subsection{Applying cumulative transformations to all B\'{e}ziers}\label{cumulative_transform}
 
-Rather than applying \eqref{view-transformation} to object coordinates specified relative to the document, we can store the bounds of objects relative to the view and modify these bounds according to transformations \eqref{} and \eqref{} as the view is changed. This is convenient for an interactive document, as detail is typically added by inserting objects into the document within the view rectangle. As a result this approach makes the rendering of detail added to the document independent of the view coordinates --- until the view is moved.
+Rather than applying \eqref{view-transformation} to object coordinates specified relative to the document, we can store the bounds of objects relative to the view and modify these bounds according to the transformations discussed in Section \ref{Coordinate Systems and Transformations} as the view is changed. This is convenient for an interactive document, as detail is typically added by inserting objects into the document within the view rectangle. As a result this approach makes the rendering of detail added to the document independent of the view coordinates --- until the view is moved.
 
 Repeated transformations on the view will cause an accumulated error on the coordinates of object bounds. This is most noticable when zooming \emph{out} and then back into the document; the object coordinates will gradually underflow and eventually round to zero. An example of this effect is shown in Figure \ref{qualitative-rendering-fox-cumulative} b)
 %label start
@@ -47,20 +56,21 @@ We can correct this drift whilst maintaining performance by using an arbitrary o
        \centering
        \includegraphics[width=800px]{figures/fox-vector_cumulative_relative_to_path.png}
        \includegraphics[width=800px]{figures/fox-vector_cumulative_relative_to_path_GMPrat.png}
-       \caption{Effect of cumulative transformations applied to Paths\\a) Path bounds represented using floats b) Path bounds represented using Rationals}\label{qualitative-rendering-fox-cumulative-relative}
+       \caption{Effect of cumulative transformations applied to Paths\\a) Path bounds represented using floats b) Path bounds represented using GMP Rationals}\label{qualitative-rendering-fox-cumulative-relative}
 \end{figure}
 
-Videos showing the effects discussed in Section \ref{direct_transform}, \ref{cumulative_transform} and \ref{path_transform} can be found at:
 
- \url{http://szmoore.net/ipdf/sam/presentation}.
        
 \section{Quantitative Measurements of Rendering Accuracy}
+
+To quantitatively measure rendering accuracy, we can record the coordinates of objects in \emph{display space} and measure how these drift as the same collection of objects is added to the document at different view locations. Alternately, since rounding errors causes different coordinates to round to the same value in display space, we may count the number of distinct object bounds in display space.
        
 A useful test SVG is a simple grid of horizontal and vertical lines seperated by 1 pixel. When this SVG is correctly scaled to a view, all that should be visible is a coloured rectangle filling the screen. Increasing the magnification will reveal the grid of lines indicating how the original size of a pixel is scaled.
 
-Figure \ref{grid-precision} illustrates the effect of applying the view transformation \eqref{view-transformation} directly to the grid. When the grid is correctly rendered, as in Figure \ref{grid-precision} a) it appears as a black rectangle. Further from the origin, not all pixels in the grid can be represented and individual lines become visible. As the distance from the origin increases, fewer pixel locations can be represented exactly after performing the view transformation.
+Figure \ref{grid-precision} illustrates the effect of applying the view transformation \eqref{view-transformation} directly to the grid, as discussed above in Section \ref{direct_transform}. When the grid is correctly rendered, as in Figure \ref{grid-precision} a) it appears as a black rectangle. Further from the origin , not all pixels in the grid can be represented and individual lines become visible. As the distance from the origin increases, fewer pixel locations can be represented exactly after performing the view transformation.
+
+We should note that with the view top left corner close to $(0,0)$ as in Figure \ref{grid-precision} a), detail can be represented more precisely due to the use of IEEE-754 denormals near the origin (see Section \ref{Floating Point Number Representations}).
 
-An error of 1 ulp is increased by a factor of $10^6$ to end up comparable to the size of the display ($0 \to 1$).
 
 
 \begin{figure}[H]
@@ -73,14 +83,12 @@ An error of 1 ulp is increased by a factor of $10^6$ to end up comparable to the
        a) Near origin (denormals) b), c), d) Increasing the exponent of $(v_x,v_y)$ by 1}\label{grid-precision}
 \end{figure}
 
+\subsection{Precision for Fixed View} \label{Precision for Fixed View}
 
-\subsection{Precision for Fixed View}
-
-
-By counting the number of distinctly representable lines within a particular view, we can show the degradation of precision quantitatively. The test grid is added to each view rectangle.
+By counting the number of distinctly representable lines within a particular view, we can show the degradation of precision quantitatively. The test grid is added to each view rectangle with increasingly smaller width and height.
 
 
-Figure \ref{loss_of_precision_grid_0.5.pdf} shows how precision degrades with $(V_x, V_y) = (0.5,0.5)$ for different precision settings using MPFR floating point values to represent the view coordinates. A constant line at $1401$ grid locations indicates no loss of precision. From this figure it is clear that 
+Figure \ref{loss_of_precision_grid_0.5.pdf} shows how precision degrades with $(V_x, V_y) = (0.5,0.5)$ for different precision settings using MPFR floating point values to represent the view coordinates. A constant line at $1401$ grid locations indicates no loss of precision. From this figure it should be clear how merely setting the precision of the floating point representation to a higher (but fixed) value will not allow insertion of detail at an arbitrary point; using 1024 bits of precision will still leave no lines representable above magnifications of $10^{300}$.
 
 
 \begin{figure}[H]
@@ -92,33 +100,60 @@ Figure \ref{loss_of_precision_grid_0.5.pdf} shows how precision degrades with $(
 
 \subsection{Accumulated error after changing the View}
 
-Figure \ref{cumulative_error_grid.pdf} shows the total error in the coordinates of each line in the grid after the view is scaled (zooming \emph{out}) by repeated transformations. A constant line at $0$ indicates no accumulated error.
+Using the cumulative transformation approach discussed in Section \ref{cumulative_transform} means that detail inserted into a fixed view will always render correctly. A fairer test of this approach is to test the rendering accuracy after applying repeated scaling to the document.
+
+Figure \ref{cumulative_error_grid.pdf} shows the total error in the coordinates of each line in the grid after the view is scaled (zooming \emph{out}) by repeated transformations. A constant line at $0$ would indicate no accumulated error.
+
+In this case, using an arbitrary precision representation such as GMP Rationals (\texttt{path-rat}) does not totally eliminate error. This is simply because the final coordinate transformation requires the conversion of rationals to IEEE-754 floats before rendering. Since the total final error for $1042$ lines is less than $10^{-2}$, and the width of the display is $1$, this would represent a negligable difference in the rendering of the grid.
+
+
 
 \begin{figure}[H]
        \centering
                \includegraphics[width=0.8\textwidth]{figures/cumulative_error_grid.pdf}
-       \caption{Error in the coordinates of the grid}
+       \caption{Error in the coordinates of the grid {\bf Note:} Logarithmic Axes}
        \label{cumulative_error_grid.pdf}
 \end{figure}
 
-By considering Figure \ref{loss_of_precision_grid_0.5.pdf} and \ref{cumulative_error_grid.pdf}, \verb/path-rat/ is the winner.
-       
 \section{Performance Measurements}
        
-As discussed above, we succeeded in preserving rendering accuracy as defined above for an arbitrary view.
-However this comes at a performance cost, as the size of the Rational number representation must grow accordingly. Figures \ref{memory.pdf} and \ref{time.pdf} were obtained by repeatedly clearing the document, scaling, and adding a fixed number of B\'{e}zier curves. The \texttt{mpfr-1024} number representation performs much better in terms of memory usage and performance; however as discussed in Section \ref{}, due to the fixed precision it cannot represent detail seperated by a truly arbitrary distance.
+\subsection{Performance of Static Detail at Different View Locations}
+As discussed above, we succeeded in preserving rendering accuracy as defined above for extremely large ranges of coordinates in the document. 
+
+However this comes at a performance cost, as the size of the Rational number representation must grow accordingly. Figures \ref{memory.pdf} a) and b) were obtained by repeatedly resetting the document, scaling, and adding a fixed number of B\'{e}zier curves. It appears that the GMP representation increases memory usage linearly, with the speed decreasing faster than linear. The \texttt{mpfr-1024} number representation performs much better in terms of a static memory usage and speed; however as discussed in Section \ref{Precision for Fixed View}, due to the fixed precision it cannot represent detail seperated by a truly arbitrary distance. 
+
+
+\begin{figure}[H]
+       \centering
+       \includegraphics[width=0.45\textwidth]{figures/memory.pdf}
+       \includegraphics[width=0.45\textwidth]{figures/time.pdf}
+       \caption{a) Memory used per Path coordinate and b) Time taken to scale} \label{memory.pdf}
+\end{figure}
+
+\subsection{Performance whilst adding Detail} \label{Performance whilst adding Detail}
+
+For a static document containing only a few imported test SVGs, the use of GMP rationals for path coordinates was not a noticable performance detriment compared to the implementations using floating point coordinates. Figure \ref{adding_things} measures the time taken for a script to scale the document to a point at which it will insert an additional copy of a test SVG (Figure \ref{turtle.pdf}).
+
+We have included the Na\"{i}ve approach discussed in Section \ref{Naive Approach} with GMP rationals (\texttt{Gmprat}) and MPFR using 1024 bits of precision (\texttt{mpfr-1024}) to illustrate its impracticality. The \texttt{Gmprat} is removed from Figure \ref{adding_things} b).
 
 \begin{figure}[H]
        \centering
-       \includegraphics[width=0.7\textwidth]{figures/memory.pdf}
-       \label{memory.pdf}
-       \caption{Memory used per Path coordinate whilst zooming in}
+       \includegraphics[width=0.49\textwidth]{figures/naive_gmprat_is_slow.pdf}
+       \includegraphics[width=0.49\textwidth]{figures/naive_mpfr_is_also_slow.pdf}
+
+       \caption{a) Performance including Na\"{i}ve Implementations b) Excluding \texttt{Gmprat} data \\ Legend is in descending order to correspond with the height of the curves}     \label{adding_things}
 \end{figure}
 
+From these results it is clear that our implementation using arbitrary precision arithmetic only for path coordinates is comparable to the straight forward floating point implementation. It is interesting to note that despite Figure \ref{memory.pdf}, GMP rationals are slightly faster than MPFR with 1024 bits for this test. This is possibly because the GMP rationals only grow in size as needed, whilst MPFR operations always use the full 1024 bits per number.
+
+\section{Video Demonstrations}
+
+Realtime videos of the IPDF software showing the results presented in this chapter can be found at 
+\url{http://szmoore.net/ipdf/sam/videos}. The performance tests in Section \ref{Performance whilst adding Detail} were taken using the same script running in these videos. 
+
 \begin{figure}[H]
        \centering
-       \includegraphics[width=0.7\textwidth]{figures/time.pdf}
-       \label{time.pdf}
-       \caption{Time taken to scale about the fixed point}
+       \includegraphics[width=0.4\textwidth]{figures/turtle.pdf}
+       \caption{The test SVG used to produce the videos} \label{turtle.pdf}
 \end{figure}
 
diff --git a/figures/github.png b/figures/github.png
new file mode 100644 (file)
index 0000000..307995e
Binary files /dev/null and b/figures/github.png differ
diff --git a/figures/memory.svg b/figures/memory.svg
new file mode 100644 (file)
index 0000000..1602efd
--- /dev/null
@@ -0,0 +1,677 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<svg
+   xmlns:dc="http://purl.org/dc/elements/1.1/"
+   xmlns:cc="http://creativecommons.org/ns#"
+   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+   xmlns:svg="http://www.w3.org/2000/svg"
+   xmlns="http://www.w3.org/2000/svg"
+   xmlns:xlink="http://www.w3.org/1999/xlink"
+   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+   width="600"
+   height="480"
+   viewBox="0 0 600 480"
+   id="svg5205"
+   version="1.1"
+   inkscape:version="0.48.5 r10040"
+   sodipodi:docname="memory.pdf">
+  <metadata
+     id="metadata5512">
+    <rdf:RDF>
+      <cc:Work
+         rdf:about="">
+        <dc:format>image/svg+xml</dc:format>
+        <dc:type
+           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+        <dc:title>Gnuplot</dc:title>
+      </cc:Work>
+    </rdf:RDF>
+  </metadata>
+  <defs
+     id="defs5510" />
+  <sodipodi:namedview
+     pagecolor="#ffffff"
+     bordercolor="#666666"
+     borderopacity="1"
+     objecttolerance="10"
+     gridtolerance="10"
+     guidetolerance="10"
+     inkscape:pageopacity="0"
+     inkscape:pageshadow="2"
+     inkscape:window-width="640"
+     inkscape:window-height="480"
+     id="namedview5508"
+     showgrid="false"
+     inkscape:zoom="0.49166667"
+     inkscape:cx="300"
+     inkscape:cy="240"
+     inkscape:window-x="0"
+     inkscape:window-y="0"
+     inkscape:window-maximized="0"
+     inkscape:current-layer="svg5205" />
+  <title
+     id="title5207">Gnuplot</title>
+  <desc
+     id="desc5209">Produced by GNUPLOT 4.6 patchlevel 5 </desc>
+  <g
+     id="gnuplot_canvas">
+    <rect
+       x="0"
+       y="0"
+       width="600"
+       height="480"
+       fill="none"
+       id="rect5212" />
+    <defs
+       id="defs5214">
+      <circle
+         id="gpDot"
+         r="0.5"
+         stroke-width="0.5" />
+      <path
+         id="gpPt0"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M-1,0 h2 M0,-1 v2" />
+      <path
+         id="gpPt1"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M-1,-1 L1,1 M1,-1 L-1,1" />
+      <path
+         id="gpPt2"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M-1,0 L1,0 M0,-1 L0,1 M-1,-1 L1,1 M-1,1 L1,-1" />
+      <rect
+         id="gpPt3"
+         stroke-width="0.222"
+         stroke="currentColor"
+         x="-1"
+         y="-1"
+         width="2"
+         height="2" />
+      <rect
+         id="gpPt4"
+         stroke-width="0.222"
+         stroke="currentColor"
+         fill="currentColor"
+         x="-1"
+         y="-1"
+         width="2"
+         height="2" />
+      <circle
+         id="gpPt5"
+         stroke-width="0.222"
+         stroke="currentColor"
+         cx="0"
+         cy="0"
+         r="1" />
+      <use
+         xlink:href="#gpPt5"
+         id="gpPt6"
+         fill="currentColor"
+         stroke="none" />
+      <path
+         id="gpPt7"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M0,-1.33 L-1.33,0.67 L1.33,0.67 z" />
+      <use
+         xlink:href="#gpPt7"
+         id="gpPt8"
+         fill="currentColor"
+         stroke="none" />
+      <use
+         xlink:href="#gpPt7"
+         id="gpPt9"
+         stroke="currentColor"
+         transform="rotate(180)" />
+      <use
+         xlink:href="#gpPt9"
+         id="gpPt10"
+         fill="currentColor"
+         stroke="none" />
+      <use
+         xlink:href="#gpPt3"
+         id="gpPt11"
+         stroke="currentColor"
+         transform="rotate(45)" />
+      <use
+         xlink:href="#gpPt11"
+         id="gpPt12"
+         fill="currentColor"
+         stroke="none" />
+    </defs>
+    <g
+       style="fill:none; color:white; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+       id="g5230" />
+    <g
+       style="fill:none; color:black; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+       id="g5232">
+      <path
+         stroke="black"
+         d="M96.8,410.7 L105.8,410.7 M575.0,410.7 L566.0,410.7  "
+         id="path5234" />
+      <g
+         transform="translate(88.5,415.2)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5236">
+        <text
+           id="text5238"> 0</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,351.4 L105.8,351.4 M575.0,351.4 L566.0,351.4  "
+         id="path5240" />
+      <g
+         transform="translate(88.5,355.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5242">
+        <text
+           id="text5244"> 100000</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,292.1 L105.8,292.1 M575.0,292.1 L566.0,292.1  "
+         id="path5246" />
+      <g
+         transform="translate(88.5,296.6)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5248">
+        <text
+           id="text5250"> 200000</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,232.7 L105.8,232.7 M575.0,232.7 L566.0,232.7  "
+         id="path5252" />
+      <g
+         transform="translate(88.5,237.2)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5254">
+        <text
+           id="text5256"> 300000</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,173.4 L105.8,173.4 M575.0,173.4 L566.0,173.4  "
+         id="path5258" />
+      <g
+         transform="translate(88.5,177.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5260">
+        <text
+           id="text5262"> 400000</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,114.1 L105.8,114.1 M575.0,114.1 L566.0,114.1  "
+         id="path5264" />
+      <g
+         transform="translate(88.5,118.6)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5266">
+        <text
+           id="text5268"> 500000</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,54.8 L105.8,54.8 M575.0,54.8 L566.0,54.8  "
+         id="path5270" />
+      <g
+         transform="translate(88.5,59.3)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g5272">
+        <text
+           id="text5274"> 600000</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,422.4 L96.8,413.4 M96.8,54.1 L96.8,63.1  "
+         id="path5276" />
+      <g
+         transform="translate(96.8,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5278">
+        <text
+           id="text5280"> 0</text>
+      </g>
+      <path
+         stroke="black"
+         d="M156.6,422.4 L156.6,413.4 M156.6,54.1 L156.6,63.1  "
+         id="path5282" />
+      <g
+         transform="translate(156.6,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5284">
+        <text
+           id="text5286"> 50</text>
+      </g>
+      <path
+         stroke="black"
+         d="M216.4,422.4 L216.4,413.4 M216.4,54.1 L216.4,63.1  "
+         id="path5288" />
+      <g
+         transform="translate(216.4,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5290">
+        <text
+           id="text5292"> 100</text>
+      </g>
+      <path
+         stroke="black"
+         d="M276.1,422.4 L276.1,413.4 M276.1,54.1 L276.1,63.1  "
+         id="path5294" />
+      <g
+         transform="translate(276.1,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5296">
+        <text
+           id="text5298"> 150</text>
+      </g>
+      <path
+         stroke="black"
+         d="M335.9,422.4 L335.9,413.4 M335.9,54.1 L335.9,63.1  "
+         id="path5300" />
+      <g
+         transform="translate(335.9,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5302">
+        <text
+           id="text5304"> 200</text>
+      </g>
+      <path
+         stroke="black"
+         d="M395.7,422.4 L395.7,413.4 M395.7,54.1 L395.7,63.1  "
+         id="path5306" />
+      <g
+         transform="translate(395.7,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5308">
+        <text
+           id="text5310"> 250</text>
+      </g>
+      <path
+         stroke="black"
+         d="M455.5,422.4 L455.5,413.4 M455.5,54.1 L455.5,63.1  "
+         id="path5312" />
+      <g
+         transform="translate(455.5,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5314">
+        <text
+           id="text5316"> 300</text>
+      </g>
+      <path
+         stroke="black"
+         d="M515.2,422.4 L515.2,413.4 M515.2,54.1 L515.2,63.1  "
+         id="path5318" />
+      <g
+         transform="translate(515.2,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5320">
+        <text
+           id="text5322"> 350</text>
+      </g>
+      <path
+         stroke="black"
+         d="M575.0,422.4 L575.0,413.4 M575.0,54.1 L575.0,63.1  "
+         id="path5324" />
+      <g
+         transform="translate(575.0,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5326">
+        <text
+           id="text5328"> 400</text>
+      </g>
+      <path
+         stroke="black"
+         d="M96.8,54.1 L96.8,422.4 L575.0,422.4 L575.0,54.1 L96.8,54.1 Z  "
+         id="path5330" />
+      <g
+         transform="translate(17.6,238.3) rotate(270)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5332">
+        <text
+           id="text5334">Size (Bytes)</text>
+      </g>
+      <g
+         transform="translate(335.9,471.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5336">
+        <text
+           id="text5338">Log10(Magnification)</text>
+      </g>
+      <g
+         transform="translate(335.9,31.6)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g5340">
+        <text
+           id="text5342">Memory per Path coordinate</text>
+      </g>
+    </g>
+    <g
+       id="gnuplot_plot_1">
+      <title
+         id="title5345">gnuplot_plot_1</title>
+      <g
+         style="fill:none; color:red; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+         id="g5347">
+        <g
+           transform="translate(507.9,76.6)"
+           style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+           id="g5349">
+          <text
+             id="text5351">Gmprat</text>
+        </g>
+        <path
+           d="M516.2,72.1 L558.4,72.1 M96.8,410.7 L109.8,399.2 L122.8,387.6 L135.7,376.0 L148.7,364.5 L161.7,352.9    L174.7,341.3 L187.7,329.8 L200.6,318.2 L213.6,306.6 L226.6,295.1 L239.6,283.5 L252.6,271.9 L265.5,260.4    L278.5,248.8 L291.5,237.2 L304.5,225.7 L317.5,214.1 L330.4,202.5 L343.4,191.0 L356.4,179.4 L369.4,167.8    L382.4,156.3 L395.3,144.7 L408.3,133.1 L421.3,121.6 L434.3,110.0 L447.3,98.4 L460.2,86.9 L473.2,75.3     "
+           id="path5353" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(96.8,410.7) scale(4.50)"
+           id="use5355" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(109.8,399.2) scale(4.50)"
+           id="use5357" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(122.8,387.6) scale(4.50)"
+           id="use5359" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(135.7,376.0) scale(4.50)"
+           id="use5361" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(148.7,364.5) scale(4.50)"
+           id="use5363" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(161.7,352.9) scale(4.50)"
+           id="use5365" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(174.7,341.3) scale(4.50)"
+           id="use5367" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(187.7,329.8) scale(4.50)"
+           id="use5369" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(200.6,318.2) scale(4.50)"
+           id="use5371" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(213.6,306.6) scale(4.50)"
+           id="use5373" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(226.6,295.1) scale(4.50)"
+           id="use5375" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(239.6,283.5) scale(4.50)"
+           id="use5377" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(252.6,271.9) scale(4.50)"
+           id="use5379" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(265.5,260.4) scale(4.50)"
+           id="use5381" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(278.5,248.8) scale(4.50)"
+           id="use5383" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(291.5,237.2) scale(4.50)"
+           id="use5385" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(304.5,225.7) scale(4.50)"
+           id="use5387" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(317.5,214.1) scale(4.50)"
+           id="use5389" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(330.4,202.5) scale(4.50)"
+           id="use5391" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(343.4,191.0) scale(4.50)"
+           id="use5393" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(356.4,179.4) scale(4.50)"
+           id="use5395" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(369.4,167.8) scale(4.50)"
+           id="use5397" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(382.4,156.3) scale(4.50)"
+           id="use5399" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(395.3,144.7) scale(4.50)"
+           id="use5401" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(408.3,133.1) scale(4.50)"
+           id="use5403" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(421.3,121.6) scale(4.50)"
+           id="use5405" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(434.3,110.0) scale(4.50)"
+           id="use5407" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(447.3,98.4) scale(4.50)"
+           id="use5409" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(460.2,86.9) scale(4.50)"
+           id="use5411" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(473.2,75.3) scale(4.50)"
+           id="use5413" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(537.3,72.1) scale(4.50)"
+           id="use5415" />
+      </g>
+    </g>
+    <g
+       id="gnuplot_plot_2">
+      <title
+         id="title5418">gnuplot_plot_2</title>
+      <g
+         style="fill:none; color:green; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+         id="g5420">
+        <g
+           transform="translate(507.9,94.6)"
+           style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+           id="g5422">
+          <text
+             id="text5424">mpfr-1024</text>
+        </g>
+        <path
+           d="M516.2,90.1 L558.4,90.1 M96.8,410.1 L109.8,410.1 L122.8,410.1 L135.7,410.1 L148.7,410.1 L161.7,410.1    L174.7,410.1 L187.7,410.1 L200.6,410.1 L213.6,410.1 L226.6,410.1 L239.6,410.1 L252.6,410.1 L265.5,410.1    L278.5,410.1 L291.5,410.1 L304.5,410.1 L317.5,410.1 L330.4,410.1 L343.4,410.1 L356.4,410.1 L369.4,410.1    L382.4,410.1 L395.3,410.1 L408.3,410.1 L421.3,410.1 L434.3,410.1 L447.3,410.1 L460.2,410.1 L473.2,410.1    L486.2,410.1 L499.2,410.1 L512.2,410.1 L525.1,410.1 L538.1,410.1 L551.1,410.1 L564.1,410.1 L575.0,410.1     "
+           id="path5426" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(96.8,410.1) scale(4.50)"
+           id="use5428" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(109.8,410.1) scale(4.50)"
+           id="use5430" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(122.8,410.1) scale(4.50)"
+           id="use5432" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(135.7,410.1) scale(4.50)"
+           id="use5434" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(148.7,410.1) scale(4.50)"
+           id="use5436" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(161.7,410.1) scale(4.50)"
+           id="use5438" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(174.7,410.1) scale(4.50)"
+           id="use5440" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(187.7,410.1) scale(4.50)"
+           id="use5442" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(200.6,410.1) scale(4.50)"
+           id="use5444" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(213.6,410.1) scale(4.50)"
+           id="use5446" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(226.6,410.1) scale(4.50)"
+           id="use5448" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(239.6,410.1) scale(4.50)"
+           id="use5450" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(252.6,410.1) scale(4.50)"
+           id="use5452" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(265.5,410.1) scale(4.50)"
+           id="use5454" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(278.5,410.1) scale(4.50)"
+           id="use5456" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(291.5,410.1) scale(4.50)"
+           id="use5458" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(304.5,410.1) scale(4.50)"
+           id="use5460" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(317.5,410.1) scale(4.50)"
+           id="use5462" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(330.4,410.1) scale(4.50)"
+           id="use5464" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(343.4,410.1) scale(4.50)"
+           id="use5466" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(356.4,410.1) scale(4.50)"
+           id="use5468" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(369.4,410.1) scale(4.50)"
+           id="use5470" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(382.4,410.1) scale(4.50)"
+           id="use5472" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(395.3,410.1) scale(4.50)"
+           id="use5474" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(408.3,410.1) scale(4.50)"
+           id="use5476" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(421.3,410.1) scale(4.50)"
+           id="use5478" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(434.3,410.1) scale(4.50)"
+           id="use5480" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(447.3,410.1) scale(4.50)"
+           id="use5482" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(460.2,410.1) scale(4.50)"
+           id="use5484" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(473.2,410.1) scale(4.50)"
+           id="use5486" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(486.2,410.1) scale(4.50)"
+           id="use5488" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(499.2,410.1) scale(4.50)"
+           id="use5490" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(512.2,410.1) scale(4.50)"
+           id="use5492" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(525.1,410.1) scale(4.50)"
+           id="use5494" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(538.1,410.1) scale(4.50)"
+           id="use5496" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(551.1,410.1) scale(4.50)"
+           id="use5498" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(564.1,410.1) scale(4.50)"
+           id="use5500" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(537.3,90.1) scale(4.50)"
+           id="use5502" />
+      </g>
+    </g>
+    <g
+       style="fill:none; color:black; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+       id="g5504">
+      <path
+         stroke="black"
+         d="M96.8,54.1 L96.8,422.4 L575.0,422.4 L575.0,54.1 L96.8,54.1 Z  "
+         id="path5506" />
+    </g>
+  </g>
+</svg>
diff --git a/figures/naive_gmprat_is_slow.pdf b/figures/naive_gmprat_is_slow.pdf
new file mode 100644 (file)
index 0000000..037b3fa
Binary files /dev/null and b/figures/naive_gmprat_is_slow.pdf differ
diff --git a/figures/naive_mpfr_is_also_slow.pdf b/figures/naive_mpfr_is_also_slow.pdf
new file mode 100644 (file)
index 0000000..611a97d
Binary files /dev/null and b/figures/naive_mpfr_is_also_slow.pdf differ
diff --git a/figures/time.svg b/figures/time.svg
new file mode 100644 (file)
index 0000000..917816a
--- /dev/null
@@ -0,0 +1,699 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<svg
+   xmlns:dc="http://purl.org/dc/elements/1.1/"
+   xmlns:cc="http://creativecommons.org/ns#"
+   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+   xmlns:svg="http://www.w3.org/2000/svg"
+   xmlns="http://www.w3.org/2000/svg"
+   xmlns:xlink="http://www.w3.org/1999/xlink"
+   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+   width="600"
+   height="480"
+   viewBox="0 0 600 480"
+   id="svg4518"
+   version="1.1"
+   inkscape:version="0.48.5 r10040"
+   sodipodi:docname="time.pdf">
+  <metadata
+     id="metadata4837">
+    <rdf:RDF>
+      <cc:Work
+         rdf:about="">
+        <dc:format>image/svg+xml</dc:format>
+        <dc:type
+           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+        <dc:title>Gnuplot</dc:title>
+      </cc:Work>
+    </rdf:RDF>
+  </metadata>
+  <defs
+     id="defs4835" />
+  <sodipodi:namedview
+     pagecolor="#ffffff"
+     bordercolor="#666666"
+     borderopacity="1"
+     objecttolerance="10"
+     gridtolerance="10"
+     guidetolerance="10"
+     inkscape:pageopacity="0"
+     inkscape:pageshadow="2"
+     inkscape:window-width="640"
+     inkscape:window-height="480"
+     id="namedview4833"
+     showgrid="false"
+     inkscape:zoom="0.49166667"
+     inkscape:cx="300"
+     inkscape:cy="240"
+     inkscape:window-x="0"
+     inkscape:window-y="0"
+     inkscape:window-maximized="0"
+     inkscape:current-layer="svg4518" />
+  <title
+     id="title4520">Gnuplot</title>
+  <desc
+     id="desc4522">Produced by GNUPLOT 4.6 patchlevel 5 </desc>
+  <g
+     id="gnuplot_canvas">
+    <rect
+       x="0"
+       y="0"
+       width="600"
+       height="480"
+       fill="none"
+       id="rect4525" />
+    <defs
+       id="defs4527">
+      <circle
+         id="gpDot"
+         r="0.5"
+         stroke-width="0.5" />
+      <path
+         id="gpPt0"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M-1,0 h2 M0,-1 v2" />
+      <path
+         id="gpPt1"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M-1,-1 L1,1 M1,-1 L-1,1" />
+      <path
+         id="gpPt2"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M-1,0 L1,0 M0,-1 L0,1 M-1,-1 L1,1 M-1,1 L1,-1" />
+      <rect
+         id="gpPt3"
+         stroke-width="0.222"
+         stroke="currentColor"
+         x="-1"
+         y="-1"
+         width="2"
+         height="2" />
+      <rect
+         id="gpPt4"
+         stroke-width="0.222"
+         stroke="currentColor"
+         fill="currentColor"
+         x="-1"
+         y="-1"
+         width="2"
+         height="2" />
+      <circle
+         id="gpPt5"
+         stroke-width="0.222"
+         stroke="currentColor"
+         cx="0"
+         cy="0"
+         r="1" />
+      <use
+         xlink:href="#gpPt5"
+         id="gpPt6"
+         fill="currentColor"
+         stroke="none" />
+      <path
+         id="gpPt7"
+         stroke-width="0.222"
+         stroke="currentColor"
+         d="M0,-1.33 L-1.33,0.67 L1.33,0.67 z" />
+      <use
+         xlink:href="#gpPt7"
+         id="gpPt8"
+         fill="currentColor"
+         stroke="none" />
+      <use
+         xlink:href="#gpPt7"
+         id="gpPt9"
+         stroke="currentColor"
+         transform="rotate(180)" />
+      <use
+         xlink:href="#gpPt9"
+         id="gpPt10"
+         fill="currentColor"
+         stroke="none" />
+      <use
+         xlink:href="#gpPt3"
+         id="gpPt11"
+         stroke="currentColor"
+         transform="rotate(45)" />
+      <use
+         xlink:href="#gpPt11"
+         id="gpPt12"
+         fill="currentColor"
+         stroke="none" />
+    </defs>
+    <g
+       style="fill:none; color:white; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+       id="g4543" />
+    <g
+       style="fill:none; color:black; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+       id="g4545">
+      <path
+         stroke="black"
+         d="M71.9,422.4 L80.9,422.4 M575.0,422.4 L566.0,422.4  "
+         id="path4547" />
+      <g
+         transform="translate(63.6,426.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4549">
+        <text
+           id="text4551"> 0</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,376.4 L80.9,376.4 M575.0,376.4 L566.0,376.4  "
+         id="path4553" />
+      <g
+         transform="translate(63.6,380.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4555">
+        <text
+           id="text4557"> 50</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,330.3 L80.9,330.3 M575.0,330.3 L566.0,330.3  "
+         id="path4559" />
+      <g
+         transform="translate(63.6,334.8)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4561">
+        <text
+           id="text4563"> 100</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,284.3 L80.9,284.3 M575.0,284.3 L566.0,284.3  "
+         id="path4565" />
+      <g
+         transform="translate(63.6,288.8)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4567">
+        <text
+           id="text4569"> 150</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,238.2 L80.9,238.2 M575.0,238.2 L566.0,238.2  "
+         id="path4571" />
+      <g
+         transform="translate(63.6,242.7)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4573">
+        <text
+           id="text4575"> 200</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,192.2 L80.9,192.2 M575.0,192.2 L566.0,192.2  "
+         id="path4577" />
+      <g
+         transform="translate(63.6,196.7)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4579">
+        <text
+           id="text4581"> 250</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,146.2 L80.9,146.2 M575.0,146.2 L566.0,146.2  "
+         id="path4583" />
+      <g
+         transform="translate(63.6,150.7)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4585">
+        <text
+           id="text4587"> 300</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,100.1 L80.9,100.1 M575.0,100.1 L566.0,100.1  "
+         id="path4589" />
+      <g
+         transform="translate(63.6,104.6)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4591">
+        <text
+           id="text4593"> 350</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,54.1 L80.9,54.1 M575.0,54.1 L566.0,54.1  "
+         id="path4595" />
+      <g
+         transform="translate(63.6,58.6)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+         id="g4597">
+        <text
+           id="text4599"> 400</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,422.4 L71.9,413.4 M71.9,54.1 L71.9,63.1  "
+         id="path4601" />
+      <g
+         transform="translate(71.9,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4603">
+        <text
+           id="text4605"> 0</text>
+      </g>
+      <path
+         stroke="black"
+         d="M134.8,422.4 L134.8,413.4 M134.8,54.1 L134.8,63.1  "
+         id="path4607" />
+      <g
+         transform="translate(134.8,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4609">
+        <text
+           id="text4611"> 50</text>
+      </g>
+      <path
+         stroke="black"
+         d="M197.7,422.4 L197.7,413.4 M197.7,54.1 L197.7,63.1  "
+         id="path4613" />
+      <g
+         transform="translate(197.7,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4615">
+        <text
+           id="text4617"> 100</text>
+      </g>
+      <path
+         stroke="black"
+         d="M260.6,422.4 L260.6,413.4 M260.6,54.1 L260.6,63.1  "
+         id="path4619" />
+      <g
+         transform="translate(260.6,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4621">
+        <text
+           id="text4623"> 150</text>
+      </g>
+      <path
+         stroke="black"
+         d="M323.5,422.4 L323.5,413.4 M323.5,54.1 L323.5,63.1  "
+         id="path4625" />
+      <g
+         transform="translate(323.5,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4627">
+        <text
+           id="text4629"> 200</text>
+      </g>
+      <path
+         stroke="black"
+         d="M386.3,422.4 L386.3,413.4 M386.3,54.1 L386.3,63.1  "
+         id="path4631" />
+      <g
+         transform="translate(386.3,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4633">
+        <text
+           id="text4635"> 250</text>
+      </g>
+      <path
+         stroke="black"
+         d="M449.2,422.4 L449.2,413.4 M449.2,54.1 L449.2,63.1  "
+         id="path4637" />
+      <g
+         transform="translate(449.2,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4639">
+        <text
+           id="text4641"> 300</text>
+      </g>
+      <path
+         stroke="black"
+         d="M512.1,422.4 L512.1,413.4 M512.1,54.1 L512.1,63.1  "
+         id="path4643" />
+      <g
+         transform="translate(512.1,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4645">
+        <text
+           id="text4647"> 350</text>
+      </g>
+      <path
+         stroke="black"
+         d="M575.0,422.4 L575.0,413.4 M575.0,54.1 L575.0,63.1  "
+         id="path4649" />
+      <g
+         transform="translate(575.0,444.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4651">
+        <text
+           id="text4653"> 400</text>
+      </g>
+      <path
+         stroke="black"
+         d="M71.9,54.1 L71.9,422.4 L575.0,422.4 L575.0,54.1 L71.9,54.1 Z  "
+         id="path4655" />
+      <g
+         transform="translate(17.6,238.3) rotate(270)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4657">
+        <text
+           id="text4659">Time to run test (s)</text>
+      </g>
+      <g
+         transform="translate(323.4,471.9)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4661">
+        <text
+           id="text4663">Log10(Magnification)</text>
+      </g>
+      <g
+         transform="translate(323.4,31.6)"
+         style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:middle"
+         id="g4665">
+        <text
+           id="text4667">Time vs scaling</text>
+      </g>
+    </g>
+    <g
+       id="gnuplot_plot_1">
+      <title
+         id="title4670">gnuplot_plot_1</title>
+      <g
+         style="fill:none; color:red; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+         id="g4672">
+        <g
+           transform="translate(507.9,76.6)"
+           style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+           id="g4674">
+          <text
+             id="text4676">Gmprat</text>
+        </g>
+        <path
+           d="M516.2,72.1 L558.4,72.1 M71.9,422.2 L85.6,414.3 L99.2,406.3 L112.9,398.1 L126.5,389.6 L140.2,380.8    L153.8,371.7 L167.5,362.4 L181.1,352.9 L194.8,343.0 L208.5,332.9 L222.1,322.7 L235.8,312.2 L249.4,301.7    L263.1,290.8 L276.7,279.5 L290.4,268.3 L304.0,256.7 L317.7,244.7 L331.4,232.7 L345.0,220.6 L358.7,208.1    L372.3,195.2 L386.0,181.9 L399.6,168.3 L413.3,154.6 L427.0,140.7 L440.7,126.6 L454.3,112.0 L467.9,97.4     "
+           id="path4678" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(71.9,422.2) scale(4.50)"
+           id="use4680" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(85.6,414.3) scale(4.50)"
+           id="use4682" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(99.2,406.3) scale(4.50)"
+           id="use4684" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(112.9,398.1) scale(4.50)"
+           id="use4686" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(126.5,389.6) scale(4.50)"
+           id="use4688" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(140.2,380.8) scale(4.50)"
+           id="use4690" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(153.8,371.7) scale(4.50)"
+           id="use4692" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(167.5,362.4) scale(4.50)"
+           id="use4694" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(181.1,352.9) scale(4.50)"
+           id="use4696" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(194.8,343.0) scale(4.50)"
+           id="use4698" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(208.5,332.9) scale(4.50)"
+           id="use4700" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(222.1,322.7) scale(4.50)"
+           id="use4702" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(235.8,312.2) scale(4.50)"
+           id="use4704" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(249.4,301.7) scale(4.50)"
+           id="use4706" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(263.1,290.8) scale(4.50)"
+           id="use4708" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(276.7,279.5) scale(4.50)"
+           id="use4710" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(290.4,268.3) scale(4.50)"
+           id="use4712" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(304.0,256.7) scale(4.50)"
+           id="use4714" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(317.7,244.7) scale(4.50)"
+           id="use4716" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(331.4,232.7) scale(4.50)"
+           id="use4718" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(345.0,220.6) scale(4.50)"
+           id="use4720" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(358.7,208.1) scale(4.50)"
+           id="use4722" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(372.3,195.2) scale(4.50)"
+           id="use4724" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(386.0,181.9) scale(4.50)"
+           id="use4726" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(399.6,168.3) scale(4.50)"
+           id="use4728" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(413.3,154.6) scale(4.50)"
+           id="use4730" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(427.0,140.7) scale(4.50)"
+           id="use4732" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(440.7,126.6) scale(4.50)"
+           id="use4734" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(454.3,112.0) scale(4.50)"
+           id="use4736" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(467.9,97.4) scale(4.50)"
+           id="use4738" />
+        <use
+           xlink:href="#gpPt0"
+           transform="translate(537.3,72.1) scale(4.50)"
+           id="use4740" />
+      </g>
+    </g>
+    <g
+       id="gnuplot_plot_2">
+      <title
+         id="title4743">gnuplot_plot_2</title>
+      <g
+         style="fill:none; color:green; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+         id="g4745">
+        <g
+           transform="translate(507.9,94.6)"
+           style="stroke:none; fill:black; font-family:Arial; font-size:12.00pt; text-anchor:end"
+           id="g4747">
+          <text
+             id="text4749">mpfr-1024</text>
+        </g>
+        <path
+           d="M516.2,90.1 L558.4,90.1 M71.9,422.1 L85.6,418.7 L99.2,415.3 L112.9,411.9 L126.5,408.5 L140.2,405.1    L153.8,401.7 L167.5,398.4 L181.1,394.9 L194.8,391.6 L208.5,388.2 L222.1,384.8 L235.8,381.5 L249.4,378.1    L263.1,374.7 L276.7,371.3 L290.4,368.0 L304.0,364.6 L317.7,361.2 L331.4,357.9 L345.0,354.5 L358.7,351.1    L372.3,347.7 L386.0,344.4 L399.6,341.0 L413.3,337.5 L427.0,334.1 L440.6,330.7 L454.3,327.2 L467.9,323.8    L481.6,320.4 L495.2,317.0 L508.9,313.5 L522.5,310.1 L536.2,306.7 L549.9,303.3 L563.5,299.9 L575.0,297.0     "
+           id="path4751" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(71.9,422.1) scale(4.50)"
+           id="use4753" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(85.6,418.7) scale(4.50)"
+           id="use4755" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(99.2,415.3) scale(4.50)"
+           id="use4757" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(112.9,411.9) scale(4.50)"
+           id="use4759" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(126.5,408.5) scale(4.50)"
+           id="use4761" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(140.2,405.1) scale(4.50)"
+           id="use4763" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(153.8,401.7) scale(4.50)"
+           id="use4765" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(167.5,398.4) scale(4.50)"
+           id="use4767" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(181.1,394.9) scale(4.50)"
+           id="use4769" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(194.8,391.6) scale(4.50)"
+           id="use4771" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(208.5,388.2) scale(4.50)"
+           id="use4773" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(222.1,384.8) scale(4.50)"
+           id="use4775" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(235.8,381.5) scale(4.50)"
+           id="use4777" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(249.4,378.1) scale(4.50)"
+           id="use4779" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(263.1,374.7) scale(4.50)"
+           id="use4781" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(276.7,371.3) scale(4.50)"
+           id="use4783" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(290.4,368.0) scale(4.50)"
+           id="use4785" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(304.0,364.6) scale(4.50)"
+           id="use4787" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(317.7,361.2) scale(4.50)"
+           id="use4789" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(331.4,357.9) scale(4.50)"
+           id="use4791" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(345.0,354.5) scale(4.50)"
+           id="use4793" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(358.7,351.1) scale(4.50)"
+           id="use4795" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(372.3,347.7) scale(4.50)"
+           id="use4797" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(386.0,344.4) scale(4.50)"
+           id="use4799" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(399.6,341.0) scale(4.50)"
+           id="use4801" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(413.3,337.5) scale(4.50)"
+           id="use4803" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(427.0,334.1) scale(4.50)"
+           id="use4805" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(440.6,330.7) scale(4.50)"
+           id="use4807" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(454.3,327.2) scale(4.50)"
+           id="use4809" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(467.9,323.8) scale(4.50)"
+           id="use4811" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(481.6,320.4) scale(4.50)"
+           id="use4813" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(495.2,317.0) scale(4.50)"
+           id="use4815" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(508.9,313.5) scale(4.50)"
+           id="use4817" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(522.5,310.1) scale(4.50)"
+           id="use4819" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(536.2,306.7) scale(4.50)"
+           id="use4821" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(549.9,303.3) scale(4.50)"
+           id="use4823" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(563.5,299.9) scale(4.50)"
+           id="use4825" />
+        <use
+           xlink:href="#gpPt1"
+           transform="translate(537.3,90.1) scale(4.50)"
+           id="use4827" />
+      </g>
+    </g>
+    <g
+       style="fill:none; color:black; stroke:currentColor; stroke-width:1.00; stroke-linecap:butt; stroke-linejoin:miter"
+       id="g4829">
+      <path
+         stroke="black"
+         d="M71.9,54.1 L71.9,422.4 L575.0,422.4 L575.0,54.1 L71.9,54.1 Z  "
+         id="path4831" />
+    </g>
+  </g>
+</svg>
diff --git a/figures/turtle.pdf b/figures/turtle.pdf
new file mode 100644 (file)
index 0000000..647ea04
Binary files /dev/null and b/figures/turtle.pdf differ
index 4c1d5fd..4b1af23 100644 (file)
@@ -22,5 +22,7 @@ IEEE-754 floats.
 
 {\bf Note:} This report is best viewed digitally as a PDF. The digital version is available at \url{http://szmoore.net/ipdf/sam/thesis.pdf}
 
+{\bf Word Count: } 7620 (9335 with appendices)
+
 % Oh dear...
 \quad \\ \quad \\ \quad \\ \quad
index e69de29..304385d 100644 (file)
@@ -0,0 +1,6 @@
+\section*{Acknowlegments}
+
+I would like to acknowledge my supervisors, Prof Tim French and Dr Rowan Davies for their support and feedback during this project. I would also like to thank my colleague David Gow for his contributions to the joint part of the project. Lastly, as a double degree student I need to express a double degree of thanks to my friends and family for their continued patience whilst I completed my second ``final year'' project in what is technically a penultimate year.
+
+The rest of this space is left intentionally blank, apart from this sentence which informs the reader that the space is left intentionally blank.
+\newpage
diff --git a/meta/Letter.tex b/meta/Letter.tex
new file mode 100644 (file)
index 0000000..31ab547
--- /dev/null
@@ -0,0 +1,3 @@
+\begin{center}
+\includegraphics[width=1.1\textwidth]{meta/letter.pdf}
+\end{center}
index 3230c05..0128193 100644 (file)
@@ -1,11 +1,11 @@
 % Suitably pretty title page is required.
 \begin{titlepage}
 \title{Number Representations and Precision in Vector Graphics}
-\author{{\it Author:} Samuel Moore\cite{proposalMoore} \\
-{{\it Partners:} David Gow\cite{proposalGow}} \\
+\author{{\it Author:} Samuel Moore\cite{thesisMoore} \\
+{{\it Partners:} David Gow\cite{thesisGow}} \\
 {{\it Supervisors:} Prof Tim French, Dr Rowan Davies}\\
 \\ \\ \\
-\includegraphics[width=0.7\textwidth]{figures/uwacrest.pdf}}
+\includegraphics[width=0.5\textwidth]{figures/uwacrest.pdf}}
 %\date{Date of submission: 02/11/2012}
 \maketitle
 \end{titlepage}
diff --git a/meta/abstract.pdf b/meta/abstract.pdf
new file mode 100644 (file)
index 0000000..9904e41
Binary files /dev/null and b/meta/abstract.pdf differ
diff --git a/meta/letter.pdf b/meta/letter.pdf
new file mode 100644 (file)
index 0000000..0724e4c
Binary files /dev/null and b/meta/letter.pdf differ
index ef7dbb3..06e8f5c 100644 (file)
Binary files a/thesis.pdf and b/thesis.pdf differ
index b3e6dee..28ca99b 100644 (file)
@@ -1,4 +1,5 @@
 \documentclass[a4paper,10pt,titlepage]{report}
+\usepackage[toc,page]{appendix}
 \linespread{1.2}
 \usepackage{setspace}
 \onehalfspacing 
 
 \include{meta/Titlepage}               % This is who you are
 
-\input{meta/Abstract}          % This is your thesis abstract
+\include{meta/Abstract}          % This is your thesis abstract
+
+\include{meta/Letter}
+
+\input{meta/Acknowledgements}
 
 %\newpage
 
 
 \input{chapters/Conclusion}
 
+
+
 %--------------------------------------------
 \renewcommand{\bibname}{References}
 \bibliography{references/refs}
 \bibliographystyle{unsrt}  
 \addcontentsline{toc}{part}{References}
-{\bf Note:} We have collated most of these references at \url{http://szmoore.net/ipdf/documents/references/}
+%{\bf Note:} We have collated most of these references at \url{http://szmoore.net/ipdf/documents/references/}
 \vspace*{6\baselineskip} % sigh
-
+%\begin{comment}
+\begin{appendices}
+\chapter{An Overview of Document Standards} \label {An Overview of Document Standards}
+Together with Section \ref{Precision Specified by Document Standards} this Appendix forms an overview of the well known standard document formats.
+
+\input{chapters/Background/Standards}
+\section{Compositing} \label{Compositing}
+\input{chapters/Background/Rendering/Compositing}
+\end{appendices}
+%\end{comment}
 
 \end{document}
 

UCC git Repository :: git.ucc.asn.au