Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Chapter 2
Kernel Representations

Our object of study is the

d-dimensional affine Euclidean space. Here we are mainly concerned with cases

d=2 and

d=3. Objects in that space are sets of points. A common way to represent the points is the use of Cartesian coordinates, which assumes a reference frame (an origin and

d orthogonal axes). In that framework, a point is represented by a

d-tuple

(c

₀,c₁,...,c_d-1), and so are vectors in the underlying linear space. Each point is represented uniquely by such Cartesian coordinates. Another way to represent points is by homogeneous coordinates. In that framework, a point is represented by a

(d+1)-tuple

(h

₀,h₁,...,h_d). Via the formulae

c

_i=h_i/h_d, the corresponding point with Cartesian coordinates

(c

₀,c₁,...,c_d-1) can be computed. Note that homogeneous coordinates are not unique. For

lambda != 0

, the tuples

(h

₀,h₁ ,...,h_d) and

(lambda  h

₀,lambda h₁,...,lambda h_d) represent the same point. For a point with Cartesian coordinates

(c

₀,c₁,...,c_d-1) a possible homogeneous representation is

(c

₀,c₁,...,c_d-1,1). Homogeneous coordinates in fact allow to represent objects in a more general space, the projective space

P

_d. In CGAL, we do not compute in projective geometry. Rather, we use homogeneous coordinates to avoid division operations, since the additional coordinate can serve as a common denominator.

2.1 Genericity through Parameterization

Almost all the kernel objects (and the corresponding functions) are templates with a parameter that allows the user to choose the representation of the kernel objects. A type that is used as an argument for this parameter must fulfill certain requirements on syntax and semantics. The list of requirements defines an abstract kernel concept. For all kernel objects Object , the types CGAL::Object<Kernel> and Kernel::Object are identical.

CGAL offers four families of concrete models for the concept Kernel, two based on the Cartesian representation of points and two based on the homogeneous representation of points. The interface of the kernel objects is designed such that it works well with both Cartesian and homogeneous representation. For example, points in 2D have a constructor with three arguments as well (the three homogeneous coordinates of the point). The common interfaces parameterized with a kernel class allow one to develop code independent of the chosen representation. We said ``families'' of models, because both families are parameterized too. A user can choose the number type used to represent the coordinates.

For reasons that will become evident later, a kernel class provides two typenames for number types, namely Kernel::FT and Kernel::RT. The type Kernel::FT must fulfill the requirements on what is called a FieldNumberType in CGAL. This roughly means that Kernel::FT is a type for which operations +, -, * and / are defined with semantics (approximately) corresponding to those of a field in a mathematical sense. Note that, strictly speaking, the built-in type int does not fullfil the requirements on a field type, since ints correspond to elements of a ring rather than a field, especially operation / is not the inverse of *. The requirements on the type Kernel::RT are weaker. This type must fulfill the requirements on what is called a RingNumberType in CGAL. This roughly means that Kernel::RT is a type for which operations +, -, * are defined with semantics (approximately) corresponding to those of a ring in a mathematical sense.

2.2 Cartesian Kernels

With Cartesian<FieldNumberType> you can choose a Cartesian representation of coordinates. When you choose Cartesian representation you have to declare at the same time the type of the coordinates. A number type used with the Cartesian representation class should be a FieldNumberType as described above. As mentioned above, the built-in type int is not a FieldNumberType. However, for some computations with Cartesian representation, no division operation is needed, i.e., a RingNumberType is sufficient in this case. With Cartesian<FieldNumberType>, both Cartesian<FieldNumberType>::FT and Cartesian<FieldNumberType>::RT are mapped to FieldNumberType.

Cartesian<FieldNumberType> uses reference counting internally to save copying costs. CGAL also provides Simple_cartesian<FieldNumberType>, a kernel that uses Cartesian representation but no reference counting. Debugging is easier with Simple_cartesian<FieldNumberType>, since the coordinates are stored within the class and hence direct access to the coordinates is possible. Depending on the algorithm, it can also be slightly more or less efficient than Cartesian<FieldNumberType>. Again, in Simple_cartesian<FieldNumberType> both Simple_cartesian<FieldNumberType>::FT and Simple_cartesian<FieldNumberType>::RT are mapped to FieldNumberType.

2.3 Homogeneous Kernels

Homogeneous coordinates permit to avoid division operations in numerical computations, since the additional coordinate can serve as a common denominator. Avoiding divisions can be useful for exact geometric computation. With Homogeneous<RingNumberType> you can choose a homogeneous representation for the coordinates of the kernel objects. As for the Cartesian representation, one has to declare the type used to store the coordinates. Since the homogeneous representation does not use divisions, the number type associated with a homogeneous representation class must be a model for the weaker concept RingNumberType only. However, some operations provided by this kernel involve divisions, for example computing squared distances or Cartesian coordinates. To keep the requirements on the number type parameter of Homogeneous low, the number type Quotient<RingNumberType> is used for operations that require divisions. This number type can be viewed as an adaptor which turns a RingNumberType into a FieldNumberType. It maintains numbers as quotients, i.e., a numerator and a denominator. With Homogeneous<RingNumberType>, Homogeneous<RingNumberType>::FT is equal to Quotient<RingNumberType>, while Homogeneous<RingNumberType>::RT is equal to RingNumberType.

Homogeneous<RingNumberType> uses reference counting internally to save copying costs. CGAL also provides Simple_homogeneous<RingNumberType>, a kernel that uses homogeneous representation but no reference counting. Debugging is easier with Simple_homogeneous<RingNumberType>, since the coordinates are stored within the class and hence direct access to the coordinates is possible. Depending on the algorithm, it can also be slightly more or less efficient than Homogeneous<RingNumberType>. Again, in Simple_homogeneous<RingNumberType> the type Simple_homogeneous<RingNumberType>::FT is equal to Quotient<RingNumberType> while Simple_homogeneous<RingNumberType>::RT is equal to RingNumberType.

2.4 Naming conventions

The use of kernel classes not only avoids problems, it also makes all CGAL classes very uniform. They always consist of:

The capitalized base name of the geometric object, such as Point, Segment, or Triangle.
An underscore followed by the dimension of the object, for example _2, _3, or _d.
A kernel class as parameter, which itself is parameterized with a number type, such as Cartesian<double> or Homogeneous<leda_integer>.

2.5 Kernel as a Traits Class

Algorithms and data structures in the basic library of CGAL are parameterized by a traits class that subsumes the objects on which the algorithm or data structure operates as well as the operations to do so. For most of the algorithms and data structures in the basic library you can use a kernel as a traits class. For some algorithms you even do not have to specify the kernel; it is detected automatically using the types of the geometric objects passed to the algorithm. In some other cases, the algorithms or data structures needs more than is provided by the kernel concept. In these cases, a kernel can not be used as a traits class.

2.6 Choosing a Kernel and Predefined Kernels

If you start with integral Cartesian coordinates, many geometric computations will involve integral numerical values only. Especially, this is true for geometric computations that evaluate only predicates, which are tantamount to determinant computations. Examples are triangulation of point sets and convex hull computation. In this case, the Cartesian representation is probably the first choice, even with a ring type. You might use limited precision integer types like int or long, use double to present your integers (they have more bits in their mantissa than an int and overflow nicely), or an arbitrary precision integer type like the wrapper Gmpz for the GMP integers, leda_integer, or MP_Float. Note, that unless you use an arbitrary precision ring type, incorrect results might arise due to overflow.

If new points are to be constructed, for example the intersection point of two lines, computation of Cartesian coordinates usually involves divisions. Hence, one needs to use a FieldNumberType with Cartesian representation, or alternatively, switch to homogeneous representation. The type double is a - though imprecise - model for FieldNumberType. You can also put any RingNumberType into the Quotient adaptor to get a field type which then can be put into Cartesian. But using homogeneous representation on the RingNumberType is usually the better option. Other valid FieldNumberTypes are leda_rational and leda_real.

If it is crucial for you that the computation is reliable, the right choice is probably a number type that guarantees exact computation. The Filtered_kernel provides a way to apply filtering techniques [BBP01] to achieve a kernel with exact and efficient predicates. Still other people will prefer the built-in type double, because they need speed and can live with approximate results, or even algorithms that, from time to time, crash or compute incorrect results due to accumulated rounding errors.

Predefined kernels. For the user's convenience, CGAL provides 3 typedefs to generally useful kernels.

They are all Cartesian kernels.
They all support constructions of points from double Cartesian coordinates.
All these 3 kernels provide exact geometric predicates.
They handle geometric constructions differently:
- Exact_predicates_exact_constructions_kernel: provides exact geometric constructions, in addition to exact geometric predicates.
- Exact_predicates_exact_constructions_kernel_with_sqrt: same as Exact_predicates_exact_constructions_kernel, but the number type it provides (Exact_predicates_exact_constructions_kernel_with_sqrt::FT) supports the square root operation exactly ¹.
- Exact_predicates_inexact_constructions_kernel: provides exact geometric predicates, but geometric constructions may be inexact due to roundoff errors. It is however enough for most CGAL algorithms, and faster than both Exact_predicates_exact_constructions_kernel and Exact_predicates_exact_constructions_kernel_with_sqrt.

Footnotes

¹ Currently it requires having either LEDA or CORE installed

Next chapter: Kernel Geometry

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .


¹	Currently it requires having either LEDA or CORE installed

Chapter 2Kernel Representations