[cairo] Updated bibliography for cairo

[Mathieu Lacage]

On Wed, 2006-11-29 at 17:35 -0800, Carl Worth wrote:
> 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():

I usually recommend the following textbook for a good visual
introduction to some of the topics you talk about below.

"Computational Geometry, Algorithms and Applications"
by de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O. 



> 
> Given a Bézier path, approximate it with line segments:
> 
> 	The deCastlejau algorithm
> 	[need a citation here]

The original work was never published other than through internal memos:
"Outillages methodes calcul",
P de Casteljau, technical report, - Andre Citroen Automobiles SA, Paris,
1959 



> 
> 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
> _______________________________________________
> cairo mailing list
> cairo at cairographics.org
> http://cairographics.org/cgi-bin/mailman/listinfo/cairo
--