-\chapter{Methods and Design}
+\chapter{Methods and Design}\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.
-
-\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)
- \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{Structure of Software}
-\begin{itemize}
- \item CPU and GPU renderer supported
- \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}
+
+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.
+
+\subsection{Document Structure}
+
+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.
+
+\subsection{Rendering Process}
+
+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.
+
+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.
+
+
+
+\subsection{Interactivity}
+
+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.
+
+\subsection{Version Control}
+
+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}
-\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}
+
+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.
+
+
+\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 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.
+
+\subsection{Quadtree Document Division}
+
+An approach identified by Gow\cite{} is to construct intermediate coordinate systems as the user manipulates the view.
+
+
\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 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
+ \item Provides Bitmap handling functions
\end{itemize}
+ \item Qt4 (optional) --- Open source toolkit for Dialog based applications
+ \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
+ \item Highly optimised using CPU specific assembly instructions
\end{itemize}
+ \item MPFR --- built on GMP but ensures IEEE-754 consistent rounding behaviour
\end{itemize}
-\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
-\end{itemize}
-
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au