source/libs/cairo/cairo-src/BIBLIOGRAPHY

   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():
   5
   6 Given a Bézier path, approximate it with line segments:
   7
   8         The deCasteljau algorithm
   9         "Outillages methodes calcul", P de Casteljau, technical
  10         report, - Andre Citroen Automobiles SA, Paris, 1959
  11
  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:
  16
  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.
  20
  21         "Computational Geometry in C (Second Edition)", Joseph
  22         O'Rourke, Cambridge University Press, ISBN 0521640105.
  23
  24 Then, if stroking, construct a polygonal representation of the pen
  25 approximating a circle (if filling skip three steps):
  26
  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.
  30
  31 Add points to that pen based on the initial/final path faces and take
  32 the convex hull:
  33
  34         Convex hull algorithm
  35
  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.]
  39
  40 Now, "convolve" the "tracing" of the pen with the tracing of the path:
  41
  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.
  46
  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:
  51
  52         John D. Hobby, Practical Segment Intersection with Finite
  53         Precision Output, Computation Geometry Theory and
  54         Applications, 13(4), 1999.
  55
  56         http://cm.bell-labs.com/who/hobby/93_2-27.pdf
  57
  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.
  62
  63 We use a data-structure called Skiplists in the our implementation
  64 of Bentley-Ottmann:
  65
  66         W. Pugh, Skip Lists: a Probabilistic Alternative to Balanced Trees,
  67         Communications of the ACM, vol. 33, no. 6, pp.668-676, 1990.
  68
  69         http://citeseer.ist.psu.edu/pugh90skip.html
  70
  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
  74 in
  75
  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
  83
  84         http://www.hindawi.com/getarticle.aspx?doi=10.1155/2007/98417&e=cta
  85
  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.
  90
  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).
  94
  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:
  98
  99         destination = (source IN mask) OP destination
 100
 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:
 105
 106         T. Porter & T. Duff, Compositing Digital Images Computer
 107         Graphics Volume 18, Number 3 July 1984 pp 253-259
 108
 109         http://keithp.com/~keithp/porterduff/p253-porter.pdf