ProjectProposalDavid.tex

   1 \documentclass[a4paper,10pt]{article}
   2 %\documentclass[a4paper,10pt]{scrartcl}
   3
   4 \usepackage[utf8]{inputenc}
   5 \usepackage{hyperref}
   6 \usepackage{acronym}
   7 \usepackage{amsmath}
   8 \usepackage{amssymb}
   9
  10 \acrodef{CAD}[CAD]{Computer-Aided Drafting}
  11 \acrodef{BIM}{Building Information Modelling}
  12 \acrodef{SKA}{Square Kilometre Array}
  13 \acrodef{CPU}{Central Processing Unit}
  14 \acrodef{GPU}{Graphics Processing Unit}
  15
  16 \title{Research Project Proposal}
  17 \author{David Gow\\
  18 20513684}
  19 \date{March 12, 2014} %Today
  20
  21 \pdfinfo{
  22   /Title    (Project Proposal: Infinite-precision Documents)
  23   /Author   (David Gow)
  24   /Creator  (A Guy who knows about document formats, yo!)
  25   /Producer (Steven Spielberg)
  26   /Subject  (Fractal Document Formats)
  27   /Keywords (document, project, proposal, vector, fractal, precision, floating-point)
  28 }
  29
  30 \begin{document}
  31 \maketitle\hrule
  32 \begin{center}
  33 \begin{tabular}{lp{0.8\textwidth}}
  34 \textbf{Title:} & Infinite-precision document formats\\
  35 \textbf{Supervisor} & A/Prof. Tim French\\
  36 \textbf{Project Group:} & David Gow, Samuel Moore
  37 \end{tabular}
  38 \end{center}
  39 \section{Background}
  40 %Since computers first displaced the typewriter, they've been used to manipulate documents: storing them, creating them, viewing them and printing them.
  41 %However, the nature of this use has changed significantly. Existing document formats, such as PDF and PostScript, were designed to mirror paper documents, and
  42 %were originally implemented as storage for documents to be printed. They are therefore
  43
  44 Traditional document formats such as PDF and Postscript were designed for
  45 documents to be printed. They therefore are optimised to rasterize an entire
  46 page at a given resolution, often on the embedded processor found in (older)
  47 printers. This, however, does not fit well with interactive display on screens,
  48 particularly on mobile devices such as telephones and tablets.
  49
  50 In particular, when displaying a document on a screen, the user has several additional
  51 ways of interacting with the document, such as viewing a subset of the document in high
  52 resolution using the ``zoom'' option.
  53
  54 Existing vector file formats do support rasterization at different resolutions, but are limited
  55 by the precision of coordinates and other intermediate values. PostScript and PDF, for example,
  56 store many values in a \emph{real} type with a limit of approximately 8 decimal digits of precision
  57 (PostScript\cite{plrm}) or 5 decimal digits of precision (PDF\cite{pdfref17}). These floating-point data
  58 types, while they provide both range (allowing for large documents) and precision (allowing for fine detail),
  59 cannot combine the two\cite{goldberg91whatevery}. It follows that objects placed further from the origin must
  60 have less detail. Furthermore, these numerical datatypes have a limited range and therefore have an absolute
  61 limit on the size or precision of any document.
  62
  63 Documents with high --- or at least consistent --- levels of precision have many applications.
  64 The building industry uses tools such as \ac{CAD} and \ac{BIM} systems for managing schematics which
  65 require precision. At the moment, this requires special tools, and it is not possible to export these as
  66 a single view without loss of precision. Similarly, infinite precision document formats would allow maps
  67 covering large areas to be stored contiguously (without requiring plates at different zoom levels) without
  68 any loss of precision.
  69
  70 \section{Aim}
  71
  72 We aim to prototype a simple document system which does not have these restrictions on zoom,
  73 and which can store data precisely at a given level of zoom. While the primary goal is to ensure
  74 the objects within documents retain the precision at which they were created (typically being the
  75 resolution of the display used during document editing), an ideal approach would also ensure stability
  76 of the object when magnified beyond its original size.
  77
  78 Should this be successful, we will prototype different methods of implementing this system,
  79 using different data structures, to compare their relative merits in terms of --- amongst
  80 other things --- performance. In particular, we hope to avoid some of the performance issues
  81 resulting from traditional use of arbitrary-precision data types, particularly on the \ac{GPU}\cite{emmart2010high}.
  82
  83 As this is a group project each group member will develop and prototype a different method of
  84 retaining precision. For \emph{this} individual part of the project, quadtrees will be investigated to provide a form of coordinate
  85 system renormalisation as the document view is scaled.
  86
  87 These systems will be compared in terms of their performance, with the aim to identify in which situations each implementation
  88 is most performant, consistent and correct.
  89
  90 \section{Method}
  91 In order to make the most efficient use of our time, much of the early implementation work will be done as a collaboration with Samuel Moore.
  92 In particular, the work to implement the basic document system will be done jointly, which we will then use as a base to implement our (individual) data structures
  93 and algorithms for infinite-precision.
  94
  95 Initially, this document system will support documents consisting only of basic shapes (such as polygons, circles and B\'ezier curves),
  96 but, should time allow, this can be extended to include font glyphs, embedded raster images and other objects.
  97
  98
  99 We will be comparing these methods primarily in terms of performance using a number of metrics:
 100 \begin{itemize}
 101         \item Performance per document object.
 102
 103         As objects are the basis of these documents, we will test against a set of ``standardised'' documents with
 104         to determine how performance scales with the number of objects. We will test this with each of the different
 105         types (or shapes) of objects, as they may have different performance characteristics. Measured in ${ms}/{object}$
 106
 107         \item Performance per visible object.
 108
 109         As above, but measuring performance against the number of objects visible in a given view. For example, when zoomed in, fewer
 110         objects will be onscreen, and so --- in some implementations --- may not contribute as heavily to the computational load.
 111
 112         Similarly measured in ${ms}/{object}$.
 113
 114         \item Performance per zoom level.
 115
 116         Time taken to render frames with the same number of visible objects will be compared at different zoom levels to determine if there is
 117         a relationship between performance and zoom. We will perform this test both with views centred at the origin and centred at a random coordinate to
 118         see which, if any, implementations are affected by this. Measured in ${ms}/{length}$, where length is the length of one edge of the view in
 119         global document coordinates.
 120
 121         \item Stability of performance under translation and scaling.
 122
 123         We will measure performance during the process of a steady zoom or translation at a predetermined rate. This should allow us to identify ``spikes'' of
 124         low performance on implementations which require a calculation (such as renormalisation) periodically. Measured in ${ms}/{frame}$.
 125 \end{itemize}
 126
 127 To accompany this, we will also be comparing the generated output from each implementation to find any discrepancies or artefacts introduced by the implementation,
 128 as well as to demonstrate the improvement in precision compared to the basic implementation. Should time permit, we would also like to demonstrate stability of the document
 129 under transformations (zooms and translations).
 130
 131 We intend to rasterize objects on the \ac{GPU} in order to take advantage of the extra performance this provides.
 132 There is copious existing research on rendering gemetric shapes such as B\'ezier curves\cite{loop2005resolution} on the \ac{GPU},
 133 and indeed entire implementations of the postscript rendering model\cite{nilsson2004glitz}\cite{kilgard2012gpu}.
 134 We therefore believe that this will allow us to better focus on the performance of the infinite-precision document
 135 structures, whose calculations will likely largely reside on the \ac{CPU}.
 136
 137 \section{Timeline}
 138 \begin{center}
 139 \begin{tabular}{l| p{8cm}}
 140 \textbf{Date} & \textbf{Milestone}  \\
 141 \hline
 142 17th April & Draft Literature Review due. \\
 143 \hline
 144 1st May & A simple document format should be designed and implemented, upon which to base further development and experiments.\\
 145 \hline
 146 22nd May & Literature Review and Revised Proposal due.\\
 147 \hline
 148 9th June & Demonstrated and documented artefacts and instability caused by floating point imprecision in the basic implementation.\\
 149 \hline
 150 1st July & Have one or more algorithms/data structures for handling infinite-precision documents implemented.\\
 151 \hline
 152 1st August & Initial performance measurements complete. Identified areas for further optimisation and experimentation.\\
 153 \hline
 154 1st September & Adjustments to existing systems and experiments with additional techniques performed, and performance measured. Work underway on dissertation.\\
 155 \hline
 156 18th September & Draft dissertation due. \\
 157 \hline
 158 23rd October & Final dissertation due. \\
 159 \hline
 160 27th -- 31st October & Seminar presentation. \\
 161 \hline
 162 \end{tabular}
 163 \end{center}
 164
 165 \section{Software \& Hardware Requirements}
 166 We intend to develop this system on a common \texttt{x86} compatible Personal Computer running the \texttt{Linux\textregistered} operating system,
 167 using the \texttt{C++} programming language and making use of the \texttt{OpenGL} graphics library.
 168 However, the techniques we develop will likely also be applicable --- or be easily extended --- to other desktop and mobile systems.
 169 We also hope that the prototype developed will be portable to other systems.
 170
 171
 172 \bibliography{papers.bib}{}
 173 \bibliographystyle{plain}
 174
 175 \end{document}