Literally Reviewed To Death
authorSam Moore <matches@ucc.asn.au>
Mon, 19 May 2014 18:54:02 +0000 (02:54 +0800)
committerSam Moore <matches@ucc.asn.au>
Mon, 19 May 2014 18:54:02 +0000 (02:54 +0800)
Don't expect me to remember what I actually did, it's 3am.

.gitignore
chapters/Background.tex
chapters/Background_Bezier.tex
chapters/Background_DOM.tex [new file with mode: 0644]
chapters/Background_Lines.tex
figures/rabbit.html
figures/shape.pdf
thesis.pdf
thesis.tex

index 5197191..57e9477 100644 (file)
@@ -9,3 +9,4 @@
 page*.pdf
 page*.svg
 ratings.db
+*.pyg
index e5720ae..bc3b089 100644 (file)
@@ -15,7 +15,7 @@ In Chapter \ref{Progress}, we will discuss our findings so far with regards to a
 
 Throughout Section \ref{vector-vs-raster-graphics} we were careful to refer to ``modern'' display devices, which are raster based. It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}.
 
-Hearn and Baker's textbook ``Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in ``Computer Graphics'' and the relevant literature. Informal tutorials are abundant on the internet\cite{elias2000graphics}. This section is by no means a comprehensive survey of the literature but intends to provide some idea computations which are required to render a document.
+Hearn and Baker's textbook ``Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in ``Computer Graphics'' and the relevant literature. Informal tutorials are abundant on the internet\cite{elias2000graphics}. This section is by no means a comprehensive survey of the literature but intends to provide some idea of the computations which are required to render a document.
 
 \subsection{Straight Lines}\label{Straight Lines}
 \input{chapters/Background_Lines}
@@ -30,7 +30,7 @@ Splines are continuous curves formed from piecewise polynomial segments. A polyn
 
 A straight line is simply a polynomial of $0$th degree. Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and rendering straight lines between  $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}. More direct algorithms for drawing splines based upon Brasenham and Wu's algorithms also exist\cite{citationneeded}.
 
-There are many different ways to define a spline. One approach is to specify ``knots'' on the spline and solve for the cooefficients to generate a cubic spline ($n = 3$) passing through the points. Alternatively, there are many ways to specify a spline using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors.
+There are many different ways to define a spline. One approach is to specify ``knots'' on the spline and solve for the cooefficients to generate a cubic spline ($n = 3$) passing through the points. Alternatively, special polynomials may be defined using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors. For example, drawing bezier curves with the mouse is the primary method of constructing paths in the Inkscape SVG editor\cite{inkscape}.
 
 \subsubsection{Bezier Curves}
 \input{chapters/Background_Bezier}
@@ -42,7 +42,14 @@ Algorithms for shading on vector displays involved drawing equally spaced lines
 On raster displays, shading is typically based upon Lane's algorithm of 1983\cite{lane1983analgorithm}. Lane's algorithm relies on the ability to ``subtract'' fill from a region. This algorithm is now implemented in the GPU \rephrase{stencil buffer-y and... stuff} \cite{kilgard2012gpu}
 
 \subsection{Compositing}
-\input{chapters/Background_Compositing} 
+
+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.
+
+Most raster displays are based on an additive red-green-blue colour representation which matches the human eye's response to light\cite{citationneeded}. In 1984, Porter and Duff introduced a fourth colour channel to be used when combining rasterised images called the ``alpha'' channel, analogous to the transparency of a pixel\cite{porter1984compositing}. Elements can be rendered seperately, with the four colour channels of successively drawn elements being combined according to one of several possible operations described by Porter and Duff. 
+
+In the ``painter's model'' described by the SVG standard, the ``over'' operation is used when rendering one primitive over another; the red-green-blue components of overlapping pixels are added but the alpha component is set to that of the uppermost pixel\cite{svg2011-1.1}. The PostScript and PDF standards also use the ``painter's model''. The painter's model is demonstrated in Figure \ref{SVG} --- originally an SVG image but converted to a PDF for inclusion in this report\footnote{PDF and SVG formats may be converted but neither standard allows for importing the other directly}.
+
+\subsection{Rasterisation on the CPU and GPU}
 
 Traditionally, vector graphics have been rasterized by the CPU before being sent to the GPU for drawing\cite{kilgard2012gpu}. Lots of people would like to change this \cite{worth2003xr, loop2007rendering, rice2008openvg, kilgard2012gpu, green2007improved}.
 
@@ -52,7 +59,9 @@ Traditionally, vector graphics have been rasterized by the CPU before being sent
 
 The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper referenced earlier has been produced on a mechanical type writer. Although the paper discusses an algorithm for shading on computer displays, the figures illustrating this algorithm have not been generated by a computer, but drawn by Brassel's assistant\cite{brassel1979analgorithm}. In contrast, modern papers such as Barnes et. al's recent paper on embedding 3d images in PDF documents\cite{barnes2013embeddding} can themselves be an interactive proof of concept.
 
-Hayes' 2012 article ``Pixels or Perish'' discusses the recent history and current state of the art in documents for scientific publications\cite{hayes2012pixels}. Hayes argued that there are currently two different approaches to representing documents although the line between these two philosophies is being blurred. We shall restrict ourselves to considering the standards discussed by Hayes.
+\rephrase{Say some stuff about Knuth's Metafont and \TeX here}
+
+Hayes' 2012 article ``Pixels or Perish'' discusses the recent history and current state of the art in documents for scientific publications\cite{hayes2012pixels}.
 
 \subsection{Interpreted Model}
 
@@ -79,19 +88,8 @@ Hayes' 2012 article ``Pixels or Perish'' discusses the recent history and curren
        \item Solves security issues, more efficient
 \end{itemize}
 
-\subsection{Document Object Model}
-
-The Document Object Model (DOM) represents a document as a tree like data structure with the document as a root node. The elements of the document are represented as children of either this root node or of a parent element. In addition, elements may have attributes which contain information about that particular element.
-
-The DOM is described by the W3C XML (extensible markup language) standard\cite{citationneeded}. XML itself is a general language which is intended for  representing any tree-like structure using the DOM, whilst languages such as HTML\cite{citationneeded} and SVG\cite{citationneeded} are specific XML based languages for representing visual information.
-
-The HyperText Markup Language (HTML) was, as its name implies, originally intended mostly for text. When combined with Cascading Style Sheets (CSS) control over the positioning and style of the text can be acheived. Images stored in some other format can be rendered within a HTML document, but HTML does not include ways to specify graphics primitives or their coordinates.
-
-The Scalable Vector Graphics (SVG) standard was designed to represent a vector image. In the SVG standard, each graphics primitive is an element in the DOM, whilst attributes of the element give information about how the primitive is to be drawn, such as path coordinates, line thickness, mitre styles and fill colours. 
-
-\subsubsection{Modifying the DOM --- Javascript}
-
-Javascript is now ubiquitous in web based documents, and is essentially used to make the DOM interactive. This can be done by altering the attributes of elements, or adding and removing elements from the DOM, in response to some event such as user input or communication with a HTTP server. In the HTML5 standard, it is also possible to draw directly to a region of the document defined by the \verb/<canvas>/ tag; as Hayes points out, this is similar to the use of PostScript in specifying the appearance of a document using low level drawing operators which are read by an interpreter.
+\subsection{Document Object Model}\label{Document Object Model}
+\input{chapters/Background_DOM}
 
 \subsection{Scientific Computation Packages}
 
@@ -115,8 +113,14 @@ We briefly summarise the requirements of standard document formats in regards to
        \item {\bf PDF} has also specified IEEE-754 binary32 since version ?. Importantly, the standard states that this is a \emph{maximum} precision; documents created with higher precision would not be viewable in Adobe Reader.
        \item {\bf SVG} specifies a minimum of IEEE-754 binary32 but recommends more bits be used internally
        \item {\bf Javascript} uses binary32 floats for all operations, and does not distinguish between integers and floats.   
+       \item {\bf Python} uses binary64 floats
+       \item {\bf Matlab} uses binary64 floats
+       \item {\bf Mathematica} uses some kind of terrifying symbolic / arbitrary float combination
+       \item {\bf Maple} is similar but by many accounts horribly broken
+       
 \end{itemize}
 
+
 \rephrase{4. Here is IEEE-754 which is what these standards use}
 
 \section{Real Number Representations}
@@ -125,7 +129,13 @@ We have found that PostScript, PDF, and SVG document standards all restrict them
 
 In this section we will begin by investigating floating point numbers as defined in the IEEE standard and their limitations. We will then consider alternative number representations including fixed point numbers, arbitrary precision floats, rational numbers, p-adic numbers and symbolic representations. \rephrase{Oh god I am still writing about IEEE floats let alone all those other things}
 
-\subsection{Floating Point}
+\rephrase{Reorder to start with Integers, General Floats, then go to IEEE, then other things}
+
+\subsection{IEEE Floating Points}
+
+Although the concept of a floating point representation has been attributed to various early computer scientists including Charles Babbage\cite{citationneeded}, it is widely accepted that William Kahan and his colleagues working on the IEEE-754 standard in the 1980s are the ``fathers of modern floating point computation''\cite{citationneeded}. The original IEEE-754 standard specified the encoding, number of bits, rounding methods, and maximum acceptable errors for the basic floating point operations for base $B = 2$ floats. It also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero\footnote{Kahan has argued that exceptions in IEEE-754 are conceptually different to Exceptions as defined in several programming languages including C++ and Java. An IEEE exception is intended to prevent an error by its detection, whilst an exception in those languages is used to indicate an error has already occurred\cite{}}. We will restrict ourselves to considering $B = 2$, since it was found that this base in general gives the smallest rounding errors\cite{HFP}, although it is worth noting that different choices of base had been used historically\cite{goldman1991whatevery}, and the IEEE-854 and later the revised IEEE-754 standard specify a decimal representation $B = 10$ intended for use in financial applications.
+
+\subsection{Floating Point Definition}
 
 A floating point number $x$ is commonly represented by a tuple of integers $(s, e, m)$ in base $B$ as\cite{HFP, ieee2008-754}:
 
@@ -136,31 +146,35 @@ A floating point number $x$ is commonly represented by a tuple of integers $(s,
 Where $s$ is the sign and may be zero or one, $m$ is commonly called the ``mantissa'' and $e$ is the exponent.
 The name ``floating point'' refers to the equivelance of the $\times B^e$ operation to a shifting of a decimal point along the mantissa. This contrasts with a ``fixed point'' representation where $x$ is the sum of two fixed size numbers representing the integer and fractional part.
 
-
-
-\subsection{The IEEE-754 Standard}
-
-Although the concept of a floating point representation has been attributed to various early computer scientists including Charles Babbage\cite{citationneeded}, it is widely accepted that William Kahan and his colleagues working on the IEEE-754 standard in the 1980s are the ``fathers of modern floating point computation''\cite{citationneeded}. The IEEE standard specifies the encoding, number of bits, rounding methods, and maximum acceptable errors for the basic floating point operations. It also specifies ``exceptions'' --- mechanisms by which a program can detect an error such as division by zero.
-
-In the IEEE-754 standard, for a base of $B = 2$, numbers are encoded in continuous memory by a fixed number of bits, with $s$ occupying 1 bit, followed by $e$ and $m$ occupying a number of bits specified by the precision; 5 and 10 for a binary16 or ``half precision'' float, 8 and 23 for a binary32 or ``single precision'' and 15 and 52 for a binary64 or ``double precision'' float\cite{HFP, ieee2008-754}. The IEEE-754 standard also specifies a base 10 encoding (useful in financial software\cite{citationneeded}), but since this is subject to similar limitations, we will restrict ourselves to the simpler base 2 encodings.
+In the IEEE-754 standard, for a base of $B = 2$, numbers are encoded in continuous memory by a fixed number of bits, with $s$ occupying 1 bit, followed by $e$ and $m$ occupying a number of bits specified by the precision; 5 and 10 for a binary16 or ``half precision'' float, 8 and 23 for a binary32 or ``single precision'' and 15 and 52 for a binary64 or ``double precision'' float\cite{HFP, ieee2008-754}.
 
 
 \subsection{Precision and Rounding}
 
-Real values which cannot be represented exactly in a floating point representation must be rounded. The results of a floating point operation may be such values and thus there is a rounding error possible in any floating point operation. Goldberg's assertively titled 1991 paper ``What Every Computer Scientist Needs to Know about Floating Point Arithmetic'' provides a comprehensive overview of issues in floating point arithmetic and relates these to the 1984 version of the IEEE-754 standard\cite{goldberg1991whatevery}. More recently, after the release of the revised IEEE-754 standard, 
+Real values which cannot be represented exactly in a floating point representation must be rounded. The results of a floating point operation will in general be such values and thus there is a rounding error possible in any floating point operation. Goldberg's assertively titled 1991 paper ``What Every Computer Scientist Needs to Know about Floating Point Arithmetic'' provides a comprehensive overview of issues in floating point arithmetic and relates these to the 1984 version of the IEEE-754 standard\cite{goldberg1991whatevery}. More recently, after the release of the revised IEEE-754 standard in 2008, a textbook ``Handbook Of Floating Point Arithmetic'' has been published which provides a thourough review of literature relating to floating point arithmetic in both software and hardware\cite{HFP}.
 
-Figure \ref{minifloat.pdf} shows the real numbers which can be represented exactly by an 8 bit base $B = 2$ floating point number; and illustrates that a set of fixed precision floating point numbers forms a discrete approximation of the reals. There are only $2^8 = 256$ numbers in this set, which means it is easier to see some of the properties of floats that would be unclear using one of the IEEE-754 encodings. The first set of points corresponds to using $(1,2,5)$ to encode $(s,e,m)$ whilst the second set of points corresponds to a $(1,3,4)$ encoding. This allows us to see the trade off between the precision and range of real values represented. 
 
+Figure \ref{minifloat.pdf} shows the positive real numbers which can be represented exactly by an 8 bit base $B = 2$ floating point number; and illustrates that a set of fixed precision floating point numbers forms a discrete approximation of the reals. There are only $2^7 = 256$ numbers in this set, which means it is easier to see some of the properties of floats that would be unclear using one of the IEEE-754 encodings. The first set of points corresponds to using 2 and 5 bits to encode $e$ and $m$ whilst the second set of points corresponds to a 3 and 4 bit encoding. This allows us to see the trade off between the precision and range of real values represented. 
+
+\begin{figure}[H]
+       \centering
+       \includegraphics[width=0.8\textwidth]{figures/minifloat.pdf} \\
+       \includegraphics[width=0.8\textwidth]{figures/minifloat_diff.pdf}
+       \caption{The mapping of 8 bit floats to reals}
+\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{citationneeded}. The improvement of FPUs remains highly active in several areas including: efficiency\cite{seidel2001onthe}; accuracy of operations\cite{dieter2007lowcost}; and even the adaptation of algorithms originally used in software for reducing the overal error of a sequence of operations\cite{kadric2013accurate}. In this section we will consider the algorithms for floating point operations without focusing on the hardware implementation of these algorithms.
 
 
-\subsection{Limitations Imposed By CPU}
+\subsection{Some sort of Example(s) or Floating Point Mayhem}
+
+\rephrase{Eg: $f(x) = |x|$ calculated from sqrt and squaring}
 
-CPU's are restricted in their representation of floating point numbers by the IEEE standard.
+\rephrase{Eg: Massive rounding errors from calculatepi}
 
+\rephrase{Eg: Actual graphics things :S}
 
 
 \subsection{Limitations Imposed By Graphics APIs and/or GPUs}
@@ -174,6 +188,7 @@ Traditionally algorithms for drawing vector graphics are performed on the CPU; t
        \item OpenGL standards specify: binary16, binary32, binary64
        \item OpenVG aims to become a standard API for SVG viewers but the API only uses binary32 and hardware implementations may use less than this internally\cite{rice2008openvg}
        \item It seems that IEEE has not been entirely successful; although all modern CPUs and GPUs are able to read and write IEEE floating point types, many do not conform to the IEEE standard in how they represent floating point numbers internally. 
+       \item \rephrase{Blog post alert} \url{https://dolphin-emu.org/blog/2014/03/15/pixel-processing-problems/}
 \end{itemize}
 
 
index 3652358..2d49de9 100644 (file)
@@ -7,6 +7,7 @@ Points $P(t)$ along the curve are defined by:
 From this definition it should be apparent $P(t)$ for a Bezier Curve of degree $0$ maps to a single point, whilst $P(t)$ for a Bezier of degree $1$ is a straight line between $P_0$ and $P_1$. $P(t)$ always begins at $P_0$ for $t = 0$ and ends at $P_n$ when $t = 1$.
 
 Figure \ref{bezier_3} shows a Bezier Curve defined by the points $\left\{(0,0), (1,0), (1,1)\right\}$.
+Figure \ref{SVG} shows a more complex spline defined by Bezier curves.
 
 A straightforward algorithm for rendering Bezier's is to simply sample $P(t)$ for some number of values of $t$ and connect the resulting points with straight lines using Bresenham or Wu's algorithm (See Section \ref{Straight Lines}). Whilst the performance of this algorithm is linear, in ???? De Casteljau derived a more efficient means of sub dividing beziers into line segments.
 
diff --git a/chapters/Background_DOM.tex b/chapters/Background_DOM.tex
new file mode 100644 (file)
index 0000000..bb5d169
--- /dev/null
@@ -0,0 +1,55 @@
+
+The Document Object Model (DOM) represents a document as a tree like data structure with the document as a root node. The elements of the document are represented as children of either this root node or of a parent element. In addition, elements may have attributes which contain information about that particular element.
+
+The DOM is described within several W3C standards including XML, HTML and SVG. XML is a general language which is intended for representing any tree-like structure using the DOM, whilst languages such as HTML\cite{citationneeded} and SVG\cite{citationneeded} are specifically intended for representing visual information. SVG is defined as a type of XML, whilst HTML is tecnically distinct from XML. Both HTML and XML are supposedly be based upon a language called SGML which is not actually defined \rephrase{except in the foulest chapters of the necromonicom}. Then there is XHTML which is HTML but also XML. \rephrase{Cut the crap about what is and is not valid XML? We only care about the DOM we're not fucking web designers here}.
+
+The HyperText Markup Language (HTML) was, as its name implies, originally intended mostly for text. When combined with Cascading Style Sheets (CSS) control over the positioning and style of the text can be acheived. Images stored in some other format can be rendered within a HTML document, but HTML does not include ways to specify graphics primitives or their coordinates.
+
+The Scalable Vector Graphics (SVG) standard was designed to represent a vector image. In the SVG standard, each graphics primitive is an element in the DOM, whilst attributes of the element give information about how the primitive is to be drawn, such as path coordinates, line thickness, mitre styles and fill colours. Figure \ref{SVG} shows an example of an image defined using the SVG format. The first two lines are only required for a stand alone image; the HTML standard allows for rendering an SVG within a web page using the \verb/<svg>/ tag. \rephrase{Read the standards a bit more carefully here...}
+
+
+\begin{figure}[H]
+\begin{minipage}[t]{0.3\textwidth}
+       \begin{figure}[H]
+       \centering
+       \includegraphics[width=1\textwidth]{figures/shape.pdf}
+       \end{figure}
+\end{minipage}
+\begin{minipage}[t]{0.5\textwidth}
+\begin{minted}{xml}
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" 
+       "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+
+<svg id="svg_example" xmlns="http://www.w3.org/2000/svg"
+       version="1.1" width="104" height="186">
+<path id="straightline" d = "m 0, 0 104, 186" 
+       style="stroke:#000000;"/>
+<rect id="rect1"
+       x = "30" y = "20" width = "30" height = "150"
+       style = "fill:#0000ff; fill-opacity:0.5; 
+               stroke:#000000;"/>
+<path id="path"
+       d = "m 57,185 c 0,0 57,-13 32,-43 -25,-30 -53,2 -25,
+               -30 28,-32 52,17 28,-32 -24,-50 -16,44 -35,12 
+               -19,-32 13,-64 13,-64 0,0 40,-50 -0,-14 -40,36 
+               -94,68 -59,109 35,41 45,62 45,62 z"
+       style = "fill:#ff0000; fill-opacity:0.75; 
+               stroke:#000000;"/>
+<rect id="rect2"
+       x = "12" y = "130" width = "60" height = "20"
+       style = "fill:#00ff00; fill-opacity:0.5; 
+               stroke:#000000;"/>
+</svg>
+\end{minted}
+\end{minipage}
+       \caption{A vector image demonstrating some ideas from Section\ref{Rasterising Vector Images} and it's representation in SVG}\label{SVG}
+\end{figure}
+
+
+\subsubsection{Modifying the DOM --- Javascript}
+
+Javascript is now ubiquitous in web based documents, and is essentially used to make the DOM interactive. This can be done by altering the attributes of elements, or adding and removing elements from the DOM, in response to some event such as user input or communication with a HTTP server. \rephrase{For some really shitty examples of this, see \url{http://szmoore.net/ipdf/sam/figures/rabbit.html} and \url{http://szmoore.net/ipdf/sam/figures/shape.html}}.
+
+In the HTML5 standard, it is also possible to draw directly to a region of the document defined by the \verb/<canvas>/ tag; as Hayes points out, this is similar to the use of PostScript in specifying the appearance of a document using low level drawing operators which are read by an interpreter. \rephrase{Say some stuff about WebGL or get as far away from this topic as possible while we still can?}
+
index 581a653..84561bb 100644 (file)
@@ -1,19 +1,22 @@
 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 = 
+       \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{}). Modifications based on computing steps $\delta x$ and $\delta y$ eliminate the multiplication but are still less than ideal in terms of performance\cite{computergraphics2}.
+On a raster display, only points $(x,y)$ with integer coordinates can be displayed; however $m$ will generally not be an integer. Thus a straight forward use of Equation \ref{eqn_line} will require costly floating point operations and rounding (See Section\ref{}). 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$; if $|m| > 1$ then sampling at every integer for $x$ would leave gaps in the line. However 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{citationneeded}. \rephrase{I studied this sort of thing in Physics, once upon a time... if you just say "Nyquist Sampling" and wave your hands people usually buy it.}
+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 anti-aliased 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 anti-aliasing primitives other than straight lines, including the anti-aliasing of images in a raster format shown at different scales (such as Figure \ref{}) are discussed in some detail in Chapter 4 of ``Computer Graphics'' \cite{computergraphics2}}.
+.
 
-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 antialiased lines which, while equivelant in results to existing algorithms by Fujimoto and Iwata, set the state of the art in performance\cite{wu1991anefficient}.
 
-\rephrase{NOTE: Should I actually discuss how the algorithms work? Or just ``review'' the literature? Bearing in mind that how they actually work doesn't really relate to infinite precision document formats...}
 
 \begin{figure}[H]
        \centering
@@ -21,6 +24,5 @@ Figure \ref{rasterising-line} c) shows an (idealised) antialiased rendering of t
        \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) Antialiased Line (Idealised)
-\end{figure} % As much as I hate to break up the party, these fit best over the page (at the moment)
-
+       a) Before Rasterisation b) Bresenham's Algorithm c) Anti-aliased Line (Idealised)
+\end{figure}
index d9902e1..74fa015 100644 (file)
@@ -9,7 +9,7 @@
                original = document.getElementById("rabbit").cloneNode();
                original.setAttribute("id", "original");
        }
-       function permutePaths()
+       function perturbPaths()
        {
                var amount = document.getElementById("permute_amount").value;
                var paths = document.getElementsByTagName("path");
 </svg>
        <p></p>
        <input type="text" value="0" id="permute_amount"/>
-       <button onclick="permutePaths();">Permute</button>
+       <button onclick="perturbPaths();">Perturb Paths</button>
 
        <button onclick="reset();">Reset</button>
 </body>
index 54d3670..d896a55 100644 (file)
Binary files a/figures/shape.pdf and b/figures/shape.pdf differ
index 4766a9e..99f62bb 100644 (file)
Binary files a/thesis.pdf and b/thesis.pdf differ
index 6808cbd..0db8399 100644 (file)
@@ -35,7 +35,9 @@
 {\normalfont\LARGE\bfseries}{\thechapter.}{1em}{}
 
 %\usepackage[usenames,dvipsnames]{color}
-%\usepackage{listings} % For code snippets
+\usepackage{minted} % For code snippets
+\AtBeginEnvironment{minted}{\singlespacing%
+    \fontsize{8}{8}\selectfont}
 \definecolor{pink}{rgb}{1.0,0.5,0.5}
 \definecolor{darkgray}{rgb}{0.1,0.1,0.1}
 \definecolor{lightgray}{rgb}{0.95,0.95,0.95}

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