Boost Multiprecision Library
[ipdf/documents.git] / ProjectProposalSam.tex
1 \documentclass[12pt]{article}
2 \usepackage{graphicx}
3 \usepackage{caption}
4 \usepackage{amsmath} % needed for math align
5 \usepackage{bm} % needed for maths bold face
6  \usepackage{graphicx}    % needed for including graphics e.g. EPS, PS
7 \usepackage{fancyhdr}   % needed for header
8
9 \usepackage{hyperref}
10
11  \topmargin -1.5cm        % read Lamport p.163
12  \oddsidemargin -0.04cm   % read Lamport p.163
13  \evensidemargin -0.04cm  % same as oddsidemargin but for left-hand pages
14  \textwidth 16.59cm
15  \textheight 21.94cm 
16  %\pagestyle{empty}       % Uncomment if don't want page numbers
17  \parskip 8.2pt           % sets spacing between paragraphs
18  %\renewcommand{\baselinestretch}{1.5}  % Uncomment for 1.5 spacing between lines
19  %\parindent 0pt                  % sets leading space for paragraphs
20
21
22 \newcommand{\vect}[1]{\boldsymbol{#1}} % Draw a vector
23 \newcommand{\divg}[1]{\nabla \cdot #1} % divergence
24 \newcommand{\curl}[1]{\nabla \times #1} % curl
25 \newcommand{\grad}[1]{\nabla #1} %gradient
26 \newcommand{\pd}[3][ ]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} %partial derivative
27 %\newcommand{\d}[3][ ]{\frac{d^{#1} #2}{d #3^{#1}}} %full derivative
28 \newcommand{\phasor}[1]{\tilde{#1}} % make a phasor
29 \newcommand{\laplacian}[1]{\nabla^2 {#1}} % The laplacian operator
30
31 \usepackage{color}
32 \usepackage{listings}
33
34 \definecolor{darkgray}{rgb}{0.95,0.95,0.95}
35 \definecolor{darkred}{rgb}{0.75,0,0}
36 \definecolor{darkblue}{rgb}{0,0,0.75}
37 \definecolor{pink}{rgb}{1,0.5,0.5}
38 \lstset{language=Java}
39 \lstset{backgroundcolor=\color{darkgray}}
40 \lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt}
41 \lstset{keywordstyle=\color{darkred}\bfseries}
42 \lstset{commentstyle=\color{darkblue}}
43 %\lstset{stringsyle=\color{red}}
44 \lstset{showstringspaces=false}
45 \lstset{basicstyle=\small}
46
47
48 \begin{document}
49
50 \pagestyle{fancy}
51 \fancyhead{}
52 \fancyfoot{}
53
54 \fancyhead[LO, L]{}
55 \fancyfoot[CO, C]{\thepage}
56
57 \begin{center}
58         B.Eng. Final Year Project \par
59         {\bf \Large Research Proposal} \par
60         Sam Moore \\
61         Faculty of Engineering, Computing and Mathematics, University of Western Australia \\
62         March 2014
63 \end{center}
64
65 \section*{Infinite Precision Document Formats}
66 {\bf \emph{Keywords:} fractals, arbitrary precision, vector graphics, postscript, pdf, OpenGL} \\
67 {\bf \emph{Superviser:}} Prof. Tim French (UWA) \\
68 {\bf \emph{Team Members:}}  \underline{Sam Moore} (Mechatronics Eng), David Gow (Software Eng)\cite{proposalGow} \\
69
70
71 %\tableofcontents
72
73 \section{Background}
74
75 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
76 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. 
77
78 The emergence of the internet, web browsers, XML/HTML and related technologies has seen a revolution in the ways in which information can be presented digitally, and the PDF standard itself has moved well beyond static text and figures\cite{hayes2012pixels, barnes2013embedding} but all modern document formats are still designed with the intention of showing information at a single, fixed level of detail.
79
80
81 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}.
82
83 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.
84
85
86 \section{Aim}
87
88 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.
89 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. 
90
91 The goal is to be able to render a primitive at the same level of detail it is specified. For example, the coordinates of primitives drawn in a graphical editor will be limited by the resolution of the display on which they are drawn, but not by the viewer.
92
93 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; digital artwork; computer aided design; and maps.
94    
95 \section{Methods}
96
97 Initial research and software development will be 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). 
98
99
100 At this stage we have identified two possible areas for individual research:
101
102 \begin{enumerate}
103
104         \item {\bf Arbitrary Precision real valued numbers} --- Sam Moore
105
106         We plan to investigate algorithms related to the representation of real values to an arbitary degree of precision. This would allow for a document to be represented
107         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.
108         We will also need to consider limitations imposed by performing calculations on the GPU or CPU.
109
110         Possible 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}.
111
112
113
114         \item {\bf Local coordinate systems} --- David Gow \cite{proposalGow}
115         
116         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.
117
118 \end{enumerate}
119 \pagebreak
120 We aim to compare these and any additional implementations considered using the following metrics:
121 \begin{enumerate}
122
123         \item {\bf Performance vs Number of Primitives}
124
125         As it is clearly desirable to include more objects in a document, this is a natural metric for the usefulness of an implementation.
126         We will compare the performance of rendering different implementations, using several ``standard'' test documents.
127         
128         \item {\bf Performance vs Visible Primitives}
129
130         There will inevitably be an overhead to all primitives in the document, whether drawn or not.
131         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. 
132         
133         
134         \item {\bf Performance vs Zoom Level}
135
136         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.
137
138         \item {\bf Performance whilst translation and scaling}
139
140         Whilst changing the view, it is ideal that the document be re-rendered as efficiently as possible, to avoid disorienting and confusing the user.
141         We will therefore compare the speed of rendering as the standard documents are translated or scaled at a constant rate.
142
143         \item {\bf Artifacts and Limitations on Precision}
144
145         As we are unlikely to achieve truly ``infinite'' precision, qualitative comparisons of the accuracy of rendering under different implementations should be made.
146
147 \end{enumerate}
148
149 \section{Software and Hardware Requirements}
150
151 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.
152
153
154 \pagebreak
155
156 \section{Timeline}
157
158 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}.
159
160 \begin{center}
161 \begin{tabular}{l|p{0.5\textwidth}}
162         {\bf Date} & {\bf Milestone}\\
163         \hline
164         $17^{\text{th}}$ April & Draft Literature Review completed.\\
165         \hline
166         $1^{\text{st}}$ May & Testbed Software (basic document format and viewer) completed and approaches for extending to allow infinite precision identified. \\
167         \hline
168         $26^{\text{th}}$ May & \emph{Progress Report and Revised Literature Review due.}\\
169         \hline
170         $9^{\text{th}}$ June & Demonstrations of limitations of floating point precision in the Testbed software. \\
171         $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. \\
172         \hline
173         $1^{\text{st}}$ August & Experiments and comparison of various infinite precision implementations completed. \\
174         \hline
175         $1^{\text{st}}$ September & Advanced features implemented and tested, work underway on Final Report. \\
176         \hline
177         TBA & \emph{Conference Abstract and Presentation due.} \\
178         \hline
179         $10^{\text{th}}$ October & \emph{Draft of Final Report due.} \\
180         \hline
181         $27^{\text{th}}$ October & \emph{Final Report due.}\\
182         \hline
183 \end{tabular}
184 \end{center}
185
186 \pagebreak
187 \bibliographystyle{unsrt}
188 \bibliography{papers}
189
190 This proposal also available at: \\ \url{http://szmoore.net/ipdf/documents/ProjectProposalSam.pdf}.
191
192 \end{document}
193

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