Dorst L., Fontijne D., Mann S. Geometric Algebra for Computer Science. An Object Oriented Approach to Geometry

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

SECTION 23.5 TRACING THE RAYS 579

partitionPlane is the plane that splits the space in two halves.

We compute the signed distance of the two flat points to the plane:

mv::Float sd1 = no << (dual(partitionPlane) << fp1);

mv::Float sd2 = no << (dual(partitionPlane) << fp2);

If the line segment lies on both sides of the partition plane, we have to compute the inter-

section point of the line segment and the plane. Otherwise, we can simply descend down

the appropriate node in the BSP tree.

The following code checks if we have to compute the intersection point, and computes it:

If one signed distance is negative, and the other is positive,

then the line segment must lie on both sides of the plane:

if (sd1 * sd2 < 0.0) {

Compute the intersection point:

-compute the line representation of the ray

-intersect rayLine line and the partitionPlane

line rayLine = ray.pos ^ ( — no << ray.direction);

flatPoint fpI = unit_r(dual(partitionPlane) << line);

// descend further down both sides of the BSP tree

//...

}

A degenerate case occurs when the line segment lies inside the partition plane. We then

simply descend to both children of the current BSP node.

Representing Line Segments with Point Pairs

Instead of pairs of ﬂat points, we could use point pairs (i.e., 0-spheres) to represent line

segments. But at some point we will have to dissect the point pair into two points to form

two new point pairs (each on a different side of the partition plane), and this would then

require the rather expensive (14.13). It is computationally more efﬁcient to have the ends

of the segments readily available.

23.5.4 REFLECTION

Reﬂections are computed as part of the shading computation treated in the next section.

Reﬂection of any blade in any other blade is quite simple in the conformal model, though

there are some signs depending on whether they are represented directly or dually (see

Table 7.1). The following function implements the reﬂection. It forms a plane from the

surface attitude (a free bivector), and reﬂects the ray direction (a free vector) in it:

color scene::reflect(const ray &R, int maxRecursion, const

surfacePoint &spt) const {

580 USING THE GEOMETRY IN A RAY-TRACING APPLICATION CHAPTER 23

Reflect the ray direction in the surface attitude,

and spawn a new ray with that direction at the surface point.

ray reflectedRay(

spt.getPt(), // starting position of new ray

— ((spt.getAtt() ^ no) *

R.get_direction() *

reverse(spt.getAtt() ^ no))

// direction of new ray

);

return trace(reflectedRay, maxRecursion — 1);

}

23.5.5 REFRACTION

Like reﬂections, refractions are also computed as part of the shading computation. The

classical equation for refraction of direction vectors is:





sign

(

n · u

)



1 − η

(

n · u

)

−

(

n · u

)



n + ηu

(23.1)

where n is the surface normal, u is the ray direction, and η is the refractive constant.

In our conformal implementation, both n and u are free vectors that can be plugged

directly into the equation. As an interesting side note we mention that the same equa-

tion holds at the level of intersecting lines, by the extension principles of Section 13.4.

23.6 SHADING

The ray tracer performs shading computations for every spawned ray that intersects a

model (unless it is a shadow ray). The shading computations should approximate how

much light the material reﬂects along direction of the ray (and thus towards the camera).

We do not discuss the shading computations in detail because they do not differ much

from the classical computations. Even in the conformal model, shading computations are

most conveniently performed using 3-D Euclidean vectors. For completeness, we brieﬂy

list the steps involved in shading:

•

Before the ray tracer can perform any shading computations, it must interpolate the

surface properties deﬁned at the vertices for the intersection point. This is done by

bar ycentric interpolation (see (11.19))

•

If the model has a bump map applied to it, we have to modulate the surface attitude

according to that bump map. This again involves interpolation.

SECTION 23.7 EVALUATION 581

•

Finally, we have to perform the actual shading computations. Our ray tracer mimics

the simple ﬁxed function pipeline shading model of OpenGL, althoug h we perform

shading per intersection point instead of per vertex.

23.7 EVALUATION

We have shown most of the geometry involved in implementing a classical ray tracer.

We have emphasized that there are usually several ways to represent computer g raphics

primitives in the conformal model of Euclidean geometry. For the ray tracer, we picked the

most efﬁcient representations we could ﬁnd, but in other, less time-sensitive applications,

we may pick the more elegant universal representations from the conformal model, since

we do think it is ultimately beneﬁcial to represent each geometric concept with a single

type of blade. It would permit one to build the elements of a geometry librar y independent

of the particular application they originated in.

Most interactive modeling transformations have been reduced to simple one-liners, direct

conformal model formulas involving the mouse parameters. This is a part of the code

where the conformal model shows off some of its power. The directness of the approach

helped make the actual writing of the code a quick and enjoyable exercise.

The direct use of coordinates in the equations and the source code has been eliminated,

except for places where they were actually useful (e.g., systematically generating position

of all pixels in a 2-D image). This would not be possible with classical homogeneous coor-

dinates. Just pick up any computer graphics text that treats construction of Euclidean

transformations, and the pages will be littered with 4×4 matrices ﬁlled with coordinates.

As we already saw in the benchmarks in Chapter 22, there is a performance penalty for

using the 5-D conformal model over the 3-D vector space model: our conformal ray tracer

is about 25 percent slower than the vector space version. The difference compared to the

4-D homogeneous version is less than 5 percent.

In the graphical user interface of Section 23.4, we demonstrated the most pure manifes-

tation of the conformal model. There, the correspondence to the algebraic elegance of

the model versors and the simplicity of the code was most striking . We view it as an ideal

example of what can be achieved by the methods for object-oriented programming of

geometry exposed in this book.

METRICS AND NULL

VECTORS

AvectorspaceR

does not necessarily have metric properties: it may not be possible to

measure and compare arbitary lengths and angles of vectors. For that, we need an inner

product. This does not need to be Euclidean.

A.1 THE BILINEAR FORM

In mathematics, the metric properties are usually introduced through a bilinear form that

encapsulates the measurement of all lengths in that space in a concise manner. As its name

implies, a bilinear form has two arguments and is linear in each of them; the word “form”

is mathematical jargon for “scalar-valued function.” The bilinear form Q of the vector

space

is therefore a bilinear function Q : R

× R

→ R, mapping pairs of vectors to a

scalar.

If we assume that the bilinear form is given (with the original deﬁnition of the metric

vector space), then we can deﬁne the inner product in terms of it as

x · y ≡ Q[x, y].

Since we deﬁne our scalar product in terms of the inner product and the contraction in

terms of the scalar product (in Chapter 3), all these subspace products pull in the same

metric as characterized by Q.

585

586 METRICS AND NULL VECTORS APPENDIX A

A.2 DIAGONALIZATION TO ORTHONORMAL BASIS

Elementary linear algebra shows that any bilinear form in R

can be brought into a

standard diagonalized form; we would say that we can choose a certain basis {e

}

i=1

so that for that basis the inner product becomes a particularly simple expression. This

basis is orthonormal, which means that it satisﬁes

· e

= ±δ

(where δ

is 1 when i = j, and 0 when i = j). For each basis vector, the inner product

with all other basis vectors is equal to 0, and with itself equal to 1 or −1.Ifallare+1, this

is obviously equivalent to a Euclidean space, and it implies that on that basis, the inner

productoftwovectorsx =



i=1

and y =



j=1

can be written as

x · y =



i=1

In particular, x · x =



i=1

, which is positive, and which we interpret as the norm

squared.

But the general deﬁnition also allows spaces in which some of the coefﬁcients are negative.

In physics, an important space is the Minkowski space, in which one of the vectors, say e

has e

· e

= −1. Then we obtain, for the inner product of x =



i=1

and y =



j=1

x · y = −x

+ x

+ ···+ x

(A.1)

Now x · x is no longer guaranteed to be positive, and strange effects occur with rotation-

like operations in this space. Four-dimensional space-time has this structure; it is the

framework of relativity. Spaces like this are surprisingly useful for computer science as

well, even when you only want to do Euclidean geometry. They are the basis of the con-

formal model of Euclidean geometry in Chapters 13 through 16.

A.3 GENERAL METRICS

We develop some terminology for general metrics. If there are p independent unit vectors

satisfying e

· e

= 1, and q independent unit vectors satisfying e

· e

= −1,thenitis

customary to say that the space has p “positive dimensions” and q “negative dimensions”

(with n = p + q). Rather than

,wethenwriteR

p,q

and call (p, q) the signature of

the space. An n-dimensional Euclidean space is then written as

n,0

, the representational

space for its conformal model as

n+1,1

, and an n-dimensional Minkowski space as R

n−1,1

When we write

, we mean to be nonspeciﬁc on the metric (don’t confuse this with R

n,0

which has a Euclidean met ric!).

SECTIONA.5 ROTORS IN GENERAL METRICS 587

A.4 NULL VECTORS AND NULL BLADES

Mixed sig nature spaces contain vectors that have an inner product equal to 0 with

themselves. These are called null vectors. In some sense, such a null vector is perpendicular

to itself, which is somewhat hard to imagine.

We can construct null vectors easily in the Minkowski space above: take n

= (e

√

and n

−

= (e

− e

√

2. Then

· n

+ e

) · (e

+ e

) =

· e

+ e

· e

) =

(−1 + 1) = 0,

and similarly n

−

· n

−

= 0. The inner product of n

and n

−

equals 1:

· n

−

+ e

) · (e

− e

) =

(−e

· e

+ e

· e

) = 1.

If the space has a basis with p “positive” basis vectors and q “negative” basis vectors, the

basis can contain at most min(p, q) null vectors. They then come in pairs, as in the example

above, and for e very null vector we can ﬁnd another null vector such that their mutual

inner product equals 1. Such vectors are each other’s inverses relative to the inner product:

they are reciprocal null vectors.

By using null vectors in composite constructions, we can make elements of higher grade

that square to zero. A null blade must contain at least one null vector to square to zero.

Yet beware that this is not a sufﬁcient condition, for if the blade contains two reciprocal

null vectors, it may not be null. An example is the 2-blade n

∧n

−

, which squares to 1 (it

is identical to e

∧ e

A.5 ROTORS IN GENERAL METRICS

The treatment of rotors in general metrics leads into subtle issues for which the under-

standing of the much simpler Euclidean case does not prepare. They include the explicit

demand that the reverse of a rotor should be its inverse; that not all rotors are continuously

connected to the identity; and that only in Euclidean and Minkowski metrics rotors can

be written as the exponentials of bivectors. These matters are touched upon in Section 7.4;

for a more precise treatment we recommend [52].

CONTRACTIONS AND

OTHER INNER PRODUCTS

This appendix collects some additional facts about contractions and inner products to

give the correspondence with much other literature, as well as three long proofs for

statements in Chapter 3.

B.1 OTHER INNER PRODUCTS

When you study the applied literature on geometric algebra, you will ﬁnd an inner

product used that is similar to the contraction, but not identical to it. It was originally

introduced by Hestenes in [33], so we refer to it as the Hestenes inner product in this

text. We deﬁne it here, and relate it to the contraction. It is most convenient to do

so via an intermediate construction, the “dot product.” More detail about these issues

may be found in [17], which defends the contraction in detail.

B.1.1 THE DOT PRODUCT

Let A

and B

be blades of grade k and l, respectively. Then the dot product A

• B

deﬁned as

dot product : A

• B



B

if k ≤ l

B

= (−1)

l(k−l )

A

if k ≥ l

(B.1)

589

590 CONTRACTIONS AND OTHER INNER PRODUCTS APPENDIX B

The dot product thus switches between left and right contraction depending on the

grades. As a consequence of the deﬁnition, the dot product has a different and somewhat

more symmetrical grade than the contraction:

grade(A

• B

) = |k − l|.

It is therefore a mapping •:



→



|k−l|

. It is less often zero than the

contraction (when the grade of the ﬁrst arguments gets too high to have a non-zero out-

come for the contraction, the second argument “takes over”). This may seem to be an

advantage, but remember from Section 3.3 that a zero contraction has a geometric signi-

ﬁcance: it means that not all of A

is contained in B

. Since that concept is of geometrical

importance it needs to be encoded somewhere in the framework. When you use the dot

product, you get a lot of conditional statements to do this, which could have been avoided

by using the natural asymmetry of the contraction.

B.1.2 HESTENES’ INNER PRODUCT

The literature on applied geometric algebra almost exclusively contains another inner

product, which is like the dot product, except that it is zero whenever one of the arguments

is a scalar. We refer to it here as the Hestenes inner product, and denote it •

. This is used

in [33], and most texts derived from his approach, such as [15], denote it as · since it is

the only inner product they use. Like the dot product, it leads to many special cases in

general derivations (even more so, to treat the scalar cases).

B.1.3 NEAR EQUIVALENCE OF INNER PRODUCTS

Whenever the ﬁrst argument has a lower or equal grade to the second, and there is no

possibility of any of then being scalar, the contraction and inner products are all identical:

A • B = AB = A •

B, when 0 = grade(A) ≤ grade(B).

With careful writing, that limits the consequences of the choice of inner product, so that

results can be compared and transferred with ease.

We have made an effort to make most equations in this book of the type “lowest grade

ﬁrst,” so that one can easily substitute one’s favorite inner product and follow the compu-

tation, but in some results of general validity (extending to scalars and arbitrary order of

arguments), the use of the contraction is essential. Therefore we have kept the asymmetric

notation  for this inner product.

Other texts often have the same tendency in their ordering of the arguments, so the issue

is not as serious as it might appear, at least algebraically.

In our

GAviewer software, which was used to render most of the ﬁgures in this book,

a preferred interpretation of the inner product can be set, so that formulas from this

SECTIONB.2 EQUIVALENCE OF THE IMPLICIT AND EXPLICIT CONTRACTION DEFINITIONS 591

or any other book may be entered by using a dot notation. Its default setting is the

left contraction. In the GA sandbox of the programming exercise, we only provide

compact operators for the left contraction

<< and the right contraction >> (with the

arrows pointing to the argument that should have the lower grade for the result to be

nonzero).

B.1.4 GEOMETRIC INTERPRETATION AND USAGE

The interpretation of the contraction AB is clear: it is “the part of B most unlike A” (in

linear fashion proportional to both, and with a speciﬁc sign, see Section 3.3). Because of

the above, the dot product A • B and the Hestenes inner product •

have a slightly more

involved interpretation: they are the part of the larger grade blade most unlike the lower

grade blade (in linear fashion, and with a different sign). This causes tests on the relative

grade in many derivations and statements, complicating their range of validity and proofs

considerably.

If you follow good programming practice and let the interpretation of your computa-

tional results be ruled automatically by the grades appearing in it, this is a nuisance. For

computer vision in which data can accidentally degenerate (4 points may determine a

plane rather than a polyhedron, somewhere deep inside a program), you may not be

able to predict the grades of the result. The contraction then appears to be the more

convenient inner product in the design of algorithms, and that is the reason we use it

in this book.

On the other hand, if you know beforehand what grades to expect from your computation,

and how to interpret them, then the dot product or the similar Hestenes inner product

may be easier to work with in compact computations, especially in combination with the

geometric product of Chapter 6. Apparently, this is the case in the applications to physics

covered in [15], and in many engineering applications by the same school. If they had a

strong need to switch to the mathematically tidier contraction, they would have done so

by now.

If you are interested in more detail on these issues, [17] attempts to give a fair overview

of pros and cons (and of course ends up preferring the contraction).

B.2 EQUIVALENCE OF THE IMPLICIT AND EXPLICIT

CONTRACTION DEFINITIONS

We show that the contraction product explicitly deﬁned by (3.7) through (3.11) is

consistent with the implicit deﬁnition (3.6). That is a bit of work, but it contains useful

techniques, and we prove a useful recursive formula in the process.

Some remarks before we start. In a degenerate metric, the implicit deﬁnition is not speciﬁc

to deﬁne the contraction for all arguments, whereas the explicit deﬁnition can do that. The

592 CONTRACTIONS AND OTHER INNER PRODUCTS APPENDIX B

strongest we can do in this case is show that in all cases where the implicit deﬁnition does

deﬁne an outcome, this is consistent with the explicit result. In nondegenerate metrics, we

have a unique outcome even with the implicit deﬁnition, so we can even show equivalence.

In that case:

X ∗ A = X ∗ B for all X ⇔ A = B.

(B.2)

We omit the proof of this statement, which is similar to the corresponding statement for

the inner product of vectors in linear algebra; it is most simply done by developing all

blades on a basis.

It is bothersome to point out the different behavior for the two kinds of metric with each

statement we derive; the nondegenerate case is “typical” in the text that follows.

Proof of consistency of (3.7): X∗(αB) = (X∧α ) ∗B = (αX) ∗B = α(X∗B) = X∗(αB),

so αB = αB.

Proof of consistency of (3.8): X∗(Bα) = (X ∧B) ∗α and the latter can only be nonzero

if (X ∧ B) is a scalar. Under the assumption of grade

(B) > 0,

therefore, Bα = 0.

Proof of consistency of (3.9): X ∗ (ab) = (X ∧ a) ∗b = X(a ∗ b) = X(a · b), since X is

scalar if the result is to be nonzero.

Proof of consistency of (3.10):Weshowhowacontractionofavectorwithabladecan

be computed by passing x through the outer product, with appropriately alter-

nating signs:

x(a

∧ a

∧···∧a

) =



i=1

(−1)

i−1

∧ a

∧···∧(xa

) ∧···∧a

(B.3)

Since the term xa

is simply the inner product x · a

, this allows rapid, one-line

evaluation of an inner product of a vector on a blade as a simple sum of terms.

That makes it an important formula to remember.

When we want to derive (3.16) from (3.6) for the (k−1)-blade x(a

∧···∧a

we have to take its scalar product with an arbitrary (k −1)-blade (y

k−1

∧···∧y

We then write the scalar product as a determinant, and use the properties of the

determinant in a Laplace expansion procedure:

k−1

∧···∧y

) ∗ (x(a

∧···∧a

))

= (y

k−1

∧···∧y

∧ x) ∗ (a

∧···∧a

)

= (a

∧···∧a

) ∗ (y

k−1

∧···∧y

∧ x)



x · a

··· x · a

· a

··· y

· a

k−1

· a

k−1

· a

···y

k−1

· a

