From: David Gow Date: Sun, 18 May 2014 23:35:53 +0000 (+0800) Subject: Eyelids drooping, neurons not quite firing. X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=commitdiff_plain;h=f7fbe7987c6bb67c1b85741426dff5c8ce54edd8;ds=sidebyside Eyelids drooping, neurons not quite firing. --- diff --git a/LitReviewDavid.pdf b/LitReviewDavid.pdf index f3510f8..81a0594 100644 Binary files a/LitReviewDavid.pdf and b/LitReviewDavid.pdf differ diff --git a/LitReviewDavid.tex b/LitReviewDavid.tex index edd8b2b..b6e75cc 100644 --- a/LitReviewDavid.tex +++ b/LitReviewDavid.tex @@ -32,6 +32,10 @@ the content of the document to be explored in ways that perhaps the author had n However, these data-driven formats typically do not support fixed layouts, and the display differs from renderer to renderer. +Ultimately, there are two fundamental stages by which all documents --- digital or otherwise --- are produced and displayed: +\emph{layout} and \emph{display}. The \emph{layout} stage is where the positions and sizes of text and other graphics are +determined, while the \emph{display} stage actually produces the final output, whether as ink on paper or pixels on a computer monitor. + Existing document formats, due to being designed to model paper, have limited precision (8 decimal digits for PostScript\cite{plrm}, 5 decimal digits for PDF\cite{pdfref17}). This matches the limited resolution of printers and ink, but is limited when compared to what aught to be possible @@ -86,7 +90,7 @@ which have the same cardinality as their \emph{unsigned} counterparts, but which represent integers between $-(2^{63})$ and $2^{63} - 1$}. Floating-point numbers\cite{goldberg1991whatevery} are the binary equivalent of scientific notation: -each number consisting of an exponent ($e$) and a mantissa $(m)$ such that a number is given by +each number consisting of an exponent ($e$) and a mantissa ($m$) such that a number is given by \begin{equation} n = 2^{e} \times m \end{equation} @@ -112,13 +116,31 @@ slow. \section{Quadtrees} -The quadtree is a data structure which keeps -\cite{finkel1974quad} +When viewing or processing a small part of a large document, it may be helpful to +only processs --- or \emph{cull} --- parts of the document which are not on-screen. \begin{figure}[h] - \includegraphics[width=0.4\linewidth]{figures/quadtree_example} + \centering \includegraphics[width=0.4\linewidth]{figures/quadtree_example} + \caption{A simple quadtree.} \end{figure} - +The quadtree\cite{finkel1974quad}is a data structure --- one of a family of \emph{spatial} +data structures --- which recursively breaks down space into smaller subregions +which can be processed independently. Points (or other objects) are added to a single +node, which if certain criteria are met --- typically the number of points in a node +exceeding a maximum, though in our case likely the level of precision required exceeding +that supported by the data type in use --- is split into four equal-sized subregions, and +points attached to the region which contains them. + +In this project, we will be experimenting with a form of quadtree in which each +node has its own independent coordinate system, allowing us to store some spatial +information\footnote{One bit per-coordinate, per-level of the quadtree} within the +quadtree structure, eliminating redundancy in the coordinates of nearby objects. + +Other spatial data structures exist, such as the KD-tree\cite{bentley1975multidimensional}, +which partitions the space on any axis-aligned line; or the BSP tree\cite{fuchs1980onvisible}, +which splits along an arbitrary line which need not be axis aligned. We believe, however, +that the simpler conversion from binary coordinates to the quadtree's binary split make +it a better avenue for initial research to explore. \bibliographystyle{unsrt} \bibliography{papers} diff --git a/papers.bib b/papers.bib index 4796a0b..8cd94c7 100644 --- a/papers.bib +++ b/papers.bib @@ -306,6 +306,45 @@ Goldberg:1991:CSK:103162.103163, publisher={Springer} } +%BSP trees +@inproceedings{fuchs1980onvisible, + author = {Fuchs, Henry and Kedem, Zvi M. and Naylor, Bruce F.}, + title = {On Visible Surface Generation by a Priori Tree Structures}, + booktitle = {Proceedings of the 7th Annual Conference on Computer Graphics and Interactive Techniques}, + series = {SIGGRAPH '80}, + year = {1980}, + isbn = {0-89791-021-4}, + location = {Seattle, Washington, USA}, + pages = {124--133}, + numpages = {10}, + url = {http://doi.acm.org/10.1145/800250.807481}, + doi = {10.1145/800250.807481}, + acmid = {807481}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +% KD-tree paper +@article{bentley1975multidimensional, + author = {Bentley, Jon Louis}, + title = {Multidimensional Binary Search Trees Used for Associative Searching}, + journal = {Commun. ACM}, + issue_date = {Sept. 1975}, + volume = {18}, + number = {9}, + month = sep, + year = {1975}, + issn = {0001-0782}, + pages = {509--517}, + numpages = {9}, + url = {http://doi.acm.org/10.1145/361002.361007}, + doi = {10.1145/361002.361007}, + acmid = {361007}, + publisher = {ACM}, + address = {New York, NY, USA}, + keywords = {associative retrieval, attribute, binary search trees, binary tree insertion, information retrieval system, intersection queries, key, nearest neighbor queries, partial match queries}, +} + % Basic overview of PDF and how it is awesome. % This doesn't seem like a major revelation for 2002 diff --git a/references/bentley1975multidimensional.pdf b/references/bentley1975multidimensional.pdf new file mode 100644 index 0000000..953e49a Binary files /dev/null and b/references/bentley1975multidimensional.pdf differ diff --git a/references/fuchs1980onvisible.pdf b/references/fuchs1980onvisible.pdf new file mode 100644 index 0000000..7ccb541 Binary files /dev/null and b/references/fuchs1980onvisible.pdf differ