From: Sam Moore Date: Thu, 9 Oct 2014 16:44:16 +0000 (+0800) Subject: It resembles a first approximation to a rough draft... X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=commitdiff_plain;h=67c33e185edd820e2ea6fef334455645bacd432b It resembles a first approximation to a rough draft... --- diff --git a/chapters/Background/CoordinateSystems.tex b/chapters/Background/CoordinateSystems.tex index 147a684..3a61cb3 100644 --- a/chapters/Background/CoordinateSystems.tex +++ b/chapters/Background/CoordinateSystems.tex @@ -39,6 +39,15 @@ The document can be scaled by a factor of $s$ about a point $(x_0,y_0)$ specifie The effect of this transformation is that, measured relative to the view rectangle, the distance of primitives with coordinates $(x, y)$ to the point $(x_0, y_0)$ will decrease by a factor of $s$. For $s < 1$ the operation is ``zooming out'' and for $s > 1$, ``zooming in''. + +{\bf TODO} +\begin{itemize} + \item Intermediate coordinate systems... + \item Write Matrix operations properly + \item Link with the results where applying \eqref{view-transformation} directly leads to disaster + \item This is because for $v_w << 1$, an error of $1 ulp$ in $x - v_x$ is comparable with $v_w$, ie: Can increase to the order of the size of the display (or more) +\end{itemize} + %TODO List % Mention that these transformations affect precision more than eg: drawing a line % Discuss floating point errors that could occur? diff --git a/chapters/Background/Rationals.tex b/chapters/Background/Rationals.tex index 8b13789..da4f77a 100644 --- a/chapters/Background/Rationals.tex +++ b/chapters/Background/Rationals.tex @@ -1 +1,15 @@ - + \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 Size $S$ grows as needed + \item Operations are always exact + \item Implemented by GNU Multiple Precision Library + \end{itemize} diff --git a/chapters/Background/Rendering.tex b/chapters/Background/Rendering.tex index 45a0167..9a9bbdb 100644 --- a/chapters/Background/Rendering.tex +++ b/chapters/Background/Rendering.tex @@ -6,6 +6,8 @@ \input{chapters/Background/Rendering/BezierSplines} \subsection{Filled Paths} \subsection{Compositing} +{\bf FIXME} Really won't have time to mention these? +They are important, but we didn't end up implementing them anyway. \subsection{Fonts} \input{chapters/Background/Rendering/Fonts} diff --git a/chapters/Background/Standards.tex b/chapters/Background/Standards.tex index 62cf5db..69dcb31 100644 --- a/chapters/Background/Standards.tex +++ b/chapters/Background/Standards.tex @@ -1,9 +1,12 @@ %\subsection{Overview} -% All this stuff can probably be appendicised -%\input{chapters/Background/Standards/Overview} -%\subsection{Interpreted Models: PostScript and PDF} -%\input{chapters/Background/Standards/Interpreted} -%\subsection{The Document Object Model: SVG} -%\input{chapters/Background/Standards/DOM} -%\subsection{Precision Specified By Standards} +{\bf FIXME: Most of this stuff should probably be appendicised} + +\input{chapters/Background/Standards/Overview} +\subsection{Interpreted Models: PostScript and PDF} +\input{chapters/Background/Standards/Interpreted} +\subsection{The Document Object Model: SVG} +\input{chapters/Background/Standards/DOM} +\subsection{Precision Specified By Standards} + +{\bf TODO: Keep this subsection, appendicise rest of this section} \input{chapters/Background/Standards/Precision} diff --git a/chapters/Conclusion.tex b/chapters/Conclusion.tex index 6d4525b..57724b9 100644 --- a/chapters/Conclusion.tex +++ b/chapters/Conclusion.tex @@ -1,5 +1,20 @@ \chapter{Conclusion}\label{Conclusion} -\section{Summary of Work and Results} -\section{Considerations for Future Work} +\begin{itemize} + \item What we have done? + \begin{itemize} + \item Implemented a basic SVG viewer + \item Demonstrated how precision affects rendering vector graphics + \item Showed how the choice of transformations to apply affects rendering + \item Using GMP rationals, demonstrated the ability to render SVGs scaled to an arbitrary position in a document + \end{itemize} + \item Possible future work + \begin{itemize} + \item Implement more of the SVG standard (eg: Shading) + \item Trial alternative number representations, eg: MPFR with algorithm to set precision + \item Allow for saving and loading SVGs with arbitrary precision + \item Deal with zooming very far in to intersection of lines (requires subdividing paths) + \item Compare with David's Quadtree + \end{itemize} +\end{itemize} diff --git a/chapters/Process.tex b/chapters/Process.tex index a57d7e0..73e631d 100644 --- a/chapters/Process.tex +++ b/chapters/Process.tex @@ -1,13 +1,124 @@ \chapter{Methods and Design} -\section{Softare Overview} -\input{chapters/Process/SoftwareOverview} -\section{Design Process} -\input{chapters/Process/DesignProcess} -\section{Coordinate Systems and Bounds Transformations} -\input{chapters/Process/Transformations} -\section{Measurements} -\input{chapters/Process/Measurements} +{\bf TODO} Write most of this section. I suspect I will have to be very selective about what to fit in considering the word limit. +\section{Collaborative Process} +\begin{itemize} + \item Collaborated with David Gow on the design and implementation of the SVG viewer + \item Individual work: Applying GMP Rationals (Sam), Quadtree (David) + \item Used git to collaborate \url{https://git.ucc.asn.au} + \item Used preprocessor defines to not interfere with each other's code too much + \item David used a \verb/goto/ letting the team down +\end{itemize} +\section{Structure of Software} +\begin{itemize} + \item CPU and GPU renderer supported + \item Rendering of Cubic B\'{e}ziers (no antialiasing) + \item Partial implementation of shading Paths on CPU (abandoned) + \item Ability to move the view around the document with the mouse + \item Ability to insert an SVG into the view location + \item \verb/typedef/ for number representations + \item Ability to control program through scripts or stdio + \item Hacky python scripts to produce plots by abusing this +\end{itemize} + +\section{Approaches to Arbitrary Precision} +\begin{itemize} + \item Replace \emph{all} operations with arbitrary precision (ie: Rationals) - Horrendously slow + \item Change approach to applying coordinate transform \eqref{view-transformation} + \item Apply view transformations directly to objects as the view is transformed, rather than just before rendering + \begin{itemize} + \item Allows much better precision and range with just regular IEEE-754 floats + \item But there is an accumulated rounding error, particularly when zooming out and back in, which is bad + \end{itemize} + \item As above, but introduce intermediate coordinate system; use the Path elements + \begin{itemize} + \item Rendering of individual paths is consistent but overall they drift apart + \end{itemize} + \item As above, but specify Path coordinates with arbitrary precision rationals + \begin{itemize} + \item Works well, rationals slow down though + \end{itemize} +\end{itemize} + +\section{Number Representations Trialed} +\begin{itemize} + \item IEEE-754 single, double, extended + \item Custom implementation of Rationals with \verb/int64_t/ + \begin{itemize} + \item Very limited since the integers grow exponentially and overflow + \end{itemize} + \item Custom implementation of Rationals with custom Arbitrary precision integers + \begin{itemize} + \item Actually works + \item Implementation of division is too slow to be feasible + \end{itemize} + \item Custom rationals but with GMP arbitrary precision integers + \begin{itemize} + \item Our implementation of GCD is not feasible + \end{itemize} + \item Paranoid Numbers; store a operation tree of IEEE-754 floats and simplify the tree wherever \verb/FE_INEXACT/ is \emph{not} raised + \begin{itemize} + \item This was a really, really, really, bad idea + \end{itemize} + \item Just use GMP rationals already + \begin{itemize} + \item Works + \end{itemize} + + \item MPFR floats + \begin{itemize} + \item They work, but they don't truly give arbitrary precision + \item Because you have to specify the maximum precision + \item However, this can be changed at runtime + \item Future work: Trial MPFR floats changing the precision as needed + \end{itemize} + +\end{itemize} + +\section{Libraries Used} +\begin{itemize} + \item SDL2 - Simple Direct media Library + \begin{itemize} + \item Used for window management and to obtain an OpenGL context + \item Also provides BMP handling which is useful + \end{itemize} + \item Qt4 (optional) + \begin{itemize} + \item Open source toolkit for Dialog based applications + \item We can optionally compile with a Qt4 based control panel + \item This is useful for interacting with the document + \item Has way more features than we actually use it for + \end{itemize} + \item OpenGL - Standard API for rendering on GPUs + \begin{itemize} + \item Using GLSL shaders + \item B\'{e}ziers are rendered using a Geometry shader which produces line segments + \end{itemize} + \item PugiXML - Open source XML parsing library + \begin{itemize} + \item Used to parse SVGs + \end{itemize} + \item GNU Multiple Precision (GMP) + \begin{itemize} + \item Implements arbitrary precision integers, floats, and rationals + \item We can use the arbitrary precision integers with a custom rational type + \item Or just use the GMP rational type (much better) + \item We don't use the floats, because they are hardware dependent + \end{itemize} + \item MPFR + \begin{itemize} + \item MPFR is built on GMP but ensures IEEE-754 consistent rounding behaviour + \item (Not hardware dependent) + \item We can compile with MPFR floats but the precision is currently fixed at compile time + \end{itemize} +\end{itemize} + + +\section{Design of Performance Tests} +\begin{itemize} + \item This is mostly covered in the Results chapter + \item Control the program through stdin using a python script +\end{itemize} diff --git a/chapters/Results.tex b/chapters/Results.tex index 923eccf..1d4d939 100644 --- a/chapters/Results.tex +++ b/chapters/Results.tex @@ -1,13 +1,17 @@ \chapter{Results and Discussion} +{\bf Note: Need to be more consistent, I often refer to B\'{e}ziers and Objects interchangably (since the original design was based around an Object and B\'{e}zier was just one possible Object, but we have moved on to pretty much only caring about B\'{e}ziers now)} \section{Qualitative Rendering Accuracy} Our ultimate goal is to be able to insert detail at an arbitrary point in the document. Therefore, we are interested in how the same test SVG would appear when scaled to the view coordinates, as the view coordinates are varied. -applying Transformation \eqref{view-transformation}. We will use single precision floats for coordinates unless otherwise stated. -Figure \ref{qualitative-rendering-fox} shows the rendering of a vector image\footnote{Unfortunately, since a rendered vector image is a raster image and this figure must be scaled to fit the PDF, the figure as seen here is not a pixel perfect representation of the actual rendering. Most notably, antialiasing effects will be apparent}. Transformation \eqref{view-transformation} is applied to object coordinates with default IEEE-754 rounding behaviour (to nearest). +\subsection{Applying the view transformation directly} + +Figure \ref{qualitative-rendering-fox} shows the rendering of a vector image\footnote{Unfortunately, since a rendered vector image is a raster image and this figure must be scaled to fit the PDF, the figure as seen here is not a pixel perfect representation of the actual rendering. Most notably, antialiasing effects will be apparent}. Transformation \eqref{view-transformation} is applied to object coordinates with default IEEE-754 rounding behaviour (to nearest). The loss of precision in the second figure is obvious. This is because division by $10^{-6}$ increases the rounding error in $x - v_x$, by $10^{6}$, so the total error is of the order $10^6$ ulp which is of the order $0.25$ + +{\bf TODO: Calculate that properly, shouldn't be hard} @@ -18,9 +22,11 @@ Figure \ref{qualitative-rendering-fox} shows the rendering of a vector image\foo \caption{The vector image from Figure \ref{vector-vs-raster} under two different scales}\label{qualitative-rendering-fox} \end{figure} -Rather than applying \eqref{view-transformation} to object coordinates specified relative to the document, we can store the bounds of objects relative to the view and modify these bounds according to transformations \eqref{} and \eqref{} as the view is changed. This approach significantly improves the range over which an image can be rendered correctly, and it is convenient for interactively created documents as no transformation must be applied to add new detail. +\subsection{Applying cumulative transformations to all B\'{e}ziers} -However, repeated transformations on the view will cause an accumulated error on the coordinates of object bounds. This is most noticable when zooming out and then back into the document; the object bounds coordinates will gradually underflow and eventually round to zero. An example of this effect is shown in Figure \ref{qualitative-rendering-fox-cumulative} b) +Rather than applying \eqref{view-transformation} to object coordinates specified relative to the document, we can store the bounds of objects relative to the view and modify these bounds according to transformations \eqref{} and \eqref{} as the view is changed. This is convenient for an interactive document, as detail is typically added by inserting objects into the document within the view rectangle. As a result this approach makes the rendering of detail added to the document independent of the view coordinates --- until the view is moved. + +Repeated transformations on the view will cause an accumulated error on the coordinates of object bounds. This is most noticable when zooming \emph{out} and then back into the document; the object coordinates will gradually underflow and eventually round to zero. An example of this effect is shown in Figure \ref{qualitative-rendering-fox-cumulative} b) %label start %setbounds 0.5 0.5 1e-6 1e-6 %loadsvg svg-tests/fox-vector.svg @@ -36,9 +42,11 @@ However, repeated transformations on the view will cause an accumulated error on \caption{The effect of applying cumulative transformations to all B\'{e}ziers}\label{qualitative-rendering-fox-cumulative} \end{figure} -In Figure \ref{qualitative-rendering-fox}, transformations are applied to the bounds of each B\'{e}zier. Figure \ref{qualitative-rendering-fox-cumulative-relative} a) shows the effect of introducing an intermediate coordinate system expressing B\'{e}zier coordinates relative to the path which contains them. In this case, the rendering of a single path is accurate, but the overall positions of the paths drift. +\subsection{Applying cumulative transformations to Paths} + +In Figure \ref{qualitative-rendering-fox}, transformations are applied to the bounds of each B\'{e}zier. Figure \ref{qualitative-rendering-fox-cumulative-relative} a) shows the effect of introducing an intermediate coordinate system expressing B\'{e}zier coordinates relative to the path which contains them. In this case, the rendering of a single path is accurate, but the overall positions of the paths drift as the view is moved. -We can correct this drift whilst maintaining performance by using an arbitrary precision number representation to express the coordinates of the paths - but maintaining the floating point coordinates for B\'{e}zier curves relative to their path. As we will discuss in Section \ref{}, this offers an acceptable trade off between rendering accuracy and performance. +We can correct this drift whilst maintaining performance by using an arbitrary or high precision number representation to express the coordinates of the paths - but maintaining the floating point coordinates for B\'{e}zier curves relative to their path. As we will discuss in Section \ref{}, this offers an acceptable trade off between rendering accuracy and performance. \begin{figure}[H] \centering @@ -51,16 +59,68 @@ We can correct this drift whilst maintaining performance by using an arbitrary p A useful test SVG is a simple grid of horizontal and vertical lines seperated by 1 pixel. When this SVG is correctly scaled to a view, all that should be visible is a coloured rectangle filling the screen. Increasing the magnification will reveal the grid of lines indicating how the original size of a pixel is scaled. -Figures \ref{} show the effect of scaling the grid to different view coordinates using single precision. This illustrates the trade off between precision and range; as the top left corner of the view moves further away from the origin, the width for which the grid appears unaltered decreases, or if the width is kept fixed, then there are fewer locations on the grid that can be correctly transformed from document to view space. +Figure \ref{grid-precision} illustrates the effect of applying the view transformation \eqref{view-transformation} directly to the grid. When the grid is correctly rendered, as in Figure \ref{grid-precision} a) it appears as a black rectangle. Further from the origin, not all pixels in the grid can be represented and individual lines become visible. As the distance from the origin increases, fewer pixel locations can be represented exactly after performing the view transformation. + +An error of 1 ulp is increased by a factor of $10^6$ to end up comparable to the size of the display ($0 \to 1$). + + +\begin{figure}[H] + \centering + \includegraphics[width=800px]{figures/grid_0_1e-6.png} + \includegraphics[width=800px]{figures/{grid_0.5_1e-6}.png} + \includegraphics[width=800px]{figures/grid_1_1e-6.png} + \includegraphics[width=800px]{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} + + +\subsection{Names of programs in figures} +\begin{itemize} + \item single - Single precision IEEE-754 with \eqref{view-transformation} applied directly + \item double - Double precision IEEE-754 with \eqref{view-transformation} applied directly + \item cumul-single - Single precision IEEE-754 with cumulative transforms to B\'{e}ziers + \item cumul-double - Double precision IEEE-754 with cumulative transforms to B\'{e}ziers + \item path-single - Single precision IEEE-754 with cumulative transforms to Paths + \item path-double - Single precision IEEE-754 with cumulative transforms to Paths + \item path-rat - GNU MP Rationals with cumulative transforms to Paths +\end{itemize} + +\subsection{Precision for Fixed View} + -Figure \ref{} shows a plot of the number of lines visible in the grid as a function of distance from the origin for IEEE-754 floats and several different precision settings for the MPFR library. +By counting the number of distinctly representable lines within a particular view, we can show the degradation of precision quantitatively. The test grid is added to each view rectangle. -Figure \ref{} shows the obvious + +Figure \ref{loss_of_precision_grid_0.5.pdf} shows how precision degrades with $(v_x, v_y) = (0.5,0.5)$. +A constant line at $1401$ grid locations indicates no loss of precision. + + +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{{figures/loss_of_precision_grid_0.5}.pdf} + \caption{Loss of precision of the grid} + \label{loss_of_precision_grid_0.5.pdf} +\end{figure} + +\subsection{Accumulated error after changing the View} + +Figure \ref{cumulative_error_grid.pdf} shows the total error in the coordinates of each line in the grid after the view is scaled (zooming \emph{out}) by repeated transformations. A constant line at $0$ indicates no accumulated error. + +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{figures/cumulative_error_grid.pdf} + \caption{Error in the coordinates of the grid} + \label{cumulative_error_grid.pdf} +\end{figure} + +By considering Figure \ref{loss_of_precision_grid_0.5.pdf} and \ref{cumulative_error_grid.pdf}, \verb/path-rat/ is the winner. \section{Performance Measurements whilst Rendering} As discussed above, we succeeded in preserving rendering accuracy as defined above for an arbitrary view. However this comes at a performance cost, as the size of the number representation must grow accordingly. +{\bf TODO: Insert performance measurements here} - +{\bf TODO: Also, would be nice to show a graph (log scale) where something goes past $10^{\pm320}$ (absolute limit for doubles, previous figures are all within range of representable floats} diff --git a/figures/cumulative_error_grid.pdf b/figures/cumulative_error_grid.pdf new file mode 100644 index 0000000..e5f553d Binary files /dev/null and b/figures/cumulative_error_grid.pdf differ diff --git a/figures/grid_0.5_1e-6.png b/figures/grid_0.5_1e-6.png new file mode 100644 index 0000000..42a6e87 Binary files /dev/null and b/figures/grid_0.5_1e-6.png differ diff --git a/figures/grid_0_1e-6.png b/figures/grid_0_1e-6.png new file mode 100644 index 0000000..ecbb8c5 Binary files /dev/null and b/figures/grid_0_1e-6.png differ diff --git a/figures/grid_1_1e-6.png b/figures/grid_1_1e-6.png new file mode 100644 index 0000000..e699726 Binary files /dev/null and b/figures/grid_1_1e-6.png differ diff --git a/figures/grid_2_1e-6.png b/figures/grid_2_1e-6.png new file mode 100644 index 0000000..31ce3a2 Binary files /dev/null and b/figures/grid_2_1e-6.png differ diff --git a/figures/loss_of_precision_grid_0.5.pdf b/figures/loss_of_precision_grid_0.5.pdf new file mode 100644 index 0000000..f2a3f41 Binary files /dev/null and b/figures/loss_of_precision_grid_0.5.pdf differ diff --git a/presentation/Logos/WAMSI.png b/presentation/Logos/WAMSI.png deleted file mode 100644 index 36d914d..0000000 Binary files a/presentation/Logos/WAMSI.png and /dev/null differ diff --git a/presentation/bezier_to_font.svg b/presentation/bezier_to_font.svg new file mode 100644 index 0000000..045f9eb --- /dev/null +++ b/presentation/bezier_to_font.svg @@ -0,0 +1,816 @@ + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + A0 + + A1 + + + A2 + B0 + + B1 + + B2 + + + + + + + + + + + + + + + diff --git a/presentation/presentation.nav b/presentation/presentation.nav index 6d0bd76..9dc92ed 100644 --- a/presentation/presentation.nav +++ b/presentation/presentation.nav @@ -18,37 +18,44 @@ \headcommand {\beamer@framepages {7}{7}} \headcommand {\slideentry {1}{0}{8}{8/8}{}{0}} \headcommand {\beamer@framepages {8}{8}} -\headcommand {\sectionentry {2}{Implementing a Basic SVG Viewer}{9}{Implementing a Basic SVG Viewer}{0}} -\headcommand {\beamer@sectionpages {4}{8}} -\headcommand {\beamer@subsectionpages {4}{8}} -\headcommand {\slideentry {2}{0}{9}{9/9}{}{0}} +\headcommand {\slideentry {1}{0}{9}{9/9}{}{0}} \headcommand {\beamer@framepages {9}{9}} -\headcommand {\slideentry {2}{0}{10}{10/10}{}{0}} +\headcommand {\slideentry {1}{0}{10}{10/10}{}{0}} \headcommand {\beamer@framepages {10}{10}} -\headcommand {\sectionentry {3}{Live Demo}{11}{Live Demo}{0}} -\headcommand {\beamer@sectionpages {9}{10}} -\headcommand {\beamer@subsectionpages {9}{10}} -\headcommand {\slideentry {3}{0}{11}{11/11}{}{0}} +\headcommand {\slideentry {1}{0}{11}{11/11}{}{0}} \headcommand {\beamer@framepages {11}{11}} -\headcommand {\sectionentry {4}{Conclusions}{12}{Conclusions}{0}} -\headcommand {\beamer@sectionpages {11}{11}} -\headcommand {\beamer@subsectionpages {11}{11}} -\headcommand {\slideentry {4}{0}{12}{12/12}{}{0}} +\headcommand {\slideentry {1}{0}{12}{12/12}{}{0}} \headcommand {\beamer@framepages {12}{12}} -\headcommand {\sectionentry {5}{References}{13}{References}{0}} -\headcommand {\beamer@sectionpages {12}{12}} -\headcommand {\beamer@subsectionpages {12}{12}} -\headcommand {\sectionentry {6}{Questions}{13}{Questions}{0}} -\headcommand {\beamer@sectionpages {13}{12}} -\headcommand {\beamer@subsectionpages {13}{12}} -\headcommand {\slideentry {6}{0}{13}{13/13}{}{0}} +\headcommand {\sectionentry {2}{Live Demo}{13}{Live Demo}{0}} +\headcommand {\beamer@sectionpages {4}{12}} +\headcommand {\beamer@subsectionpages {4}{12}} +\headcommand {\slideentry {2}{0}{13}{13/13}{}{0}} \headcommand {\beamer@framepages {13}{13}} -\headcommand {\slideentry {6}{0}{14}{14/14}{}{0}} +\headcommand {\sectionentry {3}{Conclusions}{14}{Conclusions}{0}} +\headcommand {\beamer@sectionpages {13}{13}} +\headcommand {\beamer@subsectionpages {13}{13}} +\headcommand {\slideentry {3}{0}{14}{14/14}{}{0}} \headcommand {\beamer@framepages {14}{14}} -\headcommand {\slideentry {6}{0}{15}{15/15}{}{0}} +\headcommand {\sectionentry {4}{References}{15}{References}{0}} +\headcommand {\beamer@sectionpages {14}{14}} +\headcommand {\beamer@subsectionpages {14}{14}} +\headcommand {\slideentry {4}{0}{15}{15/15}{}{0}} \headcommand {\beamer@framepages {15}{15}} -\headcommand {\beamer@partpages {1}{15}} -\headcommand {\beamer@subsectionpages {13}{15}} -\headcommand {\beamer@sectionpages {13}{15}} -\headcommand {\beamer@documentpages {15}} -\headcommand {\def \inserttotalframenumber {15}} +\headcommand {\sectionentry {5}{Questions}{16}{Questions}{0}} +\headcommand {\beamer@sectionpages {15}{15}} +\headcommand {\beamer@subsectionpages {15}{15}} +\headcommand {\slideentry {5}{0}{16}{16/16}{}{0}} +\headcommand {\beamer@framepages {16}{16}} +\headcommand {\slideentry {5}{0}{17}{17/17}{}{0}} +\headcommand {\beamer@framepages {17}{17}} +\headcommand {\slideentry {5}{0}{18}{18/18}{}{0}} +\headcommand {\beamer@framepages {18}{18}} +\headcommand {\slideentry {5}{0}{19}{19/19}{}{0}} +\headcommand {\beamer@framepages {19}{19}} +\headcommand {\slideentry {5}{0}{20}{20/20}{}{0}} +\headcommand {\beamer@framepages {20}{20}} +\headcommand {\beamer@partpages {1}{20}} +\headcommand {\beamer@subsectionpages {16}{20}} +\headcommand {\beamer@sectionpages {16}{20}} +\headcommand {\beamer@documentpages {20}} +\headcommand {\def \inserttotalframenumber {20}} diff --git a/presentation/presentation.pdf b/presentation/presentation.pdf index 1a2117f..9021d5a 100644 Binary files a/presentation/presentation.pdf and b/presentation/presentation.pdf differ diff --git a/presentation/presentation.tex b/presentation/presentation.tex index 9ad4c78..7d5494b 100644 --- a/presentation/presentation.tex +++ b/presentation/presentation.tex @@ -38,7 +38,7 @@ {Supervisors: Tim French, Rowan Davies} \date[CSS 2009]{\today} % change the actual date - \titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}} + %\titlegraphic{\includegraphics[width=3cm]{./Logos/WAMSI.png}} %% Optional stuff------------------------------------------------------------------ @@ -121,28 +121,13 @@ \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} -\begin{itemize} - \item At scale of only $1\times 10^{-6}$, the fox is very sick -\end{itemize} -\centering - \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png} - \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} -\end{frame} -\section{Implementing a Basic SVG Viewer} \begin{frame} \frametitle{Structure of Vector Graphics} \begin{itemize} @@ -164,6 +149,51 @@ \includegraphics[width=0.5\textwidth]{../figures/fox-vector_face_with_bezbounds.png} \end{frame} + +\begin{frame} +\frametitle{Floating point calculations \\ go wrong} +\begin{itemize} + \item Scaled to $~1\times 10^{-6}$, the fox is very sick +\end{itemize} +\centering + \includegraphics[width=0.5\textwidth]{../figures/fox-vector_highzoom1.png} + +\end{frame} + + +\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 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?} + \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} + \end{itemize} +\end{frame} + \section{Live Demo} \begin{frame} \frametitle{Live Demo} @@ -195,7 +225,21 @@ \end{itemize} \end{frame} \section{References} - +\begin{frame} + \frametitle{References \& More information} + \begin{itemize} + \item Work on SVG viewer collaborative with David Gow + \begin{itemize} + \item See David Gow's presentation about Quadtrees + \end{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} @@ -220,20 +264,48 @@ \begin{frame} \frametitle{Q: Arbitrary precision floats?} +\begin{align} + X &= m \times 2^{E} +\end{align} \begin{itemize} - \item We support them as well! - \item Rationals are more convenient: + \item $m$ and $E$ are of arbitrary size + \item Implemented by MPFR or GMP + \item Difficulties: \begin{itemize} - \item Need to manually set precision + \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? \end{itemize} - \item Could be future work \end{itemize} \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} +\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} + \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}$ + \end{itemize} +\end{frame} + + \end{document} diff --git a/presentation/turtles.svg b/presentation/turtles.svg new file mode 100644 index 0000000..4cae3c6 --- /dev/null +++ b/presentation/turtles.svg @@ -0,0 +1,1793 @@ + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/thesis.pdf b/thesis.pdf index c51431c..19a5b53 100644 Binary files a/thesis.pdf and b/thesis.pdf differ