summaryrefslogtreecommitdiff
path: root/BIBLIOGRAPHY
diff options
context:
space:
mode:
Diffstat (limited to 'BIBLIOGRAPHY')
-rw-r--r--BIBLIOGRAPHY109
1 files changed, 109 insertions, 0 deletions
diff --git a/BIBLIOGRAPHY b/BIBLIOGRAPHY
new file mode 100644
index 000000000..90a6cef20
--- /dev/null
+++ b/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