\rephrase{0. Here is a brilliant summary of the sections below}
-This chapter provides an overview of relevant literature. The areas of interest can be broadly grouped into two largely seperate categories; Documents and Number Representations.
+This chapter provides an overview of relevant literature. The areas of interest can be broadly grouped into two largely separate categories; Documents and Number Representations.
-The first half of this chapter will be devoted to documents themselves, including: the representation and rendering of low level graphics primitives, how collections of these primitives are represented in document formats, and the various standards for documents in use today.
+The first half of this chapter will be devoted to documents themselves, including: the representation and displaying of graphics primitives\cite{computergraphics2}, and how collections of these primitives are represented in document formats, focusing on well known standards currently in use\cite{plrm, pdfref17, svg2011-1.1}.
-We will find that although there has been a great deal of research into the rendering, storing, editing, manipulation, and extension of document formats, all popular document standards are content to specify at best a single precision IEEE-754 floating point number representations.
+We will find that although there has been a great deal of research into the rendering, storing, editing, manipulation, and extension of document formats, these widely used document standards are content to specify at best a single precision IEEE-754 floating point number representations.
The research on arbitrary precision arithmetic applied to documents is very sparse; however arbitrary precision arithmetic itself is a very active field of research. Therefore, the second half of this chapter will be devoted to considering the IEEE-754 standard, its advantages and limitations, and possible alternative number representations to allow for arbitrary precision arithmetic.
-In Chapter \ref{Progress}, we will discuss our findings so far with regards to arbitrary precision arithmetic applied to document formats.
+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}.
\pagebreak
-\section{Raster and Vector Graphics}\label{vector-vs-raster-graphics}
+\section{Raster and Vector Images}\label{Raster and Vector Images}
+\input{chapters/Background_Raster-vs-Vector}
-\rephrase{1. Here are the fundamentals of graphics (raster and vector, rendering)}
+\section{Rasterising Vector Images}\label{Rasterising Vector Images}
-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 in a much more complex document format capable of containing many other types of information.
+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}.
-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 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\cite{citationneeded}.
+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}.
-The drawback of raster images is that by their very nature there can only be one level of detail. Figures \ref{vector-vs-raster} and \ref{vector-vs-raster-scaled} attempt to illustrate this by comparing raster images to vector images in a similar way to Worth and Packard\cite{worth2003xr}.
+\subsection{Straight Lines}\label{Straight Lines}
+\input{chapters/Background_Lines}
-Consider the right side of Figure \ref{vector-vs-raster}. This is a raster image which should be recognisable as an animal defined by fairly sharp edges. Figure \ref{vector-vs-raster-scaled} shows that zooming on the animal's face causes these edges to appear jagged. 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'' which averages neighbouring pixels in the original image in order to generate extra pixels in the scaled image\cite{citationneeded}.\footnote{The exact appearance of the images at different zoom levels will depend greatly on the PDF viewer or printer used to display this report. On the author's display using the Atril (1.6.0) viewer, the top images appear to be pixel perfect mirror images at a 100\% scale. In the bottom raster image, antialiasing is not applied at zoom levels above $125\%$ and the effect of scaling is quite noticable.}
+\subsection{Spline Curves}\label{Spline Curves}
-%\footnote{\noindent This behaviour may be configured in some PDF viewers (Adobe Reader) whilst others (Evince, Atril, Okular) will choose whether or not to bother with antialiasing based on the zoom level. For best results experiment with changing the zoom level in your PDF viewer.\footnotemark}\footnotetext{On the author's hardware, the animals in the vector and raster images should appear mirrored pixel for pixel; but they may vary slightly on other PDF viewers or display devices.}
+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}
-In contrast, the left sides of Figures \ref{vector-vs-raster} and \ref{vector-vs-raster-scaled} are a vector image. A vector image contains information about a number of geometric shapes. To display this image on modern display hardware, the coordinates are transformed according to the view and \emph{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\cite{citationneeded} --- or they could be if the coordinates are stored with enough precision (see Section \ref{}). Thus, 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\cite{citationneeded}.
+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}.
-\rephrase{Woah, an entire page with only one citation ham fisted in after I had written the rest... and the ``actually writing it'' phase of the Lit Review is off to a great start.}
-
-\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}
-
-\section{Rendering Vector Images}
-
-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 so algorithms for drawing a vector image directly without rasterisation exist. An example is the shading of polygons which is somewhat more complicated on a vector display than a raster display\cite{brassel1979analgorithm, lane1983analgorithm}.
-
-All modern displays of practical interest are raster based. In this section we explore the structure of vector graphics in more detail, and how different primitives are rendered.
-
-\rephrase{After the wall of citationless text in Section \ref{vector-vs-raster-graphics} we should probably redeem ourselves a bit here}
-
-\subsection{Bezier Curves}
-
-The bezier curve is of vital importance in vector graphics.
-
-\rephrase{Things this section lacks}
-\begin{itemize}
- \item Who came up with them (presumably it was a guy named Bezier)
- \item Flesh out how they evolved or came into use?
- \item Naive algorithm
- \item De Casteljau Algorithm
-\end{itemize}
-
-Recently, Goldman presented an argument that Bezier's could be considered as fractal in nature, a fractal being the fixed point of an iterated function system\cite{goldman_thefractal}. Goldman's proof depends upon a modification to the De Casteljau Subdivision algorithm. Whilst we will not go the details of the proof, or attempt comment on its theoretical value, it is interesting to note that Goldman's algorithm is not only worse than the De Casteljau algorithm upon which it was based, but it also performs worse than a naive Bezier rendering algorithm. Figure \ref{bezier-goldman} shows our results using implementations of the various algorithms in python.
-
-\begin{figure}[H]
- \centering
- \includegraphics[width=0.7\textwidth]{figures/bezier-goldman.png}
- \caption{Performance of Bezier Subdivision Algorithms}\label{bezier-goldman}
-\end{figure}
-
-\rephrase{Does the Goldman bit need to be here? Probably NOT. Do I need to check very very carefully that I haven't made a mistake before saying this? YES. Will I have made a mistake? Probably.}
-
-
-\subsection{Shapes}
-Shapes are just bezier curves joined together.
-
-\subsubsection{Approximating a Circle Using Cubic Beziers}
-
-An example of a shape is a circle. We used some algorithm on wikipedia that I'm sure is in Literature somewhere
-\cite{citationneeded} and made a circle. It's in my magical ipython notebook with the De Casteljau stuff.
-
-\subsection{Text}
-Text is just Bezier Curves, I think we proved out point with the circle, but maybe find some papers to cite\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. Beziers are a popular spline which can be created in GUI based graphics editors using several ``control points'' which themselves are not part of the curve.
+\subsubsection{Bezier Curves}
+\input{chapters/Background_Bezier}
\subsection{Shading}
-Shading is actually extremely complicated! \cite{brassel1979analgorithm, lane1983analgorithm}
-\rephrase{Sure, but do we care enough to talk about it? We will run out of space at this rate}
+Algorithms for shading on vector displays involved drawing equally spaced lines within a region; this is limited both in the complexity of shading and the performance required to compute the lines\cite{brassel1979analgorithm}.
-\subsection{Other Things}
-We don't really care about other things in this report.
+On raster displays, shading is typically based upon Lane's algorithm of 1983\cite{lane1983analgorithm} which is implemented in the GPU \cite{kilgard2012gpu}
\rephrase{6. Sort of starts here... or at least background does}
\item They are portable; you can write an amazing document in Mathematica/Matlab but it
\item Scientific journals would need to adapt to other formats and this is not worth the effort
\item No network connection is required to view a PDF (although DRM might change this?)
- \item All rescources are stored in a single file; a website is stored accross many seperate files (call this a ``distributed'' document format?)
+ \item All rescources are stored in a single file; a website is stored accross many separate files (call this a ``distributed'' document format?)
\item You can create PDFs easily using desktop processing WYSIWYG editors; WYSIWYG editors for web based documents are worthless due to the more complex content
\item Until Javascript becomes part of the PDF standard, including Javascript in PDF documents will not become widespread
\item Once you complicate a PDF by adding Javascript, it becomes more complicated to create; it is simply easier to use a series of static figures than to embed a shader in your document. Even for people that know WebGL.
The floats map an infinite set of real numbers onto a discrete set of representations.
+
+
\rephrase{Figure: 8 bit ``minifloats'' (all 255 of them) clearly showing the ``precision vs range'' issue}
The most a result can be rounded in conversion to a floating point number is the units in last place; $m_{N} \times B^{e}$.
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au