From: David Gow Date: Mon, 19 May 2014 01:25:47 +0000 (+0800) Subject: Some stuff I learnt in maths that isn't relevant X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=commitdiff_plain;h=3195edda12155345b3d0376f97a34e0a3a0ba8ad Some stuff I learnt in maths that isn't relevant --- diff --git a/LitReviewDavid.pdf b/LitReviewDavid.pdf index 81a0594..4949e4d 100644 Binary files a/LitReviewDavid.pdf and b/LitReviewDavid.pdf differ diff --git a/LitReviewDavid.tex b/LitReviewDavid.tex index b6e75cc..532017b 100644 --- a/LitReviewDavid.tex +++ b/LitReviewDavid.tex @@ -2,6 +2,7 @@ \usepackage[utf8]{inputenc} \usepackage{hyperref} \usepackage{graphicx} +\usepackage{amsmath} %opening \title{Literature Review} @@ -36,6 +37,15 @@ Ultimately, there are two fundamental stages by which all documents --- digital \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. +Different document formats approach these stages in different ways. Some treat the document as a program, written in +a turing complete document language with instructions which emit shapes to be displayed. These shapes are either displayed +immediately, as in PostScript, or stored in another file, such as with \TeX or \LaTeX, which emit a \texttt{DVI} file. Most other +forms of document use a \emph{Document Object Model}, being a list or tree of objects to be rendered. \texttt{DVI}, \texttt{PDF}, +\texttt{HTML}\footnote{Some of these formats --- most notably \texttt{HTML} --- implement a scripting lanugage such as JavaScript, +which permit the DOM to be modified while the document is being viewed.} and SVG. Of these, only \texttt{HTML} and \TeX typically +store documents in pre-layout stages, whereas even turing complete document formats such as PostScript typically encode documents +which already have their elements placed. + 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 @@ -44,13 +54,19 @@ to issues with numeric precision. \section{Rendering} -Computer graphics comes in two forms: bit-mapped (or raster) graphics, which is defined by an array of pixel colours, +Computer graphics comes in two forms: bit-mapped (or raster) graphics, which is defined by an array of pixel colours; and \emph{vector} graphics, defined by mathematical descriptions of objects. Bit-mapped graphics are well suited to photographs and are match how cameras, printers and monitors work. However, bitmap devices do not handle zooming beyond their ``native'' resolution --- the resolution where one document pixel maps to one display pixel ---, exhibiting an artefact called pixelation where the pixel structure becomes evident. Attempts to use interpolation to hide this effect are never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly effected. +\begin{figure}[h] + \centering \includegraphics[width=0.8\linewidth]{figures/vectorraster_example} + \caption{A circle as a vector image and a $32 \times 32$ pixel raster image} +\end{figure} + + Vector graphics lack many of these problems: the representation is independent of the output resolution, and rather an abstract description of what it is being rendered, typically as a combination of simple geometric shapes like lines, arcs and ``B\'ezier curves''. @@ -89,7 +105,16 @@ between $0$ and $2^{64} - 1$\footnote{Most machines also support \emph{signed} i 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: +By introducing a fractional component (analogous to a decimal point), we can convert +integers to \emph{fixed-point} numbers, which have a more limited range, but a fixed, greater +precision. For example, a number in 4.4 fixed-point format would have four bits representing the integer +component, and four bits representing the fractional component: +\begin{equation} + \underbrace{0101}_\text{integer component}.\underbrace{1100}_\text{fractional component} = 5.75 +\end{equation} + + +Floating-point numbers\cite{goldberg1992thedesign} 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 \begin{equation} n = 2^{e} \times m @@ -98,14 +123,21 @@ each number consisting of an exponent ($e$) and a mantissa ($m$) such that a num The IEEE 754 standard\cite{ieee754std1985} defines several floating-point data types which are used\footnote{Many systems' implement the IEEE 754 standard's storage formats, but do not implement arithmetic operations in accordance with this standard.} by most -computer systems. The standard defines 32-bit (8-bit exponent, 23-bit mantissa) and -64-bit (11-bit exponent, 53-bit mantissa) formats\footnote{The 2008 +computer systems. The standard defines 32-bit (8-bit exponent, 23-bit mantissa, 1 sign bit) and +64-bit (11-bit exponent, 53-bit mantissa, 1 sign bit) formats\footnote{The 2008 revision to this standard\cite{ieee754std2008} adds some additional formats, but is -less widely supported in hardware.} - -How floating-point works and what its behaviour is w/r/t range and precision -\cite{goldberg1991whatevery} -\cite{goldberg1992thedesign} +less widely supported in hardware.}, which can store approximately 7 and 15 decimal digits +of precision respectively. + +Floating-point numbers behave quite differently to integers or fixed-point numbers, as +the representable numbers are not evenly distributed. Large numbers are stored to a lesser +precision than numbers close to zero. This can present problems in documents when zooming in +on objects far from the origin. + +IEEE floating-point has some interesting features as well, including values for negative zero, +positive and negative infinity and the ``Not a Number'' (NaN) value. Indeed, with these values, +IEEE 754 floating-point equality does not form an equivalence relation, which can cause issues +when not considered carefully.\cite{goldberg1991whatevery} Arb. precision exists diff --git a/figures/vectorraster_example.pdf b/figures/vectorraster_example.pdf new file mode 100644 index 0000000..5c36695 Binary files /dev/null and b/figures/vectorraster_example.pdf differ diff --git a/papers.bib b/papers.bib index 8cd94c7..c735181 100644 --- a/papers.bib +++ b/papers.bib @@ -25,7 +25,7 @@ @inproceedings{porter1984compositing, title={Compositing digital images}, author={Porter, Thomas and Duff, Tom}, - booktitle={ACM Siggraph Computer Graphics}, + booktitle={ACM SIGGRAPH Computer Graphics}, volume={18}, number={3}, pages={253--259},