This project demonstrates how the CGAL library and the IRIT library can be interfaced to construct arrangements of free-form curves.
The figures below show screen captures from the demo program. The demo program can be downloaded from here, and the source code can be found here. Read also the Compilation Manual and User Manual.
The left figure above shows an arrangement of 8 cubic B-Spline curves, where each edge of the arrangement is distinguished by a different color. The right figure displays the (enlarged) face that is the result of locating a point in the arrangement using the built-in point location function. The arrangement has 12 faces, 45 edges, and 35 vertices.
The left figure above shows an arrangement of 10 cubic B-Spline curves. The right figure shows the result of the point location query. The arrangement has 40 faces, 110 edges and 72 vertices.
The figures above show an arrangement of 20 quadratic Bezier curves, containing 51 faces, 173 edges and 125 vertices.
CGAL Arrangements
CGAL 2D arrangements package is a generic data structure supporting various operations. Given a set of (not necessarily x-monotone and possibly intersecting) curves, it constructs the arrangement data structure that enables easy traversal over the edges, faces and vertices of the arrangement and efficient location of a point in the arrangement. For a full survey of the operations supported by the package refer to the CGAL manual.
CGAL is a C++ library that uses the generic programming paradigm in order to achieve flexibility and genericity. Every algorithm and data structure in CGAL is parameterized by a so-called geometric traits class, in which the basic geometric functionality is implemented. The use of the C++ template mechanism enables the usage of different traits classes with the same algorithm. Thus, users can use CGAL’s algorithm’s with their own objects without having to implement the algorithm from the beginning. All that is needed is to implement the relevant traits class and parameterize the algorithm with it. For further information on the design and implementation of CGAL, and on the usage of generic programming within it refer to, e.g., here.
The traits class of the arrangement package enables even more flexibility than other CGAL packages. The arrangement traits specifications enables arrangements of different types of curves. Traits classes that have already been implemented include traits classes for arrangements of line-segments, circular-arcs, polygonal lines, and conic sections. There have also been other implementations of arrangement traits classes for different handling of robustness issues or for more specific projects.
Our project implements a traits class for arrangements of free-form curves using the IRIT library.
Project Contents
The project uses the generic CGAL arrangement package and implements an interface to the IRIT solid modeling environment, thus enabling to use the arrangement data structure and algorithms with IRIT’s free-form curves. The demo program consists of three modules:
- Arr_Irit_Traits—The module that implements the geometric traits CLASS using the IRIT library.
- IritIO—The module that implements basic display functions using IRIT’s display mechanisms.
- IritArrDemo—The main() module – calls the arrangement construction from input curves, displays the colored arrangement (see figures above), and performs a point location query (if requested).
Interface to IRIT
The interface to IRIT is performed in the Arr_Irit_traits class found in the file Arr_Irit_traits.h. In this class we implement the 25 basic geometric functions that are needed by the Arrangement_2 class.
Since IRIT is written in C and CGAL is a C++ library, we had to interface between the C memory handling used in IRIT (malloc/free) and CGAL’s C++ memory handling. In particular, CGAL assumes in its data structures and algorithms (similarly to the C++ standard library), that the object it deals with have C++ constructors, destructors and assignment operators. In order to maintain this we had to implement wrapper classes that encapsulated the IRIT points and curves and handled their memory allocation.
IRIT was also used for graphical output. We implemented the IritIO class as a convenient C++ interface to the IRIT graphical capabilities, enabling us to draw curves, points and polygons in the IRIT window.
Most of the functionality we needed was found in the IRIT cagd_lib library. This included construction and handling of Bezier and B-Spline curves and basic operations such as computing derivatives and curve evaluation at a given parameter. IRIT’s cagd library also contains higher level functionality such as curve-curve intersection (CCI), which were also used. In some cases we used the symb_lib library, which performs higher level operations on curves and surfaces, e.g., computing the zero set of a given coordinate. This was needed when we wanted to find all points of zero x-tangency for splitting the curve into x-monotone subcurves.
The list of IRIT functions used in the traits class are:
- Low Level Functions and Macros—CagdPtNew/Free, CagdCrvNew/Free, CagdCrvDomain, PT2D_PT2D_DIST_SQR, CROSS_PROD_2D and IRIT list handling functionality.
- Basic Cagd Curve manipulation—CagdCrvEval, CagdCrvDerive, CagdCrvReverse, CagdCrvsSame.
- High Level Curve Functionality—CagdCrvSubdivAtParam, CagdCrvCrvInter, SymbCrvConstSet, SymbDistCrvPoint.