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.
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
77 %\frametitle{Contents}
79 % You might wish to add the option [pausesections]
83 % Start of presentation slides
86 \frametitle{Graphics Formats}
88 \item Document formats (eg: PDF and SVG) are formats for vector graphics
89 \item Vector graphics scale better than raster graphics
93 \includegraphics[width=0.5\textwidth]{../figures/fox-vector.pdf}
94 \includegraphics[width=0.5\textwidth]{../figures/fox-raster.png}
103 \frametitle{Is there a zoom limit?}
105 \includegraphics{../figures/koch1.pdf}
108 \section{Floating Point}
111 \frametitle{Is there a zoom limit?}
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}:
120 \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
121 \item Floating Point $\approx$ Scientific Notation for computers
127 \frametitle{Visualisation of Floats}
129 \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
130 \item Operations are inexact (in general)
133 \includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
137 \frametitle{Visualisation of Floats II}
139 \item Difference between successive floats
142 \includegraphics[width=0.8\textwidth]{../figures/floats_diff.pdf}
146 \frametitle{Precision is limited}
148 \includegraphics[width=0.8\textwidth]{../figures/fox-vector_highzoom1.png}
152 \frametitle{Structure of Vector Graphics}
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}$
159 \includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}
163 \section{Vector Graphics Viewer}
165 \frametitle{Structure of Vector Graphics II}
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
171 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
176 \frametitle{Viewing Vector Graphics}
178 \item Tranform coordinates in document $\to$ display
181 \includegraphics[width=0.8\textwidth]{../figures/view_transformation.pdf}
185 \section{Precision Issues}
190 \frametitle{Floating point calculations \\ go wrong}
192 \item Example: Insert objects at very small scale
195 \includegraphics[width=0.8\textwidth]{../figures/view_transformation_fail.pdf}
200 \frametitle{Reducing error}
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...
208 \includegraphics[width=0.9\textwidth]{../figures/view_transformation_cumulative.pdf}
213 \frametitle{Cumulated Errors \\ with intermediate coord system}
215 \item Apply transformations to Paths not individual B\'{e}ziers
216 \item Paths render correctly, but drift appart
219 \includegraphics[width=0.9\textwidth]{../figures/view_transformation_paths.pdf}
223 \section{Arbitrary Precision Rationals}
226 \frametitle{Arbitrary Precision Rationals}
231 \item $N$ and $D$ are arbitrary precision integers
234 N &= \sum_{i=0}^{S} d_i \beta^{i}
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
245 \frametitle{Use Rationals to represent \\ Path Coordinates}
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
251 \item Detail is unchanged
258 \section{Demonstration}
260 \frametitle{Demonstration}
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!'.``}
267 \includegraphics[width=\textwidth]{turtles.pdf}
270 \section{Conclusions}
272 \frametitle{What was done}
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
281 \frametitle{Future work}
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
288 %\section{References}
290 \frametitle{References \& More information}
292 \item Work on SVG viewer collaborative with David Gow
294 \item See David Gow's presentation about Quadtrees
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}
309 \frametitle{Q: Why not just increase \\ floating point precision?}
311 \item Any fixed precision format will still give inexact results
312 \item Eg: Accuracy of rendering a grid
317 \frametitle{Q: Arbitrary precision floats?}
322 \item $m$ and $E$ are of arbitrary size
323 \item Implemented by MPFR or GMP
326 \item Need to manually set precision (size) of $m$
327 \item Some operations require infinite precision:
329 \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
331 \item How do you choose when to increase precision?
337 \frametitle{Q: Why don't you have colour?}
339 \item We do!\footnote{If you are willing to wait long enough}
340 \item A complete implementation of SVG is ``future work''
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}