-\chapter{Methods and Design}
+\chapter{Implementation of an SVG Viewer}\label{Process}
-{\bf TODO} Write most of this section. I suspect I will have to be very selective about what to fit in considering the word limit.
+To better understand the calculations required to represent and render a vector document, whilst allowing maximum flexibility in approaches to arbitrary precision, a custom vector graphics viewer called IPDF\footnote{The original name ``Infinite Precision Document Format'' stuck, although the use of the word ``infinite'' is highly misleading} was implemented for this project in collaboration with Gow \cite{thesisGow}. This chapter gives a brief overview of the features and limitations of this software.
-\section{Collaborative Process}
-\begin{itemize}
- \item Collaborated with David Gow on the design and implementation of the SVG viewer
- \item Individual work: Applying GMP Rationals (Sam), Quadtree (David)
- \begin{itemize}
- \item CPU renderer, SVG parsing, Control Panel, Python Scripts - Sam
- \item Most of the OpenGL stuff, Scaling/Translating controls - David
- \item Other parts were worked on by everyone
- \end{itemize}
- \item Used git to collaborate \url{https://git.ucc.asn.au}
- \item Used preprocessor defines to not interfere with each other's code too much
- \item David used a \verb/goto/ letting the team down
-\end{itemize}
+\section{Software Overview}
+
+The IPDF software has been written using the C++ programming language for x86-64 Debian GNU/Linux machines. The use of C++ offers low level control over CPU and (through the OpenGL API) GPU memory whilst allowing an Object Orientated approach. The choice of C++ was agreed on with Gow \cite{thesisGow}.
+
+IPDF has been tested on a set of SVG images\footnote{These can be found at \url{http://szmoore.net/ipdf/code/src/svg-tests}} prepared by the author. Figure \ref{fox-rendering} shows the rendering of the same vector image used in Figure \ref{vector-vs-raster-scaled} in the IPDF software.
+
+
+ The software is capable of importing SVG images scaled to the current view location, and stores a DOM like representation of the document (for discussion of the Document Object Model (DOM) compared to the PostScript style Interpreted Model, refer to Appendix \ref{An Overview of Document Standards}).
+
+ \begin{figure}[H]
+ \centering
+ \includegraphics[width=0.45\textwidth]{figures/fox-vector_face_with_bezbounds.png}
+ \includegraphics[width=0.45\textwidth]{figures/shady-the-fox.png}
+ \caption{Rendering of Figure \ref{vector-vs-raster-scaled} in the IPDF software \\ a) Outline with individual B\'{e}ziers highlighted in rectangles b) With shading enabled} \label{fox-rendering}
+\end{figure}
+
+
+\section{Document Structure}
+
+IPDF is built around Objects which are internally represented by bounding rectangles, a type, and any additional coordinates and other data required for rendering the object.
+
+Initially only very simple shapes (Rectangles and Circles) were supported, but in order to produce a meaningful demonstration of arbitrary precision viewing, Paths formed from Quadratic or Cubic B\'{e}ziers as specified by the SVG standard were added. Shading of paths is partially implemented but detailed discussion is beyond the scope of this report.
+
+\section{CPU and GPU Renderering}
+
+As discussed in Section \ref{FloatingPointOnTheGPU} it is not clear to what extend GPUs comply with the IEEE-754 standard. In addition, arbitrary precision arithmetic is most easily implemented on the CPU and well supported through libraries such as GMP. For these reasons both a CPU and GPU renderer were implemented.
+
+To render an object on the GPU its bounding rectangle and additional data are provided to a series of OpenGL shader programs. In the case of B\'{e}zier curves, a Geometry shader performs the subdivision on the GPU and the resultant points are drawn with lines.
+
+The CPU renderer behaves similarly, with the exception that a custom ``Renderer'' class performs the function of all three shader programs. A bitmap is directly modified by the CPU and then uploaded to the GPU as a texture for displaying.
+
+Figure \ref{gpufloats.pdf} shows a comparison between the renderering of a circle performed by an x86-64 (CPU) and several GPUs in the IPDF software.
+
+\section{Coordinate Systems and Transformations} \label{Coordinate Systems and Transformations}
+\input{chapters/Background/CoordinateSystems}
+
+
+\section{Interactivity and Obtaining Results}
+
+There are two basic ways to control the IPDF software; manually through use of keyboard and mouse and a Qt4 \cite{Qt4} based control panel, or automatically by reading a script containing a sequence of commands to transform the view or insert test SVGs. More complex control can be obtained by using the Python \texttt{subprocess} module to produce the commands and analyse performance results.
+
+All results presented in Chapter \ref{Results and Discussion} were obtained on a conventional Debian GNU/Linux laptop with an AMD/ATI Radeon series GPU. An attempt was made to cross compile the software for the Windows operating system, but at the time of publication there were difficulties with the Windows 7 OpenGL drivers on the author's system.
+
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=0.3\textwidth]{figures/controlpanel_screenshot.png}
+ \caption{The Qt4 Control Panel provides basic interactivity - inserting an SVG} \label{controlpanel_screenshot.png}
+\end{figure}
+
+
+\section{Version Control}
+
+The Git version control system was used to collaborate and back up work on this project; the main repository may be viewed at \url{http://git.ucc.asn.au/?p=ipdf/code.git} or on Github at \url{http://github.com/szmoore/ipdf-code}.
+
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=\textwidth]{figures/github.png}
+ \caption{Commit statistics from the repository at Github (this author is ``szmoore'')} \label{github.png}
+\end{figure}
-\section{Structure of Software}
-\begin{itemize}
- \item CPU and GPU renderer supported
- \begin{itemize}
- \item See figure in ``Floating Point Operations on the CPU and GPU''
- \end{itemize}
- \item Rendering of Cubic B\'{e}ziers (no antialiasing)
- \item Partial implementation of shading Paths on CPU (abandoned)
- \item Ability to move the view around the document with the mouse
- \item Ability to insert an SVG into the view location
- \item \verb/typedef/ for number representations
- \item Ability to control program through scripts or stdio
- \item Hacky python scripts to produce plots by abusing this
-\end{itemize}
\section{Approaches to Arbitrary Precision}
-\begin{itemize}
- \item Replace \emph{all} operations with arbitrary precision (ie: Rationals) - Horrendously slow
- \item Change approach to applying coordinate transform \eqref{view-transformation}
- \item Apply view transformations directly to objects as the view is transformed, rather than just before rendering
- \begin{itemize}
- \item Allows much better precision and range with just regular IEEE-754 floats
- \item But there is an accumulated rounding error, particularly when zooming out and back in, which is bad
- \end{itemize}
- \item As above, but introduce intermediate coordinate system; use the Path elements
- \begin{itemize}
- \item Rendering of individual paths is consistent but overall they drift apart
- \end{itemize}
- \item As above, but specify Path coordinates with arbitrary precision rationals
- \begin{itemize}
- \item Works well, rationals slow down though
- \end{itemize}
-\end{itemize}
-\section{Number Representations Trialed}
-\begin{itemize}
- \item IEEE-754 single, double, extended
- \item Custom implementation of Rationals with \verb/int64_t/
- \begin{itemize}
- \item Very limited since the integers grow exponentially and overflow
- \end{itemize}
- \item Custom implementation of Rationals with custom Arbitrary precision integers
- \begin{itemize}
- \item Actually works
- \item Implementation of division is too slow to be feasible
- \end{itemize}
- \item Custom rationals but with GMP arbitrary precision integers
- \begin{itemize}
- \item Our implementation of GCD is not feasible
- \end{itemize}
- \item Paranoid Numbers; store a operation tree of IEEE-754 floats and simplify the tree wherever \verb/FE_INEXACT/ is \emph{not} raised
- \begin{itemize}
- \item This was a really, really, really, bad idea
- \end{itemize}
- \item Just use GMP rationals already
- \begin{itemize}
- \item Works
- \end{itemize}
-
- \item MPFR floats
- \begin{itemize}
- \item They work, but they don't truly give arbitrary precision
- \item Because you have to specify the maximum precision
- \item However, this can be changed at runtime
- \item Future work: Trial MPFR floats changing the precision as needed
- \end{itemize}
-
-\end{itemize}
+\subsection{Na\"{i}ve Approach} \label{Naive Approach}
+
+A na\"{i}ve approach would be to replace all floating point operations with arbitrary precision operations, and this was in fact tried in early experiments. This approach requires use of the CPU renderer, as GLSL is restricted to floating point representations. A type definition \texttt{Real} on the CPU can be selected at compile time.
+
+Unfortunately truly arbitrary precision number representations (including custom implementations of Rationals, and the GMP library's rationals) were found to be far too inefficient for practical purposes, and indeed unnecessary. The results shown in Chapter \ref{Results and Discussion} were produced using the GPU renderer, since this na\"{i}ve approach was discarded.
+
+
+\begin{comment}
+\subsubsection{Number Representations Trialed}
+
+\begin{enumerate}
+ \item IEEE-754 single, double, extended (control)
+ \item Custom implementation of Rationals with 64 bit integers
+ \item Custom implementation of Rationals with custom Arbitrary Precision Integers
+ \item Custom implementation of Rationals but with GMP integers
+ \item GMP Rationals
+ \item MPFR Arbitrary Precision Floats
+ \item iRRAM ``exact'' real arithmetic\cite{}
+\end{enumerate}
+\end{comment}
+
+\subsection{Intermediate Coordinate Systems}
+
+When an object is visible on the screen it is only necessary to render it accurately to within the nearest pixel.
+As shown in Chapter \ref{Results and Discussion}, introducing an intermediate coordinate system for a large number of objects and applying transformations to this coordinate system instead of individual objects produces the best results both in terms of reduced rounding errors using floating point arithmetic, and reduced number of required arbitrary precision operations.
+
+\subsection{Quadtree Document Division}
+
+An approach identified by Gow\cite{thesisGow} is to construct intermediate coordinate systems as the user manipulates the view in a spatial structure called a ``Quadtree''. This involves dividing the initial view into four quadrants when the document is scaled by a required amount, and only rendering those quadrant(s) that are visible. The process repeats with additional scaling. With each division objects must be added to the appropriate quadrant, or in the case of objects which span a boundary, clipped. The advantages and disadvantages of this implementation will be explored by Gow\cite{thesisGow}.
+
\section{Libraries Used}
\begin{itemize}
\item SDL2 - Simple Direct media Library
- \begin{itemize}
- \item Used for window management and to obtain an OpenGL context
- \item Also provides BMP handling which is useful
- \end{itemize}
- \item Qt4 (optional)
- \begin{itemize}
- \item Open source toolkit for Dialog based applications
- \item We can optionally compile with a Qt4 based control panel
- \item This is useful for interacting with the document
- \item Has way more features than we actually use it for
- \end{itemize}
- \item OpenGL - Standard API for rendering on GPUs
- \begin{itemize}
- \item Using GLSL shaders
- \item B\'{e}ziers are rendered using a Geometry shader which produces line segments
- \end{itemize}
- \item PugiXML - Open source XML parsing library
- \begin{itemize}
- \item Used to parse SVGs
- \end{itemize}
+
+ SDL2 is a cross-platform library commonly used in games for window management and to obtain an OpenGL context.
+ We have also made some use of the SDL2 bitmap handling functions to save screenshots.
+
+ \item Qt4 (optional) --- Open source toolkit for Dialog based applications
+
+ The control panel shown in Figure \ref{controlpanel_screenshot.png} was created using Qt4. Use of Qt4 can cause difficulties in compiling the software, so it can be disabled at compile time.
+ \item OpenGL (4.4) --- The standard API for controlling GPUs
+ \item PugiXML --- Open source XML parsing library used to implement parsing of SVGs
\item GNU Multiple Precision (GMP)
- \begin{itemize}
- \item Implements arbitrary precision integers, floats, and rationals
- \item We can use the arbitrary precision integers with a custom rational type
- \item Or just use the GMP rational type (much better)
- \item We don't use the floats, because they are hardware dependent
- \end{itemize}
- \item MPFR
- \begin{itemize}
- \item MPFR is built on GMP but ensures IEEE-754 consistent rounding behaviour
- \item (Not hardware dependent)
- \item We can compile with MPFR floats but the precision is currently fixed at compile time
- \end{itemize}
-\end{itemize}
-
+
+ As discussed in Sections \ref{Big Integers}, \ref{Arbitrary Precision Floating Point Numbers}, \ref{Rational Number Representations} GMP implements arbitrary precision integers, floats, and rationals. Although we did explore these representations by producing custom implementations, examining the GMP source code reveals that it is highly optimised using CPU specific assembly instructions, and vastly outperformed straight forward C++ implementations of Big Integers and Rationals.
-\section{Design of Performance Tests}
-\begin{itemize}
- \item This is mostly covered in the Results chapter
- \item Control the program through stdin using a python script
- \item Results plotted with matplotlib
+ \item MPFR --- Arbitrary precision floats built on GMP but ensures IEEE-754 consistent rounding behaviour.
+ The IPDF software may be compiled with MPFR floats in place of IEEE-754 floats. The precision (size of mantissa) must be set to an arbitrary large but fixed size at compile time.
\end{itemize}
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au