Chapter 2
Preliminaries

CGAL Editorial Board

This chapter lists the licenses under which the Cgal datastructures and algorithms are distributed, and the third party libraries on which Cgal depends, or for which Cgal provides interfaces. The chapter further explains how to control inlining, thread safety, code deprecation, checking of pre- and postconditions, and how to alter the failure behavior.

2.1   License Issues

Cgal is Open Source software, and consists of different parts covered by different licenses. In this section we explain the essence of the different licenses, as well as the rationale why we have chosen them.

The fact that Cgal is Open Source software does not mean that users are free to do whatever they want with the software. Using the software means to accept the license, which has the status of a contract between the user and the owner of the Cgal software. A more detailed description of the license terms is available in the Cgal software tarball.

2.1.1   QPL

The Qpl is an Open Source license that obliges you to distribute your software based on Qpled Cgal data structures. The rationale behind this is that we can claim access to your software. The license further obliges you to put your software under an Open Source license as well. The rationale behind is that we can distribute your software, even if this is not your intention. Finally, the Qpl requires that, if you modify Cgal, you distribute the modifications in the form of patches and you distribute the sources of your changes as well.

The exact license terms can be found at the Trolltech web site: http://doc.trolltech.com/4.3/qpl.html.

2.1.2   LGPL

The Lgpl is an Open Source license that obliges you to distribute modifications you make on Cgal software accessible to the users. There is no obligation to make the source code of software you build on top of Lgpled Cgal data structures available.

Currently the linear kernel, the support library, the halfedge data structure, the kinetic data structures, and the mesh subdivision framework are distributed under the Lgpl. The rationale behind is that we want to promote them as de facto standards.

The exact license terms can be found at the Free Software Foundation web site: http://www.gnu.org/copyleft/lesser.html.

2.1.3   Commercial Licenses

Users who cannot comply to the Open Source license terms can buy individual data structures under various commercial licenses from GeometryFactory: http://www.geometryfactory.com.

2.1.4   License Compatibility

The General Public License (Gpl) has a viral effect which makes it incompatible with the Qpl. For more information, please refer to the paragraph about the Qpl on the licenses web page of the Free Software Foundation (Fsf): http://www.fsf.org/licensing/licenses/index_html. It is therefore not possible to build a program including Gpl code and some Qpl parts of Cgal. In this case, if you are the copyright owner of the Gpl code, you can amend the license by adding an exception allowing the use of Cgal with it (see again the Fsf web page).

2.2   Third Party Software

In this section we list the software that is used by the various Cgal packages.

2.2.1   Standard Template Library

Cgal heavily uses the Stl, and in particular adopted many of its design ideas. The Stl comes with the compiler, but it is possible to use the compiler together with an alternative Stl implementation. You can find online documentation for the Stl at various web sites, e.g., http://www.sgi.com/tech/stl/, http://www.cplusplus.com/reference/stl/, or http://msdn.microsoft.com/en-us/library/1fe2x6kt(VS.71).aspx.

2.2.2   Boost

Boost is a collection of libraries. Cgal needs some of them, that is it is mandatory. If Boost is not already on your system, e.g., on Windows, you can download it from http://www.boost.org.

2.2.3   Blas

The blas (Basic Linear Algebra Subprograms) are routines that provide standard building blocks for performing basic vector and matrix operations. In Cgal, blas is required by the packages Estimation of Local Differential Properties and Approximation of Ridges and Umbilics only.

You can download the official release from http://www.netlib.org/blas/ or download optimized implementations from http://www.netlib.org/blas/faq.html#5. Alternatively, installing Taucs provides blas.

2.2.4   Lapack

lapack provides routines for solving systems of simultaneous linear equations, least-squares solutions of linear systems of equations, eigenvalue problems, and singular value problems. In Cgal, lapack is required by the packages Estimation of Local Differential Properties and Approximation of Ridges and Umbilics only.

You can download the official release from http://www.netlib.org/lapack/. Alternatively, installing Taucs customized for Cgal provides lapack.

2.2.5   GMP

A library for multi precision integers and rational numbers. Cgal offers adapters for these number types. The usage of the Gmp library is optional. If it is not already on your system, e.g., on Windows, you can download it from http://gmplib.org/ or from the download section of http://www.cgal.org.

2.2.6   MPFR

A library for multi precision floating point numbers. The usage of the Mpfr library is optional, and you must install it when you use Gmp. You can download Mpfr from http://www.mpfr.org or from the download section of http://www.cgal.org.

2.2.7   Leda

A library of efficient data structures and algorithms. Cgal offers adapters to the Leda number types. The usage is optional. It is available commercially from http://www.algorithmic-solutions.com, and there exists a binary ``free edition''.

2.2.8   Taucs

Taucs is a library of sparse linear solvers. In Cgal, it is used to improve the computations within the Planar Parameterization of Triangulated Surface Meshes package only.

The Taucs web site is http://www.tau.ac.il/~stoledo/taucs/.
The latest official version is Taucs version 2.2, September 4, 2003. Copyright (c) 2001, 2002, 2003 by Sivan Toledo, Tel-Aviv University, stoledo@tau.ac.il. All Rights Reserved.
See http://www.tau.ac.il/~stoledo/taucs/ for the license and the availability note.
Used by permission of Sivan Toledo.

The Cgal project provides a modified version of Taucs in the download section of http://www.cgal.org. This version fixes some bugs, supports 64-bit platforms and allows a simplified installation process. It also contains a complete lapack implementation.
CAUTION: Since version 3.3.1, Cgal is no longer compatible with the official release of Taucs (currently 2.2). Make sure to use the modified version provided in the download section.

2.2.9   OpenNL

OpenNL (Open Numerical Library) is a library to easily construct and solve sparse linear systems. It is the default solver of the Surface Mesh Parameterization package.

OpenNL's main page is http://www.loria.fr/~levy/software/.

Cgal includes a version of OpenNL in C++, made especially for Cgal by Bruno Lévy.

2.2.10   zlib

A data compression library. It is used in the examples of the Surface Mesh Generation package. If it is not already on your system, e.g., on Windows, you can download it from http://www.gzip.org/zlib.

2.2.11   Qt

Qt is a cross-platform application framework. The usage of Qt is optional, but note that it is used for many Cgal 2D as well as 3D demos.

As Qt is the layer underneath Kde, Qt is installed on many Linux systems. Otherwise you can download it from http://www.trolltech.com.

2.2.12   libQGLViewer

A 3D widget based on Qt 4's QGLWidget. It can be downloaded from http://www.libqglviewer.com/.

2.2.13   Coin

An implementation of Open Inventor. It is used in the demo of the Kinetic Data Structures package. You can download it from http://www.coin3d.org.

2.3   Marking of Advanced Features

In this manual you will encounter sections marked as follows.

Some functionality is considered more advanced. Such functionality is described in sections such as this one that are bounded by horizontal brackets.

2.4   Namespace CGAL

All names introduced by Cgal, especially those documented in these manuals, are in a namespace called CGAL, which is in global scope. A user can either qualify names from Cgal by adding CGAL::, e.g., CGAL::Point_2< CGAL::Homogeneous< int> >, make a single name from Cgal visible in a scope via a using statement, e.g., using CGAL::Cartesian;, and then use this name unqualified in this scope, or even make all names from namespace CGAL visible in a scope with using namespace CGAL;. The latter, however, is likely to give raise to name conflicts and is therefore not recommended.

2.5   Inclusion Order of Header Files

Not all compilers fully support standard header names. Cgal provides workarounds for these problems in CGAL/basic.h. Consequently, as a golden rule, you should always include CGAL/basic.h first in your programs (or CGAL/Cartesian.h, or CGAL/Homogeneous.h, since they include CGAL/basic.h first).

2.6   Compile-time Flags to Control Inlining

Making functions inlined can, at times, improve the efficiency of your code. However this is not always the case and it can differ for a single function depending on the application in which it is used. Thus Cgal defines a set of compile-time macros that can be used to control whether certain functions are designated as inlined functions or not. The following table lists the macros and their default values, which are set in one of the Cgal include files.

macro name default

CGAL_KERNEL_INLINE inline
CGAL_KERNEL_MEDIUM_INLINE
CGAL_KERNEL_LARGE_INLINE
CGAL_MEDIUM_INLINE inline
CGAL_LARGE_INLINE
CGAL_HUGE_INLINE

If you wish to change the value of one or more of these macros, you can simply give it a new value when compiling. For example, to make functions that use the macro CGAL_KERNEL_MEDIUM_INLINE inline functions, you should set the value of this macro to inline instead of the default blank.

2.7   Identifying the Version of CGAL

#include <CGAL/version.h>

Every release of Cgal defines the following preprocessor macros:

CGAL_VERSION
- a textual description of the current release (e.g., or 3.3 or 3.2.1 or 3.2.1-I-15), and
CGAL_VERSION_NR
- a numerical description of the current release such that more recent releases have higher number.

More precisely, it is defined as 1MMmmbiiii, where MM is the major release number (e.g. 03), mm is the minor release number (e.g. 02), b is the bug-fix release number (e.g. 0), and iiii is the internal release number (e.g. 0001). For public releases, the latter is defined as 1000. Examples: for the public release 3.2.4 this number is 1030241000; for internal release 3.2-I-1, it is 1030200001. Note that this scheme was modified around 3.2-I-30.

CGAL_VERSION_NUMBER(M,m,b)
- a function macro computing the version number macro from the M.m.b release version. Note that the internal release number is dropped here. Example: CGAL_VERSION_NUMBER(3,2,4) is equal to 1030241000.

2.8   Thread Safety

Cgal is progressively being made thread-safe. The guidelines which are followed are:

If the macro CGAL_HAS_THREADS is not defined, then Cgal assumes it can use any thread-unsafe code (such as static variables). By default, this macro is not defined, unless BOOST_HAS_THREADS or _OPENMP is defined. It is possible to force its definition on the command line, and it is possible to prevent its default definition by setting CGAL_HAS_NO_THREADS from the command line.

2.9   Code Deprecation

Sometimes, the Cgal project decides that a feature is deprecated. This means that it still works in the current release, but it will be removed in the next, or a subsequent release. This can happen when we have found a better way to do something, and we would like to reduce the maintenance cost of Cgal at some point in the future. There is a trade-off between maintaining backward compatibility and implementing new features more easily.

In order to help users manage the changes to apply to their code, we attempt to make Cgal code emit warnings when deprecated code is used. This can be done using some compiler specific features. Those warnings can be disabled by defining the macro CGAL_NO_DEPRECATION_WARNINGS. On top of this, we also provide a macro, CGAL_NO_DEPRECATED_CODE, which, when defined, disables all deprecated features. This allows users to easily test if their code relies on deprecated features.

2.10   Checks

Much of the Cgal code contains checks. For example, all checks used in the kernel code are prefixed by CGAL_KERNEL. Other packages have their own prefixes, as documented in the corresponding chapters. Some are there to check if the kernel behaves correctly, others are there to check if the user calls kernel routines in an acceptable manner.

There are four types of checks. The first three are errors and lead to a halt of the program if they fail. The last only leads to a warning.

Preconditions
check if the caller of a routine has called it in a proper fashion. If such a check fails it is the responsibility of the caller (usually the user of the library).
Postconditions
check if a routine does what it promises to do. If such a check fails it is the fault of this routine, so of the library.
Assertions
are other checks that do not fit in the above two categories.
Warnings
are checks for which it is not so severe if they fail.

By default, all of these checks are performed. It is however possible to turn them off through the use of compile time switches. For example, for the checks in the kernel code, these switches are the following: CGAL_KERNEL_NO_PRECONDITIONS, CGAL_KERNEL_NO_POSTCONDITIONS, CGAL_KERNEL_NO_ASSERTIONS and CGAL_KERNEL_NO_WARNINGS. So, in order to compile the file foo.cpp with the postcondition checks off, you can do:
CC -DCGAL_KERNEL_NO_POSTCONDITIONS foo.cpp

This is also preferably done by modifying your makefile by adding -DCGAL_KERNEL_NO_POSTCONDITIONS to the CXXFLAGS variable.

The name KERNEL in the macro name can be replaced by a package specific name in order to control assertions done in a given package. This name is given in the documentation of the corresponding package, in case it exists.

Note that global macros can also be used to control the behavior over the whole Cgal library:

Setting the macro CGAL_NDEBUG disables all checks. Note that the standard flag NDEBUG sets CGAL_NDEBUG, but it also affects the standard assert macro. This way, adding -DCGAL_NDEBUG to your compilation flags removes absolutely all checks. This is the default recommended setup for performing timing benchmarks for example.

Not all checks are on by default. All four types of checks can be marked as expensive or exactness checks (or both). These checks need to be turned on explicitly by supplying one or both of the compile time switches CGAL_KERNEL_CHECK_EXPENSIVE and CGAL_KERNEL_CHECK_EXACTNESS.

Expensive checks are, as the word says, checks that take a considerable time to compute. Considerable is an imprecise phrase. Checks that add less than 10 percent to the execution time of the routine they are in are not expensive. Checks that can double the execution time are. Somewhere in between lies the border line. Checks that increase the asymptotic running time of an algorithm are always considered expensive. Exactness checks are checks that rely on exact arithmetic. For example, if the intersection of two lines is computed, the postcondition of this routine may state that the intersection point lies on both lines. However, if the computation is done with doubles as number type, this may not be the case, due to round off errors. So, exactness checks should only be turned on if the computation is done with some exact number type.

2.10.1   Altering the Failure Behavior

As stated above, if a postcondition, precondition or assertion is violated, an exception is thrown, and if nothing is done to catch it, the program will abort. This behavior can be changed by means of the following function.

#include <CGAL/assertions_behaviour.h>

Failure_behaviour set_error_behaviour ( Failure_behaviour eb)

The parameter should have one of the following values.

enum Failure_behaviour { ABORT, EXIT, EXIT_WITH_SUCCESS, CONTINUE, THROW_EXCEPTION};
The THROW_EXCEPTION value is the default, which throws an exception.

If the EXIT value is set, the program will stop and return a value indicating failure, but not dump the core. The CONTINUE value tells the checks to go on after diagnosing the error. Note that since Cgal 3.4, CONTINUE has the same effect as THROW_EXCEPTION for errors (but it keeps its meaning for warnings), it is not possible anymore to let assertion failures simply continue (except by totally disabling them).

If the EXIT_WITH_SUCCESS value is set, the program will stop and return a value corresponding to successful execution and not dump the core.

The value that is returned by set_error_behaviour is the value that was in use before.

For warnings there is a separate routine, which works in the same way. The only difference is that for warnings the default value is CONTINUE.

Failure_behaviour set_warning_behaviour ( Failure_behaviour eb)

2.10.2   Control at a Finer Granularity

The compile time flags as described up to now all operate on the whole library. Sometimes you may want to have a finer control. Cgal offers the possibility to turn checks on and off with a bit finer granularity, namely the module in which the routines are defined. The name of the module is to be appended directly after the Cgal prefix. So, the flag CGAL_KERNEL_NO_ASSERTIONS switches off assertions in the kernel only, the flag CGAL_CH_CHECK_EXPENSIVE turns on expensive checks in the convex hull module. The name of a particular module is documented with that module.

2.10.3   Customizing how Errors are Reported

Normally, error messages are written to the standard error output. It is possible to do something different with them. To that end you can register your own handler. This function should be declared as follows.

void
my_failure_function (
const char *type,
const char *expression,
const char *file,
int line,
const char *explanation)

Your failure function will be called with the following parameters. type is a string that contains one of the words precondition, postcondition, assertion or warning. The parameter expression contains the expression that was violated. file and line contain the place where the check was made. The explanation parameter contains an explanation of what was checked. It can be NULL, in which case the expression is thought to be descriptive enough.

There are several things that you can do with your own handler. You can display a diagnostic message in a different way, for instance in a pop up window or to a log file (or a combination). You can also implement a different policy on what to do after an error. For instance, you can throw an exception or ask the user in a dialog whether to abort or to continue. If you do this, it is best to set the error behavior to CONTINUE, so that it does not interfere with your policy.

You can register two handlers, one for warnings and one for errors. Of course, you can use the same function for both if you want. When you set a handler, the previous handler is returned, so you can restore it if you want.

#include <CGAL/assertions.h>

Failure_function set_error_handler ( Failure_function handler)
Failure_function set_warning_handler ( Failure_function handler)

Example

#include <CGAL/assertions.h>

void my_failure_handler(
    const char *type,
    const char *expr,
    const char* file,
    int line,
    const char* msg)
{
    /* report the error in some way. */
}

void foo()
{
    CGAL::Failure_function prev;
    prev = CGAL::set_error_handler(my_failure_handler);
    /* call some routines. */
    CGAL::set_error_handler(prev);
}