Conformal Geometric Algebra Package

 Master thesis project: Conformal Geometric Algebra Package Author: Chaïm Zonnenberg Thesis supervisor: Remco Veltkamp Master program: Game and Media Technology Date submitted: July 2007

Keywords:
CGA, CGAL, CGAP, geometry, library, flags, Edelsbrunner algorithm, Voronoi diagram, Delaunay triangulation, multidimensional

Contents of this website:

Description of the project

Conformal Geometric Algebra (CGA) is a relatively new geometric model that can represent geometric primitives, like planes, lines, points, spheres and circles. It offers a language (algebra) of operations to manipulate those primitives. Nowadays, linear algebra is mostly used in computational geometry to perform geometric operations. However, CGA offers many advantages above linear algebra. The large matrix multiplications of linear algebra can be replaced by simple formula expressions. The geometric expressions/formulas in CGA are more intuitive, less bug-sensitive and easier to understand. Besides that, the expressions are independent of dimension, so expressions that yield in 2D, also yield in 5D.

CGAL (www.cgal.org) is a C++ library that provides easy access to geometric algorithms. CGAL is used in various areas needing geometric computation, such as computer graphics. By default, the geometric primitives and operations are implemented by a cartesian or homogenous kernel, based on linear algebra methods. However, it offers the possibility to implement user-defined kernels.

In this master thesis project a CGA-kernel has been modelled and partly implemented for the CGAL-library. In this CGA-kernel the advantages of CGAL and CGA have been combined. With the help of this kernel, many geometric algorithms that are present in CGAL, can be made available in CGA-language. And scientists that use CGAL, can re-implement their algorithms in the simple expressions of CGA. As an example, algorithms for Delaunay triangulations and Voronoi diagrams have been implemented in dimensions 2D, 3D and nD. This project has been called the name 'Conformal Geometric Algebra Package'.

Besides that, specific research has been done for the use of so called 'flags' in high-dimensional polytope algorithms. As an application of the CGAP-library, an example of this is given in the thesis for high dimensional Voronoi diagrams in combination with Conformal Geometric Algebra.

This package is provided "as is", and is supported.

Screenshots of the demo applications

 Delaunay 2D app Delaunay 3D app Voronoi&CGA-Flags 2D app Voronoi&CGA-Flags 3D app