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 \\ Colleagues: David Gow}
  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 \begin{frame}
  99 \begin{itemize}
 100         \item Vector graphics scale better than raster graphics
 101 \end{itemize}
 102         \centering
 103         \includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{../figures/fox-vector.pdf}
 104         \includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{../figures/fox-raster.png}
 105 \end{frame}
 106
 107
 108
 109
 110
 111 \begin{frame}
 112 \frametitle{Is there a zoom limit?}
 113 \centering
 114 \includegraphics{../figures/koch.pdf}
 115 \end{frame}
 116
 117 \section{Floating Point}
 118
 119 \begin{frame}
 120 \frametitle{Is there a zoom limit?}
 121 \begin{itemize}
 122         \item SVG, PostScript, PDF specify IEEE-754 \emph{single} floating point number representations
 123         \item Range of values: $\approx 3 \times 10^{-38} \to 3 \times 10^{+38}$
 124         \item Bigger than size of Universe?
 125 \end{itemize}
 126 \end{frame}
 127
 128 \begin{frame}
 129 \frametitle{Floating Point Definition}
 130 \begin{itemize}
 131         \item Rough Floating Point Definition\footnote{IEEE-754 is more complicated}:
 132
 133         \begin{align}
 134                 X &= m \times 2^{E}
 135         \end{align}
 136         \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
 137         \item Floating Point $\approx$ Scientific Notation for computers
 138 \end{itemize}
 139 \end{frame}
 140
 141 \begin{frame}
 142 \frametitle{Visualisation of Floats}
 143 \begin{itemize}
 144         \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
 145         \item Operations are inexact (in general)
 146 \end{itemize}
 147 \centering
 148 \includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
 149 \end{frame}
 150
 151 \begin{frame}
 152 \frametitle{Visualisation of Floats II}
 153 \begin{itemize}
 154         \item Difference between successive floats
 155         \item Further from origin $\implies$ less precision
 156 \end{itemize}
 157 \centering
 158 \includegraphics[width=0.8\textwidth]{../figures/floats_diff.pdf}
 159 \end{frame}
 160
 161 \begin{frame}
 162         \frametitle{Precision is limited}
 163         \begin{itemize}
 164                 \item Eg: Fox scaled to width of $\approx 10^{-6}$ viewed at zoom of $\approx 10^{8}$
 165                 \item (Outline should look like images in first slide)
 166         \end{itemize}
 167         \centering
 168         \includegraphics[width=0.8\textwidth]{../figures/fox-vector_highzoom1.png}
 169 \end{frame}
 170
 171
 172 \begin{frame}
 173 \frametitle{Structure of Vector Graphics}
 174 \begin{itemize}
 175         \item B\'{e}zier Curve (Quadratic or Cubic Parametric Polynomial)
 176         \item Path of B\'{e}zier Curves $\to$ Shapes (with fill)
 177         \item Shapes include font glyphs, like this $\mathscr{Z}$
 178 \end{itemize}
 179 \centering
 180 \includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}
 181
 182 \end{frame}
 183
 184 \section{Vector Graphics Viewer}
 185 \begin{frame}
 186 \frametitle{Structure of Vector Graphics II}
 187 \begin{itemize}
 188         \item \small{Upload \emph{bounding rectangles} of individual objects to renderer (OpenGL)}
 189         \item Rectangles show individual B\'{e}ziers forming outline of the Fox
 190 \end{itemize}
 191 \centering
 192 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
 193 \end{frame}
 194
 195 \begin{frame}
 196 \frametitle{Vector Graphics Viewer Features}
 197 \begin{itemize}
 198         \item GPU (OpenGL) or CPU (custom) rendering
 199         \item Import SVG into current View location
 200         \item Control through scripts (Python) or Qt4 GUI
 201 \end{itemize}
 202 \centering
 203 \includegraphics[width=0.4\textwidth]{../figures/controlpanel_screenshot.png}
 204
 205 \end{frame}
 206
 207
 208 \begin{frame}
 209 \frametitle{Viewing Vector Graphics}
 210 \begin{itemize}
 211         \item Tranform coordinates in document $\to$ display
 212 \end{itemize}
 213 \centering
 214 \includegraphics[width=0.8\textwidth]{../figures/view_transformation.pdf}
 215 \end{frame}
 216
 217
 218 \section{Precision Issues}
 219
 220
 221
 222 \begin{frame}
 223 \frametitle{Floating point calculations \\ go wrong}
 224 \begin{itemize}
 225         \item Example: Insert objects at very small scale
 226 \end{itemize}
 227 \centering
 228         \includegraphics[width=0.8\textwidth]{../figures/view_transformation_fail.pdf}
 229
 230 \end{frame}
 231
 232 \begin{frame}
 233 \frametitle{Reducing error}
 234                 \begin{itemize}
 235                         \item Don't apply view transformation directly
 236                         \item Store object bounds relative to the display
 237                         \item When modifying the view, modify object bounds
 238                         \item Detail inserted into the view looks good, But...
 239                 \end{itemize}
 240 \centering
 241         \includegraphics[width=0.9\textwidth]{../figures/view_transformation_cumulative.pdf}
 242 \end{frame}
 243
 244
 245 \begin{frame}
 246 \frametitle{Cumulated Errors \\ with intermediate coord system}
 247         \begin{itemize}
 248                 \item Apply transformations to Paths not individual B\'{e}ziers
 249                 \item Paths render correctly, but drift appart
 250         \end{itemize}
 251 \centering
 252         \includegraphics[width=0.9\textwidth]{../figures/view_transformation_paths.pdf}
 253 \end{frame}
 254
 255
 256 \section{Arbitrary Precision Rationals}
 257
 258 \begin{frame}
 259         \frametitle{Arbitrary Precision Rationals}
 260         \begin{align}
 261                 Q &= \frac{N}{D}
 262         \end{align}
 263         \begin{itemize}
 264                 \item $N$ and $D$ are arbitrary precision integers
 265         \end{itemize}
 266         \begin{align}
 267                 N &= \sum_{i=0}^{S} d_i \beta^{i}
 268         \end{align}
 269         \begin{itemize}
 270                 \item $d_i$ are fixed size integers, $\beta = 2^{64}$
 271                 \item {\bf Size $S$ grows as needed}
 272                 \item Operations are always exact
 273                 \item Implemented by GNU Multiple Precision Library
 274         \end{itemize}
 275 \end{frame}
 276
 277 \begin{frame}
 278         \frametitle{Use Rationals to represent \\ Path Coordinates}
 279         \begin{itemize}
 280                 \item Can move view to arbitrary point
 281                 \item Insert detail (ie: Test SVG image) in Display coordinates
 282                 \item Move view to another arbitrary point
 283                 \item Move view back
 284                 \item Detail is unchanged
 285         \end{itemize}
 286 \end{frame}
 287
 288
 289 \begin{frame}
 290         \frametitle{Quantitative Results}
 291         \begin{itemize}
 292                 \item Invariance of grid of lines after scaling
 293         \end{itemize}
 294         \centering
 295         \includegraphics[width=0.8\textwidth]{../figures/cumulative_error_grid.pdf}
 296 \end{frame}
 297
 298
 299
 300
 301 \section{Demonstration}
 302 \begin{frame}
 303 \frametitle{Demonstration}
 304 \begin{itemize}
 305         \item We can import standard SVGs wherever we want
 306         \item If we are willing to wait long enough
 307         \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!'.``}
 308 \end{itemize}
 309 \centering
 310 \includegraphics[width=\textwidth]{turtles.pdf}
 311 \end{frame}
 312
 313 \section{Conclusions}
 314 \begin{frame}
 315         \frametitle{What was done}
 316         \begin{itemize}
 317                 \item Implemented a basic SVG viewer
 318                 \item Demonstrated how precision affects rendering vector graphics
 319                 \item Using GMP rationals, demonstrated the ability to render SVGs scaled to an arbitrary position in a document
 320         \end{itemize}
 321 \end{frame}
 322
 323 \begin{frame}
 324         \frametitle{Future work}
 325         \begin{itemize}
 326                 \item Implement more of the SVG standard
 327                 \item Trial alternative number representations
 328                 \item Allow for saving and loading
 329                 \item Optimisations, eg: clip objects that are not visible
 330                 \item Compile for Windows (MinGW)
 331         \end{itemize}
 332 \end{frame}
 333
 334 \begin{frame}
 335         \frametitle{Acknowledgements}
 336         \begin{itemize}
 337                 \item Work on SVG viewer collaborative with David Gow
 338                 \begin{itemize}
 339                         \item See David Gow's presentation about Quadtrees
 340                 \end{itemize}
 341                 \item Supervisors: Tim French and Rowan Davies
 342         \end{itemize}
 343 \end{frame}
 344 %\section{References}
 345 \begin{frame}
 346         \frametitle{References \& More information}
 347         \begin{itemize}
 348                 \item Muller et al, \emph{Handbook of Floating Point Arithmetic},
 349                 \item Hearn, Baker \emph{Computer Graphics}
 350                 \item Kahan et al, \emph{IEEE-754} (1985 and 2008 revision)
 351                 \item Dahlst{\'o}m et al, \emph{SVG WC3 Recommendation 2011}
 352                 \item Grunland et al, \emph{GNU Multiple Precision Manual 6.0.0a}
 353                 \item Kahan's website \url{http://http.cs.berkeley.edu/~wkahan}
 354         \end{itemize}
 355 \end{frame}
 356 %\section{Questions}
 357
 358 \begin{frame}
 359 \frametitle{Q: Why not just increase float precision?}
 360         \begin{itemize}
 361                 \item GPU uses singles anyway
 362                 \item Can use CPU for bounds transforms
 363                 \item But eventually lose precision for any \emph{fixed} precision float
 364         \end{itemize}
 365         \centering
 366         \includegraphics[width=0.8\textwidth]{{../figures/loss_of_precision_grid_0.5}.pdf}
 367 \end{frame}
 368
 369 \begin{frame}
 370
 371 \frametitle{Q: Arbitrary precision floats?}
 372 \begin{align}
 373         X &= m \times 2^{E}
 374 \end{align}
 375 \begin{itemize}
 376         \item $m$ and $E$ are of arbitrary size
 377         \item Implemented by MPFR (based on GMP)
 378         \item Difficulties:
 379         \begin{itemize}
 380                 \item Need to manually set precision (size) of $m$
 381                 \item Some operations require infinite precision:
 382                 \begin{align}
 383                         \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
 384                 \end{align}
 385                 \item How do you choose when to increase precision?
 386                 \item GMP Rational implementation automatically increases size, but MPFR floats do not
 387         \end{itemize}
 388 \end{itemize}
 389 \end{frame}
 390
 391 \begin{frame}
 392 \frametitle{Q: Why don't you have colour?}
 393 \begin{itemize}
 394         \item We do!\footnote{If you are willing to wait long enough}
 395         \item A complete implementation of SVG is ``future work''
 396 \end{itemize}
 397 \centering
 398 \includegraphics[width=0.5\textwidth]{../figures/shady-the-fox.png}
 399 \includegraphics[width=0.5\textwidth]{../figures/who-the-hell-needs-antialiasing-anyway.png}
 400
 401 \end{frame}
 402
 403 \begin{frame}
 404         \frametitle{Quantitative?}
 405 %       \begin{figure}[H]
 406         \centering
 407         \includegraphics[width=0.4\textwidth]{../figures/grid_0_1e-6.png}
 408         \includegraphics[width=0.4\textwidth]{../figures/{grid_0.5_1e-6}.png} \\
 409         \includegraphics[width=0.4\textwidth]{../figures/grid_1_1e-6.png}
 410         \includegraphics[width=0.4\textwidth]{../figures/grid_2_1e-6.png}
 411         %\caption{Effect of applying \eqref{view-transformation} to a grid of lines seperated by 1 pixel \\
 412         %a) Near origin (denormals) b), c), d) Increasing the exponent of $(v_x,v_y)$ by 1}\label{grid-precision}
 413 %\end{figure}
 414
 415
 416 \end{frame}
 417
 418 \begin{frame}
 419         \frametitle{Bresenham and Wu}
 420         \centering
 421         \includegraphics[width=0.5\textwidth]{../figures/line1.pdf}
 422         \includegraphics[width=0.5\textwidth]{../figures/line2.pdf}
 423 \end{frame}
 424
 425 \begin{frame}
 426         \frametitle{Bonus: IEEE-754 on GPUs}
 427         \begin{itemize}
 428                 \item Inconsistent behaviour of calculations on different GPUs
 429                 \item {\small Eg: $x^2 + y^2 < 1$ (shading a circle) zoomed in on the edge.}
 430         \end{itemize}
 431         \centering
 432         \includegraphics[width=0.4\textwidth]{../figures/gpufloats.pdf}
 433 \end{frame}
 434
 435 \end{document}