14. Transformations.   

Three basic transformations: 


Translation of point:

                     (x,y) --> (x+Tx,y+Ty)

                    same scale same orientation

Scale:

                     (x,y) --> (Sx*x, Sy*y)

                    same origin same orientation

Rotation:

                     (x,y) --> (x*cos-y*sin, x*sin+y*cos)

                    rotate point anticlockwise through  degrees

                    same origin same scale.

We may combine these transformations and , in fact, we almost always do but we must preserve the order of transformations and we must know what is being transformed. We shall consider transformations on the object and not the axes. Transformations on the object are obviously related to axes transforms. Note Newman and Sproull use the same system but with a clockwise angle hence the theta used is really negative theta in our system. 

Example: Assume we have a graphics box.

 (1) Rotate it through -90 degrees

 (2) Shift it up by ten units

 (3) Scale it by a factor of 2.

 Look at origin (0,0) and point (10,10) and see how they are affected.

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

          (10,10)  (10*cos(-90) - 10sin(-90), 10*sin(-90) + 10*cos(-90))

                    (10cos(90) + 10sin(90), -10sin(90) + 10cos(90))

                    (10,-10)

 (2)      (0,0)    (0,10)

          (10,-10)  (10,0)  Note we use the new co-ordinates

 (3)      (0,10)   (0,20)     Scale x and y

          (10,0)   (20,0)  use new co-ordinates from last transformation.

 
transformation.eps
Convince yourself that the order of operations is important by performing in the reverse direction. It is convenient to use matrices to store the mathematical manipulations for the transformations. 

We represent a point (x,y) as       [x y 1]

14.1. Matrices.   

This vector can then be manipulated by matrices which represent the basic transformations. It is important to understand matrix multiplication and the order in which the matrix multiplication is carried out.


To translate a point:

We can check the result of this by multiplying our vector with this matrix. 


 [ x y 1 ] . 
            =====> [x+Tx y+Ty 1 ]

Similarly to change scale we can use a matrix.


and again to check our result we multiply our vector. 


 [ x y 1 ] . 
            =====> [x*Sx y*Sy 1 ]

And to rotate the point about the origin: 


 [ x y 1 ] . 
            =====> [x*Cos- y*Sin  x*Sin+y*Cos 1 ]

In our example we would have the following transformation matrices: 

     1 0 0       2 0 0      0 -1 0 

 T=  0 1 0  S=  0 2 0  R=  1 0 0 

     0 10 1       0 0 1      0 0 1

We could apply these individually to the two points to get each intermediate new co-ordinate. However the power of this method is that we can use the total transformation matrix directly. We must multiply our three (in this case) matrices in the correct order. Therefore Rotate then Translate then Scale ==== R.T.S. Note '.' means matrix multiplication. This method multiplies the transformational matrices to give a total transformational matrix M which can then be used to transform any point:
[x' y' 1] = [x y 1] . M 


    
Examples of Transformations.

   
          Fig. 14.1 : Examples of Transformations.
Therefore the entire transformation matrix is 


     0 -1 0    1 0 0    2 0 0 

     1 0 0  .  0 1 0  .  0 2 0  == R.T.S

     0 0 1    0 10 1    0 0 1 


     0 -1 0    2 0 0 

     1 0 0  .  0 2 0  == Temp.S

     0 10 1    0 0 1 


     0 -2 0 

     2 0 0  == Total Transformation Matrix.

     0 20 1

We can check this quickly by applying it to (0,0) and (10,10): 


                  0 -2 0 

    [ 0 0 1 ] .  2 0 0  == [ 0 20 1 ]

                  0 20 1 


                  0 -2 0 

    [ 10 10 1 ] .  2 0 0  == [ 20 0 1 ]

                  0 20 1

14.2. Routines for Transforming.   

We can write general procedures to handle these 3 transformations and then use them in our programs. 



     subprogram translate(tx,ty:real;a:real array[1..3,1..3]);

      a[1,1]  1.0;     a[1,2]  0.0; a[1,3]  0.0;

        a[2,1]  0.0; a[2,2]  1.0; a[2,3]  0.0;

        a[3,1]  tx; a[3,2]  ty; a[3,3]  1.0;

     end_subprogram_translate.


     subprogram scale(sx,sy:real; a:real array[1..3,1..3]);

      a[1,1]  sx;     a[2,2]  sy; a[3,3]  1.0;


      a[1,3]  0.0; a[2,3]  0.0; a[2,1]  0.0;

      a[1,2]  0.0; a[3,1]  0.0; a[3,2]  0.0;

     end_subprogram_scale.


     subprogram rotate(theta:real;a:real array[1..3,1..3]);

     local real angle;

      angle  theta * 2.0 * PI /360.0;

      a[1,1]  cos(angle);     a[2,2]  cos(angle);

      a[2,1]  -sin(angle); a[1,2]  sin(angle);


        a[3,1]  0.0; a[3,3]  1.0;

      a[3,2]  0.0; a[1,3]  0.0; a[2,3]  0.0;

     end_subprogram_rotate.

We need to be able to multiply as well therefore we write a matrix multiply routine that multiplies two three x three matrices. 

     subprogram multiply(a,b,c: real array[1..3,1..3]);

     local integer i,j,k;

     local real cij; {Used purely for efficiency .}

      for i  1 to 3 do

       for j  1 to 3 do

         cij  0;

         for k  1 to 3 do

          cij  cij + a[i,k] * b[k,j];

         end for

         c[i,j]  cij;

       end for

      end for

     end_subprogram_multiply.

Note (yet again) that transforming the origin (axes) is different to transforming the object. How do the matrices change?

Consider the following transformation process: 


    
Strange transformation.

   
             Fig. 14.2 : Strange transformation.
What combination of translation, rotation and possibly scaling is needed to transform the left into the right?

Manipulation of three dimensional objects - (x,y,z) - also use matrices: a 4x4 matrix for rotation, scaling and translation. These may be multiplied together in a similar fashion to 3x3. 


Example:

An astroid (sic) has parametric equation

            (R* cos^3(),R* sin^3())


Move it to (xc,yc) and rotate it anti-clockwise by theta degrees.


          :

          call     rotate(theta,q);

          call     translate(xc,yc,p);     {load up these matrices}

          call     multiply(q,p,r);

          call     myplot(radius,0.0,3);

          theta  0.0;

          thetainc  0.031415.....;

          for i  1 to 200 do

            theta theta + thetainc;

            call       myplot(radius* cos^3(theta),radius* sin^3(theta),2);

          end for

          :


          subprogram  myplot(x,y:real; n:integer);

          global real array[1..3,1..3] r

           call     plot(r[1,1]*x + r[2,1]*y +r[3,1],

                         r[1,2]*x + r[2,2]*y +r[3,2], n)

           return;

          end_subprogram_myplot.

We create a new routine that plots but also applies a transform to the point to be plotted. This is a very powerful mechanism if it is used properly. We could write a program that draws a standard object using plot commands and then by changing all plots into myplots we could easily apply transformations to it.
And to remove the transformations we simply comment out the plot command in myplot that transforms and add one that does a direct plot of x, y, and n. We will see that a similar mechanism can be used when storing generated images on disk for reproduction on the plotter. Surprise!!


14.3. Circles by transforms.   

It is possible to use DDA techniques to generate circles,ellipses etc as well as straight lines. The equation of a circle is : 



       X2 + Y2 = R2                    2xdx + 2ydy = 0


       dy      -x

=>     --  =  --

       dx       y


This leads to

       Xn+1  Xn +  Yn

       Yn+1  Yn -  Xn          as before.

But we derived dy/dx = -x/y with respect to dR. i.e the unit step is not in the X or Y direction but in the radial direction. Therefore the above produces a spiral since every increment is in radial direction. It is possible to "doctor" the equations and use: 

       Xn+1  Xn +  Yn

       Yn+1  Yn -  Xn+1

This is in fact an ellipse but with small enough 1-2 ==1.
Why do we know it is an ellipse?
`Because when we combine the two equations to get a relationship between X and Y we get: 

          Yn+1  - Xn + (1-2) Yn

It is also possible to draw exact circles using our recently gained knowledge of transformations. We first draw a small line segment from (X0,Y0) to (Xn,Yn) and then rotate this segment by angle theta to get (Xn+1,Yn+1) and draw again. 


 [ Xn+1 Yn+1 1 ] =  [ Xn Yn 1] .

=> 

     Xn+1  Xn*Cos() + Yn*Sin()

     Yn+1  Yn*Cos() - Xn*Sin()  (if  clockwise)

This is as on page 28 of Newman and Sproull. Bresenham has his usual smart algorithm for DDA generation of a circle with minimal arithmetic.