cairo/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 From the result of the intersection-finding pass, we are currently
  72 computing a tessellation of trapezoids, (the exact manner is
  73 undergoing some work right now with some important speedup), but we
  74 may want to rasterize directly from those edges at some point.
  75
  76 Given the set of tessellated trapezoids, we currently execute a
  77 straightforward, (and slow), point-sampled rasterization, (and
  78 currently with a near-pessimal regular 15x17 grid).
  79
  80 We've now computed a mask which gets fed along with the source and
  81 destination into cairo's fundamental rendering equation. The most
  82 basic form of this equation is:
  83
  84         destination = (source IN mask) OP destination
  85
  86 with the restriction that no part of the destination outside the
  87 current clip region is affected. In this equation, IN refers to the
  88 Porter-Duff "in" operation, while OP refers to a any user-selected
  89 Porter-Duff operator:
  90
  91         T. Porter & T. Duff, Compositing Digital Images Computer
  92         Graphics Volume 18, Number 3 July 1984 pp 253-259
  93
  94         http://keithp.com/~keithp/porterduff/p253-porter.pdf