GMacDSL Affine Geometry Sample

-- Download GMacDSL Affine Geometry Sample as PDF --

Affine Geometry FractalAffine Geometry is one of the common mathematical representations used in many geometric modeling applications in computer science and engineering. The two most important primitive geometric concepts of Affine Geometry are points and directions. In classical representations, both are encoded using coordinate vectors having two meanings but similar numerical forms: the position vectors for points, and the free vectors for directions. Affine Transformations can be defined on positions and directions to produce other positions and directions. The two primitives and their affine transformations construct a full Affine Space useful for many practical applications.

The samples described on this page illustrate how to use GMacDSL for encoding 3D affine primitives and transformations using the simplest of all geometric algebras: the 3D Euclidean GA having 8-dimenstional multivectors. The equations used here are based on Ronald Goldman‘s nice book: “An Integrated Introduction to Computer Graphics and Geometric Modeling“. I really enjoyed teaching a post-graduate Geometric Modeling course based on this book. We will explore using GMacDSL for this task, and see how the selection of our algebra can seriously limit our ability to write geometric computing code regardless of the selected programming language.

Affine Transformations on Points and Vectors

The following GMacDSL code can be compiled in all 3 editions of GMac. The code contains several macros defined on the 3D Euclidean Geometric Algebra. The macros define some affine transforms on points (positions) and vectors (directions). 3D Euclidean GA is not the best GA space for compactly representing affine geometry. Algebraically, the best space for representing any geometry is a space where GA blades represent the main geometric primitives, and the geometric transformations are fully represented as orthogonal transforms using GA versors. The second best thing is to use outermorphisms to represent the main geometric transformations. Nevertheless, the Euclidean GA is conceptually simple to understand for anyone starting to learn to model with geometric algebra. In addition, learning GMacDSL is easier when coding with a familiar GA space.

Code Listing 1

Adding Combinatorial Geometric Objects

Points and vectors are just a base for making more complex geometric objects in affine geometry. 3D Frames, Lines, and planes can’t be represented by a single coordinate vector in 3D Euclidean space. All points on a line can be generated by defining two points, or a point and a vector. All points on a plane can be defined using a point and a normal, 3 non-colinear points, or a point and two non-parallel vectors. Consequently, no single multivector in our simple GA can represent a general line or plane. We can use GMacDSL structures for this task. Using structures require the GMac Basic or GMac Complete Editions. The following code can be added to the previous code to implement transformations on frames, lines, and planes in affine space:

Code Listing 2

In code listing 2 we can immediately see why the 3D Euclidean Geometric Algebra is not suitable for dealing with affine transformations. We selected to implement 3 kinds of basic geometric concepts:

  1. A Frame consisting of an origin point and 3 vectors that are usually orthogonal to each other, of unit length, and make a right-handed coordinates system
  2. An infinite Straight Line generated by two points or a point and a direction vector
  3. An infinite Flat Plane generated by 3 points or a point and a normal vector

The first thing we notice is that the same concept (for example a line) can be specified using several simpler concepts (2 points or a point plus a vector). We can call the set of simpler concepts “the generators” of our concept (the line). Any point on the line can be obtained using its generators using some sort of algebraic manipulations specific to our concept. This fundamental geometric representation reality results in the following problems, not related to our programming language, but rather to the underlying algebra:

  • Problem 1: There are many sets of generators for a single main geometric concept. Each set can be useful for some geometric manipulations of the main geometric concept. For example, a plane (the main geometric concept) can be generated using 3 non-colinear points, one point and a normal vector, two points and a vector, one point and two non-parallel vectors, two intersecting lines, a point and a line not passing through it, etc. Some tasks on the plane would be easier to perform using its 3-points form, but harder or not possible using its point and normal form
  • Problem 2: If we select a number of generator sets for some main concept, we must write code to convert these generator sets to each other. As in code listing 2, we must convert between the 2-points representation of a line and the point-vector representation. This conversion is required when several tasks are to be performed on the main geometric concept, while not all being applicable using a single set of generators. The conversion code must be written very carefully to ensure efficiency and numerical stability.
  • Problem 3: Related to the previous two problems is the question of enumerating all generator sets of the main geometric concept. How many ways can we generate a line using other geometric concepts? Which geometric manipulations are easier, more efficient, or numerically stable for each generator set?
  • Problem 4: If we have a geometric manipulation task that is possible on m generator sets of some main geometric concept, then we should implement m subroutines to fully realize the geometric manipulation task on all sets of generators. This is a problematic situation when there are a large number of representations for a main geometric concept.

To reduce the severity of these 4 problems we need to find an algebra that has the following properties:

  • The basic elements of the selected algebra should be able to represent as many geometric concepts as possible to reduce the need for combinatorial representations. In our 3D Euclidean GA, we have selected to limit its efficiency by dealing wth vectors and scalars while ignoring its bivectors and pseudo-scalar components. This is why this method results in an explosion in required code that will be mostly written by hand. We can try to search for a better Geometric Algebra that can directly represent lines and planes using its multivectors without the need for combinatorial structures of more basic elements.
  • The main geometric tasks should be performed using compact algebraic operations on the elements of the algebra. For example, when the rotation equation is large and difficult to write for each geometric concept, the amount of manual code will be large and error-prone. A better GA should be able to represent as many geometric transformations as possible, each using a single outermorphism or, better, a versor product.

These two requirements on the algebra can be effectively satisfied by selecting other Geometric Algebras for our problem like the 4D homogenous GA or, better, the 5D Conformal GA. The larger-dimension GAs are generally better from the algebraic point of view but will have other computational problems associated with them. That’s a topic for another discussion when we see how GMacAPI can be used to solve the computational problems of larger GAs.

Using Outermophisms

As we can see from the previous code listings, using a small space like the 3D Euclidean GA to represent 3D geometry is very limiting. Many significant geometric objects, like lines, planes, spheres, etc. can’t be directly represented as multivectors; we must use combinatorial representations (i.e. data structures) with all their problems.  In addition, the basic transformations are not linear in that space; we can’t use 3×3 matrices, GA outermorphisms, or versors of the 3D Euclidean space for many important geometric transformations like translations and shearing. A better solution is to use a higher dimensional space like the 4D Homogeneous GA for our geometric models. In the 4D Homogeneous GA lines and planes can be represented as multivectors. Also, compositions of translations, rotations, and scalings are outermorphisms in this space. For this code to work, we will need GMac Basic or GMac Complete.

Code Listing 3