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 deCasteljau algorithm | |

"Outillages methodes calcul", P de Casteljau, technical | |

report, - Andre Citroen Automobiles SA, Paris, 1959 | |

That technical report might be "hard" to find, but fortunately | |

this algorithm will be described in any reasonable textbook on | |

computational geometry. Two that have been recommended by | |

cairo contributors are: | |

"Computational Geometry, Algorithms and Applications", M. de | |

Berg, M. van Kreveld, M. Overmars, M. Schwarzkopf; | |

Springer-Verlag, ISBN: 3-540-65620-0. | |

"Computational Geometry in C (Second Edition)", Joseph | |

O'Rourke, Cambridge University Press, ISBN 0521640105. | |

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 | |

[Again, see your favorite computational geometry | |

textbook. Should cite the name of the algorithm cairo uses | |

here, if it has a name.] | |

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, Proceedings 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. | |

We use a data-structure called Skiplists in the our implementation | |

of Bentley-Ottmann: | |

W. Pugh, Skip Lists: a Probabilistic Alternative to Balanced Trees, | |

Communications of the ACM, vol. 33, no. 6, pp.668-676, 1990. | |

http://citeseer.ist.psu.edu/pugh90skip.html | |

The random number generator used in our skip list implementation is a | |

very small generator by Hars and Petruska. The generator is based on | |

an invertable function on Z_{2^32} with full period and is described | |

in | |

Hars L. and Petruska G., | |

``Pseudorandom Recursions: Small and Fast Pseurodandom | |

Number Generators for Embedded Applications'', | |

Hindawi Publishing Corporation | |

EURASIP Journal on Embedded Systems | |

Volume 2007, Article ID 98417, 13 pages | |

doi:10.1155/2007/98417 | |

http://www.hindawi.com/getarticle.aspx?doi=10.1155/2007/98417&e=cta | |

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 |