X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fdocuments.git;a=blobdiff_plain;f=LiteratureNotes.tex;h=6831428552ba9079d36d7aa84fadf3e1f073cba2;hp=a9292dc31dc6eb45fcd034c6c7678fd14116a9bd;hb=0f8e75393b859ea4b974948a86772b8abacebfc1;hpb=f1069d4e2ac6473ff167bb7385f22b446a91b2dc diff --git a/LiteratureNotes.tex b/LiteratureNotes.tex index a9292dc..6831428 100644 --- a/LiteratureNotes.tex +++ b/LiteratureNotes.tex @@ -18,7 +18,7 @@ \parskip 8.2pt % sets spacing between paragraphs %\renewcommand{\baselinestretch}{1.5} % Uncomment for 1.5 spacing between lines \parindent 0pt % sets leading space for paragraphs -\linespread{0.8} +\linespread{1} \newcommand{\vect}[1]{\boldsymbol{#1}} % Draw a vector @@ -37,14 +37,14 @@ \definecolor{darkred}{rgb}{0.75,0,0} \definecolor{darkblue}{rgb}{0,0,0.75} \definecolor{pink}{rgb}{1,0.5,0.5} -\lstset{language=Java} +\lstset{language=XML} \lstset{backgroundcolor=\color{darkgray}} -\lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt} -\lstset{keywordstyle=\color{darkred}\bfseries} -\lstset{commentstyle=\color{darkblue}} +%\lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=5pt} +%\lstset{keywordstyle=\color{darkred}\bfseries} +%\lstset{commentstyle=\color{darkblue}} %\lstset{stringsyle=\color{red}} -\lstset{showstringspaces=false} -\lstset{basicstyle=\small} +%\lstset{showstringspaces=false} +%\lstset{basicstyle=\small} \newcommand{\shell}[1]{\texttt{#1}} \newcommand{\code}[1]{\texttt{#1}} @@ -77,18 +77,56 @@ Adobe's official reference manual for PostScript. It is big. +\begin{itemize} + \item First version was published BEFORE the IEEE standard and used smaller floats than binary32 + \item Now uses binary32 floats. +\end{itemize} + \section{Portable Document Format Reference Manual \cite{pdfref17}} Adobe's official reference for PDF. It is also big. +\begin{itemize} + \item Early versions did not use IEEE binary32 but 16-16 exponent/mantissa encodings (Why?) + \item Current standard is restricted to binary32 + \item It specifically says PDF creators must use at most binary32 because higher precision is not supported by Adobe Reader. +\end{itemize} + \section{IEEE Standard for Floating-Point Arithmetic \cite{ieee2008-754}} The IEEE (revised) 754 standard. It is also big. +Successes: +\begin{itemize} + \item Has been adopted by CPUs + \item Standardised floats for programmers --- accomplishes goal of allowing non-numerical experts to write reasonably sophisticated platform independent programs that may perform complex numerical operations +\end{itemize} + +Failures: +\begin{itemize} + \item Adoption by GPUs slower\cite{hillesland2004paranoia} + \item It specifies the maximum errors for operations using IEEE types but nothing about internal representations + \item Many hardware devices (GPUs and CPUs) use non-IEEE representations internally and simply truncate/round the result + \begin{itemize} + \item This isn't so much of a problem when the device uses additional bits but it is misleading when GPUs use less than binary32 and act as if they are using binary32 from the programmer's perspective. + \item Devices using {\bf less} bits internally aren't IEEE compliant + \end{itemize} + \item Thus the same program compiled and run on different architectures may give completely different results\cite{HFP} + \begin{itemize} + \item The ultimate goal of allowing people to write numerical programs in total ignorance of the hardware is not entirely realised + \end{itemize} + \item This is the sort of thing that makes people want to use a virtual machine, and thus Java + \begin{itemize} + \item Objectively I probably shouldn't say that using Java is in itself a failure + \end{itemize} + \item Standards such as PostScript and PDF were slow to adopt IEEE representations + \item The OpenVG standard accepts IEEE binary32 in the API but specifically states that hardware may use less than this\cite{rice2008openvg} +\end{itemize} + \pagebreak @@ -389,6 +427,8 @@ Performance was much improved over the software rasterization and over XRender a on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when some transformations were applied. +In \cite{kilgard2012gpu}, Kilgard mentions that Glitz has been abandoned. He describes it as ''GPU assisted'' rather than GPU accelerated, since it used the XRender (??) extension. + %% Sam again \section{Boost Multiprecision Library \cite{boost_multiprecision}} @@ -429,6 +469,8 @@ It is probably not that useful, I don't think we'll end up writing FPU assembly? FPU's typically have 80 bit registers so they can support REAL4, REAL8 and REAL10 (single, double, extended precision). +Note: Presumably this is referring to the x86 80 bit floats that David was talking about? + \section{Floating Point Package User's Guide \cite{bishop2008floating}} @@ -615,9 +657,167 @@ IE: The more precise the representation, the slower things go wrong, but they st This is an example where the calculation of a function $f(a,b)$ is not only totally wrong, it gives completely different results depending on the CPU. Despite the CPU conforming to IEEE. +\section{Scalable Vector Graphics (SVG) 1.1 (Second Edition) \cite{svg2011-1.1}} + +Scalable Vector Graphics (SVG) is a XML language for describing two dimensional graphics. This document is \url{http://www.w3.org/TR/2011/REC-SVG11-20110816/}, the latest version of the standard at the time of writing. + +\subsubsection{Three types of object} +\begin{enumerate} + \item Vector graphics shapes (paths) + \item Images (embedded bitmaps) + \item Text +\end{enumerate} + +\subsubsection{Rendering Model and Precision} + +SVG uses the ``painter's model''. Paint is applied to regions of the page in an order, covering the paint below it according to rules for alpha blending. + +``Implementations of SVG are expected to behave as though they implement a rendering (or imaging) model cor- +responding to the one described in this chapter. A real implementation is not required to implement the model in +this way, but the result on any device supported by the implementation shall match that described by this model.'' + +SVG uses {\bf single precision floats}. Unlike PDF and PostScript, the standard specifies this as a {\bf minimum} range from \verb/-3.4e+38F/ to \verb/+3.4e+38F/ + +``It is recommended that higher precision floating point storage and computation be performed on operations +such as coordinate system transformations to provide the best possible precision and to prevent round-off errors.'' + +There is also a ``High Quality SVG Viewers'' requirement to use at least {\bf double} precision floats. + +\section{OpenVG Specification 1.1 \cite{rice2008openvg}} +``OpenVG is an application programming interface (API) for hardware-accelerated two- +dimensional vector and raster graphics developed under the auspices of the Khronos +Group \url{www.khronos.org}.'' + +Specifically, provides the same drawing functionality required by a high-performance SVG document viewer (SVG Tiny 1.2) +TODO: Look at that $\neq$ SVG 1.1 + +It is designed to be similar to OpenGL. + +\subsubsection{Precision} +``All floating-point values are specified in standard IEEE 754 format. However, +implementations may clamp extremely large or small values to a restricted +range, and internal processing may be performed with lesser precision. At least +16 bits of mantissa, 6 bits of exponent, and a sign bit must be present, allowing +values from $\pm 2^{-30}$ to $\pm2^{31}$ to be represented with a fractional precision of at least 1 +in $2^{16}$.'' + +IEEE but with a non standard number of bits. + +Presumably the decreased precision is for increased efficiency the standard states that example applications are for ebooks. + + +\section{Document Object Model --- pugixml 1.4 manual \cite{pugixmlDOM}} + +Pugixml is a C++ library for parsing XML documents\cite{kapoulkine2014pugixml}. XML is based on the Document Object Model (DOM); this is explained pretty well by the pugixml manual. + +The document is the root node of the tree. Each child node has a type. These may +\begin{itemize} + \item Have attributes + \item Have child nodes of their own + \item Contain data +\end{itemize} + +In the case of HTML/SVG an XML parser within the browser/viewer creates the DOM tree from the XML (plain text) and then interprets that tree to produce the objects that will be rendered. + +Example of XML $\to$ DOM tree given at\cite{pugixmlDOM}. +Example of XML parsing using pugixml is in \shell{code/src/tests/xml.cpp} + + +\begin{figure}[H] + \centering +\begin{lstlisting}[language=XML,basicstyle=\ttfamily] + + + + some text + + some more text + + + + + + +\end{lstlisting} + + \includegraphics[width=0.6\textwidth]{references/pugixmlDOM-dom_tree.png} + \caption{Tree representation of the above listing \cite{pugixmlDOM}} +\end{figure} + +\section{An Algorithm For Shading of Regions on Vector Display Devices \cite{brassel1979analgorithm}} + +All modern display devices are raster based and therefore this paper is mainly of historical interest. It provides some references for shading on a raster display. + +The algorithm described will shade an arbitrary simply-connected polygon using one or two sets of parallel lines. + +The ``traditional'' method is: +\begin{enumerate} + \item Start with a $N$ vertex polygon, rotate coords by the shading angle + \item Determine a bounding rectangle + \item For $M$ equally spaced parallel lines, compute the intersections with the boundaries of the polygon + \item Rotate coordinates back + \item Render the $M$ lines +\end{enumerate} + +This is pretty much exactly how an artist would shade a pencil drawing. It is $O(M\times N)$. + +The algorithm in this paper does: +\begin{enumerate} + \item Rotate polygon coords by shading angle + \item Subdivide the polygon into trapezoids (special case triangle) + \item Shade the trapezoids independently + \item Rotate it all back +\end{enumerate} +It is more complicated than it seems. The subdivision requires a sort to be performed on the vertices of the polygon based on their rotated $x$ and $y$ coordinates. + +\section{An Algorithm For Filling Regions on Graphics Display Devices \cite{lane1983analgorithm}} + +This gives an algorithm for for polygons (which may have ``holes''). +It requires the ability to ``subtract'' fill from a region; this is (as far as I can tell) difficult for vector graphics devices but simple on raster graphics devices, so the paper claims it is oriented to the raster graphics devices. + +If the polygon is defined by $(x_i, y_i)$ then this algorithm iterates from $i = 2$ and alternates between filling and erasing the triangles $[(x_i, y_i), (x_{i+1}, y_{i+1}), (x_1, y_1)]$. It requires no sorting of the points. + +The paper provides a proof that the algorithm is correct and is ``optimal in the number of pixel updates required for convex polygons''. +In the conclusion it is noted that trapezoids could be used from a fixed line and edge of the polygon, but this is not pixel optimal. + +This paper doesn't have a very high citation count but it is cited by the NVIDIA article \cite{kilgard2012gpu}. +Apparently someone else adapted this algorithm for use with the stencil buffer. + +\section{GPU-accelerated path rendering \cite{kilgard2012gpu, kilgard300programming}} + +Vector graphics on the GPU; an NVIDIA extension. \cite{kilgard300programming} is the API. + +Motivations: +\begin{itemize} + \item The focus has been on 3D acceleration in GPUs; most path rendering is done by the CPU. + \item Touch devices allow the screen to be transformed rapidly; CPU rastering of the path becomes inefficient + \begin{itemize} + \item The source of the ugly pixelated effects on a smartphone when scaling? + \end{itemize} + \item Especially when combined with increased resolution of these devices + \item Standards such as HTML5, SVG, etc, expose path rendering + \item Javascript is getting fast enough that we can't blame it anymore (the path rendering is the bottleneck not the JS) + \item GPU is more power efficient than the CPU +\end{itemize} + +Results show the extension is faster than almost every renderer it was compared with for almost every test image. + +Comparisons to other attempts: +\begin{itemize} + \item Cairo and Glitz \cite{nilsson2004glitz} (abandoned) +\ \item Direct2D from Microsoft uses CPU to tesselate trapezoids and then renders these on the GPU + \item Skia in Android/Chrome uses CPU but now has Ganesh which is also hybrid CPU/GPU + \item Khronos Group created OpenVG\cite{rice2008openvg} with several companies creating hardware units to implement the standard. Performance is not as good as ``what we report'' +\end{itemize} + + \chapter{General Notes} -\section{Floating-Point \cite{HFP,goldberg1991whatevery,goldberg1992thedesign,priest1991algorithms}} +\section{The DOM Model} + +A document is modelled as a tree. The root of the tree is the document. This has nodes of varying types. Some nodes may have children, attributes, and data. + +\section{Floating-Point Numbers\cite{HFP,goldberg1991whatevery,goldberg1992thedesign,priest1991algorithms}} A set of FP numbers is characterised by: \begin{enumerate}