diff options
Diffstat (limited to 'libs/cairo-1.16.0/BIBLIOGRAPHY')
| -rw-r--r-- | libs/cairo-1.16.0/BIBLIOGRAPHY | 109 |
1 files changed, 0 insertions, 109 deletions
diff --git a/libs/cairo-1.16.0/BIBLIOGRAPHY b/libs/cairo-1.16.0/BIBLIOGRAPHY deleted file mode 100644 index 90a6cef..0000000 --- a/libs/cairo-1.16.0/BIBLIOGRAPHY +++ /dev/null @@ -1,109 +0,0 @@ -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 |