chapters/Process.tex

   1 \chapter{Methods and Design}
   2
   3 {\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.
   4
   5 \section{Collaborative Process}
   6 \begin{itemize}
   7         \item Collaborated with David Gow on the design and implementation of the SVG viewer
   8         \item Individual work: Applying GMP Rationals (Sam), Quadtree (David)
   9         \begin{itemize}
  10                 \item CPU renderer, SVG parsing, Control Panel, Python Scripts - Sam
  11                 \item Most of the OpenGL stuff, Scaling/Translating controls - David
  12                 \item Other parts were worked on by everyone
  13         \end{itemize}
  14         \item Used git to collaborate \url{https://git.ucc.asn.au}
  15         \item Used preprocessor defines to not interfere with each other's code too much
  16         \item David used a \verb/goto/ letting the team down
  17 \end{itemize}
  18
  19 \section{Structure of Software}
  20 \begin{itemize}
  21         \item CPU and GPU renderer supported
  22         \begin{itemize}
  23                 \item See figure in ``Floating Point Operations on the CPU and GPU''
  24         \end{itemize}
  25         \item Rendering of Cubic B\'{e}ziers (no antialiasing)
  26         \item Partial implementation of shading Paths on CPU (abandoned)
  27         \item Ability to move the view around the document with the mouse
  28         \item Ability to insert an SVG into the view location
  29         \item \verb/typedef/ for number representations
  30         \item Ability to control program through scripts or stdio
  31         \item Hacky python scripts to produce plots by abusing this
  32 \end{itemize}
  33
  34 \section{Approaches to Arbitrary Precision}
  35 \begin{itemize}
  36         \item Replace \emph{all} operations with arbitrary precision (ie: Rationals) - Horrendously slow
  37         \item Change approach to applying coordinate transform \eqref{view-transformation}
  38         \item Apply view transformations directly to objects as the view is transformed, rather than just before rendering
  39         \begin{itemize}
  40                 \item Allows much better precision and range with just regular IEEE-754 floats
  41                 \item But there is an accumulated rounding error, particularly when zooming out and back in, which is bad
  42         \end{itemize}
  43         \item As above, but introduce intermediate coordinate system; use the Path elements
  44         \begin{itemize}
  45                 \item Rendering of individual paths is consistent but overall they drift apart
  46         \end{itemize}
  47         \item As above, but specify Path coordinates with arbitrary precision rationals
  48         \begin{itemize}
  49                 \item Works well, rationals slow down though
  50         \end{itemize}
  51 \end{itemize}
  52
  53 \section{Number Representations Trialed}
  54 \begin{itemize}
  55         \item IEEE-754 single, double, extended
  56         \item Custom implementation of Rationals with \verb/int64_t/
  57         \begin{itemize}
  58                 \item Very limited since the integers grow exponentially and overflow
  59         \end{itemize}
  60         \item Custom implementation of Rationals with custom Arbitrary precision integers
  61         \begin{itemize}
  62                 \item Actually works
  63                 \item Implementation of division is too slow to be feasible
  64         \end{itemize}
  65         \item Custom rationals but with GMP arbitrary precision integers
  66         \begin{itemize}
  67                 \item Our implementation of GCD is not feasible
  68         \end{itemize}
  69         \item Paranoid Numbers; store a operation tree of IEEE-754 floats and simplify the tree wherever \verb/FE_INEXACT/ is \emph{not} raised
  70         \begin{itemize}
  71                 \item This was a really, really, really, bad idea
  72         \end{itemize}
  73         \item Just use GMP rationals already
  74         \begin{itemize}
  75                 \item Works
  76         \end{itemize}
  77
  78         \item MPFR floats
  79         \begin{itemize}
  80                 \item They work, but they don't truly give arbitrary precision
  81                 \item Because you have to specify the maximum precision
  82                 \item However, this can be changed at runtime
  83                 \item Future work: Trial MPFR floats changing the precision as needed
  84         \end{itemize}
  85
  86 \end{itemize}
  87
  88 \section{Libraries Used}
  89 \begin{itemize}
  90         \item SDL2 - Simple Direct media Library
  91         \begin{itemize}
  92                 \item Used for window management and to obtain an OpenGL context
  93                 \item Also provides BMP handling which is useful
  94         \end{itemize}
  95         \item Qt4 (optional)
  96         \begin{itemize}
  97                 \item Open source toolkit for Dialog based applications
  98                 \item We can optionally compile with a Qt4 based control panel
  99                 \item This is useful for interacting with the document
 100                 \item Has way more features than we actually use it for
 101         \end{itemize}
 102         \item OpenGL - Standard API for rendering on GPUs
 103         \begin{itemize}
 104                 \item Using GLSL shaders
 105                 \item B\'{e}ziers are rendered using a Geometry shader which produces line segments
 106         \end{itemize}
 107         \item PugiXML - Open source XML parsing library
 108         \begin{itemize}
 109                 \item Used to parse SVGs
 110         \end{itemize}
 111         \item GNU Multiple Precision (GMP)
 112         \begin{itemize}
 113                 \item Implements arbitrary precision integers, floats, and rationals
 114                 \item We can use the arbitrary precision integers with a custom rational type
 115                 \item Or just use the GMP rational type (much better)
 116                 \item We don't use the floats, because they are hardware dependent
 117         \end{itemize}
 118         \item MPFR
 119         \begin{itemize}
 120                 \item MPFR is built on GMP but ensures IEEE-754 consistent rounding behaviour
 121                 \item (Not hardware dependent)
 122                 \item We can compile with MPFR floats but the precision is currently fixed at compile time
 123         \end{itemize}
 124 \end{itemize}
 125
 126
 127 \section{Design of Performance Tests}
 128 \begin{itemize}
 129         \item This is mostly covered in the Results chapter
 130         \item Control the program through stdin using a python script
 131         \item Results plotted with matplotlib
 132 \end{itemize}
 133