David's lit notes, LaTeXiFiEd
[ipdf/documents.git] / 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}

UCC git Repository :: git.ucc.asn.au