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