\chapter{Introduction}\label{Introduction}
-\rephrase{Most of this chapter is copy pasted from the project proposal} \\
- \url{http://szmoore.net/ipdf/documents/ProjectProposalSam.pdf}
+Early electronic document formats such as PostScript were motivated by a need to print documents onto a paper medium. In the PostScript standard, this lead to a model of the document as a program; a series of instructions to be executed by an interpreter which would result in ``ink'' being placed on ``pages'' of a fixed size\cite{plrm}.
-Early electronic document formats such as PostScript were motivated by a need to print documents onto a paper medium. In the PostScript standard, this lead to a model of the document as a program; a series of instructions to be executed by an interpreter which would result in ``ink'' being placed on ``pages'' of a fixed size\cite{plrm}. The ubiquitous Portable Document Format (PDF) standard provides many enhancements to PostScript taking into account desktop publishing requirements\cite{cheng2002portable}, but it is still fundamentally based on the same imaging model\cite{pdfref17}. This idea of a document as a static ``page'' has lead to limited precision in these and other traditional document formats.
+The ubiquitous Portable Document Format (PDF) standard provides many enhancements to PostScript taking into account desktop publishing requirements \cite{cheng2002portable}, but it is still fundamentally based on the same imaging model \cite{pdfref17}. This idea of a document as a static ``page'' has lead to limitations on what could be achieved with a digital document viewers \cite{hayes2012pixels}.
-The emergence of the internet, web browsers, XML/HTML, JavaScript and related technologies has seen a revolution in the ways in which information can be presented digitally, and the PDF standard itself has begun to move beyond static text and figures\cite{hayes2012pixels, barnes2013embedding}. However, the popular document formats are still designed with the intention of showing information at either a single, fixed level of detail, or a small range of levels.
+The emergence of the internet, web browsers, XML/HTML, JavaScript and related technologies has seen a revolution in the ways in which information can be presented digitally, and the PDF standard itself has begun to move beyond static text and figures \cite{hayes2012pixels, barnes2013embedding}. However, the popular document formats are still designed with the intention of showing information at either a single, fixed level of detail, or a small range of levels.
-As most digital display devices are smaller than physical paper medium, all useful viewers are able to ``zoom'' to a subset of the document. Vector graphics formats including PostScript and PDF support rasterisation at different zoom levels\cite{plrm, pdfref17}, but the use of fixed precision floating point numbers causes problems due to imprecision either far from the origin, or at a high level of detail\cite{goldberg91whatevery, goldberg1992thedesign}.
-
-We are now seeing a widespread use of mobile computing devices with touch screens, where the display size is typically much smaller than paper pages and traditional computer monitors; it seems that there is much to be gained by breaking free of the restricted precision of traditional document formats.
-
-\section{Aim}
-
-In this project, we will explore the state of the art of current document formats including PDF, PostScript, SVG, HTML, and the limitations of each in terms of precision.
-We will consider designs for a document format allowing graphics primitives at an arbitrary level of zoom with no loss of detail. We will refer to such a document format as ``infinite precision''. A viewer and editor will be implemented as a proof of concept; we adopt a low level, ground up approach to designing this viewer so as to not become restricted by any single existing document format.
-
-\rephrase{New bit} \\
-It is necessary to clarify what we mean by ``infinite'' precision. We do not propose to be able to contain an infinite amount of information within a document. The goal is to be able to render a primitive at the same level of detail it is specified by a document format. For example, the precision of coordinates of primitives drawn in a graphical editor will always be limited by the resolution of the display on which they are drawn, but not by the viewer.
+As most digital display devices are smaller than physical paper medium, all useful viewers are able to ``zoom'' to a subset of the document. Vector graphics formats including PostScript, PDF and SVG support rasterisation at different zoom levels \cite{plrm, pdfref17, svg2011-1.1}, but the use of fixed precision floating point numbers causes problems due to imprecision either far from the origin, or at a high level of detail \cite{goldberg1991whatevery, goldberg1992thedesign}.
There are many possible applications for documents in which precision is unlimited. Several areas of use include: visualisation of extremely large or infinite data sets; visualisation of high precision numerical computations; digital artwork; computer aided design; and maps.
-
-\section{Methods}
-
-Initial research and software development is being conducted in collaboration with David Gow\cite{proposalGow}. Once a simple testbed application has been developed, we will individually explore approaches for introducing arbitrary levels of precision; these approaches will be implemented as alternate versions of the same software. The focus will be on drawing simple primitives (lines, polygons, circles). However, if time permits we will explore adding more complicated primitives (font glyphs, bezier curves, embedded bitmaps).
-
-At this stage we have identified two possible areas for individual research:
-
-\begin{enumerate}
-
- \item {\bf Arbitrary Precision real valued numbers} --- Sam Moore
-
- We plan to investigate the representation of real values to a high or arbitary degree of precision. Such representations would allow for a document to be implemented
- using a single global coordinate system. However, we would expect a decrease in performance with increased complexity of the data structure used to represent a real value. \rephrase{Both software and hardware techniques will be explored.} We will also consider the limitations imposed by performing calculations on the GPU or CPU.
-
- Starting points for research in this area are Priest's 1991 paper, ``Algorithms for Arbitrary Precision Floating Point Arithmetic''\cite{priest1991algorithms}, and Goldberg's 1992 paper ``The design of floating point data types''\cite{goldberg1992thedesign}. \rephrase{A more recent and comprehensive text book, ``Handbook of Floating Point Arithmetic''\cite{hfpa}, published in 2010, has also been identified as highly relevant.}
-
- \item {\bf Local coordinate systems} --- David Gow \cite{proposalGow}
-
- An alternative approach involves segmenting the document into different regions using fixed precision floats to define primitives within each region. A quadtree or similar data structure could be employed to identify and render those regions currently visible in the document viewer.\rephrase{Say more here?}
-
-\end{enumerate}
-\pagebreak
-We aim to compare these and any additional implementations considered using the following metrics:
-\begin{enumerate}
-
- \item {\bf Performance vs Number of Primitives}
-
- As it is clearly desirable to include more objects in a document, this is a natural metric for the usefulness of an implementation.
- We will compare the performance of rendering different implementations, using several ``standard'' test documents.
-
- \item {\bf Performance vs Visible Primitives}
-
- There will inevitably be an overhead to all primitives in the document, whether drawn or not.
- As the structure of the document format and rendering algorithms may be designed independently, we will repeat the above tests considering only the number of visible primitives.
-
-
- \item {\bf Performance vs Zoom Level}
-
- We will also consider the performance of rendering at zoom levels that include primitives on both small and large scales, since these are the cases under which floating point precision causes problems in the PostScript and PDF standards.
-
- \item {\bf Performance whilst translation and scaling}
-
- Whilst changing the view, it is ideal that the document be re-rendered as efficiently as possible, to avoid disorienting and confusing the user.
- We will therefore compare the speed of rendering as the standard documents are translated or scaled at a constant rate.
-
- \item {\bf Artifacts and Limitations on Precision}
-
- As we are unlikely to achieve truly ``infinite'' precision, qualitative comparisons of the accuracy of rendering under different implementations should be made.
-
-\end{enumerate}
-
-\section{Software and Hardware Requirements}
-
-Due to the relative immaturity and inconsistency of graphics drivers on mobile devices, our proof of concept will be developed for a conventional GNU/Linux desktop or laptop computer using OpenGL. However, the techniques explored could easily be extended to other platforms and libraries.
-
-
-\pagebreak
-
-\section{Timeline}
-Deadlines enforced by the faculty of Engineering Computing and Mathematics are \emph{italicised}.\footnote{David Gow is being assessed under the 2014 rules for a BEng (Software) Final Year Project, whilst the author is being assessed under the 2014 rules for a BEng (Mechatronics) Final Year Project; deadlines and requirements as shown in Gow's proposal\cite{proposalGow} may differ}.
+The goal of this work is to explore to explore the limitations of floating point arithmetic and possible approaches to achieving arbitrary precision document formats. In collaboration with Gow \cite{thesisGow} we have implemented a proof of concept document viewer compatable with a subset of the SVG standard as a starting point for our research.
-\begin{center}
-\begin{tabular}{l|p{0.5\textwidth}}
- {\bf Date} & {\bf Milestone}\\
- \hline
- $17^{\text{th}}$ April & Draft Literature Review completed. \rephrase{This sort of didn't happen...}\\
- \hline
- $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
- \hline
- $26^{\text{th}}$ May & \emph{Progress Report and Revised Literature Review due.}\\
- \hline
- $9^{\text{th}}$ June & Demonstrations of limitations of floating point precision in the Testbed software. \\
- $1^{\text{st}}$ July & At least one implementation of infinite precision for basic primitives (lines, polygons, curves) completed. Other implementations, advanced features, and areas for more detailed research identified. \\
- \hline
- $1^{\text{st}}$ August & Experiments and comparison of various infinite precision implementations completed. \\
- \hline
- $1^{\text{st}}$ September & Advanced features implemented and tested, work underway on Final Report. \\
- \hline
- TBA & \emph{Conference Abstract and Presentation due.} \\
- \hline
- $10^{\text{th}}$ October & \emph{Draft of Final Report due.} \\
- \hline
- $27^{\text{th}}$ October & \emph{Final Report due.}\\
- \hline
-\end{tabular}
-\end{center}
+With the aim of being able to correctly insert and render ``detail'' (constructed by importing test SVG images) seperated by arbitrary distance, this work explores the limitations in floating point arithmetic and how these may be mitigated
+Using the Rational representation of the GNU Multiple Precision (GMP) library \cite{granlund2004GMP} we are able to implement correct rendering of SVG test images seperated by extremely large distances. We will present measurements of rendering accuracy and performance for our implementation.
+An alternative implementation based on a spatial approach to constructing the document is discussed by Gow \cite{thesisGow}.
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au