presentation/presentation.tex

   1 \makeatletter
   2 \newif\ifGm@compatii
   3 \makeatother
   4 \documentclass[12pt,landscape,english]{beamer}
   5 \mode<presentation>
   6
   7 \usetheme[navmenu]{uwa_eng} % Three options supported: uwa_pagen (default), navmenu, sec_navmenu, and splitfooter
   8 \usepackage{mathrsfs}
   9 \usepackage{palatino}
  10 \usepackage[T1]{fontenc}
  11 \usepackage[latin1]{inputenc}
  12 \usepackage{times}
  13 \usepackage{amsmath}
  14 \usepackage{amssymb}
  15 \usepackage{multimedia}
  16 \makeatletter
  17
  18
  19 % My personal preferences________________________________
  20 \definecolor{myframe}{rgb}{0.2,0.2,0.2}  % charcoal frametitle
  21 \setbeamercolor{frametitle}{fg=myframe}
  22 \definecolor{mystruc}{rgb}{0,0.25,0.45}  % turquoise
  23 \usecolortheme[named=mystruc]{structure} % Changing to blueish green instead of default midnight shade
  24 \setbeamertemplate{headline}{\vspace{0.25cm}} % I personally find that the defaul position of the frametitle is too high
  25 \setbeamercolor{title}{fg=black} % I personally don't like the taking the structure color for the title
  26
  27 %_________________________________
  28 % Titlepage info
  29
  30 \title[short title]{Number Representations and Precision in Vector Graphics}
  31 \subtitle{Implementation of an Arbitrary Precision SVG Viewer} % if you have one
  32 \author{Sam Moore}
  33 % - Give the names in the same order as the appear in the paper.
  34 % - Use the \inst{?} command only if the authors have different
  35 %   affiliation.
  36
  37 \institute[UWA]% (optional) {Universities of Western Australia}
  38 {Supervisors: Tim French, Rowan Davies}
  39
  40 \date[CSS 2009]{\today} % change the actual date
  41  %\titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}}
  42
  43 %% Optional stuff------------------------------------------------------------------
  44
  45 %% Delete this, if you do not want the table of contents to pop up at
  46 %% the beginning of each Section or Subsection:
  47 %\AtBeginSubsection[] % I guess you could replace this with AtBeginSection
  48   %{\begin{frame}<beamer>{Outline}
  49     %\tableofcontents[currentsection,currentsubsection]
  50   %\end{frame}}
  51  % \AtBeginSection[] % Simplified version of what's above. % Should only be used with uwa_pagen option
  52 %  {\begin{frame}<beamer>{Outline}
  53 %    \tableofcontents[currentsection]
  54 %  \end{frame}}
  55
  56 %-------------------------------------------------------------------------------------------------
  57 \begin{document}
  58
  59    {
  60    \usebackgroundtemplate{\includegraphics[width=\paperwidth,height=\paperheight]{uwa_eng_title.png}} % Required to get the UWA titlepage background different.
  61    \begin{frame}[plain]
  62  \titlepage
  63 \end{frame}
  64 }
  65
  66
  67 \begin{frame}[plain]
  68 \frametitle{Contents}
  69   \tableofcontents
  70   % You might wish to add the option [pausesections]
  71 \end{frame}
  72
  73 \begin{frame}
  74         \frametitle{Summary}
  75         \begin{itemize}
  76                 \item Vector graphics allow scaling but not arbitrary scaling
  77                 \item We implemented a vector graphics viewer that does allow arbitrary scaling
  78                 \item ... but it will take an arbitrary amount of time
  79         \end{itemize}
  80 \end{frame}
  81
  82 % Start of presentation slides
  83 \section{Motivation \& Background}
  84 \begin{frame}
  85 \frametitle{Graphics Formats}
  86 \begin{itemize}
  87         \item Document formats (eg: PDF and SVG) are formats for vector graphics
  88         \item Vector graphics scale better than raster graphics
  89 \end{itemize}
  90
  91 \centering
  92 \includegraphics[width=0.5\textwidth]{../figures/fox-vector.pdf}
  93 \includegraphics[width=0.5\textwidth]{../figures/fox-raster.png}
  94
  95 \end{frame}
  96
  97
  98 \begin{frame}
  99 \frametitle{Why is there a zoom limit?}
 100 \centering
 101 \includegraphics{../figures/koch1.pdf}
 102 \end{frame}
 103
 104 \begin{frame}
 105 \frametitle{Why is there a zoom limit?}
 106 \begin{itemize}
 107         \item SVG, PostScript, PDF specify IEEE-754 \emph{single} floating point number representations
 108         \item Range of values: $\approx 3 \times 10^{-38} \to 3 \times 10^{+38}$
 109         \item Rough Floating Point Definition\footnote{IEEE-754 is more complicated}:
 110
 111         \begin{align}
 112                 X &= m \times 2^{E}
 113         \end{align}
 114         \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
 115         \item Floating Point $\approx$ Scientific Notation for computers
 116
 117 \end{itemize}
 118 \end{frame}
 119
 120 \begin{frame}
 121 \frametitle{Visualisation of Floats}
 122 \begin{itemize}
 123         \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
 124         \item Operations are inexact (in general)
 125 \end{itemize}
 126 \centering
 127 \includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
 128 \end{frame}
 129
 130
 131 \begin{frame}
 132 \frametitle{Structure of Vector Graphics}
 133 \begin{itemize}
 134         \item B\'{e}zier Curve (Quadratic or Cubic Parametric Polynomial)
 135         \item Path of B\'{e}zier Curves $\to$ Shapes (with fill)
 136         \item Shapes include font glyphs, like this $\mathscr{Z}$
 137 \end{itemize}
 138 \centering
 139 \includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}
 140
 141 \end{frame}
 142
 143 \begin{frame}
 144 \frametitle{Structure of Vector Graphics III}
 145 \begin{itemize}
 146         \item Rectangles show individual B\'{e}ziers forming outline of the Fox
 147 \end{itemize}
 148 \centering
 149 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
 150 \end{frame}
 151
 152
 153 \begin{frame}
 154 \frametitle{Floating point calculations \\ go wrong}
 155 \begin{itemize}
 156         \item Scaled to $~1\times 10^{-6}$, the fox is very sick
 157 \end{itemize}
 158 \centering
 159         \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png}
 160
 161 \end{frame}
 162
 163
 164 \begin{frame}
 165         \frametitle{Arbitrary Precision Rationals}
 166         \begin{align}
 167                 Q &= \frac{N}{D}
 168         \end{align}
 169         \begin{itemize}
 170                 \item $N$ and $D$ are arbitrary precision integers
 171         \end{itemize}
 172         \begin{align}
 173                 N &= \sum_{i=0}^{S} d_i \beta^{i}
 174         \end{align}
 175         \begin{itemize}
 176                 \item $d_i$ are fixed size integers, $\beta = 2^{64}$
 177                 \item Size $S$ grows as needed
 178                 \item Operations are always exact
 179                 \item Implemented by GNU Multiple Precision Library
 180         \end{itemize}
 181 \end{frame}
 182
 183 \begin{frame}
 184         \frametitle{Replace floats with rationals?}
 185         \begin{itemize}
 186                 \item Rationals are \emph{slow}
 187                 \item Screen coordinates always in range $0 \to 1$
 188                 \item Introduce intermediate coordinate system
 189                 \begin{itemize}
 190                         \item Many B\'{e}ziers contained in a Path
 191                         \item Use Rationals for bounds of the Path
 192                         \item Use floats to transform B\'{e}zier coordinates
 193                 \end{itemize}
 194         \end{itemize}
 195 \end{frame}
 196
 197 \section{Live Demo}
 198 \begin{frame}
 199 \frametitle{Live Demo}
 200 \begin{itemize}
 201         \item We can import standard SVGs wherever we want
 202         \item If we are willing to wait long enough
 203         \item \tiny{``... But, asks the scientist, what does that turtle stand on? To which the lady triumphantly answers: 'You're very clever, young man, but it's no use -- it's turtles all the way down!'.``}
 204 \end{itemize}
 205 \centering
 206 \includegraphics[width=\textwidth]{turtles.pdf}
 207 \end{frame}
 208
 209 \section{Conclusions}
 210 \begin{frame}
 211         \frametitle{Conclusions}
 212 \begin{itemize}
 213         \item What we have done?
 214         \begin{itemize}
 215                 \item Implemented a basic SVG viewer
 216                 \item Demonstrated how precision affects rendering vector graphics
 217                 \item Using GMP rationals, demonstrated the ability to render SVGs scaled to an arbitrary position in a document
 218         \end{itemize}
 219         \item Possible future work
 220         \begin{itemize}
 221                 \item Implement more of the SVG standard
 222                 \item Trial alternative number representations
 223                 \item Allow for saving and loading SVGs with arbitrary precision
 224         \end{itemize}
 225 \end{itemize}
 226 \end{frame}
 227 \section{References}
 228 \begin{frame}
 229         \frametitle{References \& More information}
 230         \begin{itemize}
 231                 \item Work on SVG viewer collaborative with David Gow
 232                 \begin{itemize}
 233                         \item See David Gow's presentation about Quadtrees
 234                 \end{itemize}
 235                 \item Muller et al, \emph{Handbook of Floating Point Arithmetic},
 236                 \item Hearn, Baker \emph{Computer Graphics}
 237                 \item Kahan et al, \emph{IEEE-754} (1985 and 2008 revision)
 238                 \item Dahlst{\'o}m et al, \emph{SVG WC3 Recommendation 2011}
 239                 \item Grunland et al, \emph{GNU Multiple Precision Manual 6.0.0a}
 240                 \item Kahan's website \url{http://http.cs.berkeley.edu/~wkahan}
 241         \end{itemize}
 242 \end{frame}
 243 \section{Questions}
 244
 245 \begin{frame}
 246 \frametitle{Q: Why don't you have colour?}
 247 \begin{itemize}
 248         \item We do!\footnote{If you are willing to wait long enough}
 249         \item A complete implementation of SVG is ``future work''
 250 \end{itemize}
 251 \centering
 252 \includegraphics[width=0.5\textwidth]{../figures/shady-the-fox.png}
 253 \includegraphics[width=0.5\textwidth]{../figures/who-the-hell-needs-antialiasing-anyway.png}
 254
 255 \end{frame}
 256
 257 \begin{frame}
 258 \frametitle{Q: Why not just use doubles?}
 259 \begin{itemize}
 260         \item Any fixed precision format will still give inexact results
 261         \item But the inexact results will appear slower
 262 \end{itemize}
 263 \end{frame}
 264
 265 \begin{frame}
 266 \frametitle{Q: Arbitrary precision floats?}
 267 \begin{align}
 268         X &= m \times 2^{E}
 269 \end{align}
 270 \begin{itemize}
 271         \item $m$ and $E$ are of arbitrary size
 272         \item Implemented by MPFR or GMP
 273         \item Difficulties:
 274         \begin{itemize}
 275                 \item Need to manually set precision (size) of $m$
 276                 \item Some operations require infinite precision:
 277                 \begin{align}
 278                         \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
 279                 \end{align}
 280                 \item How do you choose when to increase precision?
 281         \end{itemize}
 282 \end{itemize}
 283 \end{frame}
 284
 285
 286 \begin{frame}
 287         \frametitle{Floating Point calculations \\ go wrong}
 288         \begin{itemize}
 289                 \item Plank Length: $1.61 \times 10^{-35}$ metres $ > 3\times10^{-38}$
 290                 \item Size of Universe: $4.3 \times 10^{26}$ metres $ << 3 \times10^{38}$
 291                 \item Why isn't this good enough for $1\times 10^{-6}$
 292         \end{itemize}
 293 \end{frame}
 294
 295 \begin{frame}
 296         \frametitle{Floating point calculations \\ go wrong}
 297         \begin{itemize}
 298                 \item Transforming from document $(x,y)$ $\to$ screen $(X,Y)$
 299                 \item View is at $(v_x,v_y)$ in document, has dimensions $(v_w,v_h)$
 300         \end{itemize}
 301         \begin{align}
 302                 X = \frac{x - v_x}{v_w} &,\quad\quad Y = \frac{y - v_y}{v_h}
 303         \end{align}
 304         \begin{itemize}
 305                 \item Division by $v_w \approx 10^{-6}$ increases the error due to $x - v_x$
 306                 \item Using \emph{double} precision, render correctly down to $v_w \approx 10^{-37}$
 307         \end{itemize}
 308 \end{frame}
 309
 310
 311 \end{document}