author Sam Moore Wed, 8 Oct 2014 14:36:03 +0000 (22:36 +0800) committer Sam Moore Wed, 8 Oct 2014 14:36:03 +0000 (22:36 +0800)
I can see where I want it to go but I can't see how I can get it there.

82 files changed:
 Makefile patch | blob | history chapters/Background.tex patch | blob | history chapters/Background/ArbitraryPrecision.tex [new file with mode: 0644] patch | blob chapters/Background/CoordinateSystems.tex [new file with mode: 0644] patch | blob chapters/Background/FixedPoint.tex [new file with mode: 0644] patch | blob chapters/Background/FloatingPointOnTheGPU.tex [new file with mode: 0644] patch | blob chapters/Background/Floats.tex [new file with mode: 0644] patch | blob chapters/Background/Floats/Definition.tex [new file with mode: 0644] patch | blob chapters/Background/Floats/Operations.tex [new file with mode: 0644] patch | blob chapters/Background/Floats/PrecisionIssues.tex [new file with mode: 0644] patch | blob chapters/Background/Floats/Visualisation.tex [new file with mode: 0644] patch | blob chapters/Background/GMP.tex [new file with mode: 0644] patch | blob chapters/Background/Overview.tex [new file with mode: 0644] patch | blob chapters/Background/RasterAndVectorGraphics.tex [new file with mode: 0644] patch | blob chapters/Background/Rationals.tex [new file with mode: 0644] patch | blob chapters/Background/Rendering.tex [new file with mode: 0644] patch | blob chapters/Background/Rendering/BezierSplines.tex [new file with mode: 0644] patch | blob chapters/Background/Rendering/Compositing.tex [new file with mode: 0644] patch | blob chapters/Background/Rendering/Fonts.tex [new file with mode: 0644] patch | blob chapters/Background/Rendering/Overview.tex [new file with mode: 0644] patch | blob chapters/Background/Rendering/StraightLines.tex [new file with mode: 0644] patch | blob chapters/Background/Standards.tex [new file with mode: 0644] patch | blob chapters/Background/Standards/DOM.tex [new file with mode: 0644] patch | blob chapters/Background/Standards/Interpreted.tex [new file with mode: 0644] patch | blob chapters/Background/Standards/Overview.tex [new file with mode: 0644] patch | blob chapters/Background/Standards/Precision.tex [new file with mode: 0644] patch | blob chapters/Background_Compositing.tex [deleted file] patch | blob | history chapters/Background_DOM.tex [deleted file] patch | blob | history chapters/Background_Fonts.tex [deleted file] patch | blob | history chapters/Background_Interpreted.tex [deleted file] patch | blob | history chapters/Background_Lines.tex [deleted file] patch | blob | history chapters/Background_Raster-vs-Vector.tex [deleted file] patch | blob | history chapters/Background_Spline.tex [deleted file] patch | blob | history chapters/Conclusion.tex patch | blob | history chapters/Introduction.tex patch | blob | history chapters/Process.tex [new file with mode: 0644] patch | blob chapters/Process/DesignProcess.tex [new file with mode: 0644] patch | blob chapters/Process/Measurements.tex [new file with mode: 0644] patch | blob chapters/Process/SoftwareOverview.tex [new file with mode: 0644] patch | blob chapters/Process/Transformations.tex [new file with mode: 0644] patch | blob chapters/Progress/Progress.tex [new file with mode: 0644] patch | blob chapters/Proposal.tex [deleted file] patch | blob | history chapters/Results.tex [new file with mode: 0644] patch | blob figures/controlpanel_screenshot.png [new file with mode: 0644] patch | blob figures/fox-vector+grid.png [new file with mode: 0644] patch | blob figures/fox-vector_cumulative_after_transforms.png [new file with mode: 0644] patch | blob figures/fox-vector_cumulative_before_transforms.png [new file with mode: 0644] patch | blob figures/fox-vector_cumulative_relative_to_path.png [new file with mode: 0644] patch | blob figures/fox-vector_cumulative_relative_to_path_GMPrat.png [new file with mode: 0644] patch | blob figures/fox-vector_face_with_bezbounds.png [new file with mode: 0644] patch | blob figures/fox-vector_highzoom1.png [new file with mode: 0644] patch | blob figures/fox-vector_screenshot1.png [new file with mode: 0644] patch | blob figures/fox-vector_screenshot2.png [new file with mode: 0644] patch | blob figures/fox-vector_screenshot2_300dpi.png [new file with mode: 0644] patch | blob figures/gpufloats.svg [new file with mode: 0644] patch | blob figures/shady-the-fox.png [new file with mode: 0644] patch | blob figures/who-the-hell-needs-antialiasing-anyway.png [new file with mode: 0644] patch | blob meta/Abstract.tex patch | blob | history meta/Proposal.tex [new file with mode: 0644] patch | blob meta/Titlepage.tex patch | blob | history notes.nb [new file with mode: 0644] patch | blob presentation.nav [new file with mode: 0644] patch | blob presentation.snm [new file with mode: 0644] patch | blob presentation/Logos/WAMSI.png [new file with mode: 0644] patch | blob presentation/Logos/uwa.png [new file with mode: 0644] patch | blob presentation/arrow.pdf [new file with mode: 0644] patch | blob presentation/beamerthemeuwa_eng.sty [new file with mode: 0644] patch | blob presentation/bezier_to_font.pdf [new file with mode: 0644] patch | blob presentation/example_uwa_eng.nav [new file with mode: 0644] patch | blob presentation/example_uwa_eng.pdf [new file with mode: 0644] patch | blob presentation/example_uwa_eng.snm [new file with mode: 0644] patch | blob presentation/presentation.nav [new file with mode: 0644] patch | blob presentation/presentation.pdf [new file with mode: 0644] patch | blob presentation/presentation.snm [new file with mode: 0644] patch | blob presentation/presentation.tex [new file with mode: 0644] patch | blob presentation/turtles.pdf [new file with mode: 0644] patch | blob presentation/uwa_eng.png [new file with mode: 0644] patch | blob presentation/uwa_eng_title.png [new file with mode: 0644] patch | blob test [new file with mode: 0644] patch | blob thesis.pdf patch | blob | history thesis.tex patch | blob | history wordcount.sh [new file with mode: 0755] patch | blob

index 788633c..bfbc00e 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -18,9 +18,9 @@ $(NAME).pdf :$(NAME).tex
$(TEX) --shell-escape$(NAME)
$(TEX) --shell-escape$(NAME)

-       silent evince $(NAME).pdf + silent atril$(NAME).pdf
rm -f *.bbl *.log *.toc *.lof *.blg *.lot *.aux *.out
-
+       ./wordcount.sh | sed 's/\t//g' | sort -k3 -n -r

clean :
rm -f $(NAME).pdf index 3cf44a8..10852bb 100644 (file) \chapter{Literature Review}\label{Background} -The first part of this chapter will be devoted to documents themselves, including: the representation and displaying of graphics primitives, and how collections of these primitives are represented in document formats, focusing on widely used standards. +%\section{Overview} +\input{chapters/Background/Overview} +\section{Raster and Vector Graphics} +\input{chapters/Background/RasterAndVectorGraphics} +\section{Rendering Vector Primitives} +\input{chapters/Background/Rendering} +\section{Coordinate Systems and Transformations} +\input{chapters/Background/CoordinateSystems} +\section{Precision Specified by Document Standards} +\input{chapters/Background/Standards} -We will find that although there has been a great deal of research into the rendering, storing, editing, manipulation, and extension of document formats, modern standards are content to specify at best single precision IEEE-754 floating point arithmetic. -The research on arbitrary precision arithmetic applied to documents is rather sparse; however arbitrary precision arithmetic itself is a very active field of research. Therefore, remainder of this chapter will be devoted to considering fixed precision floating point numbers as specified by the IEEE-754 standard, possible limitations in precision, and alternative number representations for increased or arbitrary precision arithmetic. -In Chapter \ref{Progress}, we will discuss our findings so far with regards to arbitrary precision arithmetic applied to document formats, and expand upon the goals outlined in Chapture \ref{Proposal}. +\section{Fixed Point and Integer Number Representations} +\input{chapters/Background/FixedPoint} +\section{Floating Point Number Representations} +\input{chapters/Background/Floats} +\section{Rational Number Representations} +\input{chapters/Background/Rationals} -\section{Raster and Vector Images}\label{Raster and Vector Images} -\input{chapters/Background_Raster-vs-Vector} -\section{Rendering Vector Images}\label{Rasterising Vector Images} -Hearn and Baker's textbook Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in Computer Graphics'' and the relevant literature. This section is by no means a comprehensive survey of the literature but intends to provide some idea of the computations which are required to render a document. - -It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading\cite{lane1983analgorithm}; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}. - -\subsection{Straight Lines}\label{Straight Lines} -\input{chapters/Background_Lines} - -\subsection{Spline Curves and B{\'e}ziers}\label{Spline Curves} -\input{chapters/Background_Spline} - -\subsection{Font Glyphs}\label{Font Rendering} -\input{chapters/Background_Fonts} - -%\subsection{Shading}\label{Shading} - - -%\cite{brassel1979analgorithm}; %\cite{lane1983analgorithm}. - -\subsection{Compositing}\label{Compositing} - -%So far we have discussed techniques for rendering vector graphics primitives in isolation, with no regard to the overall structure of a document which may contain many thousands of primitives. A straight forward approach would be to render all elements sequentially to the display, with the most recently drawn pixels overwriting lower elements. Such an approach is particularly inconvenient for anti-aliased images where colours must appear to smoothly blur between the edge of a primitive and any drawn underneath it. - -Colour raster displays are based on an additive red-green-blue$(r,g,b)$colour representation which matches the human eye's response to light\cite{computergraphics2}. In 1984, Porter and Duff introduced a fourth colour channel for rasterised images called the alpha'' channel, analogous to the transparency of a pixel\cite{porter1984compositing}. In compositing models, elements can be rendered seperately, with the four colour channels of successively drawn elements being combined according to one of several possible operations. - -In the painter's model'' as described by the SVG standard the over'' operation is used when rendering one primitive over another\cite{svg2011-1.1}. -Given an existing pixel$P_1$with colour values$(r_1, g_1, b_1, a_1)$and a pixel$P_2$with colours$(r_2, g_2, b_2, a_2)$to be painted over$P_1$, the resultant pixel$P_Thas colours given by: -\begin{align} - a_T &= 1 - (1-a_1)(1-a_2) \\ - r_T &= (1 - a_2)r_1 + r_2 \quad \text{(similar forg_T$and$b_T)} -\end{align} -It should be apparent that alpha values of1$correspond to an opaque pixel; that is, when$a_2 = 1$the resultant pixel$P_T$is the same as$P_2$. -When the final pixel is actually drawn on an rgb display, the$(r, g, b)$components are$(r_T/a_T, g_T/a_T, b_T/a_T)$. - -The PostScript and PDF standards, as well as the OpenGL API also use a painter's model for compositing. However, PostScript does not include an alpha channel, so$P_T = P_2$always\cite{plrm}. Figure \ref{SVG} illustrates the painter's model for partially transparent shapes as they would appear in both the SVG and PDF models. - -\subsection{Rasterisation on the CPU and GPU} - -Traditionally, vector images have been rasterized by the CPU before being sent to a specialised Graphics Processing Unit (GPU) for drawing\cite{computergraphics2}. Rasterisation of simple primitives such as lines and triangles have been supported directly by GPUs for some time through the OpenGL standard\cite{openglspec}. However complex shapes (including those based on B{\'e}zier curves such as font glyphs) must either be rasterised entirely by the CPU or decomposed into simpler primitives that the GPU itself can directly rasterise. There is a significant body of research devoted to improving the performance of rendering such primitives using the latter approach, mostly based around the OpenGL\cite{openglspec} API\cite{robart2009openvg, leymarie1992fast, frisken2000adaptively, green2007improved, loop2005resolution, loop2007rendering}. Recently Mark Kilgard of the NVIDIA Corporation described an extension to OpenGL for NVIDIA GPUs capable of drawing and shading vector paths\cite{kilgard2012gpu,kilgard300programming}. From this development it seems that rasterization of vector graphics may eventually become possible upon the GPU. - -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}. %Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations - - \pagebreak -\section{Document Representations}\label{Document Representations} - -The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper referenced earlier\cite{brassel1979analgorithm} has been produced on a mechanical type writer. Although the paper discusses an algorithm for shading on computer displays, the figures illustrating this algorithm have not been generated by a computer, but drawn by Brassel's assistant. In contrast, modern papers such as Barnes et. al's 2013 paper on embedding 3d images in PDF documents\cite{barnes2013embedding} can themselves be an interactive proof of concept. - -Haye's 2012 article Pixels or Perish'' discusses the recent history and current state of the art in documents for scientific publications\cite{hayes2012pixels}. Hayes argued that there are currently two different approaches to representing a document: As a sequence of static sheets of paper (Programmed Documents) or as a dynamic and interactive way to convey information, using the Document Object Model. We will now explore these two approaches and the extent to which they overlap. - - -\subsection{Programmed Documents} -\input{chapters/Background_Interpreted} - -\pagebreak -\subsection{Document Object Model}\label{Document Object Model} -\input{chapters/Background_DOM} - -\subsection{The Portable Document Format} - -Adobe's Portable Document Format (PDF) is currently used almost universally for sharing documents; the ability to export or print to PDF can be found in most graphical document editors and even some plain text editors\cite{cheng2002portable}. - -Hayes describes PDF as ... essentially 'flattened' PostScript; it’s what’s left when you remove all the procedures and loops in a program, replacing them with sequences of simple drawing commands.''\cite{hayes2012pixels}. Consultation of the PDF 1.7 standard shows that this statement does not a give a complete picture --- despite being based on the Adobe PostScript model of a document as a series of pages'' to be printed by executing sequential instructions, from version 1.5 the PDF standard began to borrow some ideas from the Document Object Model. For example, interactive elements such as forms may be included as XHTML objects and styled using CSS. Actions'' are objects used to modify the data structure dynamically. In particular, it is possible to include Javascript Actions. Adobe defines the API for Javascript actions seperately to the PDF standard\cite{js_3d_pdf}. There is some evidence in the literature of attempts to exploit these features, with mixed success\cite{barnes2013embedding, hayes2012pixels}. - -%\subsection{Scientific Computation Packages} - - -\section{Precision required by Document Formats} - -We briefly summarise the requirements of the standards discussed so far in regards to the precision of mathematical operations. - -\subsection{PostScript} -The PostScript reference describes a Real'' object for representing coordinates and values as follows: Real objects approximate mathematical real numbers within a much larger interval, but with limited precision; they are implemented as floating-point numbers''\cite{plrm}. There is no reference to the precision of mathematical operations, but the implementation limits \emph{suggest} a range of$\pm10^{38}$approximate'' and the smallest values not rounded to zero are$\pm10^{-38}$approximate''. - -\subsection{PDF} -PDF defines Real'' objects in a similar way to PostScript, but suggests a range of$\pm3.403\times10^{38}$and smallest non-zero values of$\pm1.175\times10^{38}$\cite{pdfref17}. A note in the PDF 1.7 manual mentions that Acrobat 6 now uses IEEE-754 single precision floats, but previous versions used 32-bit fixed point numbers'' and ... Acrobat 6 still converts floating-point numbers to fixed point for some components''. - -\subsection{{\TeX} and METAFONT} - -In The METAFONT book'' Knuth appears to describe coordinates as fixed point numbers: The computer works internally with coordinates that are integer multiples of$\frac{1}{65536} \approx 0.00002$of the width of a pixel''\cite{knuth1983metafont}. \footnote{This corresponds to using$16$bits for the fractional component of a fixed point representation} There is no mention of precision in The {\TeX} book''. In 2007 Beebe claimed that {\TeX} uses a$14.16$fixed point encoding, and that this was due to the lack of standardised floating point arithmetic on computers at the time; a problem that the IEEE-754 was designed to solve\cite{beebe2007extending}. Beebe also suggested that {\TeX} and METAFONT could now be modified to use IEEE-754 arithmetic. - -\subsection{SVG} - -The SVG standard specifies a minimum precision equivelant to that of single precision floats'' (presumably referring to IEEE-754) with a range of \verb/-3.4e+38F/ to \verb/+3.4e+38F/, and states It is recommended that higher precision floating point storage and computation be performed on operations such as -coordinate system transformations to provide the best possible precision and to prevent round-off errors.''\cite{svg2011-1.1} An SVG Viewer may refer to itself as High Quality'' if it uses a minimum of double precision'' floats. - -\subsection{Javascript} -%We include Javascript here due to its relation with the SVG, HTML5 and PDF standards. -According to the EMCA-262 standard, The Number type has exactly 18437736874454810627 (that is,$2^64-^53+3$) values, -representing the double-precision 64-bit format IEEE 754 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic''\cite{ecma-262}. -The Number type does differ slightly from IEEE-754 in that there is only a single valid representation of Not a Number'' (NaN). The EMCA-262 does not define an integer'' representation. - - - -\section{Number Representations}\label{Number Representations} - -\subsection{Exact Representations} - -Consider a value of$7.25 = 2^2 + 2^1 + 2^0 + 2^{-2}$. In binary (base 2), this could be written as$111.01_2$Such a value would require 5 binary digits (bits) of memory to represent exactly in computer hardware. Some values, for example$7.3$can not be represented exactly in one base (decimal) but not another; in binary the sequence$111.010\text{...}_2$will never terminate. A rational value such as$\frac{7}{3}$could not be represented exactly in any base, but could be represented by the combination of a numerator$7 = 111_2$and denominator$3 = 11_2$. Lastly, some values such as$e \approx 2.718\text{...}$can only be expressed exactly using a symbolical system --- in this case as the result of an infinite summation$e = \displaystyle\sum_n^{\infty} 1/n!$- -Modern computer hardware typically supports integer and floating-point number representations and operations. Due to physical limitations, the size of these representations is limited; this is the fundamental source of both limits on range and precision in computer based calculations. - -\subsection{Floating Point Definitions} - -Whilst a Fixed Point representation keeps the point'' at the same position in a string of bits, Floating point representations can be thought of as analogous to scientific notation; an exponent'' and fixed point value are encoded, with multiplication by the exponent moving the position of the point. - -A floating point number$x$is commonly represented by a tuple of values$(s, e, m)$in base$B$as\cite{HFP, ieee2008-754}:$x = (-1)^{s} \times m \times B^{e}$- -Where$s$is the sign and may be zero or one,$m$is commonly called the mantissa'' and$e$is the exponent. Whilst$e$is an integer in some range$\pm e_max$, the mantissa$m$is a fixed point value in the range$0 < m < B$. - - -The choice of base$B = 2$in the original IEEE-754 standard matches the nature of modern hardware. It has also been found that this base in general gives the smallest rounding errors\cite{HFP}. Early computers had in fact used a variety of representations including$B=3$or even$B=7$\cite{goldman1991whatevery}, and the revised IEEE-754 standard specifies a decimal representation$B = 10$intended for use in financial applications\cite{ieee754std2008}\footnote{Eg: The smallest valid unit of currency \$0.01 could not be represented exactly in base 2}. From now on we will restrict ourselves to considering base 2 floats.
-
-The IEEE-754 encoding of $s$, $e$ and $m$ requires a fixed number of continuous bits dedicated to each value. Originally two encodings were defined: binary32 and binary64. $s$ is always encoded in a single leading bit, whilst (8,23) and (11,53) bits are used for the (exponent, mantissa) encodings respectively.
-
-The encoding of $m$ in the IEEE-754 standard is not exactly equivelant to a fixed point value. By assuming an implicit leading bit (ie: restricting $1 \leq m < 2$) except for when $e = 0$, floating point values are gauranteed to have a unique representations; these representations are said to be normalised''. When $e = 0$ the leading bit is not implied; these representations are called denormals'' because multiple representations may map to the same real value. The idea of using an implicit bit appears to have been considered by Goldberg as early as 1967\cite{goldbern1967twentyseven}.
-
-Figure \ref{floats.pdf}\footnote{In a digital PDF viewer we suggest increasing the zoom level --- the graphs were created from SVG images} shows the positive real numbers which can be represented exactly by an 8 bit floating point number encoded in the IEEE-754 format\footnote{Not quite; we are ignoring the IEEE-754 definitions of NaN and Infinity for simplicity}, and the distance between successive floating point numbers. We show two encodings using (1,2,5) and (1,3,4) bits to encode (sign, exponent, mantissa) respectively. 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 on the right. 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 as straight lines - the distance between points is always constant.
-
-The earlier example $7.25$ would be converted to a (1,3,4) floating point representation as follows:
-\begin{enumerate}
-       \item Determine the fixed point representation $7.25 = 111.01_2$
-       \item Determine the sign bit; in this case $s = 0$
-       \item Calculate the exponent by shifting the point $111.01_2 = 1.1101_2 \times 2^2 \implies e = 2 = 10_2$
-       \item Determine the exponent encoding; in IEEE-754 equal to the number of exponent bits is added so $e_{enc} = e+3 = 5 = 101_2$
-       \item Remove the implicit bit if the encoded exponent $\neq 0$; $1.1101_2 \to .1101_2$
-       \item Combine the three bit strings$0,101,1101$
-       \item The final encoding is $01011101 \equiv \text{0x5D}$
-\end{enumerate}
-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.
-
-
-\begin{figure}[H]
-       \centering
-\begin{minipage}[t]{0.45\textwidth}
-       \begin{figure}[H]
-               \centering
-               \includegraphics[width=1\textwidth]{figures/floats.pdf} \\
-       \end{figure}
-\end{minipage}
-\begin{minipage}[t]{0.45\textwidth}
-       \begin{figure}[H]
-               \centering
-               \includegraphics[width=1\textwidth]{figures/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}
-\end{figure}
-
-
-
-\subsection{Precision and Rounding}\label{Precision and Rounding}
-
-Real values which cannot be represented exactly in a floating point representation must be rounded to the nearest floating point value. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Referring to Figure \ref{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.
-
-Goldberg's assertively titled 1991 paper What Every Computer Scientist Needs to Know about Floating Point Arithmetic''\cite{goldberg1991whatevery} provides a comprehensive overview of issues in floating point arithmetic and relates these to requirements of the IEEE-754 1985 standard\cite{ieee754std1985}. More recently, after the release of the revised IEEE-754 standard in 2008\cite{ieee754std2008}, a textbook Handbook Of Floating Point Arithmetic'' has been published which provides a thourough review of literature relating to floating point arithmetic in both software and hardware\cite{HFP}.
-
-William Kahan, one of the architects of the IEEE-754 standard in 1984 and a contributor to its revision in 2010, has also published many articles on his website explaining the more obscure features of the IEEE-754 standard and calling out software which fails to conform to the standard\footnote{In addition to encodings and acceptable rounding behaviour, the standard also specifies exceptions'' --- mechanisms by which a program can detect and report an error such as division by zero}\cite{kahanweb, kahan1996ieee754}, as well as examples of the limitations of floating point computations\cite{kahan2007wrong}.
-
-In  Figure \ref{calculatepi.pdf} we show the effect of accumulated rounding errors on the computation of $\pi$ through a numerical integration\footnote{This is not intended to be an example of a good way to calculate $\pi$} using 32 bit single precision'' floats and 64 bit double precision'' floats.
-
-\begin{figure}[H]
-       \centering
-       \includegraphics[width=0.6\textwidth]{figures/calculatepi.pdf}
-       \caption{Numerical calculation of $\pi$}\label{calculatepi.pdf}
-\end{figure}
-
-\subsection{Floating Point Operations}
-
-Floating point operations can in principle be performed using integer operations, but specialised Floating Point Units (FPUs) are an almost universal component of modern processors\cite{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}.
-
-In 1971 Dekker formalised a series of algorithms including the Fast2Sum method for calculating the correction term due to accumulated rounding errors\cite{dekker1971afloating}. The exact result of $x + y$ may be expressed in terms of floating point operations with rounding as follows:
-\begin{align*}
-       z = \text{RN}(x + y) &\quad w = \text{RN}(z - x) \\
-       zz = \text{RN}(y - w) &\quad \implies x + y = zz
-\end{align*}
-
-\subsection{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.
-
-As we have seen, it is trivial to find real numbers that would require an infinite number of bits to represent exactly. Implementations of arbitrary'' precision must carefully determine at what point rounding should occur so as to balance performance with memory usage.

diff --git a/chapters/Background/ArbitraryPrecision.tex b/chapters/Background/ArbitraryPrecision.tex
new file mode 100644 (file)
index 0000000..d43b470
--- /dev/null
@@ -0,0 +1,3 @@
+Modern computer hardware typically supports integer and floating-point number representations and operations. Due to physical limitations, the size of these representations is limited; this places the fundamental limit on both on range and precision in computer based calculations.
+
+
diff --git a/chapters/Background/CoordinateSystems.tex b/chapters/Background/CoordinateSystems.tex
new file mode 100644 (file)
index 0000000..147a684
--- /dev/null
@@ -0,0 +1,46 @@
+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\cite{}.
+
+Primitives which are contained within the view rectangle will be visible on the display. This involves the transformation from coordinates within the document to relative coordinates within the view rectangle as illustrated in Figure \ref{}. A point $(X,Y)$ in the document will transform to a point $(x,y)$ in the view by:
+\begin{align}
+       X = \frac{x - v_x}{v_w} &\quad\quad Y = \frac{y - v_y}{v_h}\label{view-transformation}
+\end{align}
+Where $(v_x,v_y)$ are the coordinates of the top left corner and $(v_w,v_h)$ are the dimensions of the view rectangle.
+
+
+The transformation may also be written as a 3x3 matrix $\matx{V}$ if we introduce a third coordinate $Z = 1$
+\begin{align}
+       \matx{X} &= \matx{V} \matx{x} \\
+       \left( \begin{array}{c} X \\ Y \\ 1 \end{array}\right) &=
+       \left( \begin{array}{ccc}
+               \frac{1}{v_w} & 0 & \frac{v_x}{v_w} \\
+               0 & \frac{1}{v_h} & \frac{v_y}{v_h} \\
+               0 & 0 & 1
+       \end{array}\right)
+       \left( \begin{array}{c} x \\ y \\ 1 \end{array}\right)\label{view-transformation-matrix}
+\end{align}
+
+
+
+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{}:
+\begin{align}
+       v_x \to v_x + \Delta x \\
+       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{}:
+\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
+\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''.
+
+%TODO List
+% Mention that these transformations affect precision more than eg: drawing a line
+% Discuss floating point errors that could occur?
+% Convert operations to Matrix form, more standard
+% Cite some UI paper or something
diff --git a/chapters/Background/FixedPoint.tex b/chapters/Background/FixedPoint.tex
new file mode 100644 (file)
index 0000000..707dab2
--- /dev/null
@@ -0,0 +1,21 @@
+A positive real number $z$ may be written as the sum of smaller integers digits'' $d_i < z$ multiplied by powers of a base $\beta$.
+\begin{align}
+       z &= \displaystyle\sum_{i=-\infty}^{\infty} d_i \beta^{i}\label{fixedpointZ}
+\end{align}
+Where each digit $d_i < \beta$ the base. A set of $\beta$ unique symbols are used to represent values of $d_i$.
+A seperate sign '-' can be used to represent negative integers using equation \eqref{fixedpointZ}.
+
+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*}
+
+
+
+
+
+%, but could be represented by the combination of a numerator $7 = 111_2$ and denominator $3 = 11_2$. Lastly, some values such as $e \approx 2.718\text{...}$ can only be expressed exactly using a symbolical system --- in this case as the result of an infinite summation $e = \displaystyle\sum_n^{\infty} 1/n!$
+
diff --git a/chapters/Background/FloatingPointOnTheGPU.tex b/chapters/Background/FloatingPointOnTheGPU.tex
new file mode 100644 (file)
index 0000000..bd5ea29
--- /dev/null
@@ -0,0 +1,8 @@
+\subsection{Rasterisation on the CPU and GPU}
+
+Traditionally, vector images have been rasterized by the CPU before being sent to a specialised Graphics Processing Unit (GPU) for drawing\cite{computergraphics2}. Rasterisation of simple primitives such as lines and triangles have been supported directly by GPUs for some time through the OpenGL standard\cite{openglspec}. However complex shapes (including those based on B{\'e}zier curves such as font glyphs) must either be rasterised entirely by the CPU or decomposed into simpler primitives that the GPU itself can directly rasterise. There is a significant body of research devoted to improving the performance of rendering such primitives using the latter approach, mostly based around the OpenGL\cite{openglspec} API\cite{robart2009openvg, leymarie1992fast, frisken2000adaptively, green2007improved, loop2005resolution, loop2007rendering}. Recently Mark Kilgard of the NVIDIA Corporation described an extension to OpenGL for NVIDIA GPUs capable of drawing and shading vector paths\cite{kilgard2012gpu,kilgard300programming}. From this development it seems that rasterization of vector graphics may eventually become possible upon the GPU.
+
+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}.
+
+\rephrase{We implemented a GPU and CPU renderer so we could compare them}.
+%Arbitrary precision arithmetic, is provided by many software libraries for CPU based calculations
diff --git a/chapters/Background/Floats.tex b/chapters/Background/Floats.tex
new file mode 100644 (file)
index 0000000..7eba8a2
--- /dev/null
@@ -0,0 +1,14 @@
+\input{chapters/Background/Floats/Definition}
+\subsection{Visualisation of Floating Point Representation}
+\input{chapters/Background/Floats/Visualisation}
+
+
+%\subsection{Floating Point Operations}
+%\input{chapters/Background/Floats/Operations}
+
+
+\subsection{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.
+
+As we have seen, it is trivial to find real numbers that would require an infinite number of bits to represent exactly. Implementations of arbitrary'' precision must carefully determine at what point rounding should occur so as to balance performance with memory usage.
diff --git a/chapters/Background/Floats/Definition.tex b/chapters/Background/Floats/Definition.tex
new file mode 100644 (file)
index 0000000..62d2c71
--- /dev/null
@@ -0,0 +1,13 @@
+Whilst a Fixed Point representation keeps the point'' (the location considered to be $i = 0$ in \eqref{fixedpointZ}) at the same position in a string of bits, Floating point representations can be thought of as scientific notation; an exponent'' and fixed point value are encoded, with multiplication by the exponent moving the position of the point.
+
+A floating point number $x$ is commonly represented by a tuple of values $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}: $x = (-1)^{s} \times m \times B^{e}$
+
+Where $s$ is the sign and may be zero or one, $m$ is commonly called the mantissa'' and $e$ is the exponent. Whilst $e$ is an integer in some range $\pm e_max$, the mantissa $m$ is a fixed point value in the range $0 < m < B$.
+
+
+               echo -e "$2/$(basename $i) :$(detex $i | wc -w)" + if [ -e${i%.*} ]; then
+                       doThing ${i%.*}${i%.*}
+               fi
+       done
+}
+doThing chapters chapters
+echo "Total : \$(detex thesis.tex | wc -w)"
+

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