\documentclass[a4paper,10pt]{article}
%\documentclass[a4paper,10pt]{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usepackage{acronym}
\usepackage{amsmath}
\usepackage{amssymb}

\acrodef{CAD}[CAD]{Computer-Aided Drafting}
\acrodef{BIM}{Building Information Modelling}
\acrodef{SKA}{Square Kilometre Array}
\acrodef{CPU}{Central Processing Unit}
\acrodef{GPU}{Graphics Processing Unit}

\title{Research Project Proposal}
\author{David Gow\\
20513684}
\date{March 12, 2014} %Today

\pdfinfo{
  /Title    (Project Proposal: Infinite-precision Documents)
  /Author   (David Gow)
  /Creator  (A Guy who knows about document formats, yo!)
  /Producer (Steven Spielberg)
  /Subject  (Fractal Document Formats)
  /Keywords (document, project, proposal, vector, fractal, precision, floating-point)
}

\begin{document}
\maketitle\hrule
\begin{center}
\begin{tabular}{lp{0.8\textwidth}}
\textbf{Title:} & Infinite-precision document formats\\
\textbf{Supervisor} & A/Prof. Tim French\\
\textbf{Project Group:} & David Gow, Samuel Moore
\end{tabular}
\end{center}
\section{Background}
%Since computers first displaced the typewriter, they've been used to manipulate documents: storing them, creating them, viewing them and printing them.
%However, the nature of this use has changed significantly. Existing document formats, such as PDF and PostScript, were designed to mirror paper documents, and
%were originally implemented as storage for documents to be printed. They are therefore

Traditional document formats such as PDF and Postscript were designed for
documents to be printed. They therefore are optimised to rasterize an entire
page at a given resolution, often on the embedded processor found in (older)
printers. This, however, does not fit well with interactive display on screens,
particularly on mobile devices such as telephones and tablets.

In particular, when displaying a document on a screen, the user has several additional
ways of interacting with the document, such as viewing a subset of the document in high
resolution using the ``zoom'' option. 

Existing vector file formats do support rasterization at different resolutions, but are limited
by the precision of coordinates and other intermediate values. PostScript and PDF, for example,
store many values in a \emph{real} type with a limit of approximately 8 decimal digits of precision
(PostScript\cite{plrm}) or 5 decimal digits of precision (PDF\cite{pdfref17}). These floating-point data
types, while they provide both range (allowing for large documents) and precision (allowing for fine detail),
cannot combine the two\cite{goldberg91whatevery}. It follows that objects placed further from the origin must
have less detail. Furthermore, these numerical datatypes have a limited range and therefore have an absolute
limit on the size or precision of any document.

Documents with high --- or at least consistent --- levels of precision have many applications.
The building industry uses tools such as \ac{CAD} and \ac{BIM} systems for managing schematics which
require precision. At the moment, this requires special tools, and it is not possible to export these as
a single view without loss of precision. Similarly, infinite precision document formats would allow maps
covering large areas to be stored contiguously (without requiring plates at different zoom levels) without
any loss of precision.

\section{Aim}

We aim to prototype a simple document system which does not have these restrictions on zoom,
and which can store data precisely at a given level of zoom. While the primary goal is to ensure
the objects within documents retain the precision at which they were created (typically being the
resolution of the display used during document editing), an ideal approach would also ensure stability
of the object when magnified beyond its original size.

Should this be successful, we will prototype different methods of implementing this system,
using different data structures, to compare their relative merits in terms of --- amongst
other things --- performance. In particular, we hope to avoid some of the performance issues
resulting from traditional use of arbitrary-precision data types, particularly on the \ac{GPU}\cite{emmart2010high}.

As this is a group project each group member will develop and prototype a different method of
retaining precision. For \emph{this} individual part of the project, quadtrees will be investigated to provide a form of coordinate
system renormalisation as the document view is scaled.

These systems will be compared in terms of their performance, with the aim to identify in which situations each implementation
is most performant, consistent and correct.

\section{Method}
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.
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
and algorithms for infinite-precision.

Initially, this document system will support documents consisting only of basic shapes (such as polygons, circles and B\'ezier curves),
but, should time allow, this can be extended to include font glyphs, embedded raster images and other objects.


We will be comparing these methods primarily in terms of performance using a number of metrics:
\begin{itemize}
	\item Performance per document object.
	
	As objects are the basis of these documents, we will test against a set of ``standardised'' documents with
	to determine how performance scales with the number of objects. We will test this with each of the different
	types (or shapes) of objects, as they may have different performance characteristics. Measured in ${ms}/{object}$
	
	\item Performance per visible object.
	
	As above, but measuring performance against the number of objects visible in a given view. For example, when zoomed in, fewer
	objects will be onscreen, and so --- in some implementations --- may not contribute as heavily to the computational load.
	
	Similarly measured in ${ms}/{object}$.
	
	\item Performance per zoom level.
	
	Time taken to render frames with the same number of visible objects will be compared at different zoom levels to determine if there is
	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
	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
	global document coordinates.
	
	\item Stability of performance under translation and scaling.
	
	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
	low performance on implementations which require a calculation (such as renormalisation) periodically. Measured in ${ms}/{frame}$.
\end{itemize}

To accompany this, we will also be comparing the generated output from each implementation to find any discrepancies or artefacts introduced by the implementation,
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
under transformations (zooms and translations).

We intend to rasterize objects on the \ac{GPU} in order to take advantage of the extra performance this provides.
There is copious existing research on rendering gemetric shapes such as B\'ezier curves\cite{loop2005resolution} on the \ac{GPU},
and indeed entire implementations of the postscript rendering model\cite{nilsson2004glitz}\cite{kilgard2012gpu}.
We therefore believe that this will allow us to better focus on the performance of the infinite-precision document
structures, whose calculations will likely largely reside on the \ac{CPU}.

\section{Timeline}
\begin{center}
\begin{tabular}{l| p{8cm}}
\textbf{Date} & \textbf{Milestone}  \\
\hline
17th April & Draft Literature Review due. \\
\hline
1st May & A simple document format should be designed and implemented, upon which to base further development and experiments.\\
\hline
22nd May & Literature Review and Revised Proposal due.\\
\hline
9th June & Demonstrated and documented artefacts and instability caused by floating point imprecision in the basic implementation.\\
\hline
1st July & Have one or more algorithms/data structures for handling infinite-precision documents implemented.\\
\hline
1st August & Initial performance measurements complete. Identified areas for further optimisation and experimentation.\\
\hline
1st September & Adjustments to existing systems and experiments with additional techniques performed, and performance measured. Work underway on dissertation.\\
\hline
18th September & Draft dissertation due. \\
\hline
23rd October & Final dissertation due. \\
\hline
27th -- 31st October & Seminar presentation. \\
\hline
\end{tabular}
\end{center}

\section{Software \& Hardware Requirements}
We intend to develop this system on a common \texttt{x86} compatible Personal Computer running the \texttt{Linux\textregistered} operating system,
using the \texttt{C++} programming language and making use of the \texttt{OpenGL} graphics library.
However, the techniques we develop will likely also be applicable --- or be easily extended --- to other desktop and mobile systems.
We also hope that the prototype developed will be portable to other systems.


\bibliography{papers.bib}{}
\bibliographystyle{plain}

\end{document}
