chapters/Process.tex

   1 \chapter{Methods and Design}
   2
   3
   4 \section{Structure of Software}
   5
   6 A custom vector graphics viewer called IPDF\footnote{The original name ``Infinite Precision Document Format'' stuck, although 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.
   7
   8 \subsection{Document Structure}
   9
  10 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).
  11
  12 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.
  13
  14 \subsection{Rendering Process}
  15
  16 As discussed in Section \ref{} 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.
  17
  18 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.
  19
  20
  21
  22 \subsection{Interactivity}
  23
  24 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.
  25
  26 \subsection{Version Control}
  27
  28 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}
  29
  30 \section{Approaches to Arbitrary Precision}
  31
  32 \subsection{Na\"{i}ve Approach}
  33
  34 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.
  35
  36 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.
  37
  38
  39 \begin{comment}
  40 \subsubsection{Number Representations Trialed}
  41
  42 \begin{enumerate}
  43         \item IEEE-754 single, double, extended (control)
  44         \item Custom implementation of Rationals with 64 bit integers
  45         \item Custom implementation of Rationals with custom Arbitrary Precision Integers
  46         \item Custom implementation of Rationals but with GMP integers
  47         \item GMP Rationals
  48         \item MPFR Arbitrary Precision Floats
  49         \item iRRAM ``exact'' real arithmetic\cite{}
  50 \end{enumerate}
  51 \end{comment}
  52
  53 \subsection{Intermediate Coordinate Systems}
  54
  55 When an object is visible on the screen it is only necessary to render it accurately to within the nearest pixel.
  56 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.
  57
  58 \subsection{Quadtree Document Division}
  59
  60 An approach identified by Gow\cite{} is to construct intermediate coordinate systems as the user manipulates the view.
  61
  62
  63
  64 \section{Libraries Used}
  65
  66 The libraries used to compile the IPDF software are:
  67 \begin{itemize}
  68         \item SDL2 - Simple Direct media Library
  69         \begin{itemize}
  70                 \item Used for window management and to obtain an OpenGL context
  71                 \item Provides Bitmap handling functions
  72         \end{itemize}
  73         \item Qt4 (optional) --- Open source toolkit for Dialog based applications
  74         \item OpenGL (4.4) --- The standard API for controlling GPUs
  75         \item PugiXML --- Open source XML parsing library used to implement parsing of SVGs
  76         \item GNU Multiple Precision (GMP)
  77         \begin{itemize}
  78                 \item Implements arbitrary precision integers, floats, and rationals
  79                 \item Highly optimised using CPU specific assembly instructions
  80         \end{itemize}
  81         \item MPFR --- built on GMP but ensures IEEE-754 consistent rounding behaviour
  82 \end{itemize}
  83
  84