[cairo-commit] 2 commits - BIBLIOGRAPHY RELEASING

Carl Worth cworth at kemper.freedesktop.org
Wed Nov 29 17:29:34 PST 2006

 BIBLIOGRAPHY |   70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 RELEASING    |    3 +-
 2 files changed, 72 insertions(+), 1 deletion(-)

New commits:
diff-tree d9fd942e4774aa29967f908001b62dbc987d2f66 (from 8f08daade0430bf965050a81e654aac2a2375b07)
Author: Carl Worth <cworth at cworth.org>
Date:   Wed Nov 29 17:18:50 2006 -0800

    Add an initial BIBLIOGRAPHY for cairo

new file mode 100644
index 0000000..ac7b942
--- /dev/null
@@ -0,0 +1,70 @@
+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
diff-tree 8f08daade0430bf965050a81e654aac2a2375b07 (from facffb7ea3e03d131a79486b80d4efc58c303b87)
Author: Carl Worth <cworth at cworth.org>
Date:   Wed Nov 29 17:15:29 2006 -0800

    RELEASING: Fix typo

index 3275972..dbf9df3 100644
@@ -90,7 +90,8 @@ Here are the steps to follow to create a
 	  If for some reason you lost this message, "make release-publish-message"
 	  prints it for you.
-7) Push the newly created tag out to the central tree wih a command something like:
+7) Push the newly created tag out to the central tree with a command
+   something like:
 	git push cairo X.Y.Z

More information about the cairo-commit mailing list