-\chapter{Progress Report}\label{Progress Report}
+\chapter{Progress Report}\label{Progress}
-This chapter outlines the current state of our research in relation to the aims outlined in Chapter \ref{Introduction}.
+We describe the current state of our research in relation to the aims outlined in Chapter \ref{Introduction}.
\section{Literature Review}
-We have examined a range of literature that can be broadly classed into three different areas:
+We have examined a range of literature that can be broadly classed into three different areas (with major references indicated):
\begin{enumerate}
- \item Rendering Vector Graphics
- \item Representations of Vector Documents
- \item Floating Point number representations
+ \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
+ \end{itemize}
\end{enumerate}
-In summary, we have found:
-\begin{itemize}
- \item Rasterisation of Vector Graphics is non-trivial but well understood
- \item Traditionally rasterisation has been performed on the CPU and rendering on a dedicated GPU; current interest is in techniques for utilising the GPU directly to rasterise vector graphics.
- \item The popular standards for document formats including PostScript, PDF, HTML, SVG require IEEE-754 binary32 precision
- \item Fixed precision floating point numbers make a trade off between precision and range
- \item IEEE-754 is widely used although there are instances of languages or processors which do not conform exactly to the standard
- \item GPUs in particular may not conform to IEEE-754, trading some accuracy of operations for performance
-\end{itemize}
+To improve the Literature Review we could consider the following topics in more detail:
+\begin{enumerate}
+ \item Additional approaches to arbitrary or infinite precision, possibly including symbolic computation
+ \item Floating point errors in the context of computing B\'{e}zier Curves or similar
+ \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. OpenGL 3.1 is used to interface with graphics hardware. This software has the following features:
+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 Transformations can be performed on either the GPU or CPU
- \item Performance of rendering can be measured
+ \item The time for rendering can be measured
+ \item Coordinate transformations may be performed on either the GPU or CPU
\end{enumerate}
-We have found the performance of coordinate transforms on the GPU to be far superior to the CPU. However, at large enough scales it becomes apparent that the GPU is performing operations at a lower precision than the CPU. See Figure \ref{}.
-
-
+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 Precision}
+\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{minifloat.pdf} we have also implemented functions to convert arbitrary real numbers (which may themselves 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.
+Mainly motivated by producing Figure \ref{minifloat.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.
-\subsection{Prototype Document Formats}
+\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 closest 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.
+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\cite{}. 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} and \url{david's website probably I guess}\footnote{These are all actually on the same filesystem but it sounds impressive anyway}
+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}. Tasks completed as of the submission of this report are struck through. \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}.
+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}\\
+ {\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
- ? May & Draft Progress Report and Literature Review \\
+ $17^{\text{th}}$ May & Draft Progress Report and Literature Review \\
\hline
$26^{\text{th}}$ May & \emph{Progress Report and Literature Review due.}\\
\hline
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au