X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=blobdiff_plain;f=presentation%2Fpresentation.tex;h=d98b820187f7c704d34e2c47debdacf82e641265;hp=7d5494b8602e242c60b0813fdee46066bc929c4e;hb=HEAD;hpb=67c33e185edd820e2ea6fef334455645bacd432b diff --git a/presentation/presentation.tex b/presentation/presentation.tex index 7d5494b..d98b820 100644 --- a/presentation/presentation.tex +++ b/presentation/presentation.tex @@ -35,7 +35,7 @@ % affiliation. \institute[UWA]% (optional) {Universities of Western Australia} -{Supervisors: Tim French, Rowan Davies} +{Supervisors: Tim French, Rowan Davies \\ Colleagues: David Gow} \date[CSS 2009]{\today} % change the actual date %\titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}} @@ -64,23 +64,24 @@ } -\begin{frame}[plain] -\frametitle{Contents} - \tableofcontents - % You might wish to add the option [pausesections] -\end{frame} \begin{frame} \frametitle{Summary} \begin{itemize} - \item Vector graphics allow scaling but not arbitrary scaling - \item We implemented a vector graphics viewer that does allow arbitrary scaling - \item ... but it will take an arbitrary amount of time + \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 \& Background} +\section{Motivation} \begin{frame} \frametitle{Graphics Formats} \begin{itemize} @@ -94,18 +95,39 @@ \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{Why is there a zoom limit?} +\frametitle{Is there a zoom limit?} \centering -\includegraphics{../figures/koch1.pdf} +\includegraphics{../figures/koch.pdf} \end{frame} +\section{Floating Point} + \begin{frame} -\frametitle{Why is there a zoom limit?} +\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} @@ -113,7 +135,6 @@ \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} @@ -127,6 +148,26 @@ \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} @@ -140,27 +181,80 @@ \end{frame} +\section{Vector Graphics Viewer} \begin{frame} -\frametitle{Structure of Vector Graphics III} +\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 Scaled to $~1\times 10^{-6}$, the fox is very sick + \item Example: Insert objects at very small scale \end{itemize} \centering - \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png} + \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} @@ -174,29 +268,39 @@ \end{align} \begin{itemize} \item $d_i$ are fixed size integers, $\beta = 2^{64}$ - \item Size $S$ grows as needed + \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{Replace floats with rationals?} + \frametitle{Use Rationals to represent \\ Path Coordinates} \begin{itemize} - \item Rationals are \emph{slow} - \item Screen coordinates always in range $0 \to 1$ - \item Introduce intermediate coordinate system - \begin{itemize} - \item Many B\'{e}ziers contained in a Path - \item Use Rationals for bounds of the Path - \item Use floats to transform B\'{e}zier coordinates - \end{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{Live Demo} + + + +\section{Demonstration} \begin{frame} -\frametitle{Live Demo} +\frametitle{Demonstration} \begin{itemize} \item We can import standard SVGs wherever we want \item If we are willing to wait long enough @@ -208,30 +312,39 @@ \section{Conclusions} \begin{frame} - \frametitle{Conclusions} -\begin{itemize} - \item What we have done? + \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} - \item Possible future work +\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 SVGs with arbitrary precision + \item Allow for saving and loading + \item Optimisations, eg: clip objects that are not visible + \item Compile for Windows (MinGW) \end{itemize} -\end{itemize} \end{frame} -\section{References} + \begin{frame} - \frametitle{References \& More information} + \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) @@ -240,36 +353,28 @@ \item Kahan's website \url{http://http.cs.berkeley.edu/~wkahan} \end{itemize} \end{frame} -\section{Questions} +%\section{Questions} \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} - +\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: Why not just use doubles?} -\begin{itemize} - \item Any fixed precision format will still give inexact results - \item But the inexact results will appear slower -\end{itemize} -\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 or GMP + \item Implemented by MPFR (based on GMP) \item Difficulties: \begin{itemize} \item Need to manually set precision (size) of $m$ @@ -278,34 +383,53 @@ \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{Floating Point calculations \\ go wrong} - \begin{itemize} - \item Plank Length: $1.61 \times 10^{-35}$ metres $ > 3\times10^{-38}$ - \item Size of Universe: $4.3 \times 10^{26}$ metres $ << 3 \times10^{38}$ - \item Why isn't this good enough for $1\times 10^{-6}$ - \end{itemize} + \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{Floating point calculations \\ go wrong} - \begin{itemize} - \item Transforming from document $(x,y)$ $\to$ screen $(X,Y)$ - \item View is at $(v_x,v_y)$ in document, has dimensions $(v_w,v_h)$ - \end{itemize} - \begin{align} - X = \frac{x - v_x}{v_w} &,\quad\quad Y = \frac{y - v_y}{v_h} - \end{align} + \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 Division by $v_w \approx 10^{-6}$ increases the error due to $x - v_x$ - \item Using \emph{double} precision, render correctly down to $v_w \approx 10^{-37}$ + \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}