4 \documentclass[12pt,landscape,english]{beamer}
7 \usetheme[navmenu]{uwa_eng} % Three options supported: uwa_pagen (default), navmenu, sec_navmenu, and splitfooter
10 \usepackage[T1]{fontenc}
11 \usepackage[latin1]{inputenc}
15 \usepackage{multimedia}
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
27 %_________________________________
30 \title[short title]{Number Representations and Precision in Vector Graphics}
31 \subtitle{Implementation of an Arbitrary Precision SVG Viewer} % if you have one
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
37 \institute[UWA]% (optional) {Universities of Western Australia}
38 {Supervisors: Tim French, Rowan Davies}
40 \date[CSS 2009]{\today} % change the actual date
41 %\titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}}
43 %% Optional stuff------------------------------------------------------------------
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]
51 % \AtBeginSection[] % Simplified version of what's above. % Should only be used with uwa_pagen option
52 % {\begin{frame}<beamer>{Outline}
53 % \tableofcontents[currentsection]
56 %-------------------------------------------------------------------------------------------------
60 \usebackgroundtemplate{\includegraphics[width=\paperwidth,height=\paperheight]{uwa_eng_title.png}} % Required to get the UWA titlepage background different.
70 % You might wish to add the option [pausesections]
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
82 % Start of presentation slides
83 \section{Motivation \& Background}
85 \frametitle{Graphics Formats}
87 \item Document formats (eg: PDF and SVG) are formats for vector graphics
88 \item Vector graphics scale better than raster graphics
92 \includegraphics[width=0.5\textwidth]{../figures/fox-vector.pdf}
93 \includegraphics[width=0.5\textwidth]{../figures/fox-raster.png}
99 \frametitle{Why is there a zoom limit?}
101 \includegraphics{../figures/koch1.pdf}
105 \frametitle{Why is there a zoom limit?}
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}:
114 \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
115 \item Floating Point $\approx$ Scientific Notation for computers
121 \frametitle{Visualisation of Floats}
123 \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
124 \item Operations are inexact (in general)
127 \includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
132 \frametitle{Structure of Vector Graphics}
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}$
139 \includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}
144 \frametitle{Structure of Vector Graphics III}
146 \item Rectangles show individual B\'{e}ziers forming outline of the Fox
149 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
154 \frametitle{Floating point calculations \\ go wrong}
156 \item Scaled to $~1\times 10^{-6}$, the fox is very sick
159 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png}
165 \frametitle{Arbitrary Precision Rationals}
170 \item $N$ and $D$ are arbitrary precision integers
173 N &= \sum_{i=0}^{S} d_i \beta^{i}
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
184 \frametitle{Replace floats with rationals?}
186 \item Rationals are \emph{slow}
187 \item Screen coordinates always in range $0 \to 1$
188 \item Introduce intermediate coordinate system
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
199 \frametitle{Live Demo}
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!'.``}
206 \includegraphics[width=\textwidth]{turtles.pdf}
209 \section{Conclusions}
211 \frametitle{Conclusions}
213 \item What we have done?
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
219 \item Possible future work
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
229 \frametitle{References \& More information}
231 \item Work on SVG viewer collaborative with David Gow
233 \item See David Gow's presentation about Quadtrees
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}
246 \frametitle{Q: Why don't you have colour?}
248 \item We do!\footnote{If you are willing to wait long enough}
249 \item A complete implementation of SVG is ``future work''
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}
258 \frametitle{Q: Why not just use doubles?}
260 \item Any fixed precision format will still give inexact results
261 \item But the inexact results will appear slower
266 \frametitle{Q: Arbitrary precision floats?}
271 \item $m$ and $E$ are of arbitrary size
272 \item Implemented by MPFR or GMP
275 \item Need to manually set precision (size) of $m$
276 \item Some operations require infinite precision:
278 \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
280 \item How do you choose when to increase precision?
287 \frametitle{Floating Point calculations \\ go wrong}
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}$
296 \frametitle{Floating point calculations \\ go wrong}
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)$
302 X = \frac{x - v_x}{v_w} &,\quad\quad Y = \frac{y - v_y}{v_h}
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}$