% 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}}
}
-\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}
\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}
\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}
\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}
\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}
\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
\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)
\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$
\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}
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au