Dorst L., Fontijne D., Mann S. Geometric Algebra for Computer Science. An Object Oriented Approach to Geometry
Подождите немного. Документ загружается.
482 CONFORMAL OPERATORS CHAPTER 16
16.7.2 SPHERICAL GEOMETRY
By taking the imaginary unit sphere
-
e ≡ o + ∞/2 as the preserved vector of all trans-
formations, we get a model of spherical geometry. This is actually the geometry on an
n-dimensional sphere, in which the role of the flats is played by the great circles.
We consider this model again in 2-D, for convenience in terminology and depiction (see
Figure 16.9). The flats are now blades that contain
-
e. These are all circles that cut the
unit circle in a point pair centered around the origin (i.e., in two diametrically opposite
points). The y are the images of the great circles on a sphere under stereographic projection
from the south pole onto the plane of the equator. Such a projection is conformal, for it
is the inversion in a sphere of radius
√
2 with its center at the south pole. That is how
the conformal model contains a faithful representation of the geometry of the sphere
into the plane. A flat point p ∧
-
e is a point pair (representing diametrically opposite points
on the sphere).
The conformal translations are now effectively rotations on the sphere, and the cor-
responding distance measure is the angle between two great circles. The versors are
Figure 16.9: 2-D spherical geometry in the conformal model. By considering the unit dual
imaginary circle
-
e = o+∞/2 as infinity, the spherical lines become circles in the plane that meet
the unit circle in two opposite points. (A spherical line through two red points is indicated
as the green circle.) Translations are defined as moving elements along spherical lines. We
show the translation of a black circle by equal increments of spherical distance.
Also shown is the spherical image of this planar geometry (by a 3-D inversion in the real dual
sphere
T
e
3
[o] −∞, which is not depicted). In that spherical image, the spherical lines are great
circles, and the translation is a slide along such a great circle. A flat point of the plane becomes
a pair of diametrically opposite points on the spherical image.
SECTION16.9 EXERCISES 483
generated by subsequent reflections in vectors of the form n + δe, and represent the
expected sliding over the spherical space.
By the same principle, you can now make arbitrary conformal versors act on elements
residing on a sphere. It is very satisfying that we do not need to write special software to
deal with this geometry (or hyperbolic geometry): its elements and operators are all part
of the conformal model, which we originally implemented to do Euclidean geometry.
16.8 FURTHER READING
The use of the conformal model to actually do conformal geometry is still very recent.
The original successful attempt to use rotors for their representation may have been [2],
but this reference is highly mathematical.
The richly illustrated book by Needham [46] helps develop your geometrical intuition
on conformal mappings. Even though it is mostly restricted to the complex plane and
the algebraic language of M
¨
obius transformations, he works hard at getting the geometr y
up front. You can now reproduce most illustrations in his book through the conformal
model in
GAViewer.
Our usual sources [33,15] have additional material on the rotor method of representing
conformal transformations. They explicitly spell out the relationship of the conformal
model with stereographic projection.
A good source for the other geomet ries within the conformal model is the work of
A. Lasenby, starting with the treatment in [15], which derives explicit expressions for the
distances along the lines of the geometries.
16.9 EXERCISES
16.9.1 DRILLS
1. Reflect the line L through locations e
1
and e
2
in the unit sphere at the origin.
2. Factorize the result of the previous exercise to determine its center and squared
radius.
3. Reflect the tangent vector at e
1
+ e
2
in the direction 2e
3
in the unit sphere at the
origin. Notice especially the weight of the result!
4. Scale the line L byafactorofe
2
from the origin.
5. Scale the line L byafactorofe
2
from the point e
1
.
6. Reflect the line L in the origin.
7. Reflect the line L in the point e
1
.
484 CONFORMAL OPERATORS CHAPTER 16
x
O
x
e
x
p
f
Figure 16.10: Imaging by the eye (see structural exercise 2).
16.9.2 STRUCTURAL EXERCISES
1. Show that the general inversion formula for a point in a dual sphere at the origin
o −
1
2
ρ
2
∞ is
T
x
[o] →
x
2
ρ
2
T
ρ
2
x
−1
[o].
Note that this implies that imaginar y spheres involve a central reflection in the ori-
gin (as well as the inversion of the distances to the origin).
2. Now that we have conformal model and spherical inversion, we can look at the
pinhole camera with different eyes (see Figure 16.10). In that figure, an eyeball is
defined by its pinhole o and the focal point f on the optical axis. A point x images
on the eyeball as x
e
. In the pinhole box camera of Figure 12.2, this point would have
been imaged as x
p
. Show that the two are related by inversion in the indicated sphere
f(o ∧∞), which also transforms the eyeball as whole into the blue imag ing plane.
3. Figure 16.11 shows the reflection of various elements in the brown point pair; all
elements reside in the plane of the drawing. Compare this to the spherical reflection
SECTION16.9 EXERCISES 485
σpσ
−1
∧
σKσ
−1
∧
σΛσ
−1
∧
K
p
Λ
Γ
σΓσ
−1
∧
Figure 16.11: Reflection in a point pair (see structural exercise 3).
Figure 16.1 and understand the differences. (Hint: Use the factorization of the point
pair by a sphere and well-chosen planes.)
4. Prove that flats through the origin are invariant under scaling.
5. We claimed in Section 16.4 that a transversion can also be constructed as the
reflection in two touching spheres. To determine the standard form of such a
transversion, put the spheres symmetrically around the origin, with their centers at
±a. Show that this gives the transversion versor as −a
2
(1 −2o ∧a
−1
). What should
you take as the distance of the touching spheres to obtain the standard transversion
rotor exp(o ∧ t)?
6. Show that the loxodromic rotor of (16.5) can be written as the commuting product
of two more elementary rotors:
e
(o−∞)(e
1
−e
2
)/2
e
(o+∞)(e
1
+e
2
)/2
.
Analyze what these do using software.
7. In Figure 16.12, we have generated a torus by generating a few circles. The inversion
in a sphere of a torus is called Dupin’s cycloid. In the conformal model, its circles are
simply the torus circles, inverted in the sphere. Wr ite pseudocode to generate this
figure w ith just a few parameterized operations.
8. The invariance of a vector a under the versors places the demand a = −
VaV
−1
on the versor, which implies that aV = 0.IftheversorV isarotor,itcanbe
written as the exponent of a bivector. Show that any bivector of the form aT
with T an arbitr ary trivector leaves a invariant. Relate this to the translations of
the various geometries we discussed (i.e., what trivector should you choose to get
a translation?).
486 CONFORMAL OPERATORS CHAPTER 16
Figure 16.12: The Dupin cycloid as the inversion of a torus into a sphere. All elements in
this sketch are primitives of computation in the conformal model (see structural exercise 7).
9. Figure 16.13 depicts the same situation, at the same scale, of a green line L = p∧q∧i
through two points p and q (one of which is the center of the black circles), and a
flat point r ∧ i (in blue). In all three figures, the line is used in a translation versor
exp(iL/2) to translate the point p over equal distances, and dual circles are made
with the original point as its center as t(p ∧ i). The only difference is the element
used for the infinity i (in light red). Identify the metrics and explain the differences
as quantitatively as you can. You can pick i from e
1
, o, ∞, o −∞/2, o + ∞/2,or
o + e
2
+ ∞/2.
16.10 PROGRAMMING EXAMPLES AND EXERCISES
16.10.1 HOMOGENEOUS 4 × 4 MATRICES TO CONFORMAL
VERSORS
This example draws the same GLUT models that we have used in many other exam-
ples before. The user can translate, rotate, and scale the model. The example intends
SECTION16.10 PROGRAMMING EXAMPLES AND EXERCISES 487
(a) (b)
(c) (d)
(e) (f)
Figure 16.13: Metrical Mystery Tour: The conformal model can incorporate different conformal geometries, only differing
by their concepts of infinity.
488 CONFORMAL OPERATORS CHAPTER 16
to demonstrate how to convert 4 × 4 homogeneous matrices (e.g., from OpenGL) to
conformal versors: We construct a particular transformation on the OpenGL modelview
matrix stack, read out the matrix, and convert this to a versor. Then we reset the modelview
matrix to the identity and use the versor to apply the transformation.
The full matr ix-to-versor conversion function is shown in Figure 16.14. The function
is called
matrix4x4ToVersor() and resides in c3ga_util.cpp, not in the source file of
TRSversor matrix4X4ToVersor(const mv::Float _M[4 * 4], bool transpose /*= false*/){
mv::Float M[4 * 4];
if (transpose) {
// transpose & normalize
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
M[i*4+j]=_M[j*4+i]/_M[3*4+3];
}
else {
// copy & normalize
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
M[i*4+j]=_M[i*4+j]/_M[3*4+3];
}
// extract translation:
vectorE3GA t(vectorE3GA_e1_e2_e3, M[0*4+3],M[1*4+3],M[2*4+3]);
// initialize images of Euclidean basis vectors (the columns of the matrix)
vectorE3GA imageOfE1(vectorE3GA_e1_e2_e3, M[0*4+0],M[1*4+0],M[2*4+0]);
vectorE3GA imageOfE2(vectorE3GA_e1_e2_e3, M[0*4+1],M[1*4+1],M[2*4+1]);
vectorE3GA imageOfE3(vectorE3GA_e1_e2_e3, M[0*4+2],M[1*4+2],M[2*4+2]);
// get scale of the 3x3 part (e1, e2, e3)
mv::Float scale = _Float(norm_e(imageOfE1) + norm_e(imageOfE2) + norm_e(imageOfE3))
/ 3.0f;
// compute determinant of matrix
// (if negative, negate all matrix elements)
mv::Float n = 1.0f; // used to negate the matrix
scalor negScale = _scalor(1.0f);
if ((imageOfE1 ^ imageOfE2 ^ imageOfE3).e1e2e3() < 0.0f) {
n = — 1.0f;
// no^ni provides the negative scaling in the final versor:
negScale = noni;
}
Continued
SECTION16.10 PROGRAMMING EXAMPLES AND EXERCISES 489
Continued
// initialize 3x3 ’rotation’ matrix RM, call e3ga::matrixToRotor
mv::Float si=n/scale;
mv::Float RM[3 * 3] = {
M[0*4+0]*si,M[0*4+1]*si,M[0*4+2]*si,
M[1*4+0]*si,M[1*4+1]*si,M[1*4+2]*si,
M[2*4+0]*si,M[2*4+1]*si,M[2*4+2]*si
};
e3ga::rotor tmpR = e3ga::matrixToRotor(RM);
// convert e3ga rotor to c3ga rotor:
c3ga::rotor R(rotor_scalar_e1e2_e2e3_e3e1,
tmpR.getC(e3ga::rotor_scalar_e1e2_e2e3_e3e1));
// get log of scale:
mv::Float logScale = (mv::Float) ::log(scale);
// return full versor:
return _TRSversor(
exp(_freeVector( — 0.5f * (t ^ ni))) * // translation
R* // rotation
exp(_noni_t(0.5f * logScale * noni)) * // scaling
negScale // negative scaling
);
}
Figure 16.14: This function converts 4 ×4 homogeneous matrices to conformal versors (Example 1). The 4 ×4 matrix may
only contain translation, rotation, and uniform scaling.
the example itself. We discuss it in detail below. Due to limitations on the transfor mations
that the conformal model can represent, there are certain restrictions on the type of matri-
ces we can handle. The matrix should only contain translation, rotation, and uniform
scaling (i.e., the same along all axes). Such a matrix has the form
s
1
s
2
[[ R]] s
2
[[ t]]
0
T
s
2
,
where [[
R]] is a 3 × 3 rotation matr ix, [[ t]] is a 3 × 1 translation vector, and s
1
and s
2
are
scalars. s
1
is the actual scaling, while s
2
is just a homogeneous scaling factor that can in
principle be removed without side effects (i.e., it does not affect our interpretation of
transformed objects, only their weight).
As can be seen in Figure 16.14, the first step is to get rid of the s
2
factor by normalizing
the matrix. Optionally, the matrix is transposed (OpenGL represents its matrices in
490 CONFORMAL OPERATORS CHAPTER 16
column-major order, while we use row-major order). Once normalized, the translation
part of the matrix is easily extracted as
vector t.
To separate the rotation from the scale, we initialize three vectors that are the images of the
basis vectors
imageOfE1, imageOfE2, and imageOfE3. In principle, the overall scale is
the norm of any of these three vectors. However, to increase precision slightly we set
scale
to the average of the norm all three vectors.
Once s
1
is found, we can normalize the rotation matrix and convert it to a rotor R using
the existing
matrixToRotor() function from Section 7.10.3. There is one problem, how-
ever; the scaling may be negative. In Section 16.3.2, we have described this as the appli-
cation of an extra versor o ∧∞. The algorithm needs to detect and handle this, for the
(Euclidean) norm of a vector is always positive, hence so is s
1
. Negative scaling can be
detected by computing the determinant of the rotation matrix. We implement this as
follows:
if ((imageOfE1 ^ imageOfE2 ^ imageOfE3).e1e2e3() < 0.0f) {
// negative scaling detected ...
}
When negative scaling has been detected, a negative scaling versor o ∧∞is appended to
the final versor. Hence, the code that handles the scaling and extracts the rotation is:
// get scale of the 3x3 part (e1, e2, e3)
mv::Float scale = _Float(norm_e(imageOfE1) + norm_e(imageOfE2) +
norm_e(imageOfE3)) / 3.0f;
// compute determinant of matrix
// (if negative, negate all matrix elements)
mv::Float n = 1.0f; // used to negate the matrix
scalor negScale = _scalor(1.0f);
if ((imageOfE1 ^ imageOfE2 ^ imageOfE3).e1e2e3() < 0.0f) {
n = — 1.0f;
// no^ni provides the negative scaling in the final versor
negScale = noni;
}
// initialize 3x3 ’rotation’ matrix RM, call e3ga::matrixToRotor
mv::Float si=n/scale;
mv::Float RM[3 * 3] = {
M[0*4+0]*si,M[0*4+1]*si,M[0*4+2]*si,
M[1*4+0]*si,M[1*4+1]*si,M[1*4+2]*si,
M[2*4+0]*si,M[2*4+1]*si,M[2*4+2]*si
};
e3ga::rotor tmpR = e3ga::matrixToRotor(RM);
Note that the var iable negScale will either hold the value 1 or no∧ni to handle absence
or presence of negative scaling, respectively. The final versor is returned as
SECTION16.10 PROGRAMMING EXAMPLES AND EXERCISES 491
return _TRSversor(
exp(_freeVector( — 0.5f * (t ^ ni))) * // translation
R* // rotation
exp(_noni_t(0.5f * logScale * noni)) * // scaling
negScale // negative scaling
);
Negative scaling can still be represented by a translate-rotate-scale (TRS) versor, so the
return type is
TRSversor. Do note that the negative scaling versor o ∧∞does not have a
logarithm.
While we are on the subject, we can be more specific about the flexibility and use of
the geometric algebra conformal versors versus the more common 4 × 4 homogeneous
coordinate matrices. This refines the general observations made in Section 7.7.3.
•
Storage. Storage is similar; to (densely) store a translation-rotation-scaling (TRS)
versor, 12 floats are required, while the corresponding 4 × 4 mat rix requires 13
floats.
•
Speed. Application of a versor to a vector is about 30 percent slower than applying a
4 ×4 matrix to a vector. And because 4 ×4 matrices are so commonly used, main-
stream CPUs have special hardware that can efficiently apply 4 ×4 matrix transfor-
mations. Hardware specialized for geometric algebra is not yet mainstream.
•
Universality. Transforming blades that are not versors is straightforward with ver-
sors, since the same method is used to transform any bladeorversor.The4 × 4
matrices can be applied directly only to vectors. In practice, one uses outermor-
phisms to transform the higher-grade blades. These can be generated easily with
the versors, but need to be hand-coded in the matrix approach.
•
Inverses. Computing the inverse of a versor V is trivial (V
−1
=
V /(V
V )). Inverting
a4×4 matrix is harder, even when you use the tricks that speed up inversion of TRS
transformations.
•
Interpolation. Interpolation is more natural for versors, since for many rotors we
have a logarithm in closed form. Logarithms of matrices are notoriously expen-
sive to compute (although there are some special closed form solutions known
here, too).
•
Conversion.Versorscanbeconvertedto4×4 matrices trivially (the columns of the
matrix are the images of the four basis blades e
1
∧∞, e
2
∧∞, e
3
∧∞and o ∧∞
under the versor). From matrix to versor is more involved.
•
Geometries.The4 × 4 matrices can also be used to do nonuniform scaling (and
thus skewing) and (perspective) projection of vectors. The versors in the confor-
mal model cannot, though other geometr ic algebras may be developed in which the
versors have such actions. On the other hand, conformal versors can also represent
inversions in a sphere and other conformal transformations that enable them to be
used directly for spherical geometry.