Personal tools
You are here: Home Projects Internal Projects Arrangements of Bézier Curves
« June 2017 »
June
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
252627282930
Log in


Forgot your password?
 

Arrangements of Bézier Curves

intersection of letters
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.

Abstract

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.

 

Illustrations

 

arrangement of ten bezier 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.

Links

  • 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]

Contact

Ron Wein http://www.cs.tau.ac.il/~efif wein@post.tau.ac.il
Document Actions