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 \\ Colleagues: David Gow}
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}
100 \item Vector graphics scale better than raster graphics
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}
112 \frametitle{Is there a zoom limit?}
114 \includegraphics{../figures/koch.pdf}
117 \section{Floating Point}
120 \frametitle{Is there a zoom limit?}
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?
129 \frametitle{Floating Point Definition}
131 \item Rough Floating Point Definition\footnote{IEEE-754 is more complicated}:
136 \item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
137 \item Floating Point $\approx$ Scientific Notation for computers
142 \frametitle{Visualisation of Floats}
144 \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
145 \item Operations are inexact (in general)
148 \includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
152 \frametitle{Visualisation of Floats II}
154 \item Difference between successive floats
155 \item Further from origin $\implies$ less precision
158 \includegraphics[width=0.8\textwidth]{../figures/floats_diff.pdf}
162 \frametitle{Precision is limited}
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)
168 \includegraphics[width=0.8\textwidth]{../figures/fox-vector_highzoom1.png}
173 \frametitle{Structure of Vector Graphics}
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}$
180 \includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}
184 \section{Vector Graphics Viewer}
186 \frametitle{Structure of Vector Graphics II}
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
192 \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
196 \frametitle{Vector Graphics Viewer Features}
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
203 \includegraphics[width=0.4\textwidth]{../figures/controlpanel_screenshot.png}
209 \frametitle{Viewing Vector Graphics}
211 \item Tranform coordinates in document $\to$ display
214 \includegraphics[width=0.8\textwidth]{../figures/view_transformation.pdf}
218 \section{Precision Issues}
223 \frametitle{Floating point calculations \\ go wrong}
225 \item Example: Insert objects at very small scale
228 \includegraphics[width=0.8\textwidth]{../figures/view_transformation_fail.pdf}
233 \frametitle{Reducing error}
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...
241 \includegraphics[width=0.9\textwidth]{../figures/view_transformation_cumulative.pdf}
246 \frametitle{Cumulated Errors \\ with intermediate coord system}
248 \item Apply transformations to Paths not individual B\'{e}ziers
249 \item Paths render correctly, but drift appart
252 \includegraphics[width=0.9\textwidth]{../figures/view_transformation_paths.pdf}
256 \section{Arbitrary Precision Rationals}
259 \frametitle{Arbitrary Precision Rationals}
264 \item $N$ and $D$ are arbitrary precision integers
267 N &= \sum_{i=0}^{S} d_i \beta^{i}
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
278 \frametitle{Use Rationals to represent \\ Path Coordinates}
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
284 \item Detail is unchanged
290 \frametitle{Quantitative Results}
292 \item Invariance of grid of lines after scaling
295 \includegraphics[width=0.8\textwidth]{../figures/cumulative_error_grid.pdf}
301 \section{Demonstration}
303 \frametitle{Demonstration}
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!'.``}
310 \includegraphics[width=\textwidth]{turtles.pdf}
313 \section{Conclusions}
315 \frametitle{What was done}
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
324 \frametitle{Future work}
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)
335 \frametitle{Acknowledgements}
337 \item Work on SVG viewer collaborative with David Gow
339 \item See David Gow's presentation about Quadtrees
341 \item Supervisors: Tim French and Rowan Davies
344 %\section{References}
346 \frametitle{References \& More information}
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}
359 \frametitle{Q: Why not just increase float precision?}
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
366 \includegraphics[width=0.8\textwidth]{{../figures/loss_of_precision_grid_0.5}.pdf}
371 \frametitle{Q: Arbitrary precision floats?}
376 \item $m$ and $E$ are of arbitrary size
377 \item Implemented by MPFR (based on GMP)
380 \item Need to manually set precision (size) of $m$
381 \item Some operations require infinite precision:
383 \frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
385 \item How do you choose when to increase precision?
386 \item GMP Rational implementation automatically increases size, but MPFR floats do not
392 \frametitle{Q: Why don't you have colour?}
394 \item We do!\footnote{If you are willing to wait long enough}
395 \item A complete implementation of SVG is ``future work''
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}
404 \frametitle{Quantitative?}
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}
419 \frametitle{Bresenham and Wu}
421 \includegraphics[width=0.5\textwidth]{../figures/line1.pdf}
422 \includegraphics[width=0.5\textwidth]{../figures/line2.pdf}
426 \frametitle{Bonus: IEEE-754 on GPUs}
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.}
432 \includegraphics[width=0.4\textwidth]{../figures/gpufloats.pdf}