\makeatletter
\newif\ifGm@compatii
\makeatother
\documentclass[12pt,landscape,english]{beamer}
\mode<presentation>

\usetheme[navmenu]{uwa_eng} % Three options supported: uwa_pagen (default), navmenu, sec_navmenu, and splitfooter
\usepackage{mathrsfs}
\usepackage{palatino}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{multimedia}
\makeatletter


% My personal preferences________________________________
\definecolor{myframe}{rgb}{0.2,0.2,0.2}  % charcoal frametitle
\setbeamercolor{frametitle}{fg=myframe}
\definecolor{mystruc}{rgb}{0,0.25,0.45}  % turquoise
\usecolortheme[named=mystruc]{structure} % Changing to blueish green instead of default midnight shade 
\setbeamertemplate{headline}{\vspace{0.25cm}} % I personally find that the defaul position of the frametitle is too high
\setbeamercolor{title}{fg=black} % I personally don't like the taking the structure color for the title

%_________________________________
% Titlepage info

\title[short title]{Number Representations and Precision in Vector Graphics}
\subtitle{Implementation of an Arbitrary Precision SVG Viewer} % if you have one
\author{Sam Moore}
% - Give the names in the same order as the appear in the paper.
% - Use the \inst{?} command only if the authors have different
%   affiliation.

\institute[UWA]% (optional) {Universities of Western Australia} 
{Supervisors: Tim French, Rowan Davies \\ Colleagues: David Gow}

\date[CSS 2009]{\today} % change the actual date
 %\titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}}

%% Optional stuff------------------------------------------------------------------

%% Delete this, if you do not want the table of contents to pop up at
%% the beginning of each Section or Subsection:
%\AtBeginSubsection[] % I guess you could replace this with AtBeginSection
  %{\begin{frame}<beamer>{Outline}
    %\tableofcontents[currentsection,currentsubsection]
  %\end{frame}}
 % \AtBeginSection[] % Simplified version of what's above. % Should only be used with uwa_pagen option
%  {\begin{frame}<beamer>{Outline}
%    \tableofcontents[currentsection]
%  \end{frame}}

%-------------------------------------------------------------------------------------------------
\begin{document}

   {
   \usebackgroundtemplate{\includegraphics[width=\paperwidth,height=\paperheight]{uwa_eng_title.png}} % Required to get the UWA titlepage background different. 
   \begin{frame}[plain]
 \titlepage
\end{frame}
}



\begin{frame}
	\frametitle{Summary}
	\begin{itemize}
		\item Vector graphics allow detail to be scaled but not by an arbitrary amount
		\item We've implemented a vector graphics viewer which does allow arbitrary scaling
	\end{itemize}
\end{frame}

%\begin{frame}[plain]
%\frametitle{Contents}
%  \tableofcontents
  % You might wish to add the option [pausesections]
%\end{frame}


% Start of presentation slides
\section{Motivation}
\begin{frame}
\frametitle{Graphics Formats}
\begin{itemize}
	\item Document formats (eg: PDF and SVG) are formats for vector graphics
	\item Vector graphics scale better than raster graphics
\end{itemize}

\centering
\includegraphics[width=0.5\textwidth]{../figures/fox-vector.pdf}
\includegraphics[width=0.5\textwidth]{../figures/fox-raster.png}

\end{frame}

\begin{frame}
\begin{itemize}
	\item Vector graphics scale better than raster graphics
\end{itemize}
	\centering
	\includegraphics[scale=0.7528125, viewport=210 85 280 150,clip, width=0.45\textwidth]{../figures/fox-vector.pdf}
	\includegraphics[scale=0.7528125, viewport=0 85 70 150,clip, width=0.45\textwidth]{../figures/fox-raster.png}
\end{frame}





\begin{frame} 
\frametitle{Is there a zoom limit?} 
\centering
\includegraphics{../figures/koch.pdf}
\end{frame}

\section{Floating Point}

\begin{frame} 
\frametitle{Is there a zoom limit?} 
\begin{itemize}
	\item SVG, PostScript, PDF specify IEEE-754 \emph{single} floating point number representations
	\item Range of values: $\approx 3 \times 10^{-38} \to 3 \times 10^{+38}$
	\item Bigger than size of Universe?
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Floating Point Definition}
\begin{itemize}
	\item Rough Floating Point Definition\footnote{IEEE-754 is more complicated}:
	
	\begin{align}
		X &= m \times 2^{E}
	\end{align}
	\item $m$ and $E$ are encoded in a \emph{fixed length} string of bits
	\item Floating Point $\approx$ Scientific Notation for computers
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Visualisation of Floats}
\begin{itemize}
	\item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)}
	\item Operations are inexact (in general)
\end{itemize}
\centering
\includegraphics[width=0.8\textwidth]{../figures/floats.pdf}
\end{frame}

\begin{frame}
\frametitle{Visualisation of Floats II}
\begin{itemize}
	\item Difference between successive floats
	\item Further from origin $\implies$ less precision
\end{itemize}
\centering
\includegraphics[width=0.8\textwidth]{../figures/floats_diff.pdf}
\end{frame}

\begin{frame}
	\frametitle{Precision is limited}
	\begin{itemize}
		\item Eg: Fox scaled to width of $\approx 10^{-6}$ viewed at zoom of $\approx 10^{8}$
		\item (Outline should look like images in first slide)
	\end{itemize}
	\centering
	\includegraphics[width=0.8\textwidth]{../figures/fox-vector_highzoom1.png}
\end{frame}


\begin{frame}
\frametitle{Structure of Vector Graphics}
\begin{itemize}
	\item B\'{e}zier Curve (Quadratic or Cubic Parametric Polynomial)
	\item Path of B\'{e}zier Curves $\to$ Shapes (with fill)
	\item Shapes include font glyphs, like this $\mathscr{Z}$
\end{itemize}
\centering
\includegraphics[width=0.5\textwidth]{bezier_to_font.pdf}

\end{frame}

\section{Vector Graphics Viewer}
\begin{frame}
\frametitle{Structure of Vector Graphics II}
\begin{itemize}
	\item \small{Upload \emph{bounding rectangles} of individual objects to renderer (OpenGL)}
	\item Rectangles show individual B\'{e}ziers forming outline of the Fox
\end{itemize}
\centering
\includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png}
\end{frame}

\begin{frame}
\frametitle{Vector Graphics Viewer Features}
\begin{itemize}
	\item GPU (OpenGL) or CPU (custom) rendering
	\item Import SVG into current View location
	\item Control through scripts (Python) or Qt4 GUI
\end{itemize}
\centering
\includegraphics[width=0.4\textwidth]{../figures/controlpanel_screenshot.png}

\end{frame}


\begin{frame}
\frametitle{Viewing Vector Graphics}
\begin{itemize}
	\item Tranform coordinates in document $\to$ display
\end{itemize}
\centering
\includegraphics[width=0.8\textwidth]{../figures/view_transformation.pdf}
\end{frame}


\section{Precision Issues}



\begin{frame}
\frametitle{Floating point calculations \\ go wrong}
\begin{itemize}
	\item Example: Insert objects at very small scale
\end{itemize}
\centering
	\includegraphics[width=0.8\textwidth]{../figures/view_transformation_fail.pdf}

\end{frame}

\begin{frame}
\frametitle{Reducing error}
		\begin{itemize}
			\item Don't apply view transformation directly
			\item Store object bounds relative to the display
			\item When modifying the view, modify object bounds
			\item Detail inserted into the view looks good, But...
		\end{itemize}
\centering
	\includegraphics[width=0.9\textwidth]{../figures/view_transformation_cumulative.pdf}
\end{frame}


\begin{frame}
\frametitle{Cumulated Errors \\ with intermediate coord system}
	\begin{itemize}
		\item Apply transformations to Paths not individual B\'{e}ziers
		\item Paths render correctly, but drift appart
	\end{itemize}
\centering
	\includegraphics[width=0.9\textwidth]{../figures/view_transformation_paths.pdf}
\end{frame}


\section{Arbitrary Precision Rationals}

\begin{frame}
	\frametitle{Arbitrary Precision Rationals}	
	\begin{align}
		Q &= \frac{N}{D} 
	\end{align}			
	\begin{itemize}
		\item $N$ and $D$ are arbitrary precision integers
	\end{itemize}
	\begin{align}
		N &= \sum_{i=0}^{S} d_i \beta^{i}
	\end{align}	
	\begin{itemize}
		\item $d_i$ are fixed size integers, $\beta = 2^{64}$
		\item {\bf Size $S$ grows as needed}
		\item Operations are always exact
		\item Implemented by GNU Multiple Precision Library
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Use Rationals to represent \\ Path Coordinates}
	\begin{itemize}
		\item Can move view to arbitrary point
		\item Insert detail (ie: Test SVG image) in Display coordinates
		\item Move view to another arbitrary point
		\item Move view back
		\item Detail is unchanged
	\end{itemize}
\end{frame}


\begin{frame}
	\frametitle{Quantitative Results}
	\begin{itemize}
		\item Invariance of grid of lines after scaling
	\end{itemize}
	\centering
	\includegraphics[width=0.8\textwidth]{../figures/cumulative_error_grid.pdf}
\end{frame}




\section{Demonstration}
\begin{frame}
\frametitle{Demonstration}
\begin{itemize}
	\item We can import standard SVGs wherever we want
	\item If we are willing to wait long enough
	\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!'.``}
\end{itemize}
\centering
\includegraphics[width=\textwidth]{turtles.pdf}
\end{frame}

\section{Conclusions}
\begin{frame}
	\frametitle{What was done}
	\begin{itemize}
		\item Implemented a basic SVG viewer
		\item Demonstrated how precision affects rendering vector graphics
		\item Using GMP rationals, demonstrated the ability to render SVGs scaled to an arbitrary position in a document
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Future work}
	\begin{itemize}
		\item Implement more of the SVG standard
		\item Trial alternative number representations
		\item Allow for saving and loading
		\item Optimisations, eg: clip objects that are not visible
		\item Compile for Windows (MinGW)
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{Acknowledgements}
	\begin{itemize}
		\item Work on SVG viewer collaborative with David Gow
		\begin{itemize}
			\item See David Gow's presentation about Quadtrees
		\end{itemize}
		\item Supervisors: Tim French and Rowan Davies	
	\end{itemize}
\end{frame}
%\section{References}
\begin{frame}
	\frametitle{References \& More information}
	\begin{itemize}
		\item Muller et al, \emph{Handbook of Floating Point Arithmetic}, 
		\item Hearn, Baker \emph{Computer Graphics}
		\item Kahan et al, \emph{IEEE-754} (1985 and 2008 revision)
		\item Dahlst{\'o}m et al, \emph{SVG WC3 Recommendation 2011}
		\item Grunland et al, \emph{GNU Multiple Precision Manual 6.0.0a}
		\item Kahan's website \url{http://http.cs.berkeley.edu/~wkahan}
	\end{itemize}
\end{frame}
%\section{Questions}

\begin{frame}
\frametitle{Q: Why not just increase float precision?}
	\begin{itemize}
		\item GPU uses singles anyway
		\item Can use CPU for bounds transforms
		\item But eventually lose precision for any \emph{fixed} precision float
	\end{itemize}
	\centering
	\includegraphics[width=0.8\textwidth]{{../figures/loss_of_precision_grid_0.5}.pdf}
\end{frame}

\begin{frame}

\frametitle{Q: Arbitrary precision floats?}
\begin{align}
	X &= m \times 2^{E}
\end{align}
\begin{itemize}
	\item $m$ and $E$ are of arbitrary size
	\item Implemented by MPFR (based on GMP)
	\item Difficulties:
	\begin{itemize}
		\item Need to manually set precision (size) of $m$
		\item Some operations require infinite precision:
		\begin{align}
			\frac{1}{3} &= 0.3333333333333333333333 \text{ ... } \times 10^0
		\end{align}
		\item How do you choose when to increase precision?
		\item GMP Rational implementation automatically increases size, but MPFR floats do not
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Q: Why don't you have colour?}
\begin{itemize}
	\item We do!\footnote{If you are willing to wait long enough}
	\item A complete implementation of SVG is ``future work''
\end{itemize}
\centering
\includegraphics[width=0.5\textwidth]{../figures/shady-the-fox.png}
\includegraphics[width=0.5\textwidth]{../figures/who-the-hell-needs-antialiasing-anyway.png}

\end{frame}

\begin{frame}
	\frametitle{Quantitative?}
%	\begin{figure}[H]
	\centering
	\includegraphics[width=0.4\textwidth]{../figures/grid_0_1e-6.png}
	\includegraphics[width=0.4\textwidth]{../figures/{grid_0.5_1e-6}.png} \\
	\includegraphics[width=0.4\textwidth]{../figures/grid_1_1e-6.png}
	\includegraphics[width=0.4\textwidth]{../figures/grid_2_1e-6.png}
	%\caption{Effect of applying \eqref{view-transformation} to a grid of lines seperated by 1 pixel \\
	%a) Near origin (denormals) b), c), d) Increasing the exponent of $(v_x,v_y)$ by 1}\label{grid-precision}
%\end{figure}

	
\end{frame}

\begin{frame}
	\frametitle{Bresenham and Wu}
	\centering
	\includegraphics[width=0.5\textwidth]{../figures/line1.pdf}
	\includegraphics[width=0.5\textwidth]{../figures/line2.pdf}
\end{frame}

\begin{frame}
	\frametitle{Bonus: IEEE-754 on GPUs}
	\begin{itemize}
		\item Inconsistent behaviour of calculations on different GPUs
		\item {\small Eg: $x^2 + y^2 < 1$ (shading a circle) zoomed in on the edge.}
	\end{itemize}
	\centering
	\includegraphics[width=0.4\textwidth]{../figures/gpufloats.pdf}
\end{frame}

\end{document}
