-\chapter{Methods and Design}\label{Process}
+\chapter{Implementation of an SVG Viewer}\label{Process}
+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{Structure of Software}
+\section{Software Overview}
-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 David Gow\cite{}. We will give a brief overview of the features and limitations of this software.
+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}.
-\subsection{Document Structure}
+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.
-IPDF is built around Objects which can be rendered either on the CPU (directly altering a bitmap and then uploading to the GPU) or the GPU (via the use of OpenGL GLSL shader programs).
-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.
+ 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}
-\subsection{Rendering Process}
+
+\section{Document Structure}
-As discussed in Section \ref{FloatingPointOnTheGPU
-} it is not clear to what extend GPUs comply with the IEEE-754 standard, and arbitrary precision arithmetic is most easily implemented on the CPU; for this reason a CPU renderer and GPU renderer were implemented.
+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.
-All Objects are represented by their bounding rectangles; in the case of B\'{e}zier curves the control points are stored relative to the bounding rectangle. The rendering process involves converting the bounding rectangle coordinates from Document to Screen space as discussed in Section \ref{}. For both GPU and CPU rendering a B\'{e}zier in screen space is decomposed into straight lines; the CPU renders these lines using Bresenham's algorithm.
+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.
-\subsection{Interactivity}
+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.
-There are two ways to control the IPDF software; manually through use of keyboard and mouse and a Qt4\cite{} based control panel, or automatically through a script containing a sequence of commands to transform the view or insert SVGs. In both cases SVGs can be inserted scaled to the current View rectangle.
+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.
-\subsection{Version Control}
+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} \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}
-The Git version control system was used to collaborate on this project; the main repository may be viewed at \url{http://git.ucc.asn.au/?p=ipdf/code.git}
\section{Approaches to Arbitrary Precision}
-\subsection{Na\"{i}ve Approach}
+\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 were found to be far too inefficient for practical purposes --- for example, rendering a frame with GMP Rationals could take up to 60 seconds at the default view.
+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}
\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 the Results Section \ref{}, 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.
+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{} is to construct intermediate coordinate systems as the user manipulates the view.
-
+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}
-
-The libraries used to compile the IPDF software are:
\begin{itemize}
\item SDL2 - Simple Direct media Library
- \begin{itemize}
- \item Used for window management and to obtain an OpenGL context
- \item Provides Bitmap handling functions
- \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 Highly optimised using CPU specific assembly instructions
- \end{itemize}
- \item MPFR --- built on GMP but ensures IEEE-754 consistent rounding behaviour
-\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.
+ \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