Cairo bibliography

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:

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

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

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

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:

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.

We use a data-structure called Skiplists in the our implementation of Bentley-Ottmann:

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:

However, sometimes we do not rasterise at all and are able to write directly to a vector surface. For the capabilities of each you need to read the individual reference manuals: