Bayro-Corrochano E., Scheuermann G. Geometric Algebra Computing: in Engineering and Computer Science

Подождите немного. Документ загружается.

48 L. Dorst

The same structure-preserving property holds for all operations we introduced, be

they spanning, inner product, or duality (relative to a transformed pseudoscalar). In

words: “the transformation of a construction equals the construction of the trans-

formed elements.” This fact is very convenient, for it implies that we can simply

construct something at the origin and then move it into place to ﬁnd the general

form (hence our preference for origin-based speciﬁcation in the table above). And

composite elements move by the same versor as points do: the translation versor

universally translates points, lines, planes, spheres, or tangent elements. As we

mentioned, there is no longer any need for data structures distinguishing between

“position vectors” which feel translations and “direction vectors” which do not; all

is automatically administrated in the algebraic behavior of the corresponding ele-

ments. This is an enormous advantage relative to the classical homogeneous model

for the development of structural code, either by hand or using a code genera-

tor [3].

This principle is also extremely useful in derivations. Let us, for instance, use

it to prove the general formula for the reﬂection of a line Λ in a dual plane π as

Λ → −πΛπ

−1

, simply from the 1-D direction reﬂection formula (5). A line Λ

with direction u through the origin is given as Λ

∧u ∧e

∞

, and a dual plane

through the origin with normal vector n as π

=n. The reﬂection of the direction

u is affected by (5)asu → u



≡−nun

−1

=−π

uπ

−1

. The reﬂected line is then



∧u



∧e

∞

. Now we note that due to the algebraic commutation (i.e., the geo-

metric orthogonality) of the bold Euclidean and the nonbold extra dimensions e

and

∞

,wehave−π

−1

=−ne

−1

= e

and −π

∞

−1

=−ne

∞

−1

∞

Therefore we can “pull out” the reﬂection operator to act on the whole line Λ

by (5):





−π

−1



∧



−π

uπ

−1



∧



−π

∞

−1



=−π

∧u ∧e

∞

)π

−1

=−π

−1

This is still only true at the origin, but we can move this construction by a mo-

tion versor V to an arbitrary location. All elements change to their general form

π =Vπ

−1

, Λ =VΛ

−1

, and the reﬂection transformation preserves its struc-

ture since VΛ



−1

= (V π

−1

)(V Λ

−1

)(V π

−1

) = πΛπ

−1

. Therefore the

general reﬂection formula of a line in a plane is simply

reﬂection of a line Λ in the dual plane π : Λ →−πΛπ

−1

This includes all aspects of location, direction, and orientation. Note that this com-

putation reﬂects a general line in a general plane without computing its intersection

point—try doing that using linear algebra! (If you need the intersection point of line

and plane, it is π · Λ, by straightforward application of the universal

meet opera-

Structure Preserving Motions Through CGA 49

tion (7) and duality (6), (8).)

direction u

normal vector

−−−−−−−→ a

as reﬂector

−−−−−−−→ direction u −2(u ·a)a/a

)

embed in GA

⏐



embed in GA

⏐



embed in GA

⏐



direction u

normal vector

−−−−−−−→ a

as reﬂector

−−−−−−−→ direction u



=−aua

−1

embedinCGA

⏐



embed in CGA

⏐



embed in CGA

⏐



origin line Λ

∧u ∧e

∞

dual e

-plane

−−−−−−−→ π

as reﬂector

−−−−−−−→ origin line Λ



=−π

−1

Euclidean versor

⏐



Euclidean versor

⏐



Euclidean versor

⏐



general line Λ =VΛ

−1

dual plane

−−−−−−→ π

as reﬂector

−−−−−−−→ general line Λ



=−πΛπ

−1

conformal versor

⏐



conformal versor

⏐



conformal versor

⏐



general circle K =VΛV

−1

dual sphere

−−−−−−→ σ

as invertor

−−−−−−→ general circle K



=−σKσ

−1

We can even apply an arbitrary conformal versor and change the reﬂecting dual

plane π into a dual sphere σ , and the line L into a circle K; the result is a spherical

inversion operation. (As a further extension, another application of the structure

preservation property shows that the reﬂection in σ of a general element X is X →

(−1)

grade(X)

σXσ

−1

The conformal model renders all transitions trivial in this transfer, all the way

from a reﬂection of a Euclidean direction vector at the origin to the inversion of

a general circle in a general sphere. Such is the power of a structure-preserving

framework!

6 Trick 5: Exponential Representation of Versors

Even-graded versors, made by an even number of reﬂections, represent motions that

can be performed continuously and in small amounts. In Euclidean and Minkowski

spaces, all even-graded versors can be written as the exponentials of bivectors.The

bivector speciﬁcation of an even versor is often more directly related to the geometry

of the situation than the “product of vectors” method.

As an example of the exponential rewriting, take the rotation R

Iφ

over the an-

gle φ, parallel to the I-plane as treated in (10),

Iφ

=cos(φ/2) −sin(φ/2)I =e

−Iφ/2

It is the property I

=−1 that makes the exponential rewriting permitted:

50 L. Dorst

−Iφ/2

= 1 +

(−Iφ/2)

+···



1 −

(φ/2)

+···





(φ/2)

−

(φ/2)

+···



= cos(φ/2) −sin(φ/2)I.

The translation versor of (11) can also be written in this exponential form; but since

it involves the bivector t ∧e

∞

, the expansion truncates after two terms (fundamen-

tally due to e

∞

=0):

=1 −t ∧e

∞

/2 =e

−t∧e

∞

A rotation around a general 3D unit line Λ over φ is now generated by the versor:

rotation around Λ over φ: R

Λ,φ

∗

φ/2

Proof This follows from the simply derived structural property

V exp(B)V

−1

=exp



VBV

−1



and the transfer property applied as follows. First recognize that the rotation axis

of the origin rotation R

Iφ

is the line Λ

= I

∗

=−I

−∗

, so the origin rotation is

exp(Λ

∗

φ/2). Then transfer this by a translation T to the actual location of the de-

sired axis Λ, which changes Λ

∗

to T(Λ

∗

−1

= (T Λ

−1

)/(T I

4,1

−1

) = Λ

∗

since the pseudoscalar I

4,1

involved in the dualization is translation invariant.

Done. 

General rigid body motions can of course also be made, for instance, by the

usual method of combining an origin rotation with a translation. You ﬁnd that the

result can be written as the exponential of a general conformal bivector on the ba-

sis {e

∧e

, e

∧e

, e

∧e

, e

∧e

∞

, e

∧e

∞

, e

∧e

∞

}, giving the six degrees of

freedom required. Since this space of bivectors is linear, it can be used for motion in-

terpolation. To interpolate between two poses characterized by the versors M

and

, ﬁnd their bivectors B

= log(M

) and B

= log(M

). Now apply a standard

vector interpolation method to smoothly change B

into B

through intermediate

bivectors B

; then use the versors exp(B

) to generate the interpolated poses. To ex-

ecute this procedure, one needs to ﬁnd the bivector corresponding to a given versor;

such “versor logarithms” may be found in [2].

Linearization of versor motions for extrapolation or estimation is also possible

and requires geometric calculus. When performed (see [1]), the ﬁrst order change in

an element X that is moved by a changing versor V(τ)from a standard element X

as X(τ) =V(τ)X

V(τ)

−1

X(τ +dτ) =X(τ) +



Ω(τ)X(τ)−X(τ)Ω(τ)



with Ω(τ) =



dτ

V(τ)



V(τ)

−1

Structure Preserving Motions Through CGA 51

Fig. 4 The mirror Π rotates φ round a line Λ,andalineX is reﬂected in it. Using a local

ﬁrst-order linearization of the reﬂection versor, one can derive the perturbation of the reﬂected line

to second order (in black) to be the rotation with versor exp(−φ((Λ ·Π)/Π)

∗

), i.e., around the

projection of Λ onto Π with angle 2φ cos(Π, Λ). For details, see [2]

If V is normalized, Ω is a bivector, and its commutator product with X(τ) pre-

serves the grade. This linearization of geometrical perturbations is very useful in

applications, see Fig. 4. The full geometric calculus is truly powerful, and one can

differentiate relative to an arbitrary element of the algebra (such as a blade or a ver-

sor). We cannot treat that here, and the reader is referred to introductions like [2]

and [1].

7 Trick 6: Sparse Implementation at Compiler Level

Implementation of CGA may seem to be expensive. After all, to treat a 3D space,

we embed into a 5D representational space and use the geometric algebra of that,

which involves a 2

-D basis of constructible elements of all grades. Yet the use we

make of this space is restricted, and the elements are therefore somehow sparse.

52 L. Dorst

Ultimately, the main purpose of the algebraic organization is to keep track auto-

matically of the administration of the meaning of the coordinates of points, lines,

planes, spheres, etc., simultaneous with performing the quantitative computations.

That is in a sense a Boolean selection task of the algebra, which one would intu-

itively expect not to be too expensive. Indeed it has proved possible to limit the

overhead of the use of CGA to about 10% relative to the best available coordinate

code programmed classically. For the computer science techniques that achieve this,

consult [2] and [3]. A warning: before you start using CGA in commercial applica-

tions, be aware that it is covered by a US patent [6].

References

1. Doran, C., Lasenby, A.: Geometric Algebra for Physicists. Cambridge University Press, Cam-

bridge (2000)

2. Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science, An Object-

Oriented Approach to Geometry. Morgan Kaufman, San Mateo (2007). Second revised printing

2009. See also www.geometricalgebra.net

3. Fontijne, D.: Efﬁcient implementation of geometric algebra. Ph.D. Thesis, U. of Amsterdam

(2007). See also www.science.uva.nl/~fontijne

4. Fontijne, D., Dorst, L.: Efﬁcient algorithms for factorization and join of blades. This volume

5. Hestenes, D.: New tools for computational geometry and the rejuvenation of screw theory. This

volume

6. Hestenes, D., Rockwood, A., Li, H.: System for encoding and manipulating models of objects.

US Patent 6,853,964, granted 8 February 2005

Engineering Graphics in Geometric Algebra

Alyn Rockwood and Dietmar Hildenbrand

Abstract We illustrate the suitability of geometric algebra for representing struc-

tures and developing algorithms in computer graphics, especially for engineering

applications. A number of example applications are reviewed. Geometric algebra

unites many underpinning mathematical concepts in computer graphics such as vec-

tor algebra and vector ﬁelds, quaternions, kinematics and projective geometry, and

it easily deals with geometric objects, operations, and transformations. Not only are

these properties important for computational engineering, but also for the computa-

tional point-of-view they provide. We also include the potential of geometric algebra

for optimizations and highly efﬁcient implementations.

1 Introduction

Computer graphics relies heavily on geometric models and methods. Geometric al-

gebra is a mathematical framework to easily describe geometric concepts and op-

erations. It allows us to develop algorithms fast and in an intuitive way. Geometric

algebra is based on the work of Hermann Grassmann (see the conference [45] cele-

brating his 200th birthday in 2009) and William Clifford [14, 15]. Pioneering work

has been done by David Hestenes, who ﬁrst applied geometric algebra to problems

in mechanics and physics [24, 26].

A. Rockwood (



)

Geometric Modeling and Scientiﬁc Visualization Research Center, King Abdullah University

of Science and Technology, Thuwal, Saudi Arabia

e-mail: alynrock@yahoo.com

A. Rockwood

e-mail: alyn.rockwood@kaust.edu.sa

E. Bayro-Corrochano, G. Scheuermann (eds.), Geometric Algebra Computing,

54 A. Rockwood and D. Hildenbrand

2 Beneﬁts of Geometric Algebra for Computational Engineering

We ﬁrst highlight some properties of geometric algebra that make it advantageous

for graphics engineering applications.

2.1 Uniﬁcation of Mathematical Systems

In the wide range of engineering applications many different mathematical systems

are currently used. One notable advantage of geometric algebra is that it subsumes

mathematical systems like vector algebra, complex analysis, quaternions, Plucker

coordinates, and tensor analysis. Applications described in Sect. 3 will illustrate

this advantage.

2.2 Uniform Handling of Different Geometric Primitives

Conformal geometric algebra, the geometric algebra of conformal space we focus

on, is able to treat different geometric objects such as points, vectors, lines, circles,

spheres, and planes as the same entities algebraically. Consider the spheres of Fig. 1,

for instance. These spheres are simply represented by

S =P −

∞

(1)

based on their center point P , their radius r, and the basis vector e

∞

which rep-

resents the point at inﬁnity. The circle of intersection of the spheres is then easily

computed using the outer product to operate on the spheres as simply as if they were

vectors:

Z =S

∧S

. (2)

This way of computing with geometric algebra clearly beneﬁts applications

like kinematics, pose estimation, and other computer graphics applications as seen

in Sect. 3.

Fig. 1 Spheres and circles

are basic entities of geometric

algebra. Operations like the

intersection of two spheres

are easily expressed

Engineering Graphics in Geometric Algebra 55

2.3 Simpliﬁed Rigid Body Motion

Rigid body motions in geometric algebra can be described with one compact linear

expression, the so-called screw

S =im +e

∞

n (3)

with the Euclidean pseudoscalar i =e

∧e

includes both rotational and linear

parts described with the 3D vectors m and n (see [25]). The combinations of rota-

tional and linear velocities, forces and torques are also described with the help of

one linear expression.

One result of this property is the improvement of Finite Element methods [9].

2.4 Curl, Vorticity and Rotation

The vector algebra concepts of curl, vorticity, and rotation as expressed in geometric

algebra are deﬁned in any dimension, whereas the cross-product in classical vector

algebra is restricted to three dimensions. Thus geometric calculus enables vector

algebra applications to be considered in any dimensions [13].

2.5 More Efﬁcient Implementations

Geometric algebra as a mathematical language often suggests a clearer structure and

greater elegance in understanding methods and formulae. This regularly results in

more efﬁciency and lower runtime performance for derived algorithms. In Sect. 5

we present a dramatically improved optimization approach for kinematics. We will

see there that geometric algebra inherently has a large potential for creating opti-

mizations leading to more highly efﬁcient implementations.

3 Some Applications

Computer graphics and the related areas of robotics and computer vision are active

areas of research in geometric algebra. In this section we survey some of these

applications in more detail.

For about a decade, researchers at the University of Cambridge, UK, have applied

geometric algebra to a number of graphics related projects. They started with ideas

in computer vision. Lasenby et al. [31, 32] and Perwass et al. [37, 41, 42] present

some applications dealing with structure and motion estimation as well as with the

trifocal tensor. Rigid-body pose and position interpolation, mesh deformation, and

catadioptric cameras articles using geometric algebra are presented by Cameron

56 A. Rockwood and D. Hildenbrand

et al. [12] and Wareham et al. [54, 55]. Geomerics [53] is a start-up company in

Cambridge specializing in simulation software for physics and lighting, which pre-

sented its new technology allowing real-time radiosity in videogames utilizing com-

modity graphics processing hardware. The technology is based on geometric algebra

wavelet technology.

Dorstetal.[16–18, 33, 34] at the University of Amsterdam, the Netherlands, are

applying their fundamental research on geometric algebra mainly to 3D computer

vision. Zaharia et al. [56] investigated modeling and visualization of 3D polygonal

mesh surfaces using geometric algebra. Currently D. Fontijne is primarily focusing

on the efﬁcient implementation of geometric algebra. He investigated the perfor-

mance and elegance of ﬁve models of 3D Euclidean geometry in a ray tracing, an

archetypical computer graphics application [22]. It summarized the investigation

by noting that 5D conformal space was the most elegant, but required appropriate

hardware to become the most efﬁcient as current hardware supported the 4D afﬁne

model. Along this line, research into hardware for geometric algebra continues. The

Amsterdam group developed a code generator for geometric algebras [23]. Also,

there is a book with applications of geometric algebra edited by Dorst et al. [19].

A new book [20] was published recently, which dedicates its major portion to the

issue of geometric algebra calculation.

The ﬁrst time geometric algebra was introduced to a wider Computer Graphics

audience was through a couple of courses at the SIGGRAPH conferences 2000 and

2001 (see [35]).

Bayro-Corrochano et al. from Guadalajara, Mexico, are primarily dealing with

the application of geometric algebra in the ﬁeld of computer vision, robot vision

and kinematics. They are using geometric algebra, for instance, for tasks like vi-

sual guided grasping, camera self-localization, and reconstruction of shape and mo-

tion [3]. Their methods for geometric neural computing are used for tasks like pat-

tern recognition [1, 8]. Registration, the task of ﬁnding correspondences between

two point sets, is solved based on geometric algebra methods in [47]. Some of their

kinematics algorithms can be found in [7] for the 4D motor algebra and in the con-

formal geometric algebra papers [5, 6] dealing with inverse kinematics, ﬁxation, and

grasping as well as with kinematics and differential kinematics of binocular robot

heads. Books from Bayro-Corrochano et al. with geometric algebra applications are,

for instance, [2] and [4].

At the University of Kiel, Germany, Sommer et al. [51] are applying geometric

algebra to robot vision, e.g., Rosenhahn et al. [48, 49] concerning pose estimation

and Sommer et al. [52] regarding the twist representation of free-form objects. Per-

wass et al. are applying conformal geometric algebra to uncertain geometry with

circles, spheres, and conics [40] to geometry and kinematics with uncertain data

[44] or concerning the inversion camera model [43]. There is a book with applica-

tions of geometric algebra edited by Sommer [50] and a new book about the appli-

cation of geometric algebra in engineering applications by Christian Perwass [38].

Sven Buchholz, together with Kanta Tachibana from the university of Nagoya and

Eckhard Hitzer from the university of Fukui, Japan, do some interesting research

dealing for instance with neural networks based on geometric algebra [10

, 11].

Engineering Graphics in Geometric Algebra 57

In addition to these examples, there are many other applications like geometric

algebra Fourier transforms for the visualization and analysis of vector ﬁelds [21]or

classiﬁcation and clustering of spatial patterns with geometric algebra [46] showing

a wide area of possibilities of advantageously using this mathematical system in

engineering applications.

4 The Geometric Primitives in More Detail

Here, we look into some details of the basic geometric primitives of conformal ge-

ometric algebra as introduced in Sect. 2.2 and listed in Table 1. We especially look

into the representations of spheres and planes and will see that planes are speciﬁc

spheres with inﬁnite radius. Increasing the radius of a sphere to inﬁnity, the resulting

plane is described by

π =n +de

∞

(4)

with n being the 3D unit normal vector of the plane, and d the distance of the plane

from the origin. This limit process can be used in order to ﬁt the best suitable object

into a set of points, whether it is a plane or a sphere. A locally estimated sphere can

be used in order to describe local curvature of point clouds [27], while an estimation

of a plane describes vanishing curvature.

4.1 Planes as a Limit of Spheres

Spheres and planes, both, are vectors in conformal geometric algebra. In this section,

we will see how a sphere

S =s +



−r



∞

(5)

Table 1 List of the basic geometric primitives provided by the 5D conformal geometric algebra.

The bold characters represent 3D entities (x is a 3D point, n is a 3D normal vector, and x

the scalar product of the 3D vector x). The two additional basis vectors e

and e

∞

represent the

origin and inﬁnity. Based on the outer product, circles and lines can be described as intersections

of two spheres, respectively two planes. The parameter r represents the radius of the sphere and

the parameter d the distance of the plane to the origin

Entity Representation

Point P = x +

∞

Sphere s =P −

∞

Plane π =n +de

∞

Circle z =s

∧s

Line l = π

∧π