X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=blobdiff_plain;f=presentation%2Fpresentation.tex;h=d98b820187f7c704d34e2c47debdacf82e641265;hp=9ad4c78e95112d8d264d5a067b9bc8346272aad4;hb=refs%2Fheads%2Fmaster;hpb=9fcf44a0c34f393689118e913a2d17d907036c85 diff --git a/presentation/presentation.tex b/presentation/presentation.tex index 9ad4c78..d98b820 100644 --- a/presentation/presentation.tex +++ b/presentation/presentation.tex @@ -35,10 +35,10 @@ % 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}} + %\titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}} %% Optional stuff------------------------------------------------------------------ @@ -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} @@ -121,28 +142,33 @@ \frametitle{Visualisation of Floats} \begin{itemize} \item \small{With total length of $m$ and $E$ limited to $7$ bits (1 sign bit)} - \item Showing positive numbers only + \item Operations are inexact (in general) \end{itemize} \centering \includegraphics[width=0.8\textwidth]{../figures/floats.pdf} - \end{frame} \begin{frame} -\frametitle{Floating point calculations \\ go wrong} +\frametitle{Visualisation of Floats II} \begin{itemize} - \item At scale of only $1\times 10^{-6}$, the fox is very sick + \item Difference between successive floats + \item Further from origin $\implies$ less precision \end{itemize} \centering - \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png} +\includegraphics[width=0.8\textwidth]{../figures/floats_diff.pdf} +\end{frame} + +\begin{frame} + \frametitle{Precision is limited} \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}$ + \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} -\section{Implementing a Basic SVG Viewer} + \begin{frame} \frametitle{Structure of Vector Graphics} \begin{itemize} @@ -155,18 +181,126 @@ \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} -\section{Live Demo} \begin{frame} -\frametitle{Live Demo} +\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 @@ -178,25 +312,81 @@ \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{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{itemize} \end{frame} -\section{References} +%\section{Questions} -\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?} @@ -211,29 +401,35 @@ \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} + \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{Q: Arbitrary precision floats?} -\begin{itemize} - \item We support them as well! - \item Rationals are more convenient: + \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 Need to manually set precision - \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 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} - \item Could be future work -\end{itemize} + \centering + \includegraphics[width=0.4\textwidth]{../figures/gpufloats.pdf} \end{frame} - \end{document}