X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LitReviewDavid.tex;h=a8947e81f22fde0379904455a9611aeeefc4a6b3;hp=b6e75cc90731faa24632505ad674987fc813fcaf;hb=2ec4f0eb657af1dc4314b1ec99216d7c20595229;hpb=f7fbe7987c6bb67c1b85741426dff5c8ce54edd8;ds=sidebyside diff --git a/LitReviewDavid.tex b/LitReviewDavid.tex index b6e75cc..a8947e8 100644 --- a/LitReviewDavid.tex +++ b/LitReviewDavid.tex @@ -2,6 +2,8 @@ \usepackage[utf8]{inputenc} \usepackage{hyperref} \usepackage{graphicx} +\usepackage{amsmath} +\usepackage{amssymb} %opening \title{Literature Review} @@ -36,6 +38,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\cite{svg2011-1.1}. 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,12 +55,18 @@ 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. +never entirely successful, and sharp edges, such as those found in text and diagrams, are particularly affected. + +\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, @@ -80,7 +97,7 @@ the Cairo\cite{worth2003xr} library, based around the PostScript/PDF rendering m renderer by nVidia\cite{kilgard2012gpu} as an OpenGL extension\cite{kilgard300programming}. -\section{Floating-Point Precision} +\section{Numeric formats} On modern computer architectures, there are two basic number formats supported: fixed-width integers and \emph{floating-point} numbers. Typically, computers @@ -89,7 +106,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,17 +124,39 @@ 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, the ``Not a Number'' (NaN) value and \emph{denormal} values, which +trade precision for range when dealing with very small numbers. 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} + +There also exist formats for storing numbers with arbitrary precising and/or range. +Some programming languages support ``big integer''\cite{java_bigint} types which can +represent any integer that can fit in the system's memory. Similarly, there are +arbitrary-precision floating-point data types\cite{java_bigdecimal}\cite{boost_multiprecision} +which can represent any number of the form +\begin{equation} + \frac{n}{2^d} \; \; \; \; n,d \in \mathbb{Z} % This spacing is horrible, and I should be ashamed. +\end{equation} +These types are typically built from several native data types such as integers and floats, +paired with custom routines implementing arithmetic primitives.\cite{priest1991algorithms} +These, therefore, are likely slower than the native types they are built on. -Arb. precision exists +While traditionally, GPUs have supported some approximation of IEEE 754's 32-bit floats, +modern graphics processors also support 16-bit\cite{nv_half_float} and 64-bit\cite{arb_gpu_shader_fp64} +IEEE floats. Higher precision numeric types can be implemented or used on the GPU, but are slow. \cite{emmart2010high}