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 )

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.