Drafted into submission

[ipdf/sam.git] / chapters / Results.tex

diff --git a/chapters/Results.tex b/chapters/Results.tex
index 923eccf..1d9df1a 100644 (file)
--- a/chapters/Results.tex
+++ b/chapters/Results.tex
@@ -1,14 +1,13 @@
-\chapter{Results and Discussion}
-
+\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. 
 
 
 \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}\label{direct_transform}

 
 

+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$

 
 
 \begin{figure}[H]
 
 
 \begin{figure}[H]


@@ -18,9 +17,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}
 
        \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}\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.

 
 

-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)
+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
 %label start
 %setbounds 0.5 0.5 1e-6 1e-6
 %loadsvg svg-tests/fox-vector.svg


@@ -36,9 +37,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}
 
        \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}\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. 

 
 

-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. This is shown in Figure \ref{qualitative-rendering-fox-cumulative-relative} b).

 
 \begin{figure}[H]
        \centering
 
 \begin{figure}[H]
        \centering


@@ -46,21 +49,76 @@ We can correct this drift whilst maintaining performance by using an arbitrary p
        \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}
 \end{figure}
        \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}
 \end{figure}

+
+Videos showing the effects discussed in Section \ref{direct_transform}, \ref{cumulative_transform} and \ref{path_transform} can be found at:
+
+ \url{http://szmoore.net/ipdf/sam/presentation}.

        
 \section{Quantitative Measurements of Rendering Accuracy}
        
 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.
 
        
 \section{Quantitative Measurements of Rendering Accuracy}
        
 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{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.
+
+
+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 is clear that 

 
 

-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. 

 
 

-Figure \ref{} shows the obvious 
+\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}
+\section{Performance Measurements}

        
 As discussed above, we succeeded in preserving rendering accuracy as defined above for an arbitrary view.
        
 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.
+However this comes at a performance cost, as the size of the Rational number representation must grow accordingly. Figures \ref{memory.pdf} and \ref{time.pdf} were obtained by repeatedly clearing the document, scaling, and adding a fixed number of B\'{e}zier curves. The \texttt{mpfr-1024} number representation performs much better in terms of memory usage and performance; however as discussed in Section \ref{}, due to the fixed precision it cannot represent detail seperated by a truly arbitrary distance.

 
 

+\begin{figure}[H]
+       \centering
+       \includegraphics[width=0.7\textwidth]{figures/memory.pdf}
+       \label{memory.pdf}
+       \caption{Memory used per Path coordinate whilst zooming in}
+\end{figure}

 
 

+\begin{figure}[H]
+       \centering
+       \includegraphics[width=0.7\textwidth]{figures/time.pdf}
+       \label{time.pdf}
+       \caption{Time taken to scale about the fixed point}
+\end{figure}