-\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)}
+\chapter{Results and Discussion}\label{Results and Discussion}
\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.
-\subsection{Applying the view transformation directly}
+Throughout this section we will use IEEE-754 single precision (binary32) floats unless otherwise stated. Although double precision (binary64) would allow for greater precision, one could still choose coordinates for which similar results can be obtained.
+
-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$
+\subsection{Applying the view transformation directly}\label{direct_transform}
-{\bf TODO: Calculate that properly, shouldn't be hard}
+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 the coordinates of B\'{e}zier bounds, with default IEEE-754 rounding behaviour (to nearest). The loss of precision in the second figure is obvious.
+In this case, the precision loss occurs when the test SVG is added to the document; the inverse of \eqref{view-transformation} must be applied. That is (for the $x$ coordinate, with the same equations applying for the $y$ coordinate):
+\begin{align*}
+ X = V_{w} \times \text{SVG}_x + V_{x}
+\end{align*}
+Where $V$ represents the view, $X$ is the coordinate in the document, and $\text{SVG}_x$ is the coordinate in the test SVG at original scale. In Figure \ref{qualitative-rendering-fox}, the multiplication $V_{w} \times \text{SVG}_x$ has a smaller exponent than $V_{x}$. The error of the addition operation is comparable to one ulp, ie: $\frac{V_{x}}{2}$. In this case, the rounding error is dominating the calculation. The division by $V_{w} = 10^{6}$ in \eqref{view-transformation} is merely increasing this rounding error as the coordinates are converted to display space.
\begin{figure}[H]
\centering
\caption{The vector image from Figure \ref{vector-vs-raster} under two different scales}\label{qualitative-rendering-fox}
\end{figure}
-\subsection{Applying cumulative transformations to all B\'{e}ziers}
+\subsection{Applying cumulative transformations to all B\'{e}ziers}\label{cumulative_transform}
-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.
+Rather than applying \eqref{view-transformation} to object coordinates specified relative to the document, we can store the bounds of objects in display space (relative to the view) and modify these bounds according to the transformations discussed in Section \ref{Coordinate Systems and Transformations} 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
\caption{The effect of applying cumulative transformations to all B\'{e}ziers}\label{qualitative-rendering-fox-cumulative}
\end{figure}
-\subsection{Applying cumulative transformations to Paths}
+\subsection{Applying cumulative transformations to Paths}\label{path_transform}
-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.
+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 bounding box 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 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.
+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. This is shown in Figure \ref{qualitative-rendering-fox-cumulative-relative} b).
\begin{figure}[H]
\centering
\includegraphics[width=800px]{figures/fox-vector_cumulative_relative_to_path.png}
\includegraphics[width=800px]{figures/fox-vector_cumulative_relative_to_path_GMPrat.png}
- \caption{Effect of cumulative transformations applied to Paths\\a) Path bounds represented using floats b) Path bounds represented using Rationals}\label{qualitative-rendering-fox-cumulative-relative}
+ \caption{Effect of cumulative transformations applied to Paths\\a) Path bounds represented using floats b) Path bounds represented using GMP Rationals}\label{qualitative-rendering-fox-cumulative-relative}
\end{figure}
+
+
\section{Quantitative Measurements of Rendering Accuracy}
+
+To quantitatively measure rendering accuracy, we can record the coordinates of objects in \emph{display space} and measure how these drift as the same collection of objects is added to the document at different view locations. Alternately, since rounding errors causes different coordinates to round to the same value in display space, we may count the number of distinct object bounds in display space.
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.
-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.
+Figure \ref{grid-precision} illustrates the effect of applying the view transformation \eqref{view-transformation} directly to the grid, as discussed above in Section \ref{direct_transform}. 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.
+
+We should note that with the view top left corner close to $(0,0)$ as in Figure \ref{grid-precision} a), detail can be represented more precisely due to the use of IEEE-754 denormals near the origin (see Section \ref{Floating Point Number Representations}).
-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]
a) Near origin (denormals) b), c), d) Increasing the exponent of $(v_x,v_y)$ by 1}\label{grid-precision}
\end{figure}
+\subsection{Precision for Fixed View} \label{Precision for Fixed View}
-\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}
-
-
-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.
+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 with increasingly smaller width and height.
-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.
+Figure \ref{loss_of_precision_grid_0.5.pdf} shows how precision degrades with $(V_x, V_y) = (0.5,0.5)$ for different precision settings using MPFR floating point values to represent the view coordinates. A constant line at $1401$ grid locations indicates no loss of precision. From this figure it should be clear how merely setting the precision of the floating point representation to a higher (but fixed) value will not allow insertion of detail at an arbitrary point; using 1024 bits of precision will still leave no lines representable above magnifications of $M \approx10^{310}$.
\begin{figure}[H]
\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.
+Using the cumulative transformation approach discussed in Section \ref{cumulative_transform} means that detail inserted into a fixed view will always render correctly. A fairer test of this approach is to test the rendering accuracy after applying repeated scaling to the document.
+
+Figure \ref{cumulative_error_grid.pdf} shows the total error in the coordinates of each line in the grid after the view is scaled by repeated transformations (zooming \emph{out} and then back in by the same amount). A constant line at $0$ would indicate no accumulated error.
+
+In this case, using an arbitrary precision representation such as GMP Rationals (\texttt{path-rat}) does not totally eliminate error. This is simply because the final coordinate transformation requires the conversion of rationals to IEEE-754 floats before rendering. Since the total final error for $1042$ lines is less than $10^{-2}$, and the width of the display is $1$, this would represent a negligable difference in the rendering of the grid.
+
+The legend of Figure \ref{cumulative_error_grid.pdf} should be interpreted as follows: A prefix of \texttt{path} indicates use of intermediate Path coordinate systems (Section \ref{path_transform}), \texttt{cumul} indicates cumulative transforms applied to B\'{e}ziers (Section \ref{cumulative_transform}) and no prefix indicates the direct approach (Section \ref{direct_transform}). The type of number representation used is also indicated. In the case of the Path transformations, only the bounds of the Path are expressed with the indicated representation; all other operations are done using IEEE-754 single precision floats. These results agree with those discussed qualitatively above.
+
\begin{figure}[H]
\centering
\includegraphics[width=0.8\textwidth]{figures/cumulative_error_grid.pdf}
- \caption{Error in the coordinates of the grid}
+ \caption{Error in the coordinates of the grid {\bf Note:} Logarithmic Axes}
\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}
-\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.
+\subsection{Performance of Static Detail at Different View Locations}
+As discussed above, we succeeded in preserving rendering accuracy as defined above for extremely large ranges of coordinates in the document.
+
+However this comes at a performance cost, as the size of the Rational number representation must grow accordingly. Figures \ref{memory.pdf} a) and b) were obtained by repeatedly resetting the document, scaling, and adding a fixed number of B\'{e}zier curves. It appears that the GMP representation increases memory usage linearly, with the speed decreasing faster than linear. The \texttt{mpfr-1024} number representation performs much better in terms of a fixed memory usage and a slower increase in time taken; however as discussed in Section \ref{Precision for Fixed View}, due to the fixed precision it cannot represent detail seperated by a truly arbitrary distance.
+
+
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=0.45\textwidth]{figures/memory.pdf}
+ \includegraphics[width=0.45\textwidth]{figures/time.pdf}
+ \caption{a) Memory used per Path coordinate and b) Time taken to scale} \label{memory.pdf}
+\end{figure}
+
+\subsection{Performance whilst adding Detail} \label{Performance whilst adding Detail}
+
+For a static document containing only a few imported test SVGs, the use of GMP rationals for path coordinates was not a noticable performance detriment compared to the implementations using floating point coordinates. Figure \ref{adding_things} measures the time taken for a script to scale the document to a point at which it will insert an additional copy of a test SVG (Figure \ref{turtle.pdf}).
+
+We have included the Na\"{i}ve approach discussed in Section \ref{Naive Approach} with GMP rationals (\texttt{Gmprat}) and MPFR using 1024 bits of precision (\texttt{mpfr-1024}) to illustrate its impracticality. The \texttt{Gmprat} data is removed from Figure \ref{adding_things} b).
+
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=0.49\textwidth]{figures/naive_gmprat_is_slow.pdf}
+ \includegraphics[width=0.49\textwidth]{figures/naive_mpfr_is_also_slow.pdf}
-{\bf TODO: Insert performance measurements here}
+ \caption{a) Performance including Na\"{i}ve Implementations b) Excluding \texttt{Gmprat} data \\ Legend is in descending order to correspond with the height of the curves} \label{adding_things}
+\end{figure}
+
+From these results it is clear that our implementation using arbitrary precision arithmetic only for path coordinates is comparable to the straight forward floating point implementation. It is interesting to note that despite Figure \ref{memory.pdf}, GMP rationals are slightly faster than MPFR with 1024 bits for this test. This is possibly because the GMP rationals only grow in size as needed, whilst MPFR operations always use the full 1024 bits per number.
+
+\section{Video Demonstrations}
+
+Realtime videos of the IPDF software showing the results presented in this chapter can be found at
+\url{http://szmoore.net/ipdf/sam/videos}. The performance tests in Section \ref{Performance whilst adding Detail} were taken using the same script running in these videos.
+
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=0.4\textwidth]{figures/turtle.pdf}
+ \caption{The test SVG used to produce the videos} \label{turtle.pdf}
+\end{figure}
-{\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}
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au