summaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
authorEmmanuele Bassi <ebassi@gnome.org>2023-01-30 15:17:26 +0000
committerEmmanuele Bassi <ebassi@gnome.org>2023-02-02 08:37:29 +0100
commit98fa4be56b80a2add1d1f65325c060b1f4cae7e2 (patch)
tree6c998801a957d8eab758ebc6381832a61a1e93ba /doc
parentd86a22db6d512b344a61843107f888d6f12c98fe (diff)
downloadcairo-98fa4be56b80a2add1d1f65325c060b1f4cae7e2.tar.gz
docs: Update the bibliography
Port to Markdown.
Diffstat (limited to 'doc')
-rw-r--r--doc/bibliography.md128
1 files changed, 61 insertions, 67 deletions
diff --git a/doc/bibliography.md b/doc/bibliography.md
index 90a6cef20..f3452243a 100644
--- a/doc/bibliography.md
+++ b/doc/bibliography.md
@@ -1,109 +1,103 @@
+# Bibliography
+
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():
+`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
+- 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:
+Note: 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, 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.
+- "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.
+- "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:
+Add points to that pen based on the initial/final path faces and take the
+convex hull:
- Convex hull algorithm
+- 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.]
+[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.
+- "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
+- 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.
+We use a data-structure called Skiplists in the our implementation of
+Bentley-Ottmann:
- http://citeseer.ist.psu.edu/pugh90skip.html
+- 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
+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
+- 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>
- 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.
+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).
+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
+destination into cairo's fundamental rendering equation. The most basic form
+of this equation is:
-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:
+ destination = (source IN mask) OP destination
- T. Porter & T. Duff, Compositing Digital Images Computer
- Graphics Volume 18, Number 3 July 1984 pp 253-259
+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:
- http://keithp.com/~keithp/porterduff/p253-porter.pdf
+- 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>