Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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