\section{Raster and Vector Images}\label{Raster and Vector Images}
\input{chapters/Background_Raster-vs-Vector}
-\section{Rasterising Vector Images}\label{Rasterising Vector Images}
-
-Throughout Section \ref{vector-vs-raster-graphics} we were careful to refer to ``modern'' display devices, which are raster based. It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}.
+\section{Rendering Vector Images}\label{Rasterising Vector Images}
Hearn and Baker's textbook ``Computer Graphics''\cite{computergraphics2} gives a comprehensive overview of graphics from physical display technologies through fundamental drawing algorithms to popular graphics APIs. This section will examine algorithms for drawing two dimensional geometric primitives on raster displays as discussed in ``Computer Graphics'' and the relevant literature. Informal tutorials are abundant on the internet\cite{elias2000graphics}. This section is by no means a comprehensive survey of the literature but intends to provide some idea of the computations which are required to render a document.
-\subsection{Straight Lines}\label{Straight Lines}
+It is of some historical significance that vector display devices were popular during the 70s and 80s, and papers oriented towards drawing on these devices can be found\cite{brassel1979analgorithm}. Whilst curves can be drawn at high resolution on vector displays, a major disadvantage was shading; by the early 90s the vast majority of computer displays were raster based\cite{computergraphics2}.
+
+\subsection{Straight Lines}\label{Rasterising Straight Lines}
\input{chapters/Background_Lines}
\subsection{Spline Curves}\label{Spline Curves}
y(x) &= \displaystyle\sum_{k=0}^n a_k x^k
\end{align}
+Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and rendering straight lines between $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}.
-A straight line is simply a polynomial of $0$th degree. Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and rendering straight lines between $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}. More direct algorithms for drawing splines based upon Brasenham and Wu's algorithms also exist\cite{citationneeded}.
-
-There are many different ways to define a spline. One approach is to specify ``knots'' on the spline and solve for the cooefficients to generate a cubic spline ($n = 3$) passing through the points. Alternatively, special polynomials may be defined using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors. For example, drawing bezier curves with the mouse is the primary method of constructing paths in the Inkscape SVG editor\cite{inkscape}.
+There are many different ways to define a spline. One approach is to specify ``knots'' on the curve and choosing a fixed $n$ ($n = 3$ for ``cubic'' splines) solve for the cooefficients to generate polynomials passing through the points. Alternatively, special polynomials may be defined using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors. Bezier splines are the most straight forward way to define a curve in the standards considered in Section \ref{Document Representations}. A spline defined from two cubic beziers is shown in Figure \ref{spline.pdf}
+\begin{figure}[H]
+\centering
+\begin{minipage}[t]{0.3\textwidth}
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=\textwidth]{figures/spline_labelled.pdf}
+\end{figure}
+\end{minipage}
+\begin{minipage}[t]{0.3\textwidth}
+\begin{minted}{xml}
+<!-- DOM element in SVG used to construct the spline -->
+<path d="M 0,300
+ C 0,300 200,210 90,140
+ -20,70 200,0 200,0"
+ style="stroke:#000000; stroke-width:1px;
+ fill:none;"/>
+\end{minted}
+\begin{minted}{postscript}
+% PostScript commands for a similar spline
+0 300 moveto
+0 300 200 210 90 140 curveto
+-20 70 200 0 200 0 curveto stroke
+\end{minted}
+\end{minipage}
+\begin{minipage}[t]{0.3\textwidth}
+\begin{figure}[H]
+ \centering
+ \includegraphics[width=\textwidth]{figures/spline.pdf}
+\end{figure}
+\end{minipage}
+ \caption{Constructing a Spline from two cubic beziers \\ (a) Showing the Control Points (b) Representations in SVG and PostScript (c) Rendered Spline}\label{spline.pdf}
+\end{figure}
\subsubsection{Bezier Curves}
\input{chapters/Background_Bezier}
+\subsection{Font Rendering}\label{Font Rendering}
+\input{chapters/Background_Fonts}
+
+
+
\subsection{Shading}
Algorithms for shading on vector displays involved drawing equally spaced lines in the region with endpoints defined by the boundaries of the region\cite{brassel1979analgorithm}. Apart from being unrealistic, these techniques required a computationally expensive sorting of vertices\cite{lane1983analgorithm}.
On raster displays, shading is typically based upon Lane's algorithm of 1983\cite{lane1983analgorithm}. Lane's algorithm relies on the ability to ``subtract'' fill from a region. This algorithm is now implemented in the GPU \rephrase{stencil buffer-y and... stuff} \cite{kilgard2012gpu}
-\subsection{Compositing}
+\subsection{Compositing and the Painter's Model}\label{Compositing and the Painter's Model}
So far we have discussed techniques for rendering vector graphics primitives in isolation, with no regard to the overall structure of a document which may contain many thousands of primitives. A straight forward approach would be to render all elements sequentially to the display, with the most recently drawn pixels overwriting lower elements. Such an approach is particularly inconvenient for anti-aliased images where colours must appear to smoothly blur between the edge of a primitive and any drawn underneath it.
-Most raster displays are based on an additive red-green-blue colour representation which matches the human eye's response to light\cite{citationneeded}. In 1984, Porter and Duff introduced a fourth colour channel to be used when combining rasterised images called the ``alpha'' channel, analogous to the transparency of a pixel\cite{porter1984compositing}. Elements can be rendered seperately, with the four colour channels of successively drawn elements being combined according to one of several possible operations described by Porter and Duff.
+Colour raster displays are based on an additive red-green-blue $(r,g,b)$ colour representation which matches the human eye's response to light\cite{computergraphics2}. In 1984, Porter and Duff introduced a fourth colour channel for rasterised images called the ``alpha'' channel, analogous to the transparency of a pixel\cite{porter1984compositing}. In compositing models, elements can be rendered seperately, with the four colour channels of successively drawn elements being combined according to one of several possible operations.
+
+In the ``painter's model'' as described by the SVG standard, Porter and Duff's ``over'' operation is used when rendering one primitive over another\cite{svg2011-1.1}.
+Given an existing pixel $P_1$ with colour values $(r_1, g_1, b_1, a_1)$ and a pixel $P_2$ with colours $(r_2, g_2, b_2, a_2)$ to be painted over $P_1$, the resultant pixel $P_T$ has colours given by:
+\begin{align}
+ a_T &= 1 - (1-a_1)(1-a_2) \\
+ r_T &= (1 - a_2)r_1 + r_2 \quad \text{(similar for $g_T$ and $b_T$)}
+\end{align}
+It should be apparent that alpha values of $1$ correspond to an opaque pixel; that is, when $a_2 = 1$ the resultant pixel $P_T$ is the same as $P_2$.
+When the final pixel is actually drawn on an rgb display, the $(r, g, b)$ components are $(r_T/a_T, g_T/a_T, b_T/a_T)$.
-In the ``painter's model'' described by the SVG standard, the ``over'' operation is used when rendering one primitive over another; the red-green-blue components of overlapping pixels are added but the alpha component is set to that of the uppermost pixel\cite{svg2011-1.1}. The PostScript and PDF standards also use the ``painter's model''. The painter's model is demonstrated in Figure \ref{SVG} --- originally an SVG image but converted to a PDF for inclusion in this report\footnote{PDF and SVG formats may be converted but neither standard allows for importing the other directly}.
+The PostScript and PDF standards, as well as the OpenGL API also use a painter's model for compositing. However, PostScript does not include an alpha channel, so $P_T = P_2$ always\cite{plrm}. Figure \ref{SVG} illustrates the painter's model for partially transparent shapes as they would appear in both the SVG and PDF models.
\subsection{Rasterisation on the CPU and GPU}
\rephrase{2. Here are the ways documents are structured ... we got here eventually}
-\section{Document Representations}
+\section{Document Representations}\label{Document Representations}
The representation of information, particularly for scientific purposes, has changed dramatically over the last few decades. For example, Brassel's 1979 paper referenced earlier has been produced on a mechanical type writer. Although the paper discusses an algorithm for shading on computer displays, the figures illustrating this algorithm have not been generated by a computer, but drawn by Brassel's assistant\cite{brassel1979analgorithm}. In contrast, modern papers such as Barnes et. al's recent paper on embedding 3d images in PDF documents\cite{barnes2013embeddding} can themselves be an interactive proof of concept.
-\rephrase{Say some stuff about Knuth's Metafont and \TeX here}
+In this section we will consider various approaches and motivations to specifying the structure and appearance of a document, including: early interpreted formats (PostScript, \TeX, DVI), the Document Object Model popular in standards for web based documents (HTML, SVG), and Adobe's ubiquitous Portable Document Format (PDF). Some of these formats were discussed in a recent paper ``Pixels Or Perish'' by Hayes\cite{hayes2012pixelsor} who argues for greater interactivity in the PDF standard.
-Hayes' 2012 article ``Pixels or Perish'' discusses the recent history and current state of the art in documents for scientific publications\cite{hayes2012pixels}.
+\subsection{Interpreted Document Formats}
+\input{chapters/Background_Interpreted}
-\subsection{Interpreted Model}
\begin{itemize}
\item This model treats a document as the source code program which produces graphics
\item Problems with security --- Turing complete, can be exploited easily
\end{itemize}
-\subsection{Crippled Interpreted Model}
+\pagebreak
+\subsection{Document Object Model}\label{Document Object Model}
+\input{chapters/Background_DOM}
-\rephrase{I'm pretty sure I made that one up}
+\subsection{The Portable Document Format}
+
+Adobe's Portable Document Format (PDF) is used almost universally for sharing documents; the ability to export or print to PDF can be found in most graphical document editors, even text editors.
+
+Hayes describes PDF as ``... essentially 'flattened' PostScript; it’s what’s left when you remove all the procedures and loops in a program, replacing them with sequences of simple drawing commands.''\cite{hayes2012pixelsor}. Consultation of the PDF 1.7 standard shows that this statement does not a give a complete picture --- despite being based on the Adobe PostScript model of a document as a series of ``pages'' to be printed by executing sequential instructions, from version 1.5 the PDF standard began to borrow some ideas from the Document Object Model discussed in Section \ref{Document Object Model}. For example, interactive elements such as forms may be included as XHTML objects and styled using CSS. ``Actions'' are objects used to modify the data structure dynamically. In particular, it is possible to include Javascript Actions. Adobe defines the API for Javascript actions seperately to the PDF standard\cite{js_3d_pdf}. There is evidence in the literature of attempts to exploit these features, with mixed success\cite{barnes2013embedding, hayes2012pixelsor}.
+
+To quote Adobe's PDF 1.7 reference manual, ``A PDF file should be thought of as a flattened representation of a data structure consisting of a collection of objects that can refer to each other in any arbitrary way''\cite{pdfref17}.
-\begin{itemize}
- \item PDF is PostScript but without the Turing Completeness
- \item Solves security issues, more efficient
-\end{itemize}
-\subsection{Document Object Model}\label{Document Object Model}
-\input{chapters/Background_DOM}
\subsection{Scientific Computation Packages}
\section{Precision in Modern Document Formats}
-We briefly summarise the requirements of standard document formats in regards to the precision of number representations:
+We briefly summarise the requirements of the standards discussed so far in regards to the precision of mathematical operations:
\begin{itemize}
\item {\bf PostScript} predates the IEEE-754 standard and originally specified a floating point representation with ? bits of exponent and ? bits of mantissa. Version ? of the PostScript standard changed to specify IEEE-754 binary32 ``single precision'' floats.
\item {\bf PDF} has also specified IEEE-754 binary32 since version ?. Importantly, the standard states that this is a \emph{maximum} precision; documents created with higher precision would not be viewable in Adobe Reader.
git.ucc.asn.au / ipdf / sam.git / blobdiff
UCC git Repository :: git.ucc.asn.au