Related Info: Quickdraw

Line Art Rotation

By Jeffrey J. Martin, College Station, TX

This being my first stab at an article, I will try to keep it short while leaving in all of the essential vitamins and nutrients. In that spirit my user interface will bring back nostalgic thoughts to those past Apple II and TRS-80 users, and any PC people will feel right at home.

The essence of this program is to show how a seemingly complicated transformation and rotation can be applied to an array of points that form any arbitrary line art.

Of course to form a transformation on the array of points (e.g. offset the points to the left) we simply add some delta x(dx) and/or delta y(dy) to every point:

/* 1 */

for(i=0;i<numofpoints;i++)
  {points[i].h+=dx;points[i].v+=dy;}

Now rotation is a little harder, but to spare you the heartache, it can be shown that for rotation about the origin(fig 1):

So the trick of rotating about some arbitrary point is to first transform that pivot point to be the origin(transforming every other point by the save amount). Second, perform the rotation of all points by the angle theta. Third, transform the pivot back(once again transforming all other points as well).

Now all of this may seem to be a costly maneuver, but the fact is that we can roll all of these into a single matrix multiplication, using homogeneous coordinates:

where

form one matrix.

Fig. 2 shows the multiplication of a homogeneous coordinate and a translation matrix. Please verify that this results in (X+dx,Y+dy) (if unfamiliar with matrix multiplication see mult procedure in program).

Similarly figure 3 shows multiplication with a rotation matrix - an exact translation of our rotation equations in matix form.

So the translation, rotation, and inverse translation matrices are as shown in figure 4. Which forms one matrix to be multiplied times the vertices.

The following program allows the user to enter in points with the mouse until a key is pressed. At that time the user then uses the mouse to enter a pivot point. The program uses the pivot point to form the translation and inverse translation matrices(from the x and y coordinates). The program then forms a rotation matrix of a constant rotation angle(Π/20) and calculates the new vertices based on the values of the old ones. The program undraws the old lines and redraws the new and calculates again until the object has rotated through a shift of 4Π(2 rotations). press the mouse button again to exit program.

Once again, I point out that the code does not follow the user guidelines, but then it is not exactly meant to be an application in itself. Build your own program around it and see what you can do. One suggestion is to cancel the erasing of the object to achieve spirograph patterns. I think too many of the submissions to MacTutor contain an interface that we all know too well, and for those just interested in the algorithms it can mean a lot of extra work. Have Fun.

/* 2 */

#include<math.h>
int errno;

void mult();  /*out matrix mult proc*/
/*floating value of points to avoid roundoff*/
typedef struct rec {float h,v;} points;
main()
{
  int buttondown=0, /*flagg for mouse       */
      n=-1,         /*number of vertices    */
      keypressed=0, /*flagg for key         */
      flip=0,       /*to allow alternating  */
      flop=1,       /*vertices to be drawn  */
      i;            /*array counter         */
  float x,          /*angle counter         */
      T[3][3],      /*translation matrix    */
      Tinv[3][3],   /*translate back        */
      Rz[3][3],     /*rotate matrix         */
      c[3][3],      /*result of T&R         */
      d[3][3];      /*result of c&Tinv      */
  long curtick,     /*for delay loop        */
       lastick;     /*for delay loop        */
  EventRecord nextevent;/*to get mouse&key  */
  Point origin,dummy;   /*pivot and locator */
  points points[2][30];/*vertices(don’t draw Eiffel tower)  */
  WindowPtr scnwdw;    /*window pointer     */
  Rect      scnrect;   /*window rect        */
/*************************************
*  Set things up                     *
*************************************/
InitGraf(&thePort);
InitFonts();
InitWindows();
InitDialogs((Ptr)0L);
TEInit();
InitMenus();
scnrect=screenBits.bounds;
InsetRect(&scnrect,10,25);
scnwdw=NewWindow(0,&scnrect,”\p”,TRUE,dBoxProc, -1,FALSE,0);
SetPort(scnwdw);
InitCursor();
  
/*************************************
*  Get points                        *
*************************************/
  while(!keypressed)
  {
    buttondown=0;
    SystemTask();
    if(GetNextEvent(-1,&nextevent))
      if(nextevent.what==mouseDown) buttondown=1;
      else if(nextevent.what==keyDown) keypressed=1;
    if(buttondown) /*get a point and draw it*/ 
    {
      GetMouse(&dummy);
      points[0][++n].h=dummy.h;points[0][n].v=dummy.v; 
      if(n==0)
        MoveTo((int)points[0][0].h,(int)points[0][0].v);
      LineTo((int)points[0][n].h,(int)points[0][n].v);
    } /*end of get point*/
  }  /*end of get points*/
  
/*************************************
*  Get origin                        *
*************************************/
  buttondown=0;
  do
  {
    SystemTask();
    if(GetNextEvent(-1,&nextevent))
      if(nextevent.what==mouseDown) buttondown=1;
  }while(!buttondown);
  GetMouse(&origin);
  
/*************************************
*  Make translation matrix           *
*************************************/
  T[0][0]=1;T[0][1]=0;T[0][2]=0;
  T[1][0]=0;T[1][1]=1;T[1][2]=0;
  T[2][0]=-origin.h;T[2][1]=-origin.v;T[2][2]=1;
  Tinv[0][0]=1;Tinv[0][1]=0;Tinv[0][2]=0;
  Tinv[1][0]=0;Tinv[1][1]=1;Tinv[1][2]=0;
  Tinv[2][0]=origin.h;Tinv[2][1]=origin.v;Tinv[2][2]=1;
  Rz[0][2]=0;Rz[1][2]=0;Rz[2][0]=0;Rz[2][1]=0;Rz[2][2]=1;
/*************************************
*  Rotate                            *
*************************************/
  x=0.157;  /*rotation angle - about 9 degrees*/
  Rz[0][0]=Rz[1][1]=cos(x);Rz[0][1]=sin(x);
  Rz[1][0]=-Rz[0][1];
  mult(T,Rz,c);
  mult(c,Tinv,d);
  for(x=.157;x<=12.56;x+=0.157)
  {
    flip++;flip=flip%2;flop++;flop=flop%2;
    for(i=0;i<=n;i++)
    {
      points[flip][i].h=points[flop][i].h*d[0][0]
                    +points[flop][i].v*d[1][0]+1*d[2][0];
      points[flip][i].v=points[flop][i].h*d[0][1]
                    +points[flop][i].v*d[1][1]+1*d[2][1];
    }  /*end update points*/
    ForeColor(whiteColor);  /*undraw flop*/
    lastick=TickCount(); /*time delay for retace to improve animation*/
    do{curtick=TickCount();} while(lastick+1>curtick);
    MoveTo((int)points[flop][0].h,(int)points[flop][0].v);
    for(i=1;i<=n;i++) LineTo((int)points[flop][i].h,(int)points[flop][i].v);
    ForeColor(blackColor);  /*draw flip*/
    lastick=TickCount();    
    do{curtick=TickCount();} while(lastick+1>curtick);
    MoveTo((int)points[flip][0].h,(int)points[flip][0].v);
    for(i=1;i<=n;i++) LineTo((int)points[flip][i].h,(int)points[flip][i].v);
  }  /*end rotate*/
    
/*************************************
*  End everything                    *
*************************************/
  buttondown=0;
  do
  {
    SystemTask();
    if(GetNextEvent(-1,&nextevent))
      if(nextevent.what==mouseDown) buttondown=1;
  }while(!buttondown);
DisposeWindow(scnwdw);
}  /*program end*/

void mult(A,B,C)
  float A[][3],B[][3],C[][3];
{
  int i,j,k;
  
  for(i=0;i<=2;i++)
    for(j=0;j<=2;j++)
    {
      C[i][j]=0.0;
      for(k=0;k<=2;k++)
        C[i][j]+=A[i][k]*B[k][j];
    }
}  /*end mult*/

3D Modeling & Rotation

The main thrust of this exercise is to extend the line art rotation into 3D object rotation using the same techniques as the 2D, while also implementing parallel projection as our means of 3D modeling.

The first part of the exercise requires that we define an object in a structure that we can easily manipulate. Using a cube for simplicity, we will start by defining the center of the cube and an array of vertices, vertex[2][# of pts] (see GetPoints in program). Referring to fig. 1, each vertex corresponds to a corner of the cube. The second dimension of the array is to provide a destination for transformed vertices. Having both sets will allow us to undraw and immediately redraw the shape - minimizing the hangtime between redrawing allows for smoother animation.

Figure 1.

Next let us construct an array of lines connecting these vertices. Each element of the line array refers to the index of the beginning and ending vertex of that particular line. This array will never change. Think of when you roll a die - the edges still go between the same corners, but the position of the corners has changed.

The next construct is the translation and inverse translation matrixes. As in 2D rotation, we must transform our local center of rotation to the origin, rotate, then translate back.

The idea of homogeneous coordinates was introduced in the last article and is now extended into 3D by adding a fourth term. Fig. 2 shows our homogeneous coordinate as a 1x4 matrix times our translation matrix(4x4). The purpose of this multiplication is to add a dx, dy and dz to every point, in order to center our vertices about the origin. Please verify that the matrix multiplication results in X+dx,Y+dy,Z+dz (if unfamiliar with matrix multiplication see matmult in program).

Figure 2.

Now we once again reach the challenging concept of rotation. Although similar to 2D, we now have the option of rotating around the X and Y as well as the Z-axis.

The simplest, rotation about the z-axis, is just as in our 2D rotations, because none of the z-values change. If this is hard to understand, think about this: if you look straight down a pencil with the point a foot away from you and spin it a half turn, the point is still a foot away, but the writing is now on the other side. The equations for the changes in the X and Y are as follows:

  Xnew=XoldCos(Ø) + YoldSin(Ø)
  Ynew=-XoldSin(Ø) + YoldCos(Ø)

The 3D representation in matrix form with a vertex multiplication is in fig. 3. And the proof of all this is in that dusty old trigonometry book up on your shelf. (once again direct multiplication of fig. 3 will yield the preceding equations).

Figure 3.

Similarly rotation about the X axis changes none of the x-values, and rotation about Y changes none of the y-values. The transformation equations are given as follows:

Rotation about the X:

 Ynew=YoldCos(Ø) + ZoldSin(Ø)
 Znew=-YoldSin(Ø)+ZoldCos(Ø)

Rotation about the Y:

   Xnew=XoldCos(Ø) - ZoldSin(Ø)
 Znew=XoldSin(Ø) + ZoldCos(Ø)

The corresponding matrices are shown in figures 4 and 5.

Figure 4.

Figure 5.

Once again we will construct a new array of vertices from a single transformation matrix formed from the translation to the origin, rotation about an axis, and translation back. Therefore creating the new vertices:

 Vnew=Vold*T*Rz*Tinv

or after combining T*Rz*Tinv into a single Master Transformation(MT):

 Vnew=Vold*MT

Finally the trick of parallel projection when viewing an object from down the Z axis is that all you have to do is draw lines between the x,y components of the points (ignore the z). For those mathematically inclined, you will realize that this is just the projection of those 3D lines on the X-Y plane (see fig. 6).

Figure 6.

The particular stretch of code I’ve included implements this transformation on the cube for rotation along the X and Y axes of the center of the cube using the arrow keys. The successive transformations of the vertices are loaded into the flip of the array (vertex[flip][pnt.#]). Then the flop is undrawn while the flip is drawn as mentioned previously and flip and flop are changed to their corresponding 0 or 1.

After launching, the application immediately draws the cube and then rotates it in response to the arrows. The program exits after a single mouse click.

Once again the code is not intended to match up to the guidelines - but is intended for use with other code or simple instructional purposes. It is concise as possible and should be easy to type in. A quick change to numofpts and numoflines as well as your own vertex and and line definitions would allow you to spin your favorite initial into its most flattering orientation.

The inspiration for this program came from the floating couch problem presented in Dirk Gently’s Holistic Detective Agency, by Douglas Adams. If enough interest is shown, perhaps a future article would include hidden line removal and color rendering techniques. After all, it was a red couch.

One last suggestion for those truly interested is to pull your shape definition in from a 3D cad program that will export in text format, such as Super 3D or AutoCad.

Anyway, on with the show

/* 3 */

#include<math.h>
/* Following is inline macro for drawing lines */
#define viewpts(s) {for(i=0;i<numoflns;i++)  \
                     { MoveTo((int)vertex[s][line[i].v1].x,  \
                       (int)vertex[s][line[i].v1].y); \
                       LineTo((int)vertex[s][line[i].v2].x, \
                       (int)vertex[s][line[i].v2].y); }}  
 
#define numofpts 8 /* A cube has eight vertices */
#define numoflns 12    /* lines for every face. */

/* the following are the data structs for vertices and lines*/ typedef 
struct rec1 {float x,y,z;} point3d;
typedef struct rec2 {int v1,v2;} edge;
void mult();/* Matrices multiplication */

main()
{
  point3d vertex[2][8], /* array of 3D pts   */
          center;/* centroid of cube */
  edge    line[12];/* array of lines */
  int     buttondown=0, /* mousedwn flag(for prog end)*/
          keypressed=0,       /* keydwn flg(for arrows)     */
          flip=0,             /* This is index for vertex so*/
          flop=1,             /* can undraw flip & draw flop*/
          i,                  /* counter           */
          rot=0; /* Flag for direction of rotat*/
  long    low;   /* low word of keydwn message */
  float   a,/* Particular angle of rotat     */
          R[4][4], /* Rotation matrix*/
          c[4][4], /* Product of trans & rot mats*/
          d[4][4], /* Product of c and inv trans */
          T[4][4],Tinv[4][4], /* Translation & inv trans    */
          x=0.087266;/* Algle of rot in rad  */
  EventRecord nextevent;
  KeyMap    thekeys;
  WindowPtr scnwdw;
  Rect      scnrect;
/*********************************************
*  Set things up *
*********************************************/
InitGraf(&thePort);
InitFonts();
FlushEvents(everyEvent,0);
InitWindows();
InitMenus();
TEInit();
InitDialogs(0);
InitCursor();
scnrect=screenBits.bounds;
InsetRect(&scnrect,50,50);
scnwdw=NewWindow(0,&scnrect,”\p”,TRUE,dBoxProc,-1,FALSE,0);
  
/*********************************************
*  Get points. Arbitrary cube.*
*********************************************/
center.x=300;center.y=200;center.z=120;
vertex[0][0].x=280;vertex[0][0].y=220;vertex[0][0].z=100;
vertex[0][1].x=320;vertex[0][1].y=220;vertex[0][1].z=100;
vertex[0][2].x=320;vertex[0][2].y=180;vertex[0][2].z=100;
vertex[0][3].x=280;vertex[0][3].y=180;vertex[0][3].z=100;
vertex[0][4].x=280;vertex[0][4].y=220;vertex[0][4].z=140;
vertex[0][5].x=320;vertex[0][5].y=220;vertex[0][5].z=140;
vertex[0][6].x=320;vertex[0][6].y=180;vertex[0][6].z=140;
vertex[0][7].x=280;vertex[0][7].y=180;vertex[0][7].z=140;
line[0].v1=0;line[0].v2=1;
line[1].v1=1;line[1].v2=2;
line[2].v1=2;line[2].v2=3;
line[3].v1=3;line[3].v2=0;
line[4].v1=0;line[4].v2=4;
line[5].v1=1;line[5].v2=5;
line[6].v1=2;line[6].v2=6;
line[7].v1=3;line[7].v2=7;
line[8].v1=4;line[8].v2=5;
line[9].v1=5;line[9].v2=6;
line[10].v1=6;line[10].v2=7;
line[11].v1=7;line[11].v2=4;
T[0][0]=1;T[0][1]=0;T[0][2]=0;T[0][3]=0;
T[1][0]=0;T[1][1]=1;T[1][2]=0;T[1][3]=0;
T[2][0]=0;T[2][1]=0;T[2][2]=1;T[2][3]=0;
T[3][0]=-center.x;T[3][1]=-center.y;T[3][2]=-center.z;T[3][3]=1;
Tinv[0][0]=1;Tinv[0][1]=0;Tinv[0][2]=0;Tinv[0][3]=0;
Tinv[1][0]=0;Tinv[1][1]=1;Tinv[1][2]=0;Tinv[1][3]=0;
Tinv[2][0]=0;Tinv[2][1]=0;Tinv[2][2]=1;Tinv[2][3]=0;
Tinv[3][0]=center.x;Tinv[3][1]=center.y;Tinv[3][2]=center.z;Tinv[3][3]=1;

/*********************************************
*  Rotate *
*********************************************/
viewpts(flip);   /* This draws first set of pts*/
  while(!buttondown) /* Mini event loop*/
  {
    keypressed=0;
    SystemTask();
    if(GetNextEvent(-1,&nextevent))
      if(nextevent.what==mouseDown) buttondown=1;
      else if(nextevent.what==keyDown) keypressed=1;
      else if(nextevent.what==autoKey) keypressed=1;
    if(keypressed) /* Find out which one     */
    {
      keypressed=0;
      low=LoWord(nextevent.message);
      low=BitShift(low,-8);
      if(low==126) {rot=1;a=-x;} /* Set dir flag and-*/
      if(low==124) {rot=2;a=-x;} /* angle(pos or neg */
      if(low==125) {rot=3;a=x;}
      if(low==123) {rot=4;a=x;}
      switch(rot)
      {
        case 1:/* Both of these are rot about the X axis */
        case 3: R[0][0]=1;R[0][1]=0;R[0][2]=0;R[0][3]=0;
 R[1][0]=0;R[1][1]=cos(a);R[1][2]=sin(a);R[1][3]=0;
 R[2][0]=0;R[2][1]=-sin(a);R[2][2]=cos(a);R[2][3]=0;
 R[3][0]=0;R[3][1]=0;R[3][2]=0;R[3][3]=1;break;
        case 2:/* Both of these are rot about the Y axis */
        case 4: 
 R[0][0]=cos(a);
 R[0][1]=0;R[0][2]=-sin(a);R[0][3]=0;
       R[1][0]=0;R[1][1]=1;R[1][2]=0;R[1][3]=0;
       R[2][0]=sin(a);R[2][1]=0;R[2][2]=cos(a);R[2][3]=0;
       R[3][0]=0;R[3][1]=0;R[3][2]=0;R[3][3]=1;break;
      }  /*end switch*/
      mult(T,R,c); /* Combine trans & rotation */
      mult(c,Tinv,d);/* Combine that and inv trans */
      flip++;flip=flip%2;flop++;flop=flop%2; /* flip flop   */
      /* The following actually calculates new vert of rotat*/
      for(i=0;i<numofpts;i++)
      {
        vertex[flip][i].x=vertex[flop][i].x*d[0][0]
                    +vertex[flop][i].y*d[1][0]
                    +vertex[flop][i].z*d[2][0]
                    +1*d[3][0];
        vertex[flip][i].y=vertex[flop][i].x*d[0][1]
                    +vertex[flop][i].y*d[1][1]
                    +vertex[flop][i].z*d[2][1]
                    +1*d[3][1];
        vertex[flip][i].z=vertex[flop][i].x*d[0][2]
                    +vertex[flop][i].y*d[1][2]
                    +vertex[flop][i].z*d[2][2]
                    +1*d[3][2];
       }
       ForeColor(whiteColor);
       viewpts(flop);/* Undraw*/
       ForeColor(blackColor);
       viewpts(flip);/* Draw*/
    }  /*end update points*/
  }

/*********************************************
*  End everything*
*********************************************/
DisposeWindow(scnwdw);
}  /*program end*/

void mult(A,B,C)
  float A[][4],B[][4],C[][4];
{
  int i,j,k;
  
  for(i=0;i<=3;i++)
    for(j=0;j<=3;j++)
    {
      C[i][j]=0.0;
      for(k=0;k<=3;k++)
        C[i][j]+=A[i][k]*B[k][j];
    }
}  /*end mult*/