Olivier Devillers (olivier.devillers@inria.fr)
Marc Glisse (marc.glisse@inria.fr)
Stefan Schirra
The layer of geometry kernels provides basic geometric entities of constant size1 and primitive operations on them. Each entity is provided as both a stand-alone class, which is parameterized by a kernel class, and as a type in the kernel class. Each operation in the kernel is provided via a functor class2 in the kernel class and also as either a member function or a global function. See [HHK+01] for more details about this design. Ideally, if the kernel provides all the primitives required, you can use any kernel as a traits class directly with your algorithm or data structure; see also Chapter 4. If you need primitives not provided by the kernel (yet), please read Section 3.4 below.
Cgal provides different kernels, they can differ by internal representation of objects (e.g. cartesian versus homogeneous) or provide different functionalities (e.g. circular kernel). When creating a new package, the authors have to specify clearly the requirements needed by the kernel used. For example they can specify the needs with respect to the arithmetic.
The authors may specify a targeted kernel in the list of predefined kernels (e.g. Exact_predicates_inexact_constructions_kernel).
Point coordinates can be represented in a homogeneous or cartesian way. The developer of a package can keep in mind that cartesian will be usually more space consuming, while homogeneous can be interesting if exact rational computations are needed. In any way, a package has to work with both representations.
Since Cgal uses homogeneous representation for affine geometry and not for projective geometry, the homogenizing coordinate is non zero. The cartesian representation corresponding to an homogeneous point (x0,x1,...,xd,w) is (x0/w,x1/w,...,xd/w). Hence, homogeneous representation is not unique; (αx,αy,αz,αw) is an alternative representation to (x,y,z,w) for any α ≠ 0. Internally, Cgal always maintains a non-negative homogenizing coordinate.
The classes for the geometric objects in the kernel have a standardized interface.
Whenever you need a predicate that is not present in the current kernel traits, you should first try to re-use the available predicates (you might rewrite the code or implement the new predicate using existing ones). If this is not feasible (especially for efficiency reasons), we have to decide on adding the new predicate to the kernel traits. If the new predicate is not too special, it will be added. Otherwise you cannot use the kernel as a traits class, but have to use additional traits.
See Section 3.1.1 on how to derive the homogeneous version of a predicate from the Cartesian version.
1 | In dimension d, an entity of size O(d) is considered to be of constant size. |
2 | A class which defines a member operator(). |
3 | Note that the dimension of an object might depend on its use. A line in the plane has dimension d-1. As a halfspace, it has dimension d. |