\lstset{showstringspaces=false}
\lstset{basicstyle=\small}
-
-
-
+\newcommand{\shell}[1]{\texttt{#1}}
+\newcommand{\code}[1]{\texttt{#1}}
\begin{document}
\end{itemize}
+%%%%
+% David's Stuff
+%%%%
+\section{Compositing Digital Images\cite{porter1984compositing}}
+
+
+
+Perter and Duff's classic paper "Compositing Digital Images" lays the
+foundation for digital compositing today. By providing an "alpha channel,"
+images of arbitrary shapes — and images with soft edges or sub-pixel coverage
+information — can be overlayed digitally, allowing separate objects to be
+rasterized separately without a loss in quality.
+
+Pixels in digital images are usually represented as 3-tuples containing
+(red component, green component, blue component). Nominally these values are in
+the [0-1] range. In the Porter-Duff paper, pixels are stored as $(R,G,B,\alpha)$
+4-tuples, where alpha is the fractional coverage of each pixel. If the image
+only covers half of a given pixel, for example, its alpha value would be 0.5.
+
+To improve compositing performance, albeit at a possible loss of precision in
+some implementations, the red, green and blue channels are premultiplied by the
+alpha channel. This also simplifies the resulting arithmetic by having the
+colour channels and alpha channels use the same compositing equations.
+
+Several binary compositing operations are defined:
+\begin{itemize}
+\item over
+\item in
+\item out
+\item atop
+\item xor
+\item plus
+\end{itemize}
+
+The paper further provides some additional operations for implementing fades and
+dissolves, as well as for changing the opacity of individual elements in a
+scene.
+
+The method outlined in this paper is still the standard system for compositing
+and is implemented almost exactly by modern graphics APIs such as \texttt{OpenGL}. It is
+all but guaranteed that this is the method we will be using for compositing
+document elements in our project.
+
+\section{Bresenham's Algorithm: Algorithm for computer control of a digital plotter\cite{bresenham1965algorithm}}
+Bresenham's line drawing algorithm is a fast, high quality line rasterization
+algorithm which is still the basis for most (aliased) line drawing today. The
+paper, while originally written to describe how to control a particular plotter,
+is uniquely suited to rasterizing lines for display on a pixel grid.
+
+Lines drawn with Bresenham's algorithm must begin and end at integer pixel
+coordinates, though one can round or truncate the fractional part. In order to
+avoid multiplication or division in the algorithm's inner loop,
+
+The algorithm works by scanning along the long axis of the line, moving along
+the short axis when the error along that axis exceeds 0.5px. Because error
+accumulates linearly, this can be achieved by simply adding the per-pixel
+error (equal to (short axis/long axis)) until it exceeds 0.5, then incrementing
+the position along the short axis and subtracting 1 from the error accumulator.
+
+As this requires nothing but addition, it is very fast, particularly on the
+older CPUs used in Bresenham's time. Modern graphics systems will often use Wu's
+line-drawing algorithm instead, as it produces antialiased lines, taking
+sub-pixel coverage into account. Bresenham himself extended this algorithm to
+produce Bresenham's circle algorithm. The principles behind the algorithm have
+also been used to rasterize other shapes, including B\'{e}zier curves.
+
+\section{Quad Trees: A Data Structure for Retrieval on Composite Keys\cite{finkel1974quad}}
+
+This paper introduces the ``quadtree'' spatial data structure. The quadtree structure is
+a search tree in which every node has four children representing the north-east, north-west,
+south-east and south-west quadrants of its space.
+
+\section{Xr: Cross-device Rendering for Vector Graphics\cite{worth2003xr}}
+
+Xr (now known as Cairo) is an implementation of the PDF v1.4 rendering model,
+independent of the PDF or PostScript file formats, and is now widely used
+as a rendering API. In this paper, Worth and Packard describe the PDF v1.4 rendering
+model, and their PostScript-derived API for it.
+
+The PDF v1.4 rendering model is based on the original PostScript model, based around
+a set of \emph{paths} (and other objects, such as raster images) each made up of lines
+and B\'{e}zier curves, which are transformed by the ``Current Transformation Matrix.''
+Paths can be \emph{filled} in a number of ways, allowing for different handling of self-intersecting
+paths, or can have their outlines \emph{stroked}.
+Furthermore, paths can be painted with RGB colours and/or patterns derived from either
+previously rendered objects or external raster images.
+PDF v1.4 extends this to provide, amongst other features, support for layering paths and
+objects using Porter-Duff compositing\cite{porter1984compositing}, giving each painted path
+the option of having an $\alpha$ value and a choice of any of the Porter-Duff compositing
+methods.
+
+The Cairo library approximates the rendering of some objects (particularly curved objects
+such as splines) with a set of polygons. An \texttt{XrSetTolerance} function allows the user
+of the library to set an upper bound on the approximation error in fractions of device pixels,
+providing a trade-off between rendering quality and performance. The library developers found
+that setting the tolerance to greater than $0.1$ device pixels resulted in errors visible to the
+user.
+
+\section{Glitz: Hardware Accelerated Image Compositing using OpenGL\cite{nilsson2004glitz}}
+
+This paper describes the implementation of an \texttt{OpenGL} based rendering backend for
+the \texttt{Cairo} library.
+
+The paper describes how OpenGL's Porter-Duff compositing is easily suited to the Cairo/PDF v1.4
+rendering model. Similarly, traditional OpenGL (pre-version 3.0 core) support a matrix stack
+of the same form as Cairo.
+
+The ``Glitz'' backend will emulate support for tiled, non-power-of-two patterns/textures if
+the hardware does not support it.
+
+Glitz can render both triangles and trapezoids (which are formed from pairs of triangles).
+However, it cannot guarantee that the rasterization is pixel-precise, as OpenGL does not proveide
+this consistently.
+
+Glitz also supports multi-sample anti-aliasing, convolution filters for raster image reads (implemented
+with shaders).
+
+Performance was much improved over the software rasterization and over XRender accellerated rendering
+on all except nVidia hardware. However, nVidia's XRender implementation did slow down significantly when
+some transformations were applied.
+
+%% Sam again
+
+\section{Boost Multiprecision Library\cite{boost_multiprecision}}
+
+\begin{itemize}
+ \item ``The Multiprecision Library provides integer, rational and floating-point types in C++ that have more range and precision than C++'s ordinary built-in types.''
+ \item Specify number of digits for precision as a template argument.
+ \item Precision is fixed... {\bf possible approach to project:} Use \verb/boost::mpf_float<N>/ and increase \verb/N/ as more precision is required?
+\end{itemize}
+
+
+% Some hardware related sounding stuff...
+
+\section{A CMOS Floating Point Unit\cite{kelley1997acmos}}
+
+The paper describes the implentation of a FPU for PowerPC using a particular Hewlett Packard process (HP14B 0.5$\mu$m, 3M, 3.3V).
+It implements a ``subset of the most commonly used double precision floating point instructions''. The unimplemented operations are compiled for the CPU.
+
+The paper gives a description of the architecture and design methods.
+This appears to be an entry to a student design competition.
+
+Standard is IEEE 754, but the multiplier tree is a 64-bit tree instead of a 54 bit tree.
+`` The primary reason for implementing a larger tree is for future additions of SIMD [Single Instruction Multiple Data (?)] instructions similar to Intel's MMX and Sun's VIS instructions''.
+
+HSPICE simulations used to determine transistor sizing.
+
+Paper has a block diagram that sort of vaguely makes sense to me.
+The rest requires more background knowledge.
+
+\section{Simply FPU\cite{filiatreault2003simply}}
+
+This is a webpage at one degree of seperation from wikipedia.
+
+It talks about FPU internals, but mostly focuses on the instruction sets.
+It includes FPU assembly code examples (!)
+
+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).
+
+
+\section{Floating Point Package User's Guide\cite{bishop2008floating}}
+
+This is a technical report describing floating point VHDL packages \url{http://www.vhdl.org/fphdl/vhdl.html}
+
+In theory I know VHDL (cough) so I am interested in looking at this further to see how FPU hardware works.
+It might be getting a bit sidetracked from the ``document formats'' scope though.
+
+The report does talk briefly about the IEEE standard and normalised / denormalised numbers as well.
+
+See also: Java Optimized Processor\cite{jop} (it has a VHDL implementation of a FPU).
+
+\section{Low-Cost Microarchitectural Support for Improved Floating-Point Accuracy\cite{dieter2007lowcost}}
+
+Mentions how GPUs offer very good floating point performance but only for single precision floats.
+
+Has a diagram of a Floating Point adder.
+
+Talks about some magical technique called "Native-pair Arithmetic" that somehow makes 32-bit floating point accuracy ``competitive'' with 64-bit floating point numbers.
+
+\section{Accurate Floating Point Arithmetic through Hardware Error-Free Transformations\cite{kadric2013accurate}}
+
+From the abstract: ``This paper presents a hardware approach to performing ac-
+curate floating point addition and multiplication using the idea of error-
+free transformations. Specialized iterative algorithms are implemented
+for computing arbitrarily accurate sums and dot products.''
+
+The references for this look useful.
+
+It also mentions VHDL.
+
+So whenever hardware papers come up, VHDL gets involved...
+I guess it's time to try and work out how to use the Opensource VHDL implementations.
+
+This is about reduction of error in hardware operations rather than the precision or range of floats.
+But it is probably still relevant.
+
+\section{Floating Point Unit from JOP\cite{jop}}
+
+This is a 32 bit floating point unit developed for JOP in VHDL.
+I have been able to successfully compile it and the test program using GHDL\cite{ghdl}.
+
+Whilst there are constants (eg: \verb/FP_WIDTH = 32, EXP_WIDTH = 8, FRAC_WIDTH = 23/) defined, the actual implementation mostly uses magic numbers, so
+some investigation is needed into what, for example, the "52" bits used in the sqrt units are for.
+
+\section{GHDL\cite{ghdl}}
+
+GHDL is an open source GPL licensed VHDL compiler written in Ada. It had packages in debian up until wheezy when it was removed. However the sourceforge site still provides a \shell{deb} file for wheezy.
+
+This reference explains how to use the \shell{ghdl} compiler, but not the VHDL language itself.
+
+GHDL is capable of compiling a ``testbench'' - essentially an executable which simulates the design and ensures it meets test conditions.
+A common technique is using a text file to provide the inputs/outputs of the test. The testbench executable can be supplied an argument to save a \shell{vcd} file which can be viewed in \shell{gtkwave} to see timing diagrams.
+
+Sam has successfully compiled the VHDL design for an FPU in JOP\cite{jop} into a ``testbench'' executable which uses standard i/o instead of a regular file.
+Using unix domain sockets we can execute the FPU as a child process and communicate with it from our document viewing test software. This means we can potentially simulate alternate hardware designs for FPUs and witness the effect they will have on precision in the document viewer.
+
+Using \shell{ghdl} the testbench can also be linked as part a C/C++ program and run using a function; however there is still no way to communicate with it other than forking a child process and using a unix domain socket anyway. Also, compiling the VHDL FPU as part of our document viewer would clutter the code repository and probably be highly unportable. The VHDL FPU has been given a seperate repository.
+
+
+% Back to software
+\section{Basic Issues in Floating Point Arithmetic and Error Analysis\cite{demmel1996basic}}
+
+These are lecture notes from U.C Berkelye CS267 in 1996.
\pagebreak
git.ucc.asn.au / ipdf / documents.git / blobdiff
UCC git Repository :: git.ucc.asn.au