[cairo] Updated bibliography for cairo

[Carl Worth]

Someone recently asked me for some pointers to readings on the
algorithms implemented in cairo. After I wrote a reply I thought
others might also want to look at it, so I shoved it into a top-level
file in the source repository named BIBLIOGRAPHY and linked in into
the cairo wiki, (in the place of an older "bibliography"), page with
much less content.

The version I posted can be seen here:

	http://cairographics.org/BIBLIOGRAPHY

And is also copied below.

As people improve or implement new algorithms, it would be great to
update this document as well. The URL above will always reflect the
latest version of the file as pushed out into the master branch of
cairo's central repository.

-Carl

Here's an effort to document some of the academic work that was
referenced during the implementation of cairo. It is presented in the
context of operations as they would be performed by either
cairo_stroke() or cairo_fill():

Given a Bézier path, approximate it with line segments:

	The deCastlejau algorithm
	[need a citation here]

Then, if stroking, construct a polygonal representation of the pen
approximating a circle (if filling skip three steps):

	"Good approximation of circles by curvature-continuous Bezier
	curves", Tor Dokken and Morten Daehlen, Computer Aided
	Geometric Design 8 (1990) 22-41.

Add points to that pen based on the initial/final path faces and take
the convex hull:

	Convex hull algorithm
	[need a citation here]

Now, "convolve" the "tracing" of the pen with the tracing of the path:

	"A Kinetic Framework for Computational Geometry", Leonidas
        J. Guibas, Lyle Ramshaw, and Jorge Stolfi, Proceeding of the
        24th IEEE Annual Symposium on Foundations of Computer Science
        (FOCS), November 1983, 100-111.

The result of the convolution is a polygon that must be filled. A fill
operations begins here. We use a very conventional Bentley-Ottmann
pass for computing the intersections, informed by some hints on robust
implementation courtesy of John Hobby:

	John D. Hobby, Practical Segment Intersection with Finite
	Precision Output, Computation Geometry Theory and
	Applications, 13(4), 1999.

	http://cm.bell-labs.com/who/hobby/93_2-27.pdf

Hobby's primary contribution in that paper is his "tolerance square"
algorithm for robustness against edges being "bent" due to restricting
intersection coordinates to the grid available by finite-precision
arithmetic. This is one algorithm we have not implemented yet.

From the result of the intersection-finding pass, we are currently
computing a tessellation of trapezoids, (the exact manner is
undergoing some work right now with some important speedup), but we
may want to rasterize directly from those edges at some point.

Given the set of tessellated trapezoids, we currently execute a
straightforward, (and slow), point-sampled rasterization, (and
currently with a near-pessimal regular 15x17 grid).

We've now computed a mask which gets fed along with the source and
destination into cairo's fundamental rendering equation. The most
basic form of this equation is:

	destination = (source IN mask) OP destination

with the restriction that no part of the destination outside the
current clip region is affected. In this equation, IN refers to the
Porter-Duff "in" operation, while OP refers to a any user-selected
Porter-Duff operator:

	T. Porter & T. Duff, Compositing Digital Images Computer
	Graphics Volume 18, Number 3 July 1984 pp 253-259

	http://keithp.com/~keithp/porterduff/p253-porter.pdf
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20061129/ef78c2eb/attachment-0001.pgp