chapters/Proposal.tex

   1 \chapter{Proposal}\label{Proposal}
   2
   3 \section{Aim}
   4
   5 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 with regards to  precision.
   6
   7 We will consider designs for a document format allowing graphics primitives at an arbitrary level of zoom with no loss of detail. 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. Although it is possible to produce three dimensional graphics using some of the technologies we will explore, we will focus on two dimensional graphics.
   8
   9 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.
  10
  11 \subsection{Clarification of Terms}
  12
  13 It may be necessary to clarify what we mean by the terms ``arbitrary precision'' and ``document formats''. Regarding the latter, we consider a document format to be any representation of visual information which is capable of being stored indefinitely. Regarding the former, we do not propose to be able to contain an infinite amount of information within such 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, regardless of how precise this level is. For example, the precision of coordinates of primitives drawn in a graphical document editor will always be limited by the resolution of the display on which they are drawn, but not by the viewer.
  14
  15
  16 \section{Methods}
  17
  18 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). Hearn and Baker's textbook ``Computer Graphics'' includes chapters providing a good overview of two dimensional graphics\cite{computergraphics2}.
  19
  20 The process of rendering a document will be considered as a common area of research, whilst individual research will be conducted on means for allowing infinite precision.
  21 At this stage we have identified two possible areas for individual research:
  22
  23 \begin{enumerate}
  24
  25         \item {\bf Arbitrary Precision real valued numbers} --- Sam Moore
  26
  27         We plan to investigate the representation of real values to a high or arbitary degree of precision. Such representations would allow for the coordinates of primitives to be relative to a single global coordinate system. We would expect a decrease in performance with increased complexity of the data structure used to represent a real value. We will also consider the limitations imposed by performing calculations on the GPU or CPU.
  28
  29 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}. A more recent and comprehensive text book, ``Handbook of Floating Point Arithmetic''\cite{HFP}, published in 2010, has also been identified as highly relevant.
  30
  31         \item {\bf Local coordinate systems} --- David Gow \cite{proposalGow}
  32
  33         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.
  34
  35 \end{enumerate}
  36 We aim to compare these and any additional implementations considered using the following metrics:
  37 \begin{enumerate}
  38
  39         \item {\bf Performance vs Number of Primitives}
  40
  41         As it is clearly desirable to include more objects in a document, this is a natural metric for the usefulness of an implementation.
  42         We will compare the performance of rendering different implementations, using several ``standard'' test documents.
  43
  44         \item {\bf Performance vs Visible Primitives}
  45
  46         There will inevitably be an overhead to all primitives in the document, whether drawn or not.
  47         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.
  48
  49
  50         \item {\bf Performance vs Zoom Level}
  51
  52         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.
  53
  54         \item {\bf Performance whilst translation and scaling}
  55
  56         Whilst changing the view, it is ideal that the document be re-rendered as efficiently as possible, to avoid disorienting and confusing the user.
  57         We will therefore compare the speed of rendering as the standard documents are translated or scaled at a constant rate.
  58
  59         \item {\bf Artifacts and Limitations on Precision}
  60
  61         As we are unlikely to achieve truly ``infinite'' precision, qualitative comparisons of the accuracy of rendering under different implementations should be made.
  62
  63 \end{enumerate}
  64
  65 \section{Software and Hardware Requirements}
  66
  67 Our proof of concept will be developed for a conventional GNU/Linux desktop or laptop computer using the OpenGL 3.1 API for rendering. However, the techniques explored could be extended to other platforms and libraries.
  68
  69
  70
  71
  72