22.5. 22.5 Translation, distortion, geometric transformations

Objects in the virtual world may move, get distorted, grow or shrink, that is, their equations may also depend on time. To describe dynamic geometry, we usually apply two functions. The first function selects those points of space, which belong to the object in its reference state. The second function maps these points onto points defining the object in an arbitrary time instance. Functions mapping the space onto itself are called transformations. A transformation maps point to point . If the transformation is invertible, we can also find the original for some transformed point using inverse transformation .

If the object is defined in its reference state by inequality , then the points of the transformed object are

since the originals belong to the set of points of the reference state.

Parametric equations define the Cartesian coordinates of the points directly. Thus the transformation of parametric surface requires the transformations of its points

Similarly, the transformation of curve is:

Transformation may change the type of object in the general case. It can happen, for example, that a simple triangle or a sphere becomes a complicated shape, which are hard to describe and handle. Thus it is worth limiting the set of allowed transformations. Transformations mapping planes onto planes, lines onto lines and points onto points are particularly important. In the next subsection we consider the class of homogeneous linear transformations, which meet this requirement.

22.5.1. 22.5.1 Projective geometry and homogeneous coordinates

So far the construction of the virtual world has been discussed using the means of the Euclidean geometry, which gave us many important concepts such as distance, parallelism, angle, etc. However, when the transformations are discussed in details, many of these concepts are unimportant, and can cause confusion. For example, parallelism is a relationship of two lines which can lead to singularities when the intersection of two lines is considered. Therefore, transformations are discussed in the context of another framework, called projective geometry.

The axioms of projective geometry turn around the problem of parallel lines by ignoring the concept of parallelism altogether, and state that two different lines always have an intersection. To cope with this requirement, every line is extended by a “point at infinity” such that two lines have the same extra point if and only if the two lines are parallel. The extra point is called the ideal point. The projective space contains the points of the Euclidean space (these are the so called affine points) and the ideal points. An ideal point “glues” the “ends” of an Euclidean line, making it topologically similar to a circle. Projective geometry preserves that axiom of the Euclidean geometry which states that two points define a line. In order to make it valid for ideal points as well, the set of lines of the Euclidean space is extended by a new line containing the ideal points. This new line is called the ideal line. Since the ideal points of two lines are the same if and only if the two lines are parallel, the ideal lines of two planes are the same if and only if the two planes are parallel. Ideal lines are on the ideal plane, which is added to the set of planes of the Euclidean space. Having made these extensions, no distinction is needed between the affine and ideal points. They are equal members of the projective space.

Introducing analytic geometry we noted that everything should be described by numbers in computer graphics. Cartesian coordinates used so far are in one to one relationship with the points of Euclidean space, thus they are inappropriate to describe the points of the projective space. For the projective plane and space, we need a different algebraic base.

22.5.1.1.  Projective plane.

Let us consider first the projective plane and find a method to describe its points by numbers. To start, a Cartesian coordinate system is set up in this plane. Simultaneously, another Cartesian system is established in the three-dimensional space embedding the plane in a way that axes are parallel to axes , the plane is perpendicular to axis , the origin of the Cartesian system of the plane is in point of the three-dimensional space, and the points of the plane satisfy equation . The projective plane is thus embedded into a three-dimensional Euclidean space where points are defined by Descartes-coordinates (Figure 22.29). To describe a point of the projective plane by numbers, a correspondence is found between the points of the projective plane and the points of the embedding Euclidean space. An appropriate correspondence assigns that line of the Euclidean space to either affine or ideal point of the projective plane, which is defined by the origin of the coordinate system of the space and point .

Points of an Euclidean line that crosses the origin can be defined by parametric equation where is a free real parameter. If point is an affine point of the projective plane, then the corresponding line is not parallel with plane (i.e. is not constant zero). Such line intersects the plane of equation at point , thus the Cartesian coordinates of point in planar coordinate system are . On the other hand, if point is ideal, then the corresponding line is parallel to the plane of equation (i.e. ). The direction of the ideal point is given by vector .

The presented approach assigns three dimensional lines crossing the origin and eventually triplets to both the affine and the ideal points of the projective plane. These triplets are called the homogeneous coordinates of a point in the projective plane. Homogeneous coordinates are enclosed by brackets to distinguish them from Cartesian coordinates.

A three-dimensional line crossing the origin and describing a point of the projective plane can be defined by its arbitrary point except the origin. Consequently, all three homogeneous coordinates cannot be simultaneously zero, and homogeneous coordinates can be freely multiplied by the same non-zero scalar without changing the described point. This property justifies the name “homogeneous”.

It is often convenient to select that triplet from the homogeneous coordinates of an affine point, where the third homogeneous coordinate is 1 since in this case the first two homogeneous coordinates are identical to the Cartesian coordinates:

From another point of view, Cartesian coordinates of an affine point can be converted to homogeneous coordinates by extending the pair by a third element of value 1.

The embedded model also provides means to define the equations of the lines and line segments of the projective space. Let us select two different points on the projective plane and specify their homogeneous coordinates. The two points are different if homogeneous coordinates of the first point cannot be obtained as a scalar multiple of homogeneous coordinates of the other point. In the embedding space, triplet can be regarded as Cartesian coordinates, thus the equation of the line fitted to points and is:

If , then the affine points of the projective plane can be obtained by projecting the three-dimensional space onto the plane of equation . Requiring the two points be different, we excluded the case when the line would be projected to a single point. Hence projection maps lines to lines. Thus the presented equation really identifies the homogeneous coordinates defining the points of the line. If , then the equation expresses the ideal point of the line.

If parameter has an arbitrary real value, then the points of a line are defined. If parameter is restricted to interval , then we obtain the line segment defined by the two endpoints.

22.5.1.2.  Projective space.

We could apply the same method to introduce homogeneous coordinates of the projective space as we used to define the homogeneous coordinates of the projective plane, but this approach would require the embedding of the three-dimensional projective space into a four-dimensional Euclidean space, which is not intuitive. We would rather discuss another construction, which works in arbitrary dimensions. In this construction, a point is described as the centre of mass of a mechanical system. To identify a point, let us place weight at reference point , weight at reference point , weight at reference point , and weight at reference point . The centre of mass of this mechanical system is:

Let us denote the total weight by . By definition, elements of quadruple are the homogeneous coordinates of the centre of mass.

To find the correspondence between homogeneous and Cartesian coordinates, the relationship of the two coordinate systems (the relationship of the basis vectors and the origin of the Cartesian coordinate system and of the reference points of the homogeneous coordinate system) must be established. Let us assume, for example, that the reference points of the homogeneous coordinate system are in points (1,0,0), (0,1,0), (0,0,1), and (0,0,0) of the Cartesian coordinate system. The centre of mass (assuming that total weight is not zero) is expressed in Cartesian coordinates as follows:

Hence the correspondence between homogeneous coordinates and Cartesian coordinates is ():

The equations of lines in the projective space can be obtained either deriving them from the embedding four-dimensional Cartesian space, or using the centre of mass analogy:

If parameter is restricted to interval , then we obtain the equation of the projective line segment.

To find the equation of the projective plane, the equation of the Euclidean plane is considered (equation 22.1). The Cartesian coordinates of the points on an Euclidean plane satisfy the following implicit equation

Using the correspondence between the Cartesian and homogeneous coordinates (equation 22.17) we still describe the points of the Euclidean plane but now with homogeneous coordinates:

Let us multiply both sides of this equation by , and add those points to the plane which have coordinate and satisfy this equation. With this step the set of points of the Euclidean plane is extended with the ideal points, that is, we obtained the set of points belonging to the projective plane. Hence the equation of the projective plane is a homogeneous linear equation:

or in matrix form:

Note that points and planes are described by row and column vectors, respectively. Both the quadruples of points and the quadruples of planes have the homogeneous property, that is, they can be multiplied by non-zero scalars without altering the solutions of the equation.

22.5.2. 22.5.2 Homogeneous linear transformations

Transformations defined as the multiplication of the homogeneous coordinate vector of a point by a constant matrix are called homogeneous linear transformations:

Theorem 22.12 Homogeneous linear transformations map points to points.

Proof. A point can be defined by homogeneous coordinates in form , where is an arbitrary, non-zero constant. The transformation results in when a point is transformed, which are the -multiples of the same vector, thus the result is a single point in homogeneous coordinates.

Note that due to the homogeneous property, homogeneous transformation matrix is not unambiguous, but can be freely multiplied by non-zero scalars without modifying the realized mapping.

Theorem 22.13 Invertible homogeneous linear transformations map lines to lines.

Proof. Let us consider the parametric equation of a line:

and transform the points of this line by multiplying the quadruples with the transformation matrix:

where and are the transformations of and , respectively. Since the transformation is invertible, the two points are different. The resulting equation is the equation of a line fitted to the transformed points.

We note that if we had not required the invertibility of the the transformation, then it could have happened that the transformation would have mapped the two points to the same point, thus the line would have degenerated to single point.

If parameter is limited to interval , then we obtain the equation of the projective line segment, thus we can also state that a homogeneous linear transformation maps a line segment to a line segment. Even more generally, a homogeneous linear transformation maps convex combinations to convex combinations. For example, triangles are also mapped to triangles.

However, we have to be careful when we try to apply this theorem in the Euclidean plane or space. Let us consider a line segment as an example. If coordinate has different sign at the two endpoints, then the line segment contains an ideal point. Such projective line segment can be intuitively imagined as two half lines and an ideal point sticking the “endpoints” of these half lines at infinity, that is, such line segment is the complement of the line segment we are accustomed to. It may happen that before the transformation, coordinates of the endpoints have similar sign, that is, the line segment meets our intuitive image about Euclidean line segments, but after the transformation, coordinates of the endpoints will have different sign. Thus the transformation wraps around our line segment.

Theorem 22.14 Invertible homogeneous linear transformations map planes to planes.

Proof. The originals of transformed points defined by are on a plane, thus satisfy the original equation of the plane:

Due to the associativity of matrix multiplication, the transformed points also satisfy equation

which is also a plane equation, where

This result can be used to obtain the normal vector of a transformed plane.

An important subclass of homogeneous linear transformations is the set of affine transformations, where the Cartesian coordinates of the transformed point are linear functions of the original Cartesian coordinates:

where vector describes translation, is a matrix of size and expresses rotation, scaling, mirroring, etc., and their arbitrary combination. For example, the rotation around axis , () by angle is given by the following matrix

This expression is known as the Rodrigues-formula.

Affine transformations map the Euclidean space onto itself, and transform parallel lines to parallel lines. Affine transformations are also homogeneous linear transformations since equation (22.22) can also be given as a matrix operation, having changed the Cartesian coordinates to homogeneous coordinates by adding a fourth coordinate of value 1:

A further specialization of affine transformations is the set of congruence transformations (isometries) which are distance and angle preserving.

Theorem 22.15 In a congruence transformation the rows of matrix have unit length and are orthogonal to each other.

Proof. Let us use the property that a congruence is distance and angle preserving for the case when the origin and the basis vectors of the Cartesian system are transformed. The transformation assigns point to the origin and points , , and to points , , and , respectively. Because the distance is preserved, the distances between the new points and the new origin are still 1, thus , , and . On the other hand, because the angle is also preserved, vectors , , and are also perpendicular to each other.

Exercises

22.5-1 Using the Cartesian coordinate system as an algebraic basis, prove the axioms of the Euclidean geometry, for example, that two points define a line, and that two different lines may intersect each other at most at one point.

22.5-2 Using the homogeneous coordinates as an algebraic basis, prove an axiom of the projective geometry stating that two different lines intersect each other in exactly one point.

22.5-3 Prove that homogeneous linear transformations map line segments to line segments using the centre of mass analogy.

22.5-4 How does an affine transformation modify the volume of an object?

22.5-5 Give the matrix of that homogeneous linear transformation which translates by vector .

22.5-6 Prove the Rodrigues-formula.

22.5-7 A solid defined by inequality in time moves with uniform constant velocity . Let us find the inequality of the solid at an arbitrary time instance .

22.5-8 Prove that if the rows of matrix are of unit length and are perpendicular to each other, then the affine transformation is a congruence. Show that for such matrices .

22.5-9 Give that homogeneous linear transformation which projects the space from point onto a plane of normal and place vector .

22.5-10 Show that five point correspondences unambiguously identify a homogeneous linear transformation if no four points are co-planar.