... Yep.
\section{Rendering}
-As existing displays (and printers) are bit-mapped devices, one of the core problems which must be solved when
-designing a document format is how it is to be \emph{rasterized} into a bitmap at a given resolution.
-
-\subsection{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.
-
-\subsection{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.
+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.
+
+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''.
+As existing displays (and printers) are bit-mapped devices, vector documents must be \emph{rasterized} into a bitmap at
+a given resolution. This bitmap is then displayed or printed. The resulting bitmap is then an approximation of the vector image
+at that resolution.
+
+This project will be based around vector graphics, as these properties make it more suited to experimenting with zoom
+quality.
+
+
+The rasterization process typically operates on an individual ``object'' or ``shape'' at a time: there are special algorithms
+for rendering lines\cite{bresenham1965algorithm}, triangles\cite{giesen2013triangle}, polygons\cite{pineda1988parallel} and B\'ezier
+Curves\cite{goldman_thefractal}. Typically, these are rasterized independently and composited in the bitmap domain using Porter-Duff
+compositing\cite{porter1984compositing} into a single image. This allows complex images to be formed from many simple pieces, as well
+as allowing for layered translucent objects, which would otherwise require the solution of some very complex constructive geometry problems.
+
+While traditionally, rasterization was done entirely in software, modern computers and mobile devices have hardware support for rasterizing
+some basic primitives --- typically lines and triangles ---, designed for use rendering 3D scenes. This hardware is usually programmed with an
+API like \texttt{OpenGL}\cite{openglspec}.
+
+More complex shapes like B\'ezier curves can be rendered by combining the use of bitmapped textures (possibly using signed-distance
+fields\cite{leymarie1992fast}\cite{frisken2000adaptively}\cite{green2007improved}) with polygons approximating the curve's shape\cite{loop2005resolution}\cite{loop2007rendering}.
+
+Indeed, there are several implementations of these vector graphics
\emph{GPU Rendering}\cite{loop2005resolution}, OpenVG implementation on GLES: \cite{oh2007implementation},
\cite{robart2009openvg}
21:57 <@matches> SVG defines a "minimum" precision of IEEE binary32
21:58 <@matches> But there's a specification for "High Quality" viewers that have to use binary64
21:58 <@matches> That's probably the only real thing relevant directly to our problem
+--- Day changed Thu May 01 2014
+01:23 <@matches> It's May 1st
+01:23 <@matches> This means we can no longer say "The Literature Review is due Next Month"
+01:23 <@matches> IT'S DUE THIS MONTH
+01:23 * matches freaks out
+01:23 <@matches> ... but after sleep
+01:25 <@matches> Page 12 of my Literature Review by the way
+01:25 <@matches> Is the only page I like
+16:34 <@matches> The C version of paranoia compiled for me
+16:34 <@matches> Not terribly exciting (I have an IEEE 754 compatible processor! Amazing)
+22:17 <@matches> W Kahan's website is a very interesting if slightly difficult read
+22:24 <@matches> He appears to have written this 80 page pdf in a day
+22:27 <@matches> It kind of reads like one of those religious propaganda pamphlets
+22:27 <@matches> "Java is the Work of Satan"
+22:27 <@matches> "Kernighan-Ritcie C floating-point semantics are the light"
+22:28 <@matches> But every so often he has a graph or example that makes him seem less crazy
+22:34 <@matches> "And now Java forbits you to mention or use extra-precise long double arithmetic, though IEEE Standard 754 recommends its use and over 95% of computers on desktops have it built into their hardware. You paid for it, but Java denies you its benefits."
+22:34 <@matches> Java has long double now right?
+22:34 <@matches> Although that JOP I was looking at was just 32 bit
+22:36 <@matches> Ah, java.lang.math.BigDecimal
+22:37 <@matches> "But be careful with division, because it will throw exceptions if it's like 1/3, then it will be Non-terminating decimal expansion."
+22:37 <@matches> That sounds horrifying
+22:40 -!- mode/#ipdf [-o matches] by matches
+--- Day changed Sat May 03 2014
+22:01 < sulix> My crazy idea to you would be to research p-adic number representations.
+22:01 < sulix> It's been a while, but they were mentioned a couple of times in pure maths units and seemed interesting/crazy and I can't remember much about them.
+22:28 -!- mode/#ipdf [+o matches] by OperServ
+22:29 <@matches> I will look at them, the "just use a float but with more bits until you run out of memory" doesn't seem a very well thought out approach
+22:29 <@matches> Maybe someone actually cares enough to research better ways
+22:29 <@matches> I mean, something's wrong with an idea when you can write "1/3" and have a runtime exception (re: Java BigNumber)
+22:30 <@matches> I plan to write some nasty things about Java based on Kahan's rants so as to gloss over the fact that it has BigNumber built into it and forstall the inevitable "Why didn't you use Java!"
+22:31 < sulix> I think we want to truncate to whatever the most accurate you can see at the given zoom level.
+22:31 <@matches> Yeah
+22:32 <@matches> It annoys me that XML and HTML specs don't have a PDF version
+22:32 < sulix> I've been printing to pdf for some of those things.
+22:33 <@matches> None of the links to different sections would work though
+22:35 <@matches> Specifications are thrilling
+22:35 <@matches> "How to read this specification"
+22:35 <@matches> "This specification should be read like all other specifications"
+22:35 <@matches> Oh wait
+22:35 <@matches> It actually gets better
+22:35 <@matches> Is that...
+22:35 <@matches> Humour!
+22:36 <@matches> I thought that wasn't allowed!
+22:36 <@matches> "First it should be read cover-to-cover, multiple times. Then, it should be read backwards at least once. Then it should be read by picking random sections from the contents list and following all the cross references"
+22:37 <@matches> As much as I love the idea of reading 626 pages of specification backwards...
+--- Day changed Tue May 06 2014
+00:39 <@matches> http://szmoore.net/ipdf/sam/rate-my-litreview.py
+00:39 <@matches> Tim will be thrilled!
+00:40 <@matches> I'm probably going to really regret making that
+00:41 <@matches> The regret is rising to the surface
+00:41 <@matches> It's an example of an interactive document format
+00:41 <@matches> The pixels or perish guy would approve
+00:43 <@matches> So much regret
+00:43 -!- mode/#ipdf [-o matches] by matches
+23:37 -!- mode/#ipdf [+o matches] by OperServ
+23:38 <@matches> So, I have this book called "Computer Graphics" that is pretty amazing
+23:38 <@matches> Funnily enough it has all the algorithms in it
+23:38 <@matches> For computer graphics
+23:38 <@matches> Probably should have been reading it ages ago but I thought we were worrying more about precision
+23:38 <@matches> I don't even know anymore
+23:39 <@matches> Have to read 500pg textbook on graphics, 500pg textbook on floating point numbers, 500pg PDF/PostScript standards...
+23:39 <@matches> Too many pages
+23:39 <@matches> Anyway it has a section on Octrees
+23:39 <@matches> But don't worry
+23:39 <@matches> It mentions Quad trees
+23:39 <@matches> It also actually mentions fractals
+23:39 <@matches> As a thing
+23:40 <@matches> In other news, extending the document we have at the moment to allow anything other than rectangles will be interesting
+23:41 <@matches> Did you do this on purpose? :P
+--- Day changed Wed May 07 2014
+12:32 <@matches> We need to do something about all the warnings generated by the magic OpenGL 3 stuff
+12:32 <@matches> It's making it hard to sport warnings that I actually care about
+12:33 <@matches> Like: You forgot to return a value in this function :S
+13:52 <@matches> Gah I did it again
+13:52 <@matches> auto is dangerous
+13:53 <@matches> Possibly because it's buggy
+13:53 <@matches> I can't actually see any compiler warnings at all
+17:39 <@matches> So you can almost maybe see a difference between beziers calculated using floats and doubles
+17:40 <@matches> If you squint
+17:40 <@matches> And view them on different monitors
+17:41 <@matches> Ah there we go
+17:41 <@matches> I successfully broke it
+17:42 <@matches> When you round to pixel positions it doesn't make a difference
+17:43 <@matches> But on the other hand if you calculate beziers using really big numbers they look wierd :P
+17:43 <@matches> That's important
+17:43 <@matches> Because if you have an arbitrary infinite document you might be at coordinate positions that are really big
+17:43 <@matches> Captain Obvious strikes again
+17:45 <@matches> I think I will make a video of a circle moving towards infinity
+17:45 <@matches> This probably won't help the literature view much but it's too tempting to resist
+17:46 <@matches> I gave up trying to deal with our document format so I currently just generate vector<pair<T, T> > and then map that to a bitmap :P
publisher={IBM Corp.}
}
-
+% Basically my favourite thing on triangle rasterization.
+% There are older ones, but this one makes sense.
+@misc{giesen2013triangle,
+ title={Triangle rasterization in practice},
+ author={Giesen, Fabien},
+ year={2013},
+ journal={The ryg blog},
+ type={Blog},
+ number={February 8},
+ howpublished={\url{http://fgiesen.wordpress.com/2013/02/08/triangle-rasterization-in-practice/}}
+}
+
+% A paper on polygon rasterization. Probably should find a nice textbook on
+% this.
+@article{pineda1988parallel,
+ title={A parallel algorthim for polygon rasterization},
+ author={Pineda, Juan},
+ journal={ACM Computer Graphics},
+ year={1988},
+ volume={22},
+ number={4},
+ pages={17--20},
+ publisher={ACM}
+}
%%%%%%%%%%%%%%%%%%%%%%%
% Floating-pt Precision
% GPU-y Stuff
%%%%%%%%%%%%%%%%%%%%%%%%
+% OpenGL 4.4 (core profile) spec.
+% The latest OpenGL spec.
+% See: http://www.opengl.org/registry/doc/glspec44.core.pdf
+@book{openglspec,
+ title={The OpenGL\textregistered Graphics System: A Specification},
+ author={Segal, Mark and Akely, Kurt and Leech, Jon},
+ year={2014},
+ publisher={The Kronos Group, Inc},
+ url={http://www.opengl.org/registry/doc/glspec44.core.pdf}
+}
+
% The valve paper on using signed distance fields, scaling them and then alpha testing
% them to have a smooth, defined boundary for "vector"-like effects.
% Also talks of using several channels in the image and running boolean operations on them
git.ucc.asn.au / ipdf / documents.git / commitdiff
UCC git Repository :: git.ucc.asn.au