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