From 530ffd0b7d3c39757b20f00716e486b5caf89aff Mon Sep 17 00:00:00 2001 From: sanine Date: Wed, 12 Oct 2022 12:03:23 -0500 Subject: add cairo --- libs/cairo-1.16.0/BIBLIOGRAPHY | 109 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 109 insertions(+) create mode 100644 libs/cairo-1.16.0/BIBLIOGRAPHY (limited to 'libs/cairo-1.16.0/BIBLIOGRAPHY') diff --git a/libs/cairo-1.16.0/BIBLIOGRAPHY b/libs/cairo-1.16.0/BIBLIOGRAPHY new file mode 100644 index 0000000..90a6cef --- /dev/null +++ b/libs/cairo-1.16.0/BIBLIOGRAPHY @@ -0,0 +1,109 @@ +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 -- cgit v1.2.1