1 Here's an effort to document some of the academic work that was
2 referenced during the implementation of cairo. It is presented in the
3 context of operations as they would be performed by either
4 cairo_stroke() or cairo_fill():
6 Given a Bézier path, approximate it with line segments:
8 The deCasteljau algorithm
9 "Outillages methodes calcul", P de Casteljau, technical
10 report, - Andre Citroen Automobiles SA, Paris, 1959
12 That technical report might be "hard" to find, but fortunately
13 this algorithm will be described in any reasonable textbook on
14 computational geometry. Two that have been recommended by
15 cairo contributors are:
17 "Computational Geometry, Algorithms and Applications", M. de
18 Berg, M. van Kreveld, M. Overmars, M. Schwarzkopf;
19 Springer-Verlag, ISBN: 3-540-65620-0.
21 "Computational Geometry in C (Second Edition)", Joseph
22 O'Rourke, Cambridge University Press, ISBN 0521640105.
24 Then, if stroking, construct a polygonal representation of the pen
25 approximating a circle (if filling skip three steps):
27 "Good approximation of circles by curvature-continuous Bezier
28 curves", Tor Dokken and Morten Daehlen, Computer Aided
29 Geometric Design 8 (1990) 22-41.
31 Add points to that pen based on the initial/final path faces and take
36 [Again, see your favorite computational geometry
37 textbook. Should cite the name of the algorithm cairo uses
38 here, if it has a name.]
40 Now, "convolve" the "tracing" of the pen with the tracing of the path:
42 "A Kinetic Framework for Computational Geometry", Leonidas
43 J. Guibas, Lyle Ramshaw, and Jorge Stolfi, Proceedings of the
44 24th IEEE Annual Symposium on Foundations of Computer Science
45 (FOCS), November 1983, 100-111.
47 The result of the convolution is a polygon that must be filled. A fill
48 operations begins here. We use a very conventional Bentley-Ottmann
49 pass for computing the intersections, informed by some hints on robust
50 implementation courtesy of John Hobby:
52 John D. Hobby, Practical Segment Intersection with Finite
53 Precision Output, Computation Geometry Theory and
54 Applications, 13(4), 1999.
56 http://cm.bell-labs.com/who/hobby/93_2-27.pdf
58 Hobby's primary contribution in that paper is his "tolerance square"
59 algorithm for robustness against edges being "bent" due to restricting
60 intersection coordinates to the grid available by finite-precision
61 arithmetic. This is one algorithm we have not implemented yet.
63 We use a data-structure called Skiplists in the our implementation
66 W. Pugh, Skip Lists: a Probabilistic Alternative to Balanced Trees,
67 Communications of the ACM, vol. 33, no. 6, pp.668-676, 1990.
69 http://citeseer.ist.psu.edu/pugh90skip.html
71 The random number generator used in our skip list implementation is a
72 very small generator by Hars and Petruska. The generator is based on
73 an invertable function on Z_{2^32} with full period and is described
76 Hars L. and Petruska G.,
77 ``Pseudorandom Recursions: Small and Fast Pseurodandom
78 Number Generators for Embedded Applications'',
79 Hindawi Publishing Corporation
80 EURASIP Journal on Embedded Systems
81 Volume 2007, Article ID 98417, 13 pages
82 doi:10.1155/2007/98417
84 http://www.hindawi.com/getarticle.aspx?doi=10.1155/2007/98417&e=cta
86 From the result of the intersection-finding pass, we are currently
87 computing a tessellation of trapezoids, (the exact manner is
88 undergoing some work right now with some important speedup), but we
89 may want to rasterize directly from those edges at some point.
91 Given the set of tessellated trapezoids, we currently execute a
92 straightforward, (and slow), point-sampled rasterization, (and
93 currently with a near-pessimal regular 15x17 grid).
95 We've now computed a mask which gets fed along with the source and
96 destination into cairo's fundamental rendering equation. The most
97 basic form of this equation is:
99 destination = (source IN mask) OP destination
101 with the restriction that no part of the destination outside the
102 current clip region is affected. In this equation, IN refers to the
103 Porter-Duff "in" operation, while OP refers to a any user-selected
104 Porter-Duff operator:
106 T. Porter & T. Duff, Compositing Digital Images Computer
107 Graphics Volume 18, Number 3 July 1984 pp 253-259
109 http://keithp.com/~keithp/porterduff/p253-porter.pdf