author David Gow Tue, 21 Oct 2014 06:56:50 +0000 (14:56 +0800) committer David Gow Tue, 21 Oct 2014 06:56:50 +0000 (14:56 +0800)
 DavidSeminarAbstract [new file with mode: 0644] patch | blob cshonours.cls [new file with mode: 0644] patch | blob davidfinal.pdf [new file with mode: 0644] patch | blob davidfinal.tex [new file with mode: 0644] patch | blob papers.bib patch | blob | history

diff --git a/DavidSeminarAbstract b/DavidSeminarAbstract
new file mode 100644 (file)
index 0000000..17cceb3
--- /dev/null
@@ -0,0 +1,17 @@
+Precision in vector documents: a spatial approach
+
+Despite being scalable, vector images are typically specified and manipulated
+with fixed-precision numbers. Existing formats therefore are unable to store
+documents which need greater precision, and existing viewers perform coordinate
+system transforms at a fixed precision, limiting the amount any document may be
+"zoomed".
+
+Using existing arbitrary-precision numeric types can resolve these issues, but
+often at a significant or infeasible performance penalty. By taking into
+account the spatial nature of the data, we can store and view documents to an
+arbitrary precision with little-to-no performance impact. This is achieved by
+clipping the document's constituent Bézier paths to nodes in a quadtree.
+
+We'll discuss the artefacts caused by low-precision, the theory and
+implementation of our quadtree-based format and some remaining issues and future
+possibilities with the technique.
diff --git a/cshonours.cls b/cshonours.cls
new file mode 100644 (file)
index 0000000..c2e0638
--- /dev/null
@@ -0,0 +1,798 @@
+%%
+%% This is file cshonours.cls' modified by Cara MacNish from
+%% report.cls', August 1999.
+%% It is described in more detail in the accompanying example
+%% document, cshonours.tex'.
+%%
+%% The following refers to the original report.cls.
+%% The original source files were:
+%%
+%% classes.dtx  (with options: report')
+%%
+%% This is a generated file.
+%%
+%% Copyright 1993 1994 1995 1996 1997 1998 1999
+%% The LaTeX3 Project and any individual authors listed elsewhere
+%% in this file.
+%%
+%% This file is part of the LaTeX2e system.
+%% ----------------------------------------
+%%
+%% It may be distributed under the terms of the LaTeX Project Public
+%% License, as described in lppl.txt in the base LaTeX distribution.
+%% Either version 1.0 or, at your option, any later version.
+%% \CharacterTable
+%%  {Upper-case    \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
+%%   Lower-case    \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
+%%   Digits        \0\1\2\3\4\5\6\7\8\9
+%%   Exclamation   \!     Double quote  \"     Hash (number) \#
+we ensure that the first and last coefficients have the endpoints' coodinates, and therefore
+
+{\bf TODO: Prove that the other control points' magnitude is reduced, and try to quantify it, prove that
+it will never overflow.}
+
+\section{Implementation Details}
+\begin{itemize}
+       \item Store object ID ranges.
+       \item Pointers to children and parent.
+       \item Linked-list of overlay'' nodes for mutation.
+       \item Have billions of bugs.
+\end{itemize}
+
+
+
+\chapter{Experimental Results}
+These are all iPython-y at the moment.
+
+Roughly 3s/frame for GMP rationals, 16ms for Quadtree which is still slightly broken.
+\section{Performance per object}
+
+\section{Performance per onscreen object}
+
+\section{Performance per zoom-level}
+
+\section{Stability of performance}
+
+\chapter{Further Work and Conclusion}
+The use of spatial data structures to specify documents with arbitrary precision
+has been validated as a viable alternative to the use of arbitrary precision numeric
+types where an arbitrary (rather than infinite) amount of precision is needed.
+Once constructed, they are faster in many circumstanced, and the structure
+can also be used for culling. When the viewport moves and scales smoothly, the cost
+of constructing new nodes is amortised over the movement.
+Unfortunately, the mutation of the quadtree is difficult and slow, and discontinuous
+movement can result in a large number of nodes needing to be created.
+
+Quadtree seems to be viable and is really performant.
+
+
+
+\bibliography{papers}
+
+\end{document}
index 362dedf..e6302ae 100644 (file)
@@ -1147,3 +1147,77 @@ ISSN={0164-1239},}
pages = 69,
doi = "10.1016/S1571-0661(05)80215-4"
}
+
+
+% XKCD comic "pixels"
+@misc{munroe2014pixels,
+author={Munroe, Randall},
+title={Pixels},
+url={http://xkcd.com/1416},
+howpublished={\url{http://xkcd.com/1416/} accessed 2014-09-03},
+journal={xkcd: A webcomic of romance, sarcasm, math, and language.}
+year={2014},
+month={September},
+day={3},
+date={2014-09-03},
+number={1416}
+}
+
+author={Kessenich, John},
+year={2010},
+}
+
+@article{intelgpuspec,
+author={Intel Corporation},
+title={{3D/Media --- 3D Pipeline (Ivy Bridge)}},
+journal={{Intel OpenSource HD Graphics Programmer's Reference Manual (PRM)}},
+year={2012},
+url={https://01.org/linuxgraphics/sites/default/files/documentation/ivb_ihd_os_vol2_part1.pdf},
+volume={2},
+number={1}
+}
+
+@misc{dawson2012notnormal,
+author={Dawson, Bruce},
+title={{That's Not Normal --- the Performance of Odd Floats}},
+year={2012},
+howpublished={\url{https://randomascii.wordpress.com/2012/05/20/thats-not-normalthe-performance-of-odd-floats/} accessed 2014-10-18}
+}
+
+# Original cubic solution
+@misc{cardano1545artis,
+author={Cardano, Gerolamo},
+title={Artis magnae sive de regulis agebraicis: liber unus},
+year={1545}
+}
+
+author={Sederberg, T. W.},
+title={Computer Aided Geometric Design Course Notes},
+year={2007}
+}
+
+@book{salomon2007data,
+  title={Data Compression: The Complete Reference},
+  author={Salomon, D. and Motta, G. and Bryant, D.},
+  isbn={9781846286032},
+  lccn={2006931789},
+  series={Molecular biology intelligence unit},
+  year={2007},
+  publisher={Springer}
+}
+
+@book{taocp2,
+       title={Seminumerical Algorithms},
+       author={Knuth, Donald},
+       year={1998},
+       volume={2},
+       series={The Art of Computer Programming},