Arrangements of Bézier Curves
|Computing the intersection of the characters 'm' and 'g'
in the Times New Roman font. The boundary of each
character is given as a chain of Bézier curves of degree
3 and 6. The intersecting regions are shaded.
We present the representations and algorithms that are needed for implementing arrangements of Bézier curves using exact arithmetic in the CGAL arrangement package. The implementation is efficient and complete, handling all degenerate cases. We make extensive use of the geometric properties of Bézier curves for filtering to avoid the prohibitive running times incurred by an indiscriminate usage of exact arithmetic. As a result, most operations are carried out using fast approximate methods, and only in degenerate (or near-degenerate) cases we resort to the exact, and more computationally-demanding, procedures. This is the first complete implementation that can construct arrangements of Bezier curves of any degree, and handle all degenerate cases in a robust manner, to the best of our knowledge. Integrated with the Boolean set-operation package in CGAL, our implementation can also compute Boolean operations on generalized polygons bounded by closed chains of Bézier curves.
|The arrangement induced by a set of 10 Bézier curves of degree 5. Most points are not computed in an exact manner and are drawn as small circles. Other points are drawn as small discs.|
- Iddo Hanniel and Ron Wein
An exact, complete and efficient computation of arrangements of Bézier curves.
In Proceedings of the Symposium on Solid and Physical Modeling (SPM), pages 253-263, 2007 [link] [bibtex]