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:
Lifting a point to a paraboloid in 2D

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


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

Downloads

Masters thesis PS PDF
CGAP user & reference manual PS PDF
CGAP source code & demos & binaries
  Supports GCC and MS Visual Studio 2005
ZIP
Master thesis presentation PDF


Links

Geometric Algebra
University of Amsterdam,
  GA Research
Website of Leo Dorst (University of Amsterdam) about CGA
GAIGEN A C++-code generator for Geometric Algebras (up to dimension 8)
Euclidian Geometric Algebra
  and Quaternions
Geometric Algebra applied to OpenGL
Geometric Calculus David Hestenes' Geometric Algebra site
Geometric Algebra research group Geometric Algebra research group at the University of Cambridge, England.
 
CGAL
CGAL Computational Geometry Algorithms Library website
CGAL Reference manual Reference manual of CGAL
 
C++-programming
Boost C++-Libraries
  and Documentation
The CGAL-library uses some pieces of this library.
OpenGL Official website OpenGL, including downloads, tutorials etc.
OpenGL Tutorial  
 
Voronoi, Delaunay, Convex Hull
Computational Geometry:
  Delaunay Triagulations and
  Voronoi Diagrams
Links and Java applets
Convex hull links Arbitrary dimensional convex hull, Voronoi diagram, Delaunay triangulation links