From: Sam Moore Date: Wed, 8 Oct 2014 14:36:03 +0000 (+0800) Subject: Restructure chapters, delete a bunch of words, add more words, do some things, panic... X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=commitdiff_plain;h=9fcf44a0c34f393689118e913a2d17d907036c85 Restructure chapters, delete a bunch of words, add more words, do some things, panic a little I can see where I want it to go but I can't see how I can get it there. --- diff --git a/Makefile b/Makefile index 788633c..bfbc00e 100644 --- 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 diff --git a/chapters/Background.tex b/chapters/Background.tex index 3cf44a8..10852bb 100644 --- a/chapters/Background.tex +++ b/chapters/Background.tex @@ -1,196 +1,25 @@ \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_T$ has 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 for $g_T$ and $b_T$)} -\end{align} -It should be apparent that alpha values of $1$ 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 index 0000000..d43b470 --- /dev/null +++ b/chapters/Background/ArbitraryPrecision.tex @@ -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 index 0000000..147a684 --- /dev/null +++ b/chapters/Background/CoordinateSystems.tex @@ -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 index 0000000..707dab2 --- /dev/null +++ b/chapters/Background/FixedPoint.tex @@ -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 index 0000000..bd5ea29 --- /dev/null +++ b/chapters/Background/FloatingPointOnTheGPU.tex @@ -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 index 0000000..7eba8a2 --- /dev/null +++ b/chapters/Background/Floats.tex @@ -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 index 0000000..62d2c71 --- /dev/null +++ b/chapters/Background/Floats/Definition.tex @@ -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$. + + +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}. + diff --git a/chapters/Background/Floats/Operations.tex b/chapters/Background/Floats/Operations.tex new file mode 100644 index 0000000..1a724f9 --- /dev/null +++ b/chapters/Background/Floats/Operations.tex @@ -0,0 +1,29 @@ + + +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. + + + +{\bf Put this stuff in an Appendix?} +\subsection{Addition and Subtraction} + +According to the IEEE-754 standard, if $e_1 < e_2$, then the preferred form of $f_1 + f_2$ is: +\begin{align} + m_1 \beta^{e_1} \pm m_2 \beta^{e_2} &= (m_1 \pm \beta^{e_2 - e_1} m_2) \beta^{e_1} +\end{align} + +This is equivelant to shifting the fixed point in $m_2$ by $e_2 - e_1$ to the left, and then performing fixed point addition or subtraction. If the result of the addition/subtraction requires a carry/borrow, divide result by $\beta$ (ie: shift digits by $1$ the right) and increment/decrement exponent. Then normalise the result (subtract leading zeros in mantissa from the exponent). Lastly perform the rounding operation; if this would generate a carry/borrow, shift right and increment/decrement exponent again, repeat. + + +\subsection{Multiplication and Division} +\begin{align} + m_1 \beta^{e_1} \times m_2 \beta^{e_2} &= (m_1 \times m_2 ) \beta^{e_1 + e_2} +\end{align} + +\begin{align} + m_1 \beta^{e_1} \div m_2 \beta^{e_2} &= (m_1 \div m_2 ) \beta^{e_1 - e_2} +\end{align} + +Multiplication and Division are not inverses. + +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}. diff --git a/chapters/Background/Floats/PrecisionIssues.tex b/chapters/Background/Floats/PrecisionIssues.tex new file mode 100644 index 0000000..ff23a17 --- /dev/null +++ b/chapters/Background/Floats/PrecisionIssues.tex @@ -0,0 +1,6 @@ +\subsection{Precision and Rounding Issues}\label{Precision and Rounding} + + +Goldberg's 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}. diff --git a/chapters/Background/Floats/Visualisation.tex b/chapters/Background/Floats/Visualisation.tex new file mode 100644 index 0000000..1588b03 --- /dev/null +++ b/chapters/Background/Floats/Visualisation.tex @@ -0,0 +1,35 @@ + +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 as straight lines - the distance between points is always constant. + +\begin{comment} +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. +\end{comment} + +%\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} + \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} + \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} diff --git a/chapters/Background/GMP.tex b/chapters/Background/GMP.tex new file mode 100644 index 0000000..c358f09 --- /dev/null +++ b/chapters/Background/GMP.tex @@ -0,0 +1,3 @@ +The GNU Multiple Precision Library implements arbitrary precision arithmetic for integers, floating point numbers, and rationals\cite{granlund2014}. + +The MPFR library is based on GMP but implements IEEE-754 rounding\cite{fousse2007mpfr}. diff --git a/chapters/Background/Overview.tex b/chapters/Background/Overview.tex new file mode 100644 index 0000000..7b4256b --- /dev/null +++ b/chapters/Background/Overview.tex @@ -0,0 +1 @@ +An overview will go here. diff --git a/chapters/Background/RasterAndVectorGraphics.tex b/chapters/Background/RasterAndVectorGraphics.tex new file mode 100644 index 0000000..f729ece --- /dev/null +++ b/chapters/Background/RasterAndVectorGraphics.tex @@ -0,0 +1,32 @@ +At a fundamental level everything that is seen on a display device is represented as either a vector or raster image. These images can be stored as stand alone documents or embedded within a more complex document format capable of containing many other types of information. + +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}). + +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}. + +The left side of the Figures are a vector image. When scaled, the edges maintain a smooth appearance which is limited by the resolution of the display rather than the image itself. %Vector images are well suited to high quality digital art\footnote{Figure \ref{vector-vs-raster} is not to be taken as an example of this.} and text. + + +\newlength\imageheight +\newlength\imagewidth +\settoheight\imageheight{\includegraphics{figures/fox-raster.png}} +\settowidth\imagewidth{\includegraphics{figures/fox-raster.png}} + +%Height: \the\imageheight +%Width: \the\imagewidth + + +\begin{figure}[H] + \centering + \includegraphics[scale=0.7528125]{figures/fox-vector.pdf} + \includegraphics[scale=0.7528125]{figures/fox-raster.png} + \caption{Original Vector and Raster Images}\label{vector-vs-raster} +\end{figure} % As much as I hate to break up the party, these fit best over the page (at the moment) +\begin{figure}[H] + \centering + \includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{figures/fox-vector.pdf} + \includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{figures/fox-raster.png} + \caption{Scaled Vector and Raster Images}\label{vector-vs-raster-scaled} +\end{figure} diff --git a/chapters/Background/Rationals.tex b/chapters/Background/Rationals.tex new file mode 100644 index 0000000..8b13789 --- /dev/null +++ b/chapters/Background/Rationals.tex @@ -0,0 +1 @@ + diff --git a/chapters/Background/Rendering.tex b/chapters/Background/Rendering.tex new file mode 100644 index 0000000..45a0167 --- /dev/null +++ b/chapters/Background/Rendering.tex @@ -0,0 +1,11 @@ +%\subsection{Overview} +\input{chapters/Background/Rendering/Overview} +\subsection{Straight Lines} +\input{chapters/Background/Rendering/StraightLines} +\subsection{B\'{e}zier Splines} +\input{chapters/Background/Rendering/BezierSplines} +\subsection{Filled Paths} +\subsection{Compositing} +\subsection{Fonts} +\input{chapters/Background/Rendering/Fonts} + diff --git a/chapters/Background/Rendering/BezierSplines.tex b/chapters/Background/Rendering/BezierSplines.tex new file mode 100644 index 0000000..fd0ec01 --- /dev/null +++ b/chapters/Background/Rendering/BezierSplines.tex @@ -0,0 +1,69 @@ + +Splines are continuous curves formed from piecewise polynomial segments. A polynomial of $n$th degree is defined by $n$ constants $\{a_0, a_1, ... a_n\}$ and: +\begin{align} + y(x) &= \displaystyle\sum_{k=0}^n a_k x^k +\end{align} + + \begin{comment} +Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and drawing straight lines between $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}. + +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}. + +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: +\begin{align} + P(t) &= \displaystyle\sum_{j=0}^{n} B_j^n(t) P_j +\end{align} +Where $t \epsilon [0,1]$ is a control parameter. The polynomials $B_j^n(t)$ are Bernstein Basis Polynomials which are defined as: +\begin{align} + B_j^n(t) &= \left(^n_j\right) t^j\left(1-t\right)^{n-j} \quad \quad j=0,1,...,n \\ + \text{Where } \left(^n_j\right) &= \frac{n!}{n!(n-j)!} \quad \text{ (The Binomial Coefficients)} +\end{align} +From these definitions it should be apparent that in all cases, $P(0) = P_0$ and $P(1) = P_n$. An $n = 1$ B{\'e}zier Curve is a straight line. + +Algorithms for rendering B{\'e}zier's may simply sample $P(t)$ for suffiently many values of $t$ --- enough so that the spacing between successive points is always less than one pixel distance. Alternately, a smaller number of points may be sampled with the resulting points connected by straight lines using one of the algorithms discussed in Section \ref{Straight Lines}. + +De Casteljau's algorithm of 1959 is often used for decomposing B{\'e}ziers into line segments\cite{computergraphics2, knuth1983metafont}. This algorithm subdivides the original curve with $n$ control points $\left\{P_0, ... P_n\right\}$ into $2$ halves, each with $n$ control points: $\left\{Q_0, ... Q_n\right\}$ and $\left\{R_0, ... R_n\right\}$; when iterated, the produced points will converge to $P(t)$. As a tensor equation this subdivision can be expressed as\cite{goldman_thefractal}: +\begin{align} + Q_i = \left(\frac{\left(^n_j\right)}{2^j}\right) P_i &\text{ and } R_i = \left(\frac{\left(^{n-j}_{n-k}\right)}{2^{n-j}}\right) P_i +\end{align} + + +%In much of the literature it is taken as trivial that it is only necessary to specify the control points of a B{\'e}zier in order to be able to render it at any level of detail\cite{knuth1983metafont, computergraphics2}. Recently, Goldman presented an argument that B{\'e}zier's could be considered as fractal in nature, because the De Casteljau algorithm may be modified to be expressed the polynomial $P(t)$ as the result of iterated function system\cite{goldman_thefractal}. If this argument is correct, any primitive that can be described soley in terms of B{\'e}zier Curves may also be considered as fractal in nature. Ideally all these primitives may be rendered at any level of detail or ``zoom'' desired; however, computation of the pixel locations of the curve will be subject to the precision limits of the numerical representation which is used; we discuss these issues in Section \ref{Number Representations}. + + +\begin{figure}[H] +\centering +\begin{minipage}[t]{0.3\textwidth} +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{figures/spline_labelled.pdf} +\end{figure} +\end{minipage} +\begin{minipage}[t]{0.3\textwidth} +\begin{minted}{xml} + + +\end{minted} +\begin{minted}{postscript} +% PostScript commands for a similar spline +0 300 moveto +0 300 200 210 90 140 curveto +-20 70 200 0 200 0 curveto stroke +\end{minted} +\end{minipage} +\begin{minipage}[t]{0.3\textwidth} +\begin{figure}[H] + \centering + \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} +\end{figure} diff --git a/chapters/Background/Rendering/Compositing.tex b/chapters/Background/Rendering/Compositing.tex new file mode 100644 index 0000000..e2ba1e9 --- /dev/null +++ b/chapters/Background/Rendering/Compositing.tex @@ -0,0 +1,17 @@ +%\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_T$ has 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 for $g_T$ and $b_T$)} +\end{align} +It should be apparent that alpha values of $1$ 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. + diff --git a/chapters/Background/Rendering/Fonts.tex b/chapters/Background/Rendering/Fonts.tex new file mode 100644 index 0000000..910897c --- /dev/null +++ b/chapters/Background/Rendering/Fonts.tex @@ -0,0 +1,21 @@ +\begin{figure}[H] +\begin{minipage}[t]{0.5\textwidth} +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{figures/z.pdf} +\end{figure} +\end{minipage} +\begin{minipage}[t]{0.5\textwidth} +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{figures/z.png} +\end{figure} +\end{minipage} + \caption{a) Vector glyph for the letter Z b) Screenshot showing B{\'e}zier control points in Inkscape}\label{zglyph} +\end{figure} + +A the term ``font'' refers to a set of images used to represent text on a graphical display. In 1983, Donald Knuth published ``The METAFONT Book'' which described a vector approach to specifying fonts and a program for creating these fonts\cite{knuth1983metafont}. Previously, only rasterised font images (glyphs) were popular; as can be seen from the zooming in Figure \ref{vector-vs-raster-scaled} this can be problematic given the prevelance of textual information at different scales and on different resolution displays. + +Knuth used B{\'e}zier Cubic Splines to define ``pleasing'' curves in METAFONT, and this approach is still used in modern vector fonts. Since the paths used to render an individual glyph are used far more commonly than general curves, document formats do not require such curves to be specified in situ, but allow for a choice between a number of internal fonts or externally specified fonts. In the case of Knuth's typesetting language \TeX, fonts were intended to be created using METAFONT\cite{knuth1983metafont}. Figure \ref{zglyph} shows a $\mathscr{Z}$ (script Z) produced by {\LaTeX} with B{\'e}zier cubics identified. + + diff --git a/chapters/Background/Rendering/Overview.tex b/chapters/Background/Rendering/Overview.tex new file mode 100644 index 0000000..00352de --- /dev/null +++ b/chapters/Background/Rendering/Overview.tex @@ -0,0 +1,3 @@ +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}. diff --git a/chapters/Background/Rendering/StraightLines.tex b/chapters/Background/Rendering/StraightLines.tex new file mode 100644 index 0000000..a1a1393 --- /dev/null +++ b/chapters/Background/Rendering/StraightLines.tex @@ -0,0 +1,30 @@ +It is well known that in cartesian coordinates, a line between points $(x_1, y_1)$ and $(x_2, y_2)$, can be described by: +\begin{align} + y(x) &= m x + c\label{eqn_line} \quad \text{ on $x \in [x_1, x_2]$} + \text{ for } m = \frac{(y_2 - y_1)}{(x_2 - x_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}. + +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$. + +Bresenham's Line Algorithm was developed in 1965 with the motivation of controlling a particular mechanical plotter in use at the time\cite{bresenham1965algorithm}. The plotter's motion was confined to move between discrete positions on a grid one cell at a time, horizontally, vertically or diagonally. As a result, the algorithm presented by Bresenham requires only integer addition and subtraction, and it is easily adopted for drawing pixels on a raster display. Because integer operations are exact, only an error in the calculation of the line end points will affect the rendering. + +%Bresenham himself points out that rasterisation processes have existed since long before the first computer displays\cite{bresenham1996pixel}. + +In Figure \ref{rasterising-line} a) and b) we illustrate the rasterisation of a line width a single pixel width. The path followed by Bresenham's algorithm is shown. It can be seen that the pixels which are more than half filled by the line are set by the algorithm. This causes a jagged effect called aliasing which is particularly noticable on low resolution displays. From a signal processing point of view this can be understood as due to the sampling of a continuous signal on a discrete grid\cite{wu1991anefficient}. + +Figure \ref{rasterising-line} c) shows an (idealised) antialiased rendering of the line. The pixel intensity has been set to the average of the line and background colours over that pixel. Such an ideal implementation would be impractically computationally expensive on real devices\cite{elias2000graphics}. In 1991 Wu introduced an algorithm for drawing approximately antialiased lines which, while equivelant in results to existing algorithms by Fujimoto and Iwata, set the state of the art in performance\cite{wu1991anefficient}\footnote{Techniques for antialiasing primitives other than straight lines are discussed in some detail in Chapter 4 of ``Computer Graphics'' \cite{computergraphics2}}. +. + + + +\begin{figure}[H] + \centering + \includegraphics[width=0.25\textwidth]{figures/line1.pdf} + \includegraphics[width=0.25\textwidth]{figures/line2.pdf} + \includegraphics[width=0.25\textwidth]{figures/line3.pdf} + \caption{Rasterising a Straight Line}\label{rasterising-line} + a) Before Rasterisation b) Bresenham's Algorithm c) Anti-aliased Line (Idealised) +\end{figure} diff --git a/chapters/Background/Standards.tex b/chapters/Background/Standards.tex new file mode 100644 index 0000000..62cf5db --- /dev/null +++ b/chapters/Background/Standards.tex @@ -0,0 +1,9 @@ +%\subsection{Overview} +% All this stuff can probably be appendicised +%\input{chapters/Background/Standards/Overview} +%\subsection{Interpreted Models: PostScript and PDF} +%\input{chapters/Background/Standards/Interpreted} +%\subsection{The Document Object Model: SVG} +%\input{chapters/Background/Standards/DOM} +%\subsection{Precision Specified By Standards} +\input{chapters/Background/Standards/Precision} diff --git a/chapters/Background/Standards/DOM.tex b/chapters/Background/Standards/DOM.tex new file mode 100644 index 0000000..c12b3f1 --- /dev/null +++ b/chapters/Background/Standards/DOM.tex @@ -0,0 +1,98 @@ +The Document Object Model (DOM) represents a document as a tree like data structure with the document as a root node. The elements of the document are represented as children of either this root node or of a parent element. In addition, elements may have attributes which contain information about that particular element. + +The World Wide Web Consortium (W3C) is an organisation devoted to the development of standards for structuring and rendering web pages based on industry needs. The DOM is used in and described by several W3C recommendations including XML\cite{xml2008-1.0}, HTML\cite{html2014-draft} and SVG\cite{svg2011-1.1}. XML is a general language which is intended for representing any tree-like structure using the DOM, whilst HTML and SVG are specifically intended for representing text documents and more general graphics respectively. These languages make use of Cascading Style Sheets (CSS)\cite{css2011-level2} for specifying the appearance of elements. + +%Version 5 of the Hypertext Markup Language (HTML5) is currently a candidate recommendation which aims to standardise the state of the art in technologies relating to web based documents. In HTML5 it is possible to achieve almost any level of control over both the structure and rendering of a document desirable. In particular, the language Javascript (based upon ECMAScript \cite{ecma-262}) can be used to dynamically alter a HTML5 document in response to user input or other events, including communication with HTTP servers. + +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{}. + +%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// elements to position rectangles and \verb// 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} + +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. + +For example, the following Javascript acting on the DOM described in Figure \ref{SVG} will change the fill colour of the curved region. +\begin{minted}{javascript} +var node = document.getElementById("curvedshape"); // Find the node by its unique id +node.style.fill = "#000000"; // Change the ``style'' attribute and set the CSS fill colour +\end{minted} + +To illustrate the power of this technique we have produced an example to generate an SVG interactively using HTML. The example generates successive iterations of a particular type of fractal curve first described by Koch\cite{koch1904surune} in 1904 and a popular example in modern literature \cite{goldman_thefractal}. Unfortunately as including W3C HTML directly in a standard PDF is not possible, we are only able to provide some examples of the output as static images in Figure \ref{koch}. The W3C has produced a primer describing the use of HTML5 and Javascript to produce interactive SVG's\cite{w3c2010svghtmlprimer}, and the HTML5 and SVG standards themselves include several examples. + +In HTML5, Javascript is not restricted to merely manipulating the DOM to alter the appearance of a document. The \verb// tag and associated API provide a means to directly set the values of pixels on a display. This sort of low level API is inteded for performance intensive graphical applications such as web based games\footnote{For an example by the author including both the canvas2d and experimental WebGL APIs see \url{http://rabbitgame.net}}. As Hayes points out, there is some similarity between the \verb// API, the SVG path descriptions and the PostScript interpreted approach to drawing\cite{hayes2012pixels}. + +\begin{figure}[H] +\begin{minipage}[t]{0.65\textwidth} +\begin{minted}{xml} + + + + + + + + + + + + + + +\end{minted} +\end{minipage} +\begin{minipage}[t]{0.3\textwidth} + \begin{figure}[H] + \centering + \includegraphics[width=1\textwidth]{figures/shape.pdf} + \end{figure} +\end{minipage} + \caption{Vector image and a possible SVG representation}\label{SVG} +\end{figure} + +\begin{figure}[H] +\begin{minipage}[t]{0.33\textwidth} + \begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{figures/koch1.pdf} + \end{figure} +\end{minipage} +\begin{minipage}[t]{0.33\textwidth} + \begin{figure}[H] + \centering + \includegraphics[width=1\textwidth]{figures/koch2.pdf} + \end{figure} +\end{minipage} +\begin{minipage}[t]{0.33\textwidth} + \begin{figure}[H] + \centering + \includegraphics[width=0.9\textwidth]{figures/koch3.pdf} + \end{figure} +\end{minipage} + \caption{Koch ``snowflakes'' generated using Javascript to modify an SVG DOM. The interactive HTML5 document can be found at \url{http://szmoore.net/ipdf/sam/figures/koch.html}}\label{koch} +\end{figure} + + +\end{comment} diff --git a/chapters/Background/Standards/Interpreted.tex b/chapters/Background/Standards/Interpreted.tex new file mode 100644 index 0000000..2c58f25 --- /dev/null +++ b/chapters/Background/Standards/Interpreted.tex @@ -0,0 +1,74 @@ +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{}. +\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}. + + + +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}. + +%Figure \ref{PS} shows a vector image and one possible way to express this image in PostScript. + +%There are some limitations in PostScript's model. As mentioned in Section \ref{Compositing}, since PostScript predates Porter and Duff Compositing, there is no concept of transparency. In fact, using tools to convert between the SVG image in Figure \ref{SVG} and PostScript will simply rasterise the image and embed the rastered image in PostScript\footnote{For Figure \ref{SVG} converted using the Inkscape SVG editor: \url{http://szmoore.net/ipdf/figures/shape-svg-converted-to.ps}} + +%Another limitation of PostScript is that the model of a document as a static page, convenient for printers which literally produce static pages, is unable to include interactive or dynamic elements. Dynamic PostScript attempted to fix this problem, but ``never caught on''\cite{hayes2012pixels}. + +\begin{comment} +\begin{figure}[H] +\begin{minipage}[t]{0.65\textwidth} +\begin{minted}{postscript} +%!PS-Adobe-3.0 EPSF-3.0 +%%BoundingBox: 0 -1 85 150 +% These lines are comments to aid in human understanding +% Define an operator to produce a rectangular path +/re { exch dup neg 3 1 roll 5 3 roll moveto 0 rlineto + 0 exch rlineto 0 rlineto closepath } bind def +% Operator to produce the path for the first rectangle +/re1 { 24.613 133.001 24 -120 re } bind def +% Operator to produce the path for the second rectangle +/re2 { 10.215 45.001 48 -16 re } bind def +% Operator which will produce the curved path +/curve { 46.215 1.001 moveto + 46.215 1.001 91.812 11.399 71.812 35.399 curveto + 51.812 59.399 29.414 33.802 51.812 59.399 curveto + 74.215 85.001 93.414 45.802 74.215 85.001 curveto + 55.016 125.001 61.414 49.802 46.215 75.399 curveto + 31.016 101.001 56.613 126.598 56.613 126.598 curveto + 56.613 126.598 88.613 166.598 56.613 137.802 curveto + 24.613 109.001 -18.586 83.399 9.414 50.598 curveto + 37.414 17.802 45.414 1.001 45.414 1.001 curveto +closepath } bind def +% Set stroke properties +0.8 setlinewidth 0 setlinecap 0 setlinejoin [] + 0.0 setdash 4 setmiterlimit +% Draw the straight line +0 setgray 0.613 149.001 moveto 83.812 0.2 lineto fill +% Fill and outline the first rectangular path +0 0 1 setrgbcolor re1 fill 0 setgray re1 stroke +% Fill and outline the curved shape +1 0 0 setrgbcolor curve fill 0 setgray curve stroke +% Fill and outline the second rectangle +0 1 0 setrgbcolor re2 fill 0 setgray re2 stroke +showpage +\end{minted} +\end{minipage} +\begin{minipage}[t]{0.3\textwidth} + \begin{figure}[H] + \centering + \includegraphics[width=1\textwidth]{figures/shape.eps} + \end{figure} +\end{minipage} + \caption{Vector image and a possible PostScript representation}\label{PS} +\end{figure} + + +\subsubsection{{\TeX}, METAFONT and {\LaTeX}} + +Knuth's ``The {\TeX}book''\cite{knuth1984texbook} and ``The METAFONT book''\cite{knuth1983metafont} define two complementary programming languages for typesetting documents. Wheras PostScript may be considered an interpreted language, in that it can be produced in a human readable form which is also readable by an interpreter, {\TeX} is a compiled language; a program parses human readable {\TeX} to produce a machine readable format DVI (``DeVice Independent''). A DVI interpreter might be thought of as a virtual ``Display Processor'' for drawing vector graphics directly (as defined in the earlier editions of ``Computer Graphics''\cite{computergraphics2}). + +DVI itself is not a widely used format for sharing documents. However, an system based upon {\TeX} called {\LaTeX} which includes libraries for advanced typesetting and programs that ultimately produce PDF output is particularly popular for producing technical reports and papers\footnote{The site \url{http://tex.stackexchange.com} (accessed 2014-05-22) is devoted to {\TeX} and {\LaTeX}} --- this report itself has been produced using the CTAN {\LaTeX} packages\footnote{The complete {\TeX} source code to produce this document can be found at \url{http://szmoore.net/ipdf/sam/}}. +\end{comment} diff --git a/chapters/Background/Standards/Overview.tex b/chapters/Background/Standards/Overview.tex new file mode 100644 index 0000000..2adef7e --- /dev/null +++ b/chapters/Background/Standards/Overview.tex @@ -0,0 +1,6 @@ +The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper on shading polygons\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 commands for producing an image on a static sheets of paper (Interpreted Model) 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. diff --git a/chapters/Background/Standards/Precision.tex b/chapters/Background/Standards/Precision.tex new file mode 100644 index 0000000..afb5f24 --- /dev/null +++ b/chapters/Background/Standards/Precision.tex @@ -0,0 +1,25 @@ + +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''. +\begin{comment} +\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. +\end{comment} + +\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. +\begin{comment} +\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. +\end{comment} diff --git a/chapters/Background_Compositing.tex b/chapters/Background_Compositing.tex deleted file mode 100644 index 453fc7a..0000000 --- a/chapters/Background_Compositing.tex +++ /dev/null @@ -1 +0,0 @@ -In 1984, Porter and Duff introduced Digital Compositing for rastered images\cite{porter1984compositing}. diff --git a/chapters/Background_DOM.tex b/chapters/Background_DOM.tex deleted file mode 100644 index a388230..0000000 --- a/chapters/Background_DOM.tex +++ /dev/null @@ -1,93 +0,0 @@ -The Document Object Model (DOM) represents a document as a tree like data structure with the document as a root node. The elements of the document are represented as children of either this root node or of a parent element. In addition, elements may have attributes which contain information about that particular element. - -The World Wide Web Consortium (W3C) is an organisation devoted to the development of standards for structuring and rendering web pages based on industry needs. The DOM is used in and described by several W3C recommendations including XML\cite{xml2008-1.0}, HTML\cite{html2014-draft} and SVG\cite{svg2011-1.1}. XML is a general language which is intended for representing any tree-like structure using the DOM, whilst HTML and SVG are specifically intended for representing visual information to humans. These languages make use of Cascading Style Sheets (CSS)\cite{css2011-level2} for specifying the appearance of elements. - -Version 5 of the Hypertext Markup Language (HTML5) is currently a candidate recommendation which aims to standardise the state of the art in technologies relating to web based documents. In HTML5 it is possible to achieve almost any level of control over both the structure and rendering of a document desirable. In particular, the language Javascript (based upon ECMAScript \cite{ecma-262}) can be used to dynamically alter a HTML5 document in response to user input or other events, including communication with HTTP servers. - -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. 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// elements to position rectangles and \verb// 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. - - -\subsubsection{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. - -For example, the following Javascript acting on the DOM described in Figure \ref{SVG} will change the fill colour of the curved region. -\begin{minted}{javascript} -var node = document.getElementById("curvedshape"); // Find the node by its unique id -node.style.fill = "#000000"; // Change the ``style'' attribute and set the CSS fill colour -\end{minted} - -To illustrate the power of this technique we have produced an example to generate an SVG interactively using HTML. The example generates successive iterations of a particular type of fractal curve first described by Koch\cite{koch1904surune} in 1904 and a popular example in modern literature \cite{goldman_thefractal}. Unfortunately as including W3C HTML directly in a standard PDF is not possible, we are only able to provide some examples of the output as static images in Figure \ref{koch}. The W3C has produced a primer describing the use of HTML5 and Javascript to produce interactive SVG's\cite{w3c2010svghtmlprimer}, and the HTML5 and SVG standards themselves include several examples. - -In HTML5, Javascript is not restricted to merely manipulating the DOM to alter the appearance of a document. The \verb// tag and associated API provide a means to directly set the values of pixels on a display. This sort of low level API is inteded for performance intensive graphical applications such as web based games\footnote{For an example by the author including both the canvas2d and experimental WebGL APIs see \url{http://rabbitgame.net}}. As Hayes points out, there is some similarity between the \verb// API, the SVG path descriptions and the PostScript interpreted approach to drawing\cite{hayes2012pixels}. - -\begin{figure}[H] -\begin{minipage}[t]{0.65\textwidth} -\begin{minted}{xml} - - - - - - - - - - - - - - -\end{minted} -\end{minipage} -\begin{minipage}[t]{0.3\textwidth} - \begin{figure}[H] - \centering - \includegraphics[width=1\textwidth]{figures/shape.pdf} - \end{figure} -\end{minipage} - \caption{Vector image and a possible SVG representation}\label{SVG} -\end{figure} - -\begin{figure}[H] -\begin{minipage}[t]{0.33\textwidth} - \begin{figure}[H] - \centering - \includegraphics[width=0.8\textwidth]{figures/koch1.pdf} - \end{figure} -\end{minipage} -\begin{minipage}[t]{0.33\textwidth} - \begin{figure}[H] - \centering - \includegraphics[width=1\textwidth]{figures/koch2.pdf} - \end{figure} -\end{minipage} -\begin{minipage}[t]{0.33\textwidth} - \begin{figure}[H] - \centering - \includegraphics[width=0.9\textwidth]{figures/koch3.pdf} - \end{figure} -\end{minipage} - \caption{Koch ``snowflakes'' generated using Javascript to modify an SVG DOM. The interactive HTML5 document can be found at \url{http://szmoore.net/ipdf/sam/figures/koch.html}}\label{koch} -\end{figure} - - diff --git a/chapters/Background_Fonts.tex b/chapters/Background_Fonts.tex deleted file mode 100644 index 910897c..0000000 --- a/chapters/Background_Fonts.tex +++ /dev/null @@ -1,21 +0,0 @@ -\begin{figure}[H] -\begin{minipage}[t]{0.5\textwidth} -\begin{figure}[H] - \centering - \includegraphics[width=0.7\textwidth]{figures/z.pdf} -\end{figure} -\end{minipage} -\begin{minipage}[t]{0.5\textwidth} -\begin{figure}[H] - \centering - \includegraphics[width=0.7\textwidth]{figures/z.png} -\end{figure} -\end{minipage} - \caption{a) Vector glyph for the letter Z b) Screenshot showing B{\'e}zier control points in Inkscape}\label{zglyph} -\end{figure} - -A the term ``font'' refers to a set of images used to represent text on a graphical display. In 1983, Donald Knuth published ``The METAFONT Book'' which described a vector approach to specifying fonts and a program for creating these fonts\cite{knuth1983metafont}. Previously, only rasterised font images (glyphs) were popular; as can be seen from the zooming in Figure \ref{vector-vs-raster-scaled} this can be problematic given the prevelance of textual information at different scales and on different resolution displays. - -Knuth used B{\'e}zier Cubic Splines to define ``pleasing'' curves in METAFONT, and this approach is still used in modern vector fonts. Since the paths used to render an individual glyph are used far more commonly than general curves, document formats do not require such curves to be specified in situ, but allow for a choice between a number of internal fonts or externally specified fonts. In the case of Knuth's typesetting language \TeX, fonts were intended to be created using METAFONT\cite{knuth1983metafont}. Figure \ref{zglyph} shows a $\mathscr{Z}$ (script Z) produced by {\LaTeX} with B{\'e}zier cubics identified. - - diff --git a/chapters/Background_Interpreted.tex b/chapters/Background_Interpreted.tex deleted file mode 100644 index 55308be..0000000 --- a/chapters/Background_Interpreted.tex +++ /dev/null @@ -1,60 +0,0 @@ -\subsubsection{PostScript} - -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. 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. Figure \ref{PS} shows a vector image and one possible way to express this image in PostScript. PostScript was and is still widely used in printing of documents onto paper; many printers execute postscript directly, and newer formats including PDFs must still be converted into PostScript by printer drivers\cite{pdfref17, cheng2002portable}. - -There are some limitations in PostScript's model. As mentioned in Section \ref{Compositing}, since PostScript predates Porter and Duff Compositing, there is no concept of transparency. In fact, using tools to convert between the SVG image in Figure \ref{SVG} and PostScript will simply rasterise the image and embed the rastered image in PostScript\footnote{For Figure \ref{SVG} converted using the Inkscape SVG editor: \url{http://szmoore.net/ipdf/figures/shape-svg-converted-to.ps}} - -Another limitation of PostScript is that the model of a document as a static page, convenient for printers which literally produce static pages, is unable to include interactive or dynamic elements. Dynamic PostScript attempted to fix this problem, but ``never caught on''\cite{hayes2012pixels}. - -\begin{figure}[H] -\begin{minipage}[t]{0.65\textwidth} -\begin{minted}{postscript} -%!PS-Adobe-3.0 EPSF-3.0 -%%BoundingBox: 0 -1 85 150 -% These lines are comments to aid in human understanding -% Define an operator to produce a rectangular path -/re { exch dup neg 3 1 roll 5 3 roll moveto 0 rlineto - 0 exch rlineto 0 rlineto closepath } bind def -% Operator to produce the path for the first rectangle -/re1 { 24.613 133.001 24 -120 re } bind def -% Operator to produce the path for the second rectangle -/re2 { 10.215 45.001 48 -16 re } bind def -% Operator which will produce the curved path -/curve { 46.215 1.001 moveto - 46.215 1.001 91.812 11.399 71.812 35.399 curveto - 51.812 59.399 29.414 33.802 51.812 59.399 curveto - 74.215 85.001 93.414 45.802 74.215 85.001 curveto - 55.016 125.001 61.414 49.802 46.215 75.399 curveto - 31.016 101.001 56.613 126.598 56.613 126.598 curveto - 56.613 126.598 88.613 166.598 56.613 137.802 curveto - 24.613 109.001 -18.586 83.399 9.414 50.598 curveto - 37.414 17.802 45.414 1.001 45.414 1.001 curveto -closepath } bind def -% Set stroke properties -0.8 setlinewidth 0 setlinecap 0 setlinejoin [] - 0.0 setdash 4 setmiterlimit -% Draw the straight line -0 setgray 0.613 149.001 moveto 83.812 0.2 lineto fill -% Fill and outline the first rectangular path -0 0 1 setrgbcolor re1 fill 0 setgray re1 stroke -% Fill and outline the curved shape -1 0 0 setrgbcolor curve fill 0 setgray curve stroke -% Fill and outline the second rectangle -0 1 0 setrgbcolor re2 fill 0 setgray re2 stroke -showpage -\end{minted} -\end{minipage} -\begin{minipage}[t]{0.3\textwidth} - \begin{figure}[H] - \centering - \includegraphics[width=1\textwidth]{figures/shape.eps} - \end{figure} -\end{minipage} - \caption{Vector image and a possible PostScript representation}\label{PS} -\end{figure} - -\subsubsection{{\TeX}, METAFONT and {\LaTeX}} - -Knuth's ``The {\TeX}book''\cite{knuth1984texbook} and ``The METAFONT book''\cite{knuth1983metafont} define two complementary programming languages for typesetting documents. Wheras PostScript may be considered an interpreted language, in that it can be produced in a human readable form which is also readable by an interpreter, {\TeX} is a compiled language; a program parses human readable {\TeX} to produce a machine readable format DVI (``DeVice Independent''). A DVI interpreter might be thought of as a virtual ``Display Processor'' for drawing vector graphics directly (as defined in the earlier editions of ``Computer Graphics''\cite{computergraphics2}). - -DVI itself is not a widely used format for sharing documents. However, an system based upon {\TeX} called {\LaTeX} which includes libraries for advanced typesetting and programs that ultimately produce PDF output is particularly popular for producing technical reports and papers\footnote{The site \url{http://tex.stackexchange.com} (accessed 2014-05-22) is devoted to {\TeX} and {\LaTeX}} --- this report itself has been produced using the CTAN {\LaTeX} packages\footnote{The complete {\TeX} source code to produce this document can be found at \url{http://szmoore.net/ipdf/sam/}}. diff --git a/chapters/Background_Lines.tex b/chapters/Background_Lines.tex deleted file mode 100644 index 7ae437d..0000000 --- a/chapters/Background_Lines.tex +++ /dev/null @@ -1,28 +0,0 @@ -It is well known that in cartesian coordinates, a line between points $(x_1, y_1)$ and $(x_2, y_2)$, can be described by: -\begin{align} - y(x) &= m x + c\label{eqn_line} \quad \text{ on $x \in [x_1, x_2]$} - \text{ for } m = \frac{(y_2 - y_1)}{(x_2 - x_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}. - -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$. - -Bresenham's Line Algorithm was developed in 1965 with the motivation of controlling a particular mechanical plotter in use at the time\cite{bresenham1965algorithm}. The plotter's motion was confined to move between discrete positions on a grid one cell at a time, horizontally, vertically or diagonally. As a result, the algorithm presented by Bresenham requires only integer addition and subtraction, and it is easily adopted for drawing pixels on a raster display. Bresenham himself points out that rasterisation processes have existed since long before the first computer displays\cite{bresenham1996pixel}. - -In Figure \ref{rasterising-line} a) and b) we illustrate the rasterisation of a line width a single pixel width. The path followed by Bresenham's algorithm is shown. It can be seen that the pixels which are more than half filled by the line are set by the algorithm. This causes a jagged effect called aliasing which is particularly noticable on low resolution displays. From a signal processing point of view this can be understood as due to the sampling of a continuous signal on a discrete grid\cite{wu1991anefficient}. - -Figure \ref{rasterising-line} c) shows an (idealised) antialiased rendering of the line. The pixel intensity has been set to the average of the line and background colours over that pixel. Such an ideal implementation would be impractically computationally expensive on real devices\cite{elias2000graphics}. In 1991 Wu introduced an algorithm for drawing approximately antialiased lines which, while equivelant in results to existing algorithms by Fujimoto and Iwata, set the state of the art in performance\cite{wu1991anefficient}\footnote{Techniques for antialiasing primitives other than straight lines are discussed in some detail in Chapter 4 of ``Computer Graphics'' \cite{computergraphics2}}. -. - - - -\begin{figure}[H] - \centering - \includegraphics[width=0.25\textwidth]{figures/line1.pdf} - \includegraphics[width=0.25\textwidth]{figures/line2.pdf} - \includegraphics[width=0.25\textwidth]{figures/line3.pdf} - \caption{Rasterising a Straight Line}\label{rasterising-line} - a) Before Rasterisation b) Bresenham's Algorithm c) Anti-aliased Line (Idealised) -\end{figure} diff --git a/chapters/Background_Raster-vs-Vector.tex b/chapters/Background_Raster-vs-Vector.tex deleted file mode 100644 index c4ef568..0000000 --- a/chapters/Background_Raster-vs-Vector.tex +++ /dev/null @@ -1,32 +0,0 @@ -At a fundamental level everything that is seen on a display device is represented as either a vector or raster image. These images can be stored as stand alone documents or embedded within a more complex document format capable of containing many other types of information. - -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}). - -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''. - -The left side of the Figures are a vector image. When scaled, the edges maintain a smooth appearance which is limited by the resolution of the display rather than the image itself. %Vector images are well suited to high quality digital art\footnote{Figure \ref{vector-vs-raster} is not to be taken as an example of this.} and text. - - -\newlength\imageheight -\newlength\imagewidth -\settoheight\imageheight{\includegraphics{figures/fox-raster.png}} -\settowidth\imagewidth{\includegraphics{figures/fox-raster.png}} - -%Height: \the\imageheight -%Width: \the\imagewidth - - -\begin{figure}[H] - \centering - \includegraphics[scale=0.7528125]{figures/fox-vector.pdf} - \includegraphics[scale=0.7528125]{figures/fox-raster.png} - \caption{Original Vector and Raster Images}\label{vector-vs-raster} -\end{figure} % As much as I hate to break up the party, these fit best over the page (at the moment) -\begin{figure}[H] - \centering - \includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{figures/fox-vector.pdf} - \includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{figures/fox-raster.png} - \caption{Scaled Vector and Raster Images}\label{vector-vs-raster-scaled} -\end{figure} diff --git a/chapters/Background_Spline.tex b/chapters/Background_Spline.tex deleted file mode 100644 index d54ef10..0000000 --- a/chapters/Background_Spline.tex +++ /dev/null @@ -1,69 +0,0 @@ - -Splines are continuous curves formed from piecewise polynomial segments. A polynomial of $n$th degree is defined by $n$ constants $\{a_0, a_1, ... a_n\}$ and: -\begin{align} - y(x) &= \displaystyle\sum_{k=0}^n a_k x^k -\end{align} - - \begin{comment} -Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and drawing straight lines between $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}. - -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}. - -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: -\begin{align} - P(t) &= \displaystyle\sum_{j=0}^{n} B_j^n(t) P_j -\end{align} -Where $t \epsilon [0,1]$ is a control parameter. The polynomials $B_j^n(t)$ are Bernstein Basis Polynomials which are defined as: -\begin{align} - B_j^n(t) &= \left(^n_j\right) t^j\left(1-t\right)^{n-j} \quad \quad j=0,1,...,n \\ - \text{Where } \left(^n_j\right) &= \frac{n!}{n!(n-j)!} \quad \text{ (The Binomial Coefficients)} -\end{align} -From these definitions it should be apparent that in all cases, $P(0) = P_0$ and $P(1) = P_n$. An $n = 1$ B{\'e}zier Curve is a straight line. - -Algorithms for rendering B{\'e}zier's may simply sample $P(t)$ for suffiently many values of $t$ --- enough so that the spacing between successive points is always less than one pixel distance. Alternately, a smaller number of points may be sampled with the resulting points connected by straight lines using one of the algorithms discussed in Section \ref{Straight Lines}. - -De Casteljau's algorithm of 1959 is often used for approximating B{\'e}ziers\cite{computergraphics2, knuth1983metafont}. This algorithm subdivides the original $n$ control points $\left\{P_0, ... P_n\right\}$ into $2n$ points $\left\{Q_0, ... Q_n\right\}$ and $\left\{R_0, ... R_n\right\}$; when iterated, the produced points will converge to $P(t)$. As a tensor equation this subdivision can be expressed as\cite{goldman_thefractal}: -\begin{align} - Q_i = \left(\frac{\left(^n_j\right)}{2^j}\right) P_i &\text{ and } R_i = \left(\frac{\left(^{n-j}_{n-k}\right)}{2^{n-j}}\right) P_i -\end{align} - - -In much of the literature it is taken as trivial that it is only necessary to specify the control points of a B{\'e}zier in order to be able to render it at any level of detail\cite{knuth1983metafont, computergraphics2}. Recently, Goldman presented an argument that B{\'e}zier's could be considered as fractal in nature, because the De Casteljau algorithm may be modified to be expressed the polynomial $P(t)$ as the result of iterated function system\cite{goldman_thefractal}. If this argument is correct, any primitive that can be described soley in terms of B{\'e}zier Curves may also be considered as fractal in nature. Ideally all these primitives may be rendered at any level of detail or ``zoom'' desired; however, computation of the pixel locations of the curve will be subject to the precision limits of the numerical representation which is used; we discuss these issues in Section \ref{Number Representations}. - - -\begin{figure}[H] -\centering -\begin{minipage}[t]{0.3\textwidth} -\begin{figure}[H] - \centering - \includegraphics[width=0.7\textwidth]{figures/spline_labelled.pdf} -\end{figure} -\end{minipage} -\begin{minipage}[t]{0.3\textwidth} -\begin{minted}{xml} - - -\end{minted} -\begin{minted}{postscript} -% PostScript commands for a similar spline -0 300 moveto -0 300 200 210 90 140 curveto --20 70 200 0 200 0 curveto stroke -\end{minted} -\end{minipage} -\begin{minipage}[t]{0.3\textwidth} -\begin{figure}[H] - \centering - \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} -\end{figure} diff --git a/chapters/Conclusion.tex b/chapters/Conclusion.tex index 22ccc64..6d4525b 100644 --- a/chapters/Conclusion.tex +++ b/chapters/Conclusion.tex @@ -1,25 +1,5 @@ \chapter{Conclusion}\label{Conclusion} -This report has provided motivation for considering approaches to achieving an infinite level of zoom in a document. +\section{Summary of Work and Results} +\section{Considerations for Future Work} -\section{Acheived Milestones} - -\section{Areas of further work} - -\begin{itemize} - \item Continue looking for relevant literature - \item Implement all those tests mentioned in Chapter \ref{Introduction} - \item \rephrase{Actually identify the techniques I will use} {\bf THIS ONE SHOULD BE DONE BEFORE I HAND IN THE LITERATURE REVIEW!} - \item Possible Ultimate Goal: Implement (a subset) of SVG and then show an SVG document that we can render but a browser can't - \begin{itemize} - \item This means extending our viewer to be able to read (a subset) SVG - \item Can already read XML, so this shouldn't actually be too bad - \begin{itemize} - \item Emphasis on {\bf subset} - \item (I've seen the SVG standard; I'm talking about implementing the 18 pages under ``Basic Shapes''. The other 818 pages can complain to someone who cares.) - \end{itemize} - \item Suggestion to David that he probably won't like (or read): Make his octree structure specifiable as an SVG extension - \end{itemize} -\end{itemize} - -\section{Witty Conclusion Goes Here} diff --git a/chapters/Introduction.tex b/chapters/Introduction.tex index 8dc81a3..1d31e79 100644 --- a/chapters/Introduction.tex +++ b/chapters/Introduction.tex @@ -1,15 +1,11 @@ \chapter{Introduction}\label{Introduction} -\section{Motivation} +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 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 limited precision in these and other traditional document formats. - -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 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}. -We are now seeing a widespread use of mobile computing devices with touch screens, where the display size is typically much smaller than paper pages and traditional computer monitors; it seems that there is much to be gained by breaking free of the restricted precision of traditional document formats. - -\section{Overview} +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. -The remainder of this document will be organised as follows: In Chapter \ref{Proposal} we give an overview of the current state of the research in document formats, and the motivation for implementing ``infinite precision'' in a document format. We will outline our approach to research in collaboration with David Gow\cite{proposalGow}. In Chapter \ref{Background} we provide more detailed background examining the literature related to rendering, interpreting, and creating document formats, as well as possible techniques for increased and possibly infinite precision. In Chapter \ref{Progress} gives the current state of our research and the progress towards the goals outlined in Chapter \ref{Introduction}. +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{granlund2014GMP} we are able to implement correct rendering of SVG test images seperated by arbitrary distances. We demonstrate the trade off between performance cost and the accuracy of rendering diff --git a/chapters/Process.tex b/chapters/Process.tex new file mode 100644 index 0000000..a57d7e0 --- /dev/null +++ b/chapters/Process.tex @@ -0,0 +1,13 @@ +\chapter{Methods and Design} + +\section{Softare Overview} +\input{chapters/Process/SoftwareOverview} +\section{Design Process} +\input{chapters/Process/DesignProcess} +\section{Coordinate Systems and Bounds Transformations} +\input{chapters/Process/Transformations} +\section{Measurements} +\input{chapters/Process/Measurements} + + + diff --git a/chapters/Process/DesignProcess.tex b/chapters/Process/DesignProcess.tex new file mode 100644 index 0000000..d2acd08 --- /dev/null +++ b/chapters/Process/DesignProcess.tex @@ -0,0 +1,8 @@ +\subsection{Timeline} +A timeline will go here. + +\subsection{Version Control} +We used Git. + +\subsection{Debugging Methods} +We used GDB and Valgrind and copious amounts of \verb/Debug/ (ie: \verb/printf/) calls. diff --git a/chapters/Process/Measurements.tex b/chapters/Process/Measurements.tex new file mode 100644 index 0000000..770d04e --- /dev/null +++ b/chapters/Process/Measurements.tex @@ -0,0 +1,7 @@ +\subsection{Measurement Techniques} + +\begin{itemize} + \item Control panel allows inserting test images, screenshots, saving bound coordinates, changing program behaviour + \item For more automated tests, a basic scripting language is implemented + \item It has goto +\end{itemize} diff --git a/chapters/Process/SoftwareOverview.tex b/chapters/Process/SoftwareOverview.tex new file mode 100644 index 0000000..92afe9f --- /dev/null +++ b/chapters/Process/SoftwareOverview.tex @@ -0,0 +1,3 @@ +UML diagram. + + diff --git a/chapters/Process/Transformations.tex b/chapters/Process/Transformations.tex new file mode 100644 index 0000000..9f586ab --- /dev/null +++ b/chapters/Process/Transformations.tex @@ -0,0 +1,38 @@ +Equation \eqref{view-transformation} involves a division operation; in general, the result cannot be represented exactly in either a fixed or floating point format. However, if the coordinates involved are expressed as rational numbers, the result will always be exact. + + + + +\begin{enumerate} + \item Store static object bounds, transform to view before rendering + \begin{itemize} + \item Straight foward approach + \item Causes the most obvious rounding errors; impossible to render objects accurately below epsilon + \item The transformation can be performed by the GPU or CPU; the GPU is restricted to floats + \item CPU can perform transformation to arbitrary precision, but this requires all object bounds to be expressed with arbitrary precision + \end{itemize} + \item Modify all object bounds, no transformation required before rendering + \begin{itemize} + \item The rounding error on floats does not accumulate as quickly + \item Instead of one division by a very small number there are repeated divisions by larger numbers + \item However, if the document is scaled so object bounds $\to 0$ then the object will not be recoverable + \item For arbitrary precision we still need to apply all bounds transformations on the GPU + \end{itemize} + \item Keep object bounds static to some intermediate object and transform the bounds of that object + \begin{itemize} + \item We have used SVG \verb// to construct the intermediate objects; all beziers are relative to their parent path. + \item One could instead use the entire SVG bounds; however + for an SVG with a high level of detail this would have problems \rephrase{elaborate}. + \item We only need to apply some bounds transformations on the CPU + \item However as the document grows we still need to apply transformations to all paths, even those that are not visible + \end{itemize} + \item Quad tree + \begin{itemize} + \item Divide space up into a quad tree + \item Refer to David's stuff + \item The advantage over Path based transformations is that the bounds of objects which are not visible do not need to be recalculated + \end{itemize} + +\end{enumerate} + + diff --git a/chapters/Progress/Progress.tex b/chapters/Progress/Progress.tex new file mode 100644 index 0000000..e37865d --- /dev/null +++ b/chapters/Progress/Progress.tex @@ -0,0 +1,106 @@ +\chapter{Progress Report}\label{Progress} + +We describe the current state of our project in relation to the aims outlined in Chapter \ref{Introduction}. At this stage work on the project has been done in collaboration with David Gow; however the Project Proposals and Literature Reviews were produced individually. + +\section{Literature Review} +The literature examined in Chapter\ref{Background} can broadly classed into three different areas (with major references indicated): +\begin{enumerate} + \item Rendering Vector Graphics \cite{computergraphics2, knuth1983metafont, kilgard2012gpu} + \begin{itemize} + \item Rasterisation of Vector Graphics is non-trivial but well understood + \item Traditionally most rasterisation has been performed on the CPU and drawing on a dedicated GPU; current interest is in techniques for utilising the GPU directly to rasterise vector graphics + \end{itemize} + \item Representations of Vector Documents \cite{hayes2012pixels, plrm, knuth1984texbook, svg2011-1.1, pdfref17} + \begin{itemize} + \item Traditional approaches are be based on a programmatic model (PostScript, {\TeX}, DVI) + \item The Document Object Model (DOM) used by web technologies is a powerful way to produce dynamic documents (HTML5, SVG, Javascript) + \item These approaches can overlap (PDF) + \end{itemize} + \item Number Representations \cite{ieee754std2008, HFP, goldberg1991whatevery, fousse2007mpfr} + \begin{itemize} + \item Most document standards either specify, suggest, or imply a IEEE-754 floating point representation ({\TeX} is an exception) + \item IEEE-754 is widely used, although there are instances of languages or processors which do not conform exactly to the standard + \item Some GPUs in particular may not conform to IEEE-754, possibly trading some accuracy for performance + \item Arbitrary precision floating point arithmetic is possible through several libraries + \end{itemize} +\end{enumerate} + +To improve the Literature Review we could consider the following topics in more detail: +\begin{enumerate} + \item Additional approaches to arbitrary precision possibly including symbolic computation + \begin{itemize} + \item The Mathematica computational package claims to use symbolic computation, but we have yet to explore this field + \end{itemize} + \item Floating point errors in the context of computing B\'{e}zier Curves or similar + \item Algorithms for reducing overall error other than Fast2Sum + \item Alternative number representations such as rationals (eg: $\frac{1}{3}$) + \item How well GPUs conform or do not conform to IEEE-754 in more detail + \item Additional aspects of rendering vector documents including shading +\end{enumerate} + + +\section{Development of Testbed Software} + +We have produced a basic Document Viewer capable of rendering simple primitives under translation and scaling. The OpenGL 3.1 API is used to interface with graphics hardware. This software has the following features: +\begin{enumerate} + \item A type name \verb/Real/ is used in place of the standard floating point types \verb/float/, \verb/double/ or \verb/long double/. This type name can be redefined to refer to one of the standard types or a custom real number representation, allowing us to easily recompile and test our software for different representations. + \item Screenshots can be overlaid on top of each other to get a pixel comparison of the graphical output of different versions of the program + \item Test documents can be loaded and saved so that we can compare different versions of the program on identical inputs + \item The time for rendering can be measured + \item Coordinate transformations may be performed on either the GPU or CPU +\end{enumerate} + +We have noticed the CPU produces more precise coordinate transformations at large ``zoom'' levels, but is significantly slower than the GPU. We have yet to quantitatively measure this difference. + +\section{Floating Point Arithmetic} + +Algorithms for floating point arithmetic may be implemented in software (CPU) or on dedicated hardware (FPU). We have made progress towards both approaches. + +An open source Virtual FPU implemented in the VHDL language has been successfully compiled and can be substituted into our testbed software in place of native arithmetic running on the CPU. The timing diagram for this FPU throughout the execution of test programs can be extracted. Currently the virtual FPU is restricted to 32 bit floats and the square root operation is unimplemented. + +Mainly motivated by producing Figure \ref{floats.pdf} we have also implemented functions to convert an arbitrary \verb/Real/ type (which may be IEEE-754 floats) to and from a fixed size floating point representation of our choosing. We have not implemented any operations for floating point arithmetic using these representations. + +By using the functions to convert real numbers to variable precision floats as an interface for the virtual FPU, we hope to illustrate the limitations of floating point arithmetic more clearly than would be possible using IEEE-754 binary32 as is native to the C and C++ languages. Using the virtual FPU instead of a CPU based software library will prove useful for determining the exact performance of floating point operations. + +\section{Prototype Document Formats} + +Our testbed software is capable of reading primitive attributes from either a binary file or XML plain text file. Our format is conceptually similar to the Document Object Model, although there is currently only one generation in the tree as no primitives can contain other elements as of yet. + +If time permits, we plan to extend our XML format to cover a subset of the SVG standard. This may allow us to compare the rasterisation of an SVG using our own software and traditional software relying on IEEE-754 floats. + +Some of the figures produced for Chapter \ref{Background} may prove useful as standard test images for comparing the qualitative performance of versions of our software. + +\section{Version Control and Backup of Work} + +Git is a distributed version control system widely used in the development of open source software. All rescources created for or used by this project have been placed in git repositories on several servers. The repositories are publically accessable at \url{http://git.ucc.asn.au}, \url{http://szmoore.net/ipdf}. + +\section{Timeline} + +Deadlines enforced by the faculty of Engineering Computing and Mathematics are \emph{italicised}.\footnote{David Gow is being assessed under the 2014 rules for a BEng (Software) Final Year Project, whilst the author is being assessed under the 2014 rules for a BEng (Mechatronics) Final Year Project; deadlines and requirements as shown in Gow's proposal\cite{proposalGow} may differ}. + +\begin{center} +\begin{tabular}{l|p{0.5\textwidth}} + {\bf Date} & {\bf Milestone} \\ + \hline + $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\ + \hline + $17^{\text{th}}$ May & Draft Progress Report and Literature Review \\ + \hline + $26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\ + \hline + $9^{\text{th}}$ June & Demonstrations of limitations of floating point precision in the Testbed software. \\ + $1^{\text{st}}$ July & At least one implementation of arbitrary precision for basic primitives (lines, polygons, curves) completed. Other implementations, advanced features, and areas for more detailed research identified. \\ + \hline + $1^{\text{st}}$ August & Experiments and comparison of various arbitrary precision implementations completed. \\ + \hline + $1^{\text{st}}$ September & Advanced features implemented and tested, work underway on Final Report. \\ + \hline + TBA & \emph{Conference Abstract and Presentation due.} \\ + \hline + $10^{\text{th}}$ October & \emph{Draft of Final Report due.} \\ + \hline + $27^{\text{th}}$ October & \emph{Final Report due.}\\ + \hline +\end{tabular} +\end{center} + diff --git a/chapters/Proposal.tex b/chapters/Proposal.tex deleted file mode 100644 index ff9a5f3..0000000 --- a/chapters/Proposal.tex +++ /dev/null @@ -1,72 +0,0 @@ -\chapter{Proposal}\label{Proposal} - -\section{Aim} - -In this project, we will explore the state of the art of current document formats including PDF, PostScript, SVG, HTML, and the limitations of each with regards to precision. - -We will consider designs for a document format allowing graphics primitives at an arbitrary level of zoom with no loss of detail. A viewer and editor will be implemented as a proof of concept; we adopt a low level, ground up approach to designing this viewer so as to not become restricted by any single existing document format. Although it is possible to produce three dimensional graphics using some of the technologies we will explore, we will focus on two dimensional graphics. - -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. - -\subsection{Clarification of Terms} - -It may be necessary to clarify what we mean by the terms ``arbitrary precision'' and ``document formats''. Regarding the latter, we consider a document format to be any representation of visual information which is capable of being stored indefinitely. Regarding the former, we do not propose to be able to contain an infinite amount of information within such a document. The goal is to be able to render a primitive at the same level of detail it is specified by a document format, regardless of how precise this level is. For example, the precision of coordinates of primitives drawn in a graphical document editor will always be limited by the resolution of the display on which they are drawn, but not by the viewer. - - -\section{Methods} - -Initial research and software development is being conducted in collaboration with David Gow\cite{proposalGow}. Once a simple testbed application has been developed, we will individually explore approaches for introducing arbitrary levels of precision; these approaches will be implemented as alternate versions of the same software. The focus will be on drawing simple primitives (lines, polygons, circles). However, if time permits we will explore adding more complicated primitives (font glyphs, bezier curves, embedded bitmaps). Hearn and Baker's textbook ``Computer Graphics'' includes chapters providing a good overview of two dimensional graphics\cite{computergraphics2}. - -The process of rendering a document will be considered as a common area of research, whilst individual research will be conducted on means for allowing infinite precision. -At this stage we have identified two possible areas for individual research: - -\begin{enumerate} - - \item {\bf Arbitrary Precision real valued numbers} --- Sam Moore - - We plan to investigate the representation of real values to a high or arbitary degree of precision. Such representations would allow for the coordinates of primitives to be relative to a single global coordinate system. We would expect a decrease in performance with increased complexity of the data structure used to represent a real value. We will also consider the limitations imposed by performing calculations on the GPU or CPU. - -Starting points for research in this area are Priest's 1991 paper, ``Algorithms for Arbitrary Precision Floating Point Arithmetic''\cite{priest1991algorithms}, and Goldberg's 1992 paper ``The design of floating point data types''\cite{goldberg1992thedesign}. A more recent and comprehensive text book, ``Handbook of Floating Point Arithmetic''\cite{HFP}, published in 2010, has also been identified as highly relevant. - - \item {\bf Local coordinate systems} --- David Gow \cite{proposalGow} - - An alternative approach involves segmenting the document into different regions using fixed precision floats to define primitives within each region. A quadtree or similar data structure could be employed to identify and render those regions currently visible in the document viewer. - -\end{enumerate} -We aim to compare these and any additional implementations considered using the following metrics: -\begin{enumerate} - - \item {\bf Performance vs Number of Primitives} - - As it is clearly desirable to include more objects in a document, this is a natural metric for the usefulness of an implementation. - We will compare the performance of rendering different implementations, using several ``standard'' test documents. - - \item {\bf Performance vs Visible Primitives} - - There will inevitably be an overhead to all primitives in the document, whether drawn or not. - As the structure of the document format and rendering algorithms may be designed independently, we will repeat the above tests considering only the number of visible primitives. - - - \item {\bf Performance vs Zoom Level} - - We will also consider the performance of rendering at zoom levels that include primitives on both small and large scales, since these are the cases under which floating point precision causes problems in the PostScript and PDF standards. - - \item {\bf Performance whilst translation and scaling} - - Whilst changing the view, it is ideal that the document be re-rendered as efficiently as possible, to avoid disorienting and confusing the user. - We will therefore compare the speed of rendering as the standard documents are translated or scaled at a constant rate. - - \item {\bf Artifacts and Limitations on Precision} - - As we are unlikely to achieve truly ``infinite'' precision, qualitative comparisons of the accuracy of rendering under different implementations should be made. - -\end{enumerate} - -\section{Software and Hardware Requirements} - -Our proof of concept will be developed for a conventional GNU/Linux desktop or laptop computer using the OpenGL 3.1 API for rendering. However, the techniques explored could be extended to other platforms and libraries. - - - - - diff --git a/chapters/Results.tex b/chapters/Results.tex new file mode 100644 index 0000000..923eccf --- /dev/null +++ b/chapters/Results.tex @@ -0,0 +1,66 @@ +\chapter{Results and Discussion} + + +\section{Qualitative Rendering Accuracy} + +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. + +applying Transformation \eqref{view-transformation}. We will use single precision floats for coordinates unless otherwise stated. + +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). + + + +\begin{figure}[H] + \centering + \includegraphics[width=800px]{figures/fox-vector_screenshot2.png} + \includegraphics[width=800px]{figures/fox-vector_highzoom1.png} + \caption{The vector image from Figure \ref{vector-vs-raster} under two different scales}\label{qualitative-rendering-fox} +\end{figure} + +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 approach significantly improves the range over which an image can be rendered correctly, and it is convenient for interactively created documents as no transformation must be applied to add new detail. + +However, repeated transformations on the view will cause an accumulated error on the coordinates of object bounds. This is most noticable when zooming out and then back into the document; the object bounds 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 +%setbounds 0.5 0.5 1e-6 1e-6 +%loadsvg svg-tests/fox-vector.svg +%loop 1950 pxzoom 0 0 -1 +%loop 200 wait +%debug hi +%loop 1950 pxzoom 0 0 1 +%wait +\begin{figure}[H] + \centering + \includegraphics[width=800px]{figures/fox-vector_cumulative_before_transforms.png} + \includegraphics[width=800px]{figures/fox-vector_cumulative_after_transforms.png} + \caption{The effect of applying cumulative transformations to all B\'{e}ziers}\label{qualitative-rendering-fox-cumulative} +\end{figure} + +In Figure \ref{qualitative-rendering-fox}, transformations are applied to the bounds of each B\'{e}zier. Figure \ref{qualitative-rendering-fox-cumulative-relative} a) shows the effect of introducing an intermediate coordinate system expressing B\'{e}zier coordinates relative to the path which contains them. In this case, the rendering of a single path is accurate, but the overall positions of the paths drift. + +We can correct this drift whilst maintaining performance by using an arbitrary precision number representation to express the coordinates of the paths - but maintaining the floating point coordinates for B\'{e}zier curves relative to their path. As we will discuss in Section \ref{}, this offers an acceptable trade off between rendering accuracy and performance. + +\begin{figure}[H] + \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} +\end{figure} + +\section{Quantitative Measurements of Rendering Accuracy} + +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. + +Figures \ref{} show the effect of scaling the grid to different view coordinates using single precision. This illustrates the trade off between precision and range; as the top left corner of the view moves further away from the origin, the width for which the grid appears unaltered decreases, or if the width is kept fixed, then there are fewer locations on the grid that can be correctly transformed from document to view space. + +Figure \ref{} shows a plot of the number of lines visible in the grid as a function of distance from the origin for IEEE-754 floats and several different precision settings for the MPFR library. + +Figure \ref{} shows the obvious + +\section{Performance Measurements whilst Rendering} + +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 number representation must grow accordingly. + + + diff --git a/figures/controlpanel_screenshot.png b/figures/controlpanel_screenshot.png new file mode 100644 index 0000000..23d17f0 Binary files /dev/null and b/figures/controlpanel_screenshot.png differ diff --git a/figures/fox-vector+grid.png b/figures/fox-vector+grid.png new file mode 100644 index 0000000..532d0b2 Binary files /dev/null and b/figures/fox-vector+grid.png differ diff --git a/figures/fox-vector_cumulative_after_transforms.png b/figures/fox-vector_cumulative_after_transforms.png new file mode 100644 index 0000000..038cd13 Binary files /dev/null and b/figures/fox-vector_cumulative_after_transforms.png differ diff --git a/figures/fox-vector_cumulative_before_transforms.png b/figures/fox-vector_cumulative_before_transforms.png new file mode 100644 index 0000000..da235f3 Binary files /dev/null and b/figures/fox-vector_cumulative_before_transforms.png differ diff --git a/figures/fox-vector_cumulative_relative_to_path.png b/figures/fox-vector_cumulative_relative_to_path.png new file mode 100644 index 0000000..defd775 Binary files /dev/null and b/figures/fox-vector_cumulative_relative_to_path.png differ diff --git a/figures/fox-vector_cumulative_relative_to_path_GMPrat.png b/figures/fox-vector_cumulative_relative_to_path_GMPrat.png new file mode 100644 index 0000000..814dd43 Binary files /dev/null and b/figures/fox-vector_cumulative_relative_to_path_GMPrat.png differ diff --git a/figures/fox-vector_face_with_bezbounds.png b/figures/fox-vector_face_with_bezbounds.png new file mode 100644 index 0000000..e1e27f9 Binary files /dev/null and b/figures/fox-vector_face_with_bezbounds.png differ diff --git a/figures/fox-vector_highzoom1.png b/figures/fox-vector_highzoom1.png new file mode 100644 index 0000000..8560bb4 Binary files /dev/null and b/figures/fox-vector_highzoom1.png differ diff --git a/figures/fox-vector_screenshot1.png b/figures/fox-vector_screenshot1.png new file mode 100644 index 0000000..bef092a Binary files /dev/null and b/figures/fox-vector_screenshot1.png differ diff --git a/figures/fox-vector_screenshot2.png b/figures/fox-vector_screenshot2.png new file mode 100644 index 0000000..95e1488 Binary files /dev/null and b/figures/fox-vector_screenshot2.png differ diff --git a/figures/fox-vector_screenshot2_300dpi.png b/figures/fox-vector_screenshot2_300dpi.png new file mode 100644 index 0000000..ae4803c Binary files /dev/null and b/figures/fox-vector_screenshot2_300dpi.png differ diff --git a/figures/gpufloats.svg b/figures/gpufloats.svg new file mode 100644 index 0000000..76eb9ae --- /dev/null +++ b/figures/gpufloats.svg @@ -0,0 +1,685 @@ + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + x86-64 CPU + nVidia shader + fglrx shader + intel shader + + + diff --git a/figures/shady-the-fox.png b/figures/shady-the-fox.png new file mode 100644 index 0000000..e352404 Binary files /dev/null and b/figures/shady-the-fox.png differ diff --git a/figures/who-the-hell-needs-antialiasing-anyway.png b/figures/who-the-hell-needs-antialiasing-anyway.png new file mode 100644 index 0000000..15fafdd Binary files /dev/null and b/figures/who-the-hell-needs-antialiasing-anyway.png differ diff --git a/meta/Abstract.tex b/meta/Abstract.tex index b3239f2..4c1d5fd 100644 --- a/meta/Abstract.tex +++ b/meta/Abstract.tex @@ -1,10 +1,26 @@ \section*{Abstract} -At the fundamental level, a document is a means to convey information. The limitations on a digital document format therefore restrict the types and quality of information that can be communicated. Whilst modern document formats are now able to include increasingly complex dynamic content, they still suffer from early views of a document as a static page; to be viewed at a fixed scale and position. In this report, we focus on the limitations of modern document formats (including PDF, PostScript, SVG) with regards to the level of detail, or precision at which primatives can be drawn. We propose a research project to investigate whether it is possible to obtain an ``arbitrary precision'' document format, capable of including primitives created at an arbitrary level of zoom. +Early document formats such as PostScript were motivated by a desire to +print text and visual information onto a static paper medium. +Although documents are increasingly viewed digitally, modern standards +including PDF and SVG are still largely based upon this model. +Digital document viewers are able to scale a subregion of the document to +fit the display. However, coordinates of graphics primitives are +typically represented with IEEE-754 floating point numbers. This places +limits on the precision with which primitives in the document can be +specified and rendered. -{\bf Keywords:} \emph{document formats, precision, floating point, vector images, graphics, OpenGL, VHDL, PostScript, PDF, {\TeX}, SVG, HTML5, Javascript } +We have implemented a minimal SVG viewer, with which we have +compared a number of approaches to achieving arbitrary precision +document formats. We demonstrate the trade off between performance and +precision with alternative number representations including arbitrary +precision floats, rationals, and IEEE-754 fixed precision floats. We also +consider approaches to increasing the precision that can be attained with +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/documents/LitReviewSam.pdf} +{\bf Keywords:} \emph{document formats, precision, floating point, vector images, graphics, OpenGL, SDL2, PostScript, PDF, {\TeX}, SVG, HTML5, Javascript } + +{\bf Note:} This report is best viewed digitally as a PDF. The digital version is available at \url{http://szmoore.net/ipdf/sam/thesis.pdf} % Oh dear... \quad \\ \quad \\ \quad \\ \quad diff --git a/meta/Proposal.tex b/meta/Proposal.tex new file mode 100644 index 0000000..ff9a5f3 --- /dev/null +++ b/meta/Proposal.tex @@ -0,0 +1,72 @@ +\chapter{Proposal}\label{Proposal} + +\section{Aim} + +In this project, we will explore the state of the art of current document formats including PDF, PostScript, SVG, HTML, and the limitations of each with regards to precision. + +We will consider designs for a document format allowing graphics primitives at an arbitrary level of zoom with no loss of detail. A viewer and editor will be implemented as a proof of concept; we adopt a low level, ground up approach to designing this viewer so as to not become restricted by any single existing document format. Although it is possible to produce three dimensional graphics using some of the technologies we will explore, we will focus on two dimensional graphics. + +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. + +\subsection{Clarification of Terms} + +It may be necessary to clarify what we mean by the terms ``arbitrary precision'' and ``document formats''. Regarding the latter, we consider a document format to be any representation of visual information which is capable of being stored indefinitely. Regarding the former, we do not propose to be able to contain an infinite amount of information within such a document. The goal is to be able to render a primitive at the same level of detail it is specified by a document format, regardless of how precise this level is. For example, the precision of coordinates of primitives drawn in a graphical document editor will always be limited by the resolution of the display on which they are drawn, but not by the viewer. + + +\section{Methods} + +Initial research and software development is being conducted in collaboration with David Gow\cite{proposalGow}. Once a simple testbed application has been developed, we will individually explore approaches for introducing arbitrary levels of precision; these approaches will be implemented as alternate versions of the same software. The focus will be on drawing simple primitives (lines, polygons, circles). However, if time permits we will explore adding more complicated primitives (font glyphs, bezier curves, embedded bitmaps). Hearn and Baker's textbook ``Computer Graphics'' includes chapters providing a good overview of two dimensional graphics\cite{computergraphics2}. + +The process of rendering a document will be considered as a common area of research, whilst individual research will be conducted on means for allowing infinite precision. +At this stage we have identified two possible areas for individual research: + +\begin{enumerate} + + \item {\bf Arbitrary Precision real valued numbers} --- Sam Moore + + We plan to investigate the representation of real values to a high or arbitary degree of precision. Such representations would allow for the coordinates of primitives to be relative to a single global coordinate system. We would expect a decrease in performance with increased complexity of the data structure used to represent a real value. We will also consider the limitations imposed by performing calculations on the GPU or CPU. + +Starting points for research in this area are Priest's 1991 paper, ``Algorithms for Arbitrary Precision Floating Point Arithmetic''\cite{priest1991algorithms}, and Goldberg's 1992 paper ``The design of floating point data types''\cite{goldberg1992thedesign}. A more recent and comprehensive text book, ``Handbook of Floating Point Arithmetic''\cite{HFP}, published in 2010, has also been identified as highly relevant. + + \item {\bf Local coordinate systems} --- David Gow \cite{proposalGow} + + An alternative approach involves segmenting the document into different regions using fixed precision floats to define primitives within each region. A quadtree or similar data structure could be employed to identify and render those regions currently visible in the document viewer. + +\end{enumerate} +We aim to compare these and any additional implementations considered using the following metrics: +\begin{enumerate} + + \item {\bf Performance vs Number of Primitives} + + As it is clearly desirable to include more objects in a document, this is a natural metric for the usefulness of an implementation. + We will compare the performance of rendering different implementations, using several ``standard'' test documents. + + \item {\bf Performance vs Visible Primitives} + + There will inevitably be an overhead to all primitives in the document, whether drawn or not. + As the structure of the document format and rendering algorithms may be designed independently, we will repeat the above tests considering only the number of visible primitives. + + + \item {\bf Performance vs Zoom Level} + + We will also consider the performance of rendering at zoom levels that include primitives on both small and large scales, since these are the cases under which floating point precision causes problems in the PostScript and PDF standards. + + \item {\bf Performance whilst translation and scaling} + + Whilst changing the view, it is ideal that the document be re-rendered as efficiently as possible, to avoid disorienting and confusing the user. + We will therefore compare the speed of rendering as the standard documents are translated or scaled at a constant rate. + + \item {\bf Artifacts and Limitations on Precision} + + As we are unlikely to achieve truly ``infinite'' precision, qualitative comparisons of the accuracy of rendering under different implementations should be made. + +\end{enumerate} + +\section{Software and Hardware Requirements} + +Our proof of concept will be developed for a conventional GNU/Linux desktop or laptop computer using the OpenGL 3.1 API for rendering. However, the techniques explored could be extended to other platforms and libraries. + + + + + diff --git a/meta/Titlepage.tex b/meta/Titlepage.tex index cfbd463..3230c05 100644 --- a/meta/Titlepage.tex +++ b/meta/Titlepage.tex @@ -1,11 +1,11 @@ % Suitably pretty title page is required. \begin{titlepage} -\title{Precision In Document Formats} %From ipdf -> pidf (-_-) +\title{Number Representations and Precision in Vector Graphics} \author{{\it Author:} Samuel Moore\cite{proposalMoore} \\ {{\it Partners:} David Gow\cite{proposalGow}} \\ -{{\it Supervisor:} Prof Tim French}\\ +{{\it Supervisors:} Prof Tim French, Dr Rowan Davies}\\ \\ \\ \\ -\includegraphics[width=150px]{figures/uwacrest.pdf}} +\includegraphics[width=0.7\textwidth]{figures/uwacrest.pdf}} %\date{Date of submission: 02/11/2012} \maketitle \end{titlepage} diff --git a/notes.nb b/notes.nb new file mode 100644 index 0000000..a18d234 --- /dev/null +++ b/notes.nb @@ -0,0 +1,294 @@ +(* Content-type: application/vnd.wolfram.mathematica *) + +(*** Wolfram Notebook File ***) +(* http://www.wolfram.com/nb *) + +(* CreatedBy='Mathematica 9.0' *) + +(*CacheID: 234*) +(* Internal cache information: +NotebookFileLineBreakTest +NotebookFileLineBreakTest +NotebookDataPosition[ 157, 7] +NotebookDataLength[ 8384, 285] +NotebookOptionsPosition[ 7404, 248] +NotebookOutlinePosition[ 7739, 263] +CellTagsIndexPosition[ 7696, 260] +WindowFrame->Normal*) + +(* Beginning of Notebook Content *) +Notebook[{ +Cell[TextData[{ + "The view \[OpenCurlyDoubleQuote]scale about point\[CloseCurlyDoubleQuote] \ +transformation\nmx, my is mouse coordinates ", + StyleBox["relative to the view", + FontSlant->"Italic"], + "\nx, y, w, h are current view coordinates ", + StyleBox["relative to the document", + FontSlant->"Italic"], + "\nX, Y, W, H are transformed coordinates\nThis operation cannot be \ +represented as a 2D matrix operation..." +}], "Text", + CellChangeTimes->{{3.621645547391625*^9, 3.621645590446886*^9}, { + 3.621645788609687*^9, 3.621645803583606*^9}}], + +Cell[BoxData[{ + RowBox[{ + RowBox[{"vx", " ", "=", " ", + RowBox[{ + RowBox[{"w", " ", "*", "mx"}], " ", "+", " ", "x"}]}], + ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"vy", " ", "=", " ", + RowBox[{ + RowBox[{"h", " ", "*", " ", "my"}], " ", "+", " ", "y"}]}], + ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"top", " ", "=", " ", + RowBox[{"vy", " ", "-", " ", "y"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"left", " ", "=", " ", + RowBox[{"vx", " ", "-", " ", "x"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"top", " ", "=", " ", + RowBox[{"top", "*", "s"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"left", " ", "=", " ", + RowBox[{"left", " ", "*", " ", "s"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"X", " ", "=", " ", + RowBox[{"vx", " ", "-", " ", "left"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"Y", " ", "=", " ", + RowBox[{"vy", " ", "-", " ", "top"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"W", " ", "=", " ", + RowBox[{"w", "*", "s"}]}], ";"}], "\[IndentingNewLine]", + RowBox[{ + RowBox[{"H", " ", "=", " ", + RowBox[{"h", "*", "s"}]}], ";"}]}], "Input", + CellChangeTimes->{{3.621644450038117*^9, 3.621644517724819*^9}, { + 3.6216455001839314`*^9, 3.6216455061448193`*^9}}], + +Cell[CellGroupData[{ + +Cell[BoxData[ + RowBox[{"xy1", " ", "=", " ", + RowBox[{"{", + RowBox[{ + RowBox[{"{", + RowBox[{"x", ",", "y"}], "}"}], ",", + RowBox[{"{", + RowBox[{"x", "+", "w"}], "}"}], ",", + RowBox[{"{", + RowBox[{"y", "+", "h"}], "}"}]}], "}"}]}]], "Input", + CellChangeTimes->{{3.621645646537537*^9, 3.621645677183116*^9}}], + +Cell[BoxData[ + RowBox[{"{", + RowBox[{ + RowBox[{"{", + RowBox[{"x", ",", "y"}], "}"}], ",", + RowBox[{"{", + RowBox[{"w", "+", "x"}], "}"}], ",", + RowBox[{"{", + RowBox[{"h", "+", "y"}], "}"}]}], "}"}]], "Output", + CellChangeTimes->{3.62164567753369*^9}] +}, Open ]], + +Cell[CellGroupData[{ + +Cell[BoxData[ + RowBox[{"xy2", " ", "=", " ", + RowBox[{"FullSimplify", "[", + RowBox[{"{", + RowBox[{"X", ",", " ", "Y", ",", " ", + RowBox[{"X", "+", "W"}], ",", " ", + RowBox[{"Y", "+", "H"}]}], "}"}], "]"}]}]], "Input", + CellChangeTimes->{{3.62164452159755*^9, 3.621644525242661*^9}, { + 3.621645606946629*^9, 3.621645623731018*^9}, {3.6216456891302*^9, + 3.621645689867572*^9}}], + +Cell[BoxData[ + RowBox[{"{", + RowBox[{ + RowBox[{ + RowBox[{"mx", " ", + RowBox[{"(", + RowBox[{"w", "-", + RowBox[{"s", " ", "w"}]}], ")"}]}], "+", "x"}], ",", + RowBox[{ + RowBox[{"h", " ", + RowBox[{"(", + RowBox[{"my", "-", + RowBox[{"my", " ", "s"}]}], ")"}]}], "+", "y"}], ",", + RowBox[{ + RowBox[{ + RowBox[{"(", + RowBox[{"mx", "+", "s", "-", + RowBox[{"mx", " ", "s"}]}], ")"}], " ", "w"}], "+", "x"}], ",", + RowBox[{ + RowBox[{"h", " ", + RowBox[{"(", + RowBox[{"my", "+", "s", "-", + RowBox[{"my", " ", "s"}]}], ")"}]}], "+", "y"}]}], "}"}]], "Output", + CellChangeTimes->{ + 3.621644525784692*^9, {3.621645598921043*^9, 3.62164562472651*^9}, { + 3.621645679592589*^9, 3.6216456913785887`*^9}}] +}, Open ]], + +Cell[CellGroupData[{ + +Cell[BoxData[ + RowBox[{"xywh2", " ", "=", " ", + RowBox[{"FullSimplify", "[", + RowBox[{"{", + RowBox[{"X", ",", " ", "Y", ",", " ", "W", ",", "H"}], "}"}], + "]"}]}]], "Input", + CellChangeTimes->{{3.621645929284232*^9, 3.621645939176342*^9}}], + +Cell[BoxData[ + RowBox[{"{", + RowBox[{ + RowBox[{ + RowBox[{"mx", " ", + RowBox[{"(", + RowBox[{"w", "-", + RowBox[{"s", " ", "w"}]}], ")"}]}], "+", "x"}], ",", + RowBox[{ + RowBox[{"h", " ", + RowBox[{"(", + RowBox[{"my", "-", + RowBox[{"my", " ", "s"}]}], ")"}]}], "+", "y"}], ",", + RowBox[{"s", " ", "w"}], ",", + RowBox[{"h", " ", "s"}]}], "}"}]], "Output", + CellChangeTimes->{3.621645939693961*^9}] +}, Open ]], + +Cell[TextData[{ + "For primitives in document,\nV X \[Rule] V X + S[V X - ", + Cell[BoxData[ + FormBox[ + RowBox[{ + SubscriptBox["X", "0"], "]"}], TraditionalForm]], + FormatType->"TraditionalForm"], + "\nV is view matrix, S is scale matrix" +}], "Text", + CellChangeTimes->{{3.62164641213169*^9, 3.62164647339319*^9}}], + +Cell[BoxData[ + RowBox[{ + RowBox[{"(*", + RowBox[{"TODO", ":", " ", + RowBox[{"Express", " ", "as", " ", "a", " ", "matrix", " ", + RowBox[{"operation", "?"}]}]}], "*)"}], "\[IndentingNewLine]"}]], "Input",\ + + CellChangeTimes->{{3.6216459415176992`*^9, 3.621645948934423*^9}, { + 3.6216463980527067`*^9, 3.6216464053607597`*^9}}], + +Cell[BoxData[ + RowBox[{"ClearAll", "[", + RowBox[{"Evaluate", "[", + RowBox[{ + RowBox[{"Context", "[", "]"}], "<>", "\"\<*\>\""}], "]"}], "]"}]], "Input"], + +Cell["Floating point operations", "Text", + CellChangeTimes->{{3.621665522093079*^9, 3.6216655239496813`*^9}}], + +Cell[BoxData[ + RowBox[{"FullSimplify", "[", + RowBox[{"m1", " ", + SuperscriptBox["B", "e1"], " ", "*", " ", "m2", " ", + SuperscriptBox["B", "e2"]}], "]"}]], "Input", + CellChangeTimes->{{3.621665107840431*^9, 3.6216651376842957`*^9}}], + +Cell[BoxData[ + RowBox[{ + SuperscriptBox["B", + RowBox[{"e1", "+", "e2"}]], " ", "m1", " ", "m2"}]], "Input", + CellChangeTimes->{{3.62166519824517*^9, 3.62166520820506*^9}}], + +Cell[BoxData[ + RowBox[{ + SuperscriptBox["B", + RowBox[{"e1", "+", "e2"}]], " ", "m1", " ", "m2"}]], "Output", + CellChangeTimes->{{3.621665204836622*^9, 3.621665208534109*^9}}], + +Cell[CellGroupData[{ + +Cell[BoxData[ + RowBox[{"FullSimplify", "[", + RowBox[{"Solve", "[", + RowBox[{ + RowBox[{ + RowBox[{ + RowBox[{"m1", " ", + SuperscriptBox["B", "e1"]}], " ", "+", " ", + RowBox[{"m2", " ", + SuperscriptBox["B", "e2"]}]}], " ", "\[Equal]", " ", + RowBox[{"m3", " ", + SuperscriptBox["B", "e1"]}]}], ",", " ", "m3"}], "]"}], "]"}]], "Input",\ + + CellChangeTimes->{ + 3.621665148857037*^9, {3.621665392367518*^9, 3.62166542126152*^9}}], + +Cell[BoxData[ + RowBox[{"{", + RowBox[{"{", + RowBox[{"m3", "\[Rule]", + RowBox[{"m1", "+", + RowBox[{ + SuperscriptBox["B", + RowBox[{ + RowBox[{"-", "e1"}], "+", "e2"}]], " ", "m2"}]}]}], "}"}], + "}"}]], "Output", + CellChangeTimes->{ + 3.621665149470646*^9, {3.621665400108696*^9, 3.621665421774309*^9}}] +}, Open ]] +}, +WindowSize->{740, 575}, +WindowMargins->{{Automatic, 79}, {Automatic, 0}}, +FrontEndVersion->"9.0 for Linux x86 (64-bit) (February 7, 2013)", +StyleDefinitions->"Default.nb" +] +(* End of Notebook Content *) + +(* Internal cache information *) +(*CellTagsOutline +CellTagsIndex->{} +*) +(*CellTagsIndex +CellTagsIndex->{} +*) +(*NotebookFileOutline +Notebook[{ +Cell[557, 20, 546, 12, 110, "Text"], +Cell[1106, 34, 1309, 36, 231, "Input"], +Cell[CellGroupData[{ +Cell[2440, 74, 337, 10, 32, "Input"], +Cell[2780, 86, 271, 9, 32, "Output"] +}, Open ]], +Cell[CellGroupData[{ +Cell[3088, 100, 397, 9, 32, "Input"], +Cell[3488, 111, 782, 25, 32, "Output"] +}, Open ]], +Cell[CellGroupData[{ +Cell[4307, 141, 251, 6, 32, "Input"], +Cell[4561, 149, 446, 15, 32, "Output"] +}, Open ]], +Cell[5022, 167, 318, 9, 71, "Text"], +Cell[5343, 178, 338, 8, 55, "Input"], +Cell[5684, 188, 160, 4, 32, "Input"], +Cell[5847, 194, 109, 1, 30, "Text"], +Cell[5959, 197, 240, 5, 35, "Input"], +Cell[6202, 204, 175, 4, 32, "Input"], +Cell[6380, 210, 178, 4, 32, "Output"], +Cell[CellGroupData[{ +Cell[6583, 218, 469, 14, 35, "Input"], +Cell[7055, 234, 333, 11, 35, "Output"] +}, Open ]] +} +] +*) + +(* End of internal cache information *) diff --git a/presentation.nav b/presentation.nav new file mode 100644 index 0000000..83db07d --- /dev/null +++ b/presentation.nav @@ -0,0 +1,8 @@ +\beamer@endinputifotherversion {3.33pt} +\headcommand {\slideentry {0}{0}{1}{1/1}{}{0}} +\headcommand {\beamer@framepages {1}{1}} +\headcommand {\beamer@partpages {1}{1}} +\headcommand {\beamer@subsectionpages {1}{1}} +\headcommand {\beamer@sectionpages {1}{1}} +\headcommand {\beamer@documentpages {1}} +\headcommand {\def \inserttotalframenumber {1}} diff --git a/presentation.snm b/presentation.snm new file mode 100644 index 0000000..e69de29 diff --git a/presentation/Logos/WAMSI.png b/presentation/Logos/WAMSI.png new file mode 100644 index 0000000..36d914d Binary files /dev/null and b/presentation/Logos/WAMSI.png differ diff --git a/presentation/Logos/uwa.png b/presentation/Logos/uwa.png new file mode 100644 index 0000000..2790277 Binary files /dev/null and b/presentation/Logos/uwa.png differ diff --git a/presentation/arrow.pdf b/presentation/arrow.pdf new file mode 100644 index 0000000..2a7460e --- /dev/null +++ b/presentation/arrow.pdf @@ -0,0 +1,70 @@ +%PDF-1.5 +%µí®û +3 0 obj +<< /Length 4 0 R + /Filter /FlateDecode +>> +stream +xœeŽ1 Â@ …÷üŠ7 “ô¼^WAp¨Žâ +i‡ÖÁ¿oZµ’@òò¾ô$c¿Áò,h¤‰+Í9'<}·õ¼ÓñaÁ•"vè¡ÓI[4¶ª4]áґk$”5ftðÊÑÒwÐâ€úƒÌÜÈ6Y8¯› +þ¬ƒZfuQ˜íƒª²IPd–”´ŽšgUû£rNA>¹ÑzáÔôç‡1· +endstream +endobj +4 0 obj + 161 +endobj +2 0 obj +<< + /ExtGState << + /a0 << /CA 1 /ca 1 >> + >> +>> +endobj +5 0 obj +<< /Type /Page + /Parent 1 0 R + /MediaBox [ 0 0 178.138641 42.297215 ] + /Contents 3 0 R + /Group << + /Type /Group + /S /Transparency + /I true + /CS /DeviceRGB + >> + /Resources 2 0 R +>> +endobj +1 0 obj +<< /Type /Pages + /Kids [ 5 0 R ] + /Count 1 +>> +endobj +6 0 obj +<< /Creator (cairo 1.12.16 (http://cairographics.org)) + /Producer (cairo 1.12.16 (http://cairographics.org)) +>> +endobj +7 0 obj +<< /Type /Catalog + /Pages 1 0 R +>> +endobj +xref +0 8 +0000000000 65535 f +0000000574 00000 n +0000000275 00000 n +0000000015 00000 n +0000000253 00000 n +0000000347 00000 n +0000000639 00000 n +0000000768 00000 n +trailer +<< /Size 8 + /Root 7 0 R + /Info 6 0 R +>> +startxref +820 +%%EOF diff --git a/presentation/beamerthemeuwa_eng.sty b/presentation/beamerthemeuwa_eng.sty new file mode 100644 index 0000000..d78ccec --- /dev/null +++ b/presentation/beamerthemeuwa_eng.sty @@ -0,0 +1,160 @@ +% Copyright 2007 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Public License. +% +% See the file doc/licenses/LICENSE for more details. +% Modifed by CBluteau to create the UWA engineering themes + +\ProvidesPackageRCS $Header: /cvsroot/latex-beamer/latex-beamer/themes/theme/beamerthemeuwa_eng.sty,v 1.7 2007/01/28 20:48:30 tantau Exp $ + +\def\themeoption{uwa_pagen} + +\DeclareOption{uwa_pagen}{\def\themeoption{uwa_pagen}} +\DeclareOption{navmenu}{\def\themeoption{navmenu}} +\DeclareOption{sec_navmenu}{\def\themeoption{sec_navmenu}} +\DeclareOption{splitfooter}{\def\themeoption{splitfooter}} + +%\inserttotalframenumber +\ProcessOptions + + +\mode +\usefonttheme{default} +\usecolortheme{default} +\useinnertheme{default} +\useoutertheme{split} + +\usebackgroundtemplate{\includegraphics[width=\paperwidth,height=\paperheight]{uwa_eng.png}} % need this to get the UWA format + +\setbeamertemplate{navigation symbols}{} % remove those weird naviga buttons that are hard to use at the bottom + + + \setbeamertemplate{headline}[default] + +% Defining the 3 UWA footline themes %===================================== + +%Simplest of themes and default one, where currentframenumber / total frame number appears at bottom right + % Modifying the [page numbers] option offered in beamer... to get the footer page number out of the UWA orange outline. + \defbeamertemplate*{footline}{uwa_pagen} + { + \begin{beamercolorbox}[wd=0.95\textwidth,ht=1cm,right]{page number in head/foot} + \vskip2pt \usebeamerfont{page number}\insertframenumber{/}\inserttotalframenumber \vskip3pt + \end{beamercolorbox} + } + + % section navigation menu appears at bottom right of each frame +\defbeamertemplate*{footline}{navmenu} + { + \leavevmode% + \@tempdimb=2.4375ex% + \ifnum\beamer@subsectionmax<\beamer@sectionmax% + \multiply\@tempdimb by\beamer@sectionmax% + \else% + \multiply\@tempdimb by\beamer@subsectionmax% + \fi% + \ifdim\@tempdimb>0pt% + \advance\@tempdimb by 1.125ex + \ifdim\@tempdimb<.47in + \@tempdimb=.47in% + \fi% + \begin{beamercolorbox}[wd=0.99\paperwidth,ht=\@tempdimb,right]{section in head/foot} + \vbox to\@tempdimb{\vfil\insertsectionnavigation{.9\textwidth}\vfil} + \end{beamercolorbox} + \fi% + } + + + %Hybrid of the 2 previous themes. When a new section commences, section menu appears at bottom otherwise you see just the page/total frame number + \defbeamertemplate*{footline}{sec_navmenu} + { + \ifnum\beamer@startpageofsection=\c@page + \leavevmode% + \@tempdimb=2.4375ex% + \ifnum\beamer@subsectionmax<\beamer@sectionmax% + \multiply\@tempdimb by\beamer@sectionmax% + \else% + \multiply\@tempdimb by\beamer@subsectionmax% + \fi% + \ifdim\@tempdimb>0pt% + \advance\@tempdimb by 1.125ex + \ifdim\@tempdimb<.47in + \@tempdimb=.47in% + \fi% + \begin{beamercolorbox}[wd=0.99\paperwidth,ht=\@tempdimb,right]{section in head/foot} + \vbox to\@tempdimb{\vfil\insertsectionnavigation{.33\textwidth}\vfil} + \end{beamercolorbox} + \fi% + \else % placing pge number + \begin{beamercolorbox}[wd=0.95\textwidth,ht=1cm,right]{page number in head/foot} + \vskip2pt \usebeamerfont{page number}\insertframenumber{/}\inserttotalframenumber \vskip3pt + \end{beamercolorbox} + \fi% + } + + % Another custom theme with author in footline (left) and nav menu (bottom right)... + % You can place anything really in the left or right box + \defbeamertemplate*{footline}{splitfooter} + { + \leavevmode% + \@tempdimb=2.4375ex% + \ifnum\beamer@subsectionmax<\beamer@sectionmax% + \multiply\@tempdimb by\beamer@sectionmax% + \else% + \multiply\@tempdimb by\beamer@subsectionmax% + \fi% + \ifdim\@tempdimb>0pt% + \advance\@tempdimb by 1.125ex + \ifdim\@tempdimb<.47in + \@tempdimb=.47in% + \fi% + \hskip5pt +{\begin{beamercolorbox}[wd=.48\paperwidth,dp=1.125ex,leftskip=.3cm plus1fill,left]{author in head/foot}% + \usebeamerfont{author in head/foot}{\insertshortauthor} + \end{beamercolorbox} + \begin{beamercolorbox}[wd=.49\paperwidth,ht=\@tempdimb,right]{section in head/foot} + \vbox to\@tempdimb{\vfil\insertsectionnavigation{.48\textwidth}\vfil}% + \end{beamercolorbox}} + \fi% + } + +\setbeamertemplate{footline}[\themeoption] %apply selected theme + + +%% Creating new titlepage format to avoid text going into the banner========================================== +\defbeamertemplate*{title page}{uwa} +{ + \vspace{2.5cm} + \begin{flushleft} + {\usebeamerfont{title}\usebeamercolor[fg]{title}\inserttitle} + \vskip0pt plus 0.25fill + {\usebeamerfont{subtitle}\usebeamercolor[fg]{subtitle}\insertsubtitle} + \vskip0pt plus 0.5fill + {\usebeamerfont{author}\insertauthor}\\ + \vskip0pt plus 0.25fill + + \begin{columns}[totalwidth=\textwidth, t] + \begin{column}{0.65\textwidth} + {\usebeamerfont{institute}\insertinstitute} + \end{column} + \begin{column}[t]{0.35\textwidth} + \vspace{-1.25cm} + \begin{center} + \inserttitlegraphic + \end{center} + \end{column} + \end{columns} + \end{flushleft} + {\usebeamerfont{date}\insertdate} + \vskip0pt plus 0.25fill +} + +\setbeamertemplate{title page}[uwa] + +\setbeamertemplate{headline}{\vspace{0.25cm}} + + +\mode + diff --git a/presentation/bezier_to_font.pdf b/presentation/bezier_to_font.pdf new file mode 100644 index 0000000..a209115 Binary files /dev/null and b/presentation/bezier_to_font.pdf differ diff --git a/presentation/example_uwa_eng.nav b/presentation/example_uwa_eng.nav new file mode 100644 index 0000000..fd801fd --- /dev/null +++ b/presentation/example_uwa_eng.nav @@ -0,0 +1,47 @@ +\beamer@endinputifotherversion {3.33pt} +\headcommand {\slideentry {0}{0}{1}{1/1}{}{0}} +\headcommand {\beamer@framepages {1}{1}} +\headcommand {\slideentry {0}{0}{2}{2/2}{}{0}} +\headcommand {\beamer@framepages {2}{2}} +\headcommand {\sectionentry {1}{Motivation \& Background}{3}{Motivation \& Background}{0}} +\headcommand {\beamer@sectionpages {1}{2}} +\headcommand {\beamer@subsectionpages {1}{2}} +\headcommand {\slideentry {1}{0}{3}{3/3}{}{0}} +\headcommand {\beamer@framepages {3}{3}} +\headcommand {\slideentry {1}{0}{4}{4/4}{}{0}} +\headcommand {\beamer@framepages {4}{4}} +\headcommand {\slideentry {1}{0}{5}{5/5}{}{0}} +\headcommand {\beamer@framepages {5}{5}} +\headcommand {\sectionentry {2}{Some theory}{6}{Some theory}{0}} +\headcommand {\beamer@sectionpages {3}{5}} +\headcommand {\beamer@subsectionpages {3}{5}} +\headcommand {\slideentry {2}{0}{6}{6/6}{}{0}} +\headcommand {\beamer@framepages {6}{6}} +\headcommand {\sectionentry {3}{Field Methods}{7}{Field Methods}{0}} +\headcommand {\beamer@sectionpages {6}{6}} +\headcommand {\beamer@subsectionpages {6}{6}} +\headcommand {\slideentry {3}{0}{7}{7/7}{}{0}} +\headcommand {\beamer@framepages {7}{7}} +\headcommand {\slideentry {3}{0}{8}{8/8}{}{0}} +\headcommand {\beamer@framepages {8}{8}} +\headcommand {\slideentry {3}{0}{9}{9/9}{}{0}} +\headcommand {\beamer@framepages {9}{9}} +\headcommand {\sectionentry {4}{Modeling}{10}{Modeling}{0}} +\headcommand {\beamer@sectionpages {7}{9}} +\headcommand {\beamer@subsectionpages {7}{9}} +\headcommand {\slideentry {4}{0}{10}{10/10}{}{0}} +\headcommand {\beamer@framepages {10}{10}} +\headcommand {\sectionentry {5}{Modeling2}{11}{Modeling2}{0}} +\headcommand {\beamer@sectionpages {10}{10}} +\headcommand {\beamer@subsectionpages {10}{10}} +\headcommand {\slideentry {5}{0}{11}{11/11}{}{0}} +\headcommand {\beamer@framepages {11}{11}} +\headcommand {\slideentry {5}{0}{12}{12/12}{}{0}} +\headcommand {\beamer@framepages {12}{12}} +\headcommand {\slideentry {5}{0}{13}{13/13}{}{0}} +\headcommand {\beamer@framepages {13}{13}} +\headcommand {\beamer@partpages {1}{13}} +\headcommand {\beamer@subsectionpages {11}{13}} +\headcommand {\beamer@sectionpages {11}{13}} +\headcommand {\beamer@documentpages {13}} +\headcommand {\def \inserttotalframenumber {13}} diff --git a/presentation/example_uwa_eng.pdf b/presentation/example_uwa_eng.pdf new file mode 100644 index 0000000..031c65c Binary files /dev/null and b/presentation/example_uwa_eng.pdf differ diff --git a/presentation/example_uwa_eng.snm b/presentation/example_uwa_eng.snm new file mode 100644 index 0000000..e69de29 diff --git a/presentation/presentation.nav b/presentation/presentation.nav new file mode 100644 index 0000000..6d0bd76 --- /dev/null +++ b/presentation/presentation.nav @@ -0,0 +1,54 @@ +\beamer@endinputifotherversion {3.33pt} +\headcommand {\slideentry {0}{0}{1}{1/1}{}{0}} +\headcommand {\beamer@framepages {1}{1}} +\headcommand {\slideentry {0}{0}{2}{2/2}{}{0}} +\headcommand {\beamer@framepages {2}{2}} +\headcommand {\slideentry {0}{0}{3}{3/3}{}{0}} +\headcommand {\beamer@framepages {3}{3}} +\headcommand {\sectionentry {1}{Motivation \& Background}{4}{Motivation \& Background}{0}} +\headcommand {\beamer@sectionpages {1}{3}} +\headcommand {\beamer@subsectionpages {1}{3}} +\headcommand {\slideentry {1}{0}{4}{4/4}{}{0}} +\headcommand {\beamer@framepages {4}{4}} +\headcommand {\slideentry {1}{0}{5}{5/5}{}{0}} +\headcommand {\beamer@framepages {5}{5}} +\headcommand {\slideentry {1}{0}{6}{6/6}{}{0}} +\headcommand {\beamer@framepages {6}{6}} +\headcommand {\slideentry {1}{0}{7}{7/7}{}{0}} +\headcommand {\beamer@framepages {7}{7}} +\headcommand {\slideentry {1}{0}{8}{8/8}{}{0}} +\headcommand {\beamer@framepages {8}{8}} +\headcommand {\sectionentry {2}{Implementing a Basic SVG Viewer}{9}{Implementing a Basic SVG Viewer}{0}} +\headcommand {\beamer@sectionpages {4}{8}} +\headcommand {\beamer@subsectionpages {4}{8}} +\headcommand {\slideentry {2}{0}{9}{9/9}{}{0}} +\headcommand {\beamer@framepages {9}{9}} +\headcommand {\slideentry {2}{0}{10}{10/10}{}{0}} +\headcommand {\beamer@framepages {10}{10}} +\headcommand {\sectionentry {3}{Live Demo}{11}{Live Demo}{0}} +\headcommand {\beamer@sectionpages {9}{10}} +\headcommand {\beamer@subsectionpages {9}{10}} +\headcommand {\slideentry {3}{0}{11}{11/11}{}{0}} +\headcommand {\beamer@framepages {11}{11}} +\headcommand {\sectionentry {4}{Conclusions}{12}{Conclusions}{0}} +\headcommand {\beamer@sectionpages {11}{11}} +\headcommand {\beamer@subsectionpages {11}{11}} +\headcommand {\slideentry {4}{0}{12}{12/12}{}{0}} +\headcommand {\beamer@framepages {12}{12}} +\headcommand {\sectionentry {5}{References}{13}{References}{0}} +\headcommand {\beamer@sectionpages {12}{12}} +\headcommand {\beamer@subsectionpages {12}{12}} +\headcommand {\sectionentry {6}{Questions}{13}{Questions}{0}} +\headcommand {\beamer@sectionpages {13}{12}} +\headcommand {\beamer@subsectionpages {13}{12}} +\headcommand {\slideentry {6}{0}{13}{13/13}{}{0}} +\headcommand {\beamer@framepages {13}{13}} +\headcommand {\slideentry {6}{0}{14}{14/14}{}{0}} +\headcommand {\beamer@framepages {14}{14}} +\headcommand {\slideentry {6}{0}{15}{15/15}{}{0}} +\headcommand {\beamer@framepages {15}{15}} +\headcommand {\beamer@partpages {1}{15}} +\headcommand {\beamer@subsectionpages {13}{15}} +\headcommand {\beamer@sectionpages {13}{15}} +\headcommand {\beamer@documentpages {15}} +\headcommand {\def \inserttotalframenumber {15}} diff --git a/presentation/presentation.pdf b/presentation/presentation.pdf new file mode 100644 index 0000000..1a2117f Binary files /dev/null and b/presentation/presentation.pdf differ diff --git a/presentation/presentation.snm b/presentation/presentation.snm new file mode 100644 index 0000000..e69de29 diff --git a/presentation/presentation.tex b/presentation/presentation.tex new file mode 100644 index 0000000..9ad4c78 --- /dev/null +++ b/presentation/presentation.tex @@ -0,0 +1,239 @@ +\makeatletter +\newif\ifGm@compatii +\makeatother +\documentclass[12pt,landscape,english]{beamer} +\mode + +\usetheme[navmenu]{uwa_eng} % Three options supported: uwa_pagen (default), navmenu, sec_navmenu, and splitfooter +\usepackage{mathrsfs} +\usepackage{palatino} +\usepackage[T1]{fontenc} +\usepackage[latin1]{inputenc} +\usepackage{times} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{multimedia} +\makeatletter + + +% My personal preferences________________________________ +\definecolor{myframe}{rgb}{0.2,0.2,0.2} % charcoal frametitle +\setbeamercolor{frametitle}{fg=myframe} +\definecolor{mystruc}{rgb}{0,0.25,0.45} % turquoise +\usecolortheme[named=mystruc]{structure} % Changing to blueish green instead of default midnight shade +\setbeamertemplate{headline}{\vspace{0.25cm}} % I personally find that the defaul position of the frametitle is too high +\setbeamercolor{title}{fg=black} % I personally don't like the taking the structure color for the title + +%_________________________________ +% Titlepage info + +\title[short title]{Number Representations and Precision in Vector Graphics} +\subtitle{Implementation of an Arbitrary Precision SVG Viewer} % if you have one +\author{Sam Moore} +% - Give the names in the same order as the appear in the paper. +% - Use the \inst{?} command only if the authors have different +% affiliation. + +\institute[UWA]% (optional) {Universities of Western Australia} +{Supervisors: Tim French, Rowan Davies} + +\date[CSS 2009]{\today} % change the actual date + \titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}} + +%% Optional stuff------------------------------------------------------------------ + +%% Delete this, if you do not want the table of contents to pop up at +%% the beginning of each Section or Subsection: +%\AtBeginSubsection[] % I guess you could replace this with AtBeginSection + %{\begin{frame}{Outline} + %\tableofcontents[currentsection,currentsubsection] + %\end{frame}} + % \AtBeginSection[] % Simplified version of what's above. % Should only be used with uwa_pagen option +% {\begin{frame}{Outline} +% \tableofcontents[currentsection] +% \end{frame}} + +%------------------------------------------------------------------------------------------------- +\begin{document} + + { + \usebackgroundtemplate{\includegraphics[width=\paperwidth,height=\paperheight]{uwa_eng_title.png}} % Required to get the UWA titlepage background different. + \begin{frame}[plain] + \titlepage +\end{frame} +} + + +\begin{frame}[plain] +\frametitle{Contents} + \tableofcontents + % You might wish to add the option [pausesections] +\end{frame} + +\begin{frame} + \frametitle{Summary} + \begin{itemize} + \item Vector graphics allow scaling but not arbitrary scaling + \item We implemented a vector graphics viewer that does allow arbitrary scaling + \item ... but it will take an arbitrary amount of time + \end{itemize} +\end{frame} + +% Start of presentation slides +\section{Motivation \& Background} +\begin{frame} +\frametitle{Graphics Formats} +\begin{itemize} + \item Document formats (eg: PDF and SVG) are formats for vector graphics + \item Vector graphics scale better than raster graphics +\end{itemize} + +\centering +\includegraphics[width=0.5\textwidth]{../figures/fox-vector.pdf} +\includegraphics[width=0.5\textwidth]{../figures/fox-raster.png} + +\end{frame} + + +\begin{frame} +\frametitle{Why is there a zoom limit?} +\centering +\includegraphics{../figures/koch1.pdf} +\end{frame} + +\begin{frame} +\frametitle{Why is there a zoom limit?} +\begin{itemize} + \item SVG, PostScript, PDF specify IEEE-754 \emph{single} floating point number representations + \item Range of values: $\approx 3 \times 10^{-38} \to 3 \times 10^{+38}$ + \item Rough Floating Point Definition\footnote{IEEE-754 is more complicated}: + + \begin{align} + X &= m \times 2^{E} + \end{align} + \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits + \item Floating Point $\approx$ Scientific Notation for computers + +\end{itemize} +\end{frame} + +\begin{frame} +\frametitle{Visualisation of Floats} +\begin{itemize} + \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)} + \item Showing positive numbers only +\end{itemize} +\centering +\includegraphics[width=0.8\textwidth]{../figures/floats.pdf} + +\end{frame} + +\begin{frame} +\frametitle{Floating point calculations \\ go wrong} +\begin{itemize} + \item At scale of only $1\times 10^{-6}$, the fox is very sick +\end{itemize} +\centering + \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png} + \begin{itemize} + \item Plank Length: $1.61 \times 10^{-35}$ metres $ > 3\times10^{-38}$ + \item Size of Universe: $4.3 \times 10^{26}$ metres $ << 3 \times10^{38}$ + \item Why isn't this good enough for $1\times 10^{-6}$ + \end{itemize} +\end{frame} + +\section{Implementing a Basic SVG Viewer} +\begin{frame} +\frametitle{Structure of Vector Graphics} +\begin{itemize} + \item B\'{e}zier Curve (Quadratic or Cubic Parametric Polynomial) + \item Path of B\'{e}zier Curves $\to$ Shapes (with fill) + \item Shapes include font glyphs, like this $\mathscr{Z}$ +\end{itemize} +\centering +\includegraphics[width=0.5\textwidth]{bezier_to_font.pdf} + +\end{frame} + +\begin{frame} +\frametitle{Structure of Vector Graphics III} +\begin{itemize} + \item Rectangles show individual B\'{e}ziers forming outline of the Fox +\end{itemize} +\centering +\includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png} +\end{frame} + +\section{Live Demo} +\begin{frame} +\frametitle{Live Demo} +\begin{itemize} + \item We can import standard SVGs wherever we want + \item If we are willing to wait long enough + \item \tiny{``... But, asks the scientist, what does that turtle stand on? To which the lady triumphantly answers: 'You're very clever, young man, but it's no use -- it's turtles all the way down!'.``} +\end{itemize} +\centering +\includegraphics[width=\textwidth]{turtles.pdf} +\end{frame} + +\section{Conclusions} +\begin{frame} + \frametitle{Conclusions} +\begin{itemize} + \item What we have done? + \begin{itemize} + \item Implemented a basic SVG viewer + \item Demonstrated how precision affects rendering vector graphics + \item Using GMP rationals, demonstrated the ability to render SVGs scaled to an arbitrary position in a document + \end{itemize} + \item Possible future work + \begin{itemize} + \item Implement more of the SVG standard + \item Trial alternative number representations + \item Allow for saving and loading SVGs with arbitrary precision + \end{itemize} +\end{itemize} +\end{frame} +\section{References} + +\section{Questions} + +\begin{frame} +\frametitle{Q: Why don't you have colour?} +\begin{itemize} + \item We do!\footnote{If you are willing to wait long enough} + \item A complete implementation of SVG is ``future work'' +\end{itemize} +\centering +\includegraphics[width=0.5\textwidth]{../figures/shady-the-fox.png} +\includegraphics[width=0.5\textwidth]{../figures/who-the-hell-needs-antialiasing-anyway.png} + +\end{frame} + +\begin{frame} +\frametitle{Q: Why not just use doubles?} +\begin{itemize} + \item Any fixed precision format will still give inexact results + \item But the inexact results will appear slower +\end{itemize} +\end{frame} + +\begin{frame} +\frametitle{Q: Arbitrary precision floats?} +\begin{itemize} + \item We support them as well! + \item Rationals are more convenient: + \begin{itemize} + \item Need to manually set precision + \item Some operations require infinite precision: + \begin{align} + \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0 + \end{align} + \item How do you choose when to increase precision? + \end{itemize} + \item Could be future work +\end{itemize} +\end{frame} + + +\end{document} diff --git a/presentation/turtles.pdf b/presentation/turtles.pdf new file mode 100644 index 0000000..d156bac Binary files /dev/null and b/presentation/turtles.pdf differ diff --git a/presentation/uwa_eng.png b/presentation/uwa_eng.png new file mode 100644 index 0000000..db42db9 Binary files /dev/null and b/presentation/uwa_eng.png differ diff --git a/presentation/uwa_eng_title.png b/presentation/uwa_eng_title.png new file mode 100644 index 0000000..c26efc0 Binary files /dev/null and b/presentation/uwa_eng_title.png differ diff --git a/test b/test new file mode 100644 index 0000000..8235350 --- /dev/null +++ b/test @@ -0,0 +1,3 @@ + + +hi diff --git a/thesis.pdf b/thesis.pdf index 6610108..c51431c 100644 Binary files a/thesis.pdf and b/thesis.pdf differ diff --git a/thesis.tex b/thesis.tex index 3004690..ec75412 100644 --- a/thesis.tex +++ b/thesis.tex @@ -75,6 +75,7 @@ \newcommand{\that}[0]{\hat{\theta}} \newcommand{\vect}[1]{\boldsymbol{#1}} % Draw a vector +\newcommand{\matx}[1]{\boldsymbol{#1}} % Matrix \newcommand{\divg}[1]{\nabla \cdot #1} % divergence \newcommand{\curl}[1]{\nabla \times #1} % curl \newcommand{\grad}[1]{\nabla #1} %gradient @@ -112,6 +113,12 @@ \rhead{\bfseries \thepage} } \cfoot{} +\setlength{\pdfpxdimen}{1in/300} % Define resolution of PDF + +\def\changemargin#1#2{\list{}{\rightmargin#2\leftmargin#1}\item[]} +\let\endchangemargin=\endlist + + %--------------------------------------------------------- %--------------------------------------------------------- @@ -125,7 +132,6 @@ %\include{meta/Acknowledgments} % This is who you thank - \pagenumbering{roman} %\newpage %--------------------------------------------------------- @@ -149,13 +155,18 @@ %--------------------------------------------------------- %Include the chapters! -\include{chapters/Introduction} -\include{chapters/Proposal} -\include{chapters/Background} -\include{chapters/Progress} -%\include{chapters/Conclusion} -%\newpage -%--------------------------------------------------------- + +\input{chapters/Introduction} + +\input{chapters/Background} + +\input{chapters/Process} + +\input{chapters/Results} + +\input{chapters/Conclusion} + +%-------------------------------------------- \renewcommand{\bibname}{References} \bibliography{references/refs} \bibliographystyle{unsrt} @@ -163,26 +174,6 @@ {\bf Note:} We have collated most of these references at \url{http://szmoore.net/ipdf/documents/references/} \vspace*{6\baselineskip} % sigh -\begin{figure}[H] - \centering - \includegraphics[width=0.5\textwidth]{figures/rabbit_simple.pdf} -\end{figure} - -%--------------------------------------------------------- - -% Appendices -%\appendix -%\include{appendices/achievements} -%\include{proposal/proposal.tex} -%\renewcommand\chaptername{Appendix} -%\chapter{Appendix} -%\include{appendices/electron_optics} -%\include{appendices/electron_gun_circuit} -%\include{appendices/tcs_noise} -%\include{appendices/data_aquisition} - - -%--------------------------------------------------------- \end{document} diff --git a/wordcount.sh b/wordcount.sh new file mode 100755 index 0000000..0c63f10 --- /dev/null +++ b/wordcount.sh @@ -0,0 +1,14 @@ +#!/bin/bash +# Count words in thesis + +function doThing { + for i in $1/*.tex; do + 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)" +