Concatenation of Transformations and Homogeneous Coordinates

Look again at transformations in terms of vectors.

Scaling: x' = x * Sx, y' = y * Sy, which can be written as:

 (x' y') = (x  y) * (Sx   0)
                    (0   Sy)

Rotation: x' = x cos q - y sin q, y' = y cos q + x sin q, which can be written as:

(x' y') = (x y) * ( cos q    sin q)  
                  (-sin q    cos q)  

So if we wanted to scale and then rotate the object we could do the following:

		  
(x' y')  =  (x  y) * ( Sx   0 )
                     ( 0   Sy )   

(x" y")  =  (x' y') * ( cos q   sin q )
                      (-sin q   cos q)

But this is the same as:

(x" y") =  (x  y) * (Sx  0) * ( cos q   sin q )
                    (0  Sy)    (-sin q   cos q )
	 
       =   (x  y) * ( Sx * cos q    Sx * sin q)
                    (-Sy * sin q    Sy * cos q )

Hence, we can concatenate the Scaling and Rotation matrices, and then multiply the old points by resultant matrix.

What about translation?

x' = x + Tx
y' = y + Ty

There isno way to express this as a multiplicative transformation with a 2D matrix. Therefore we go into hyperspace (N + 1 dimensions) , i.e., we embed 2D space into 3D space. We express all coordinates as (xh, yh, w) where w is the "z" coordinate. This is called a "Homogeneous" coordinate system.

The relationship between the original coordinates (x,y) and the homogeneous coordinates (xh, yh) is given by: xh = x * w, yh = y * w . We will generally use w = 1 so our 3D vector is (x, y, 1). Then we can express the modeling transformations as follows:

Translation (represented by T= (Tx,Ty)):

                      ( 1   0   0 )
(x' y' 1) = (x y 1) * ( 0   1   0 )
                      ( Tx  Ty  1 ) 

which gives:

x' = x + 1 * Tx          
y' = y + 1 * Ty                             
1 = 1                                           

Scaling (represented by S= (Sx, Sy)): 
                      ( Sx  0  0 ) 
(x' y' 1) = (x y 1) * ( 0  Sy  0 ) 
                      ( 0   0  1 )

which gives:

x' = x * Sx 
y' = y * Sy  

Rotation (represented by R(q):  
		      ( cos q sin q 0 )
(x' y' 1) = (x y 1) * (-sin q cos q 0 ) 
                      ( 0      0    1 ) 
which gives: 
x' = x cos q - y sin q 
y' = y cos q + x sin q 

So the solution to the problem of rotating or scaling an object about a point Po (xo, yo) is as follows:

1. Translate Po to origin: T(-xo, -yo)
2. Rotate: R(q)
3. Translate back to Po: T(+xo, +yo)

So (x' y') = (x y) * M with M = T(-xo , -yo) * R(q) * T(+xo , +yo )

Efficiency of using a composition matrix

Look at efficiency of constructing a composition matrix M and applying M to a set of points versus applying each transformation matrix to the set of points.

3D-matrix multiplication requires 3 * and 2 + for each element. Hence 3 x 9 = 27 (* & + operations) are required to multiply two 3D matrices, (Note: even with numeric data processors a * is about 1/3 the speed of a + so we are ignoring +) , So to concatenate N matrices requires: (N - 1)*( 27 ops.).

Multiplying a 3 element vector x 3D matrix 3 x 3 = 9 (ops.), But we have a special case since

                      ( a   d   0)
(x' y' 1) = (x y 1) * ( b   e   0)  
                      ( c   f   1)  

which gives:

x' = ax + by + c     4 * and 4 +  or 4 ops per point
y' = dx + ey + f  

 

So if we applied each matrix individually to the points:

N = number of transformations = number of matrices
k = number of points
The total number of operation. = N * k * 4 (1)

For the case where we concatenate the transformations and then apply the resultant matrix tothe points:

(2) number of ops. = (N - 1) * 27 + 4 * k
At some value of k (1) > (2)

To find the crossover value of k, set the two equations equal to each other and find k:

27( N - 1 ) + 4k = 4Nk n > 2
27(N - 1) = 4Nk - 4k
27(N - 1) / 4(N - 1) = k = 27 / 4 or about 7 points.

Therefore, (2) is more efficient for any object with > 7 points.

Examples of transformations:

Look at scaling.

For bottom transformation this corresponds to :

1. R(-45) i.e. rotation by -45 (aligning y = x with x)
2. reflection about x-axis
3. R(+45 )

Composite matrix =

(0 1 0)
(1 0 0)
(0 1 0)


Main 2D Modeling page
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed June 02, 1999, G. Scott Owen, owen@siggraph.org