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