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
  68 \begin{frame}
  69         \frametitle{Summary}
  70         \begin{itemize}
  71                 \item Vector graphics allow detail to be scaled but not by an arbitrary amount
  72                 \item We've implemented a vector graphics viewer which does allow arbitrary scaling
  73         \end{itemize}
  74 \end{frame}
  75
  76 %\begin{frame}[plain]
  77 %\frametitle{Contents}
  78 %  \tableofcontents
  79   % You might wish to add the option [pausesections]
  80 %\end{frame}
  81
  82
  83 % Start of presentation slides
  84 \section{Motivation}
  85 \begin{frame}
  86 \frametitle{Graphics Formats}
  87 \begin{itemize}
  88         \item Document formats (eg: PDF and SVG) are formats for vector graphics
  89         \item Vector graphics scale better than raster graphics
  90 \end{itemize}
  91
  92 \centering
  93 \includegraphics[width=0.5\textwidth]{../figures/fox-vector.pdf}
  94 \includegraphics[width=0.5\textwidth]{../figures/fox-raster.png}
  95
  96 \end{frame}
  97
  98
  99
 100
 101
 102 \begin{frame}
 103 \frametitle{Is there a zoom limit?}
 104 \centering
 105 \includegraphics{../figures/koch1.pdf}
 106 \end{frame}
 107
 108 \section{Floating Point}
 109
 110 \begin{frame}
 111 \frametitle{Is there a zoom limit?}
 112 \begin{itemize}
 113         \item SVG, PostScript, PDF specify IEEE-754 \emph{single} floating point number representations
 114         \item Range of values: $\approx 3 \times 10^{-38} \to 3 \times 10^{+38}$
 115         \item Rough Floating Point Definition\footnote{IEEE-754 is more complicated}:
 116
 117         \begin{align}
 118                 X &= m \times 2^{E}
 119         \end{align}
 120         \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
 121         \item Floating Point $\approx$ Scientific Notation for computers
 122
 123 \end{itemize}
 124 \end{frame}
 125
 126 \begin{frame}
 127 \frametitle{Visualisation of Floats}
 128 \begin{itemize}
 129         \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
 130         \item Operations are inexact (in general)
 131 \end{itemize}
 132 \centering
 133 \includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
 134 \end{frame}
 135
 136 \begin{frame}
 137 \frametitle{Visualisation of Floats II}
 138 \begin{itemize}
 139         \item Difference between successive floats
 140 \end{itemize}
 141 \centering
 142 \includegraphics[width=0.8\textwidth]{../figures/floats_diff.pdf}
 143 \end{frame}
 144
 145 \begin{frame}
 146         \frametitle{Precision is limited}
 147         \centering
 148         \includegraphics[width=0.8\textwidth]{../figures/fox-vector_highzoom1.png}
 149 \end{frame}
 150
 151 \begin{frame}
 152 \frametitle{Structure of Vector Graphics}
 153 \begin{itemize}
 154         \item B\'{e}zier Curve (Quadratic or Cubic Parametric Polynomial)
 155         \item Path of B\'{e}zier Curves $\to$ Shapes (with fill)
 156         \item Shapes include font glyphs, like this $\mathscr{Z}$
 157 \end{itemize}
 158 \centering
 159 \includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}
 160
 161 \end{frame}
 162
 163 \section{Vector Graphics Viewer}
 164 \begin{frame}
 165 \frametitle{Structure of Vector Graphics II}
 166 \begin{itemize}
 167         \item \small{Upload \emph{bounding rectangles} of individual objects to renderer (OpenGL)}
 168         \item Rectangles show individual B\'{e}ziers forming outline of the Fox
 169 \end{itemize}
 170 \centering
 171 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
 172 \end{frame}
 173
 174
 175 \begin{frame}
 176 \frametitle{Viewing Vector Graphics}
 177 \begin{itemize}
 178         \item Tranform coordinates in document $\to$ display
 179 \end{itemize}
 180 \centering
 181 \includegraphics[width=0.8\textwidth]{../figures/view_transformation.pdf}
 182 \end{frame}
 183
 184
 185 \section{Precision Issues}
 186
 187
 188
 189 \begin{frame}
 190 \frametitle{Floating point calculations \\ go wrong}
 191 \begin{itemize}
 192         \item Example: Insert objects at very small scale
 193 \end{itemize}
 194 \centering
 195         \includegraphics[width=0.8\textwidth]{../figures/view_transformation_fail.pdf}
 196
 197 \end{frame}
 198
 199 \begin{frame}
 200 \frametitle{Reducing error}
 201                 \begin{itemize}
 202                         \item Don't apply view transformation directly
 203                         \item Store object bounds relative to the display
 204                         \item When modifying the view, modify object bounds
 205                         \item Detail inserted into the view looks good, But...
 206                 \end{itemize}
 207 \centering
 208         \includegraphics[width=0.9\textwidth]{../figures/view_transformation_cumulative.pdf}
 209 \end{frame}
 210
 211
 212 \begin{frame}
 213 \frametitle{Cumulated Errors \\ with intermediate coord system}
 214         \begin{itemize}
 215                 \item Apply transformations to Paths not individual B\'{e}ziers
 216                 \item Paths render correctly, but drift appart
 217         \end{itemize}
 218 \centering
 219         \includegraphics[width=0.9\textwidth]{../figures/view_transformation_paths.pdf}
 220 \end{frame}
 221
 222
 223 \section{Arbitrary Precision Rationals}
 224
 225 \begin{frame}
 226         \frametitle{Arbitrary Precision Rationals}
 227         \begin{align}
 228                 Q &= \frac{N}{D}
 229         \end{align}
 230         \begin{itemize}
 231                 \item $N$ and $D$ are arbitrary precision integers
 232         \end{itemize}
 233         \begin{align}
 234                 N &= \sum_{i=0}^{S} d_i \beta^{i}
 235         \end{align}
 236         \begin{itemize}
 237                 \item $d_i$ are fixed size integers, $\beta = 2^{64}$
 238                 \item {\bf Size $S$ grows as needed}
 239                 \item Operations are always exact
 240                 \item Implemented by GNU Multiple Precision Library
 241         \end{itemize}
 242 \end{frame}
 243
 244 \begin{frame}
 245         \frametitle{Use Rationals to represent \\ Path Coordinates}
 246         \begin{itemize}
 247                 \item Can move view to arbitrary point
 248                 \item Insert detail (ie: Test SVG image) in Display coordinates
 249                 \item Move view to another arbitrary point
 250                 \item Move view back
 251                 \item Detail is unchanged
 252         \end{itemize}
 253 \end{frame}
 254
 255
 256
 257
 258 \section{Demonstration}
 259 \begin{frame}
 260 \frametitle{Demonstration}
 261 \begin{itemize}
 262         \item We can import standard SVGs wherever we want
 263         \item If we are willing to wait long enough
 264         \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!'.``}
 265 \end{itemize}
 266 \centering
 267 \includegraphics[width=\textwidth]{turtles.pdf}
 268 \end{frame}
 269
 270 \section{Conclusions}
 271 \begin{frame}
 272         \frametitle{What was done}
 273         \begin{itemize}
 274                 \item Implemented a basic SVG viewer
 275                 \item Demonstrated how precision affects rendering vector graphics
 276                 \item Using GMP rationals, demonstrated the ability to render SVGs scaled to an arbitrary position in a document
 277         \end{itemize}
 278 \end{frame}
 279
 280 \begin{frame}
 281         \frametitle{Future work}
 282         \begin{itemize}
 283                 \item Implement more of the SVG standard
 284                 \item Trial alternative number representations
 285                 \item Allow for saving and loading SVGs with arbitrary precision
 286         \end{itemize}
 287 \end{frame}
 288 %\section{References}
 289 \begin{frame}
 290         \frametitle{References \& More information}
 291         \begin{itemize}
 292                 \item Work on SVG viewer collaborative with David Gow
 293                 \begin{itemize}
 294                         \item See David Gow's presentation about Quadtrees
 295                 \end{itemize}
 296                 \item Muller et al, \emph{Handbook of Floating Point Arithmetic},
 297                 \item Hearn, Baker \emph{Computer Graphics}
 298                 \item Kahan et al, \emph{IEEE-754} (1985 and 2008 revision)
 299                 \item Dahlst{\'o}m et al, \emph{SVG WC3 Recommendation 2011}
 300                 \item Grunland et al, \emph{GNU Multiple Precision Manual 6.0.0a}
 301                 \item Kahan's website \url{http://http.cs.berkeley.edu/~wkahan}
 302         \end{itemize}
 303 \end{frame}
 304 %\section{Questions}
 305
 306
 307
 308 \begin{frame}
 309 \frametitle{Q: Why not just increase \\ floating point precision?}
 310 \begin{itemize}
 311         \item Any fixed precision format will still give inexact results
 312         \item Eg: Accuracy of rendering a grid
 313 \end{itemize}
 314 \end{frame}
 315
 316 \begin{frame}
 317 \frametitle{Q: Arbitrary precision floats?}
 318 \begin{align}
 319         X &= m \times 2^{E}
 320 \end{align}
 321 \begin{itemize}
 322         \item $m$ and $E$ are of arbitrary size
 323         \item Implemented by MPFR or GMP
 324         \item Difficulties:
 325         \begin{itemize}
 326                 \item Need to manually set precision (size) of $m$
 327                 \item Some operations require infinite precision:
 328                 \begin{align}
 329                         \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
 330                 \end{align}
 331                 \item How do you choose when to increase precision?
 332         \end{itemize}
 333 \end{itemize}
 334 \end{frame}
 335
 336 \begin{frame}
 337 \frametitle{Q: Why don't you have colour?}
 338 \begin{itemize}
 339         \item We do!\footnote{If you are willing to wait long enough}
 340         \item A complete implementation of SVG is ``future work''
 341 \end{itemize}
 342 \centering
 343 \includegraphics[width=0.5\textwidth]{../figures/shady-the-fox.png}
 344 \includegraphics[width=0.5\textwidth]{../figures/who-the-hell-needs-antialiasing-anyway.png}
 345
 346 \end{frame}
 347
 348
 349 \end{document}