home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_06_06 / v6n6055a.txt < prev    next >
Text File  |  1989-09-28  |  14KB  |  498 lines
  1. /* *********************************************************************
  2. *
  3.  *
  4.  *  A Simple Model for Hiding Surfaces
  5.  *  Jay Martin Anderson
  6.  *  Franklin & Marshall College, Lancaster, Pennsylvania
  7.  *  Tymlabs Corporation, Austin, Texas
  8.  *
  9.  *  This program draws a three-dimensional object described by a table
  10.  *  of faces using hidden-surface elimination.
  11.  *  The algorithm is described briefly in M. Berger, "Computer Graphics
  12.  *  with Pascal," (Benjamin/Cummings, 1986), and in somewhat greater
  13.  *  detail by R. J. Rost, reported in Creative Computing, February, 1984
  14. .
  15.  *
  16.  *  Implemented for HP CRTs on HP 3000, using Pascal and AGL (HP's graph
  17. ics
  18.  *     language, April, 1984; revised, April, 1986; March, 1988; revised
  19.  *     to use Tymlabs' C/3000 for the HP 3000, May, 1988.
  20.  *
  21.  *  Implemented May, 1988, for the Apple Macintosh (monochrome), using
  22.  *     Lightspeed C and Quickdraw graphics (Macintosh toolbox).
  23.  *
  24.  * ********************************************************************
  25. */
  26.  
  27.  /* ********************* #INCLUDEd files *****************************
  28. */
  29.  #include "stdio.h"
  30.   /* Use the "stdio" window provided by Lightspeed C, which is
  31.    * 500 pixels wide by 288 pixels tall, rather than using window
  32.    * management from Mac toolbox directly.
  33.    */
  34.  #include "unix.h"
  35.  #include "Quickdraw.h"
  36.  #include "math.h"
  37.  
  38.  /* ********************* Some Common DEFINEs *************************
  39. */
  40.  #define MAXFACES 60     /* maximum number of faces */
  41.  #define MAXPTS 100                    /* maximum number of vertices */
  42.  #define NVF 4       /* vertices/face; squares  */
  43.  #define HUGE_VAL 1.0E77    /* a very large number */
  44.  #define TRUE  1
  45.  #define FALSE 0
  46.  #define sysPatListID 0     /* Resource ID, patterns */
  47.  typedef float MATRIX[4][4];            /* 4x4 matrix of real numers */
  48.  struct faceS       /* what we know about a face */
  49.  {
  50.   float z;    /* smallest Z, eye coords, for face */
  51.   int color;    /* "color" of this face */
  52.   int v[NVF];    /* list of vertices for this face */
  53.  };
  54.  
  55.  /* ********************* Global Variables ****************************
  56. */
  57.  int v[MAXFACES][NVF];      /* vertex list */
  58.  float x0[MAXPTS], y0[MAXPTS], z0[MAXPTS]; /* original coordinates */
  59.  float xt[MAXPTS], yt[MAXPTS], zt[MAXPTS]; /* transformed coordinates */
  60.  float xs[MAXPTS], ys[MAXPTS];    /* screen coordinates */
  61.  struct faceS faceList[MAXFACES];   /* list of faces */
  62.  MATRIX view;        /* viewing transformation */
  63.  float eyex, eyey, eyez;     /* position of eye */
  64.  float fx, fy, fz;       /* where eye is focussing */
  65.  float ds;         /* scale factor */
  66.  float horizRotn;       /* rotation of horizon */
  67.  float n1, n2, n3;       /* normal to a face */
  68.  int numFaces, numVertices, numVisFaces;
  69.  
  70.  int readFaceData()
  71.  {
  72.   /* Hardcoded for one cube of size 2, centered at origin;
  73.    * Example 1.
  74.    */
  75.   /* for each vertex, its coordinates */
  76.   x0[0] =  1.0, y0[0] =  1.0, z0[0] =  1.0;
  77.   x0[1] = -1.0, y0[1] =  1.0, z0[1] =  1.0;
  78.   x0[2] = -1.0, y0[2] = -1.0, z0[2] =  1.0;
  79.   x0[3] =  1.0, y0[3] = -1.0, z0[3] =  1.0;
  80.   x0[4] =  1.0, y0[4] =  1.0, z0[4] = -1.0;
  81.   x0[5] = -1.0, y0[5] =  1.0, z0[5] = -1.0;
  82.   x0[6] = -1.0, y0[6] = -1.0, z0[6] = -1.0;
  83.   x0[7] =  1.0, y0[7] = -1.0, z0[7] = -1.0;
  84.   /* for each face, its vertex list in CCW order */
  85.   v[0][0] = 0, v[0][1] = 1, v[0][2] = 2, v[0][3] = 3; /* top */
  86.   v[1][0] = 1, v[1][1] = 5, v[1][2] = 6, v[1][3] = 2; /* rear */
  87.   v[2][0] = 3, v[2][1] = 2, v[2][2] = 6, v[2][3] = 7; /* left */
  88.   v[3][0] = 0, v[3][1] = 3, v[3][2] = 7, v[3][3] = 4; /* front */
  89.   v[4][0] = 1, v[4][1] = 0, v[4][2] = 4, v[4][3] = 5; /* right */
  90.   v[5][0] = 4, v[5][1] = 7, v[5][2] = 6, v[5][3] = 5; /* bottom */
  91.  
  92.   return(TRUE);
  93.  }
  94.  
  95.  #define COS1 0.540302
  96.  #define SIN1 0.841471
  97.  int getParams()
  98.  {
  99.   /* Hardcoded for a sequence of views of the one cube which is
  100.    * hardcoded in "readDataFile."  Values are initialized in "initStuff"
  101. .
  102.    */
  103.  
  104.    float tempx, tempy;
  105.  
  106.    /* Position of eye */
  107.    tempx = eyex;
  108.    tempy = eyey;
  109.  
  110.    /* Spiral the viewer, or eye, around the object; at each
  111.     * iteration, rotation by 1 radian, and move up by 1/2 unit.
  112.     * To save time, use defined constants for cos(1) and sin(1).
  113.     */
  114.    eyex = COS1*tempx - SIN1*tempy;
  115.    eyey = SIN1*tempx + COS1*tempy;
  116.    eyez += 0.5;
  117.  
  118.   /* Focus point; where eye is looking */
  119.    fx = fy = fz = 0.0;
  120.  
  121.    if (eyez > 10.0) return(FALSE);  /* that's enough */
  122.    else return(TRUE);
  123.  }
  124.  
  125.  void initMat(M)
  126.  MATRIX M;
  127.  {
  128.   /* Construct a 4x4 identity matrix */
  129.   int i, j;       /* subscript; loop index */
  130.  
  131.   for (i = 0; i < 4; i++)
  132.    for (j = 0; j < 4; j++)
  133.     M[i][j] = (i != j) ? 0.0 : 1.0;
  134.  }
  135.  
  136.  void multMat(M3, M1, M2)
  137.  MATRIX M1, M2, M3;
  138.  {
  139.   /* Multiply M1 x M2 and put result in M3; 4x4 square matrices */
  140.   int i, j, k;      /* subscript; loop index */
  141.  
  142.   for (i = 0; i < 4; i++)
  143.    for (j = 0; j < 4; j++)
  144.    {
  145.     M3[i][j] = 0.0;
  146.     for (k = 0; k < 4; k++) M3[i][j] += M1[i][k]*M2[k][j];
  147.    }
  148.  }
  149.  
  150.  void calcViewMatrix()
  151.  {
  152.   /* Calculate the viewing transformation matrix */
  153.   int i, j;     /* matrix subscripts; loop index */
  154.   MATRIX t1, t2;    /* temp matrices for transformation */
  155.   double d1, d2;    /* temporary results */
  156.  
  157.   initMat(view);
  158.  
  159.   /* translate origin to eye position */
  160.   view[3][0] = -eyex;
  161.   view[3][1] = -eyey;
  162.   view[3][2] = -eyez;
  163.   initMat(t1);
  164.  
  165.   /* rotate about x-axis by 90 degrees */
  166.   t1[1][1] = 0.0;
  167.   t1[2][2] = 0.0;
  168.   t1[1][2] = -1.0;
  169.   t1[2][1] = 1.0;
  170.   multMat(t2, view, t1);
  171.   for (i = 0; i < 4; i++)
  172.    for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  173.  initMat(t1);
  174.  
  175.   /* rotate about y-axis by an angle dependent on focus point */
  176.   fx = eyex - fx;
  177.   fy = eyey - fy;
  178.   fz = eyez - fz;
  179.   d1 = sqrt((double)(fx*fx + fy*fy));
  180.   if (fabs(d1) > 0.0001)
  181.   {
  182.    t1[0][0] = -fy/d1;
  183.    t1[2][2] = -fy/d1;
  184.    t1[0][2] =  fx/d1;
  185.    t1[2][0] = -fx/d1;
  186.    multMat(t2, view, t1);
  187.    for (i = 0; i < 4; i++)
  188.     for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  189.   }
  190.   initMat(t1);
  191.  
  192.   /* rotate about x-axis by angle dependent on focus point */
  193.   d2 = sqrt((double)(fx*fx + fy*fy  + fz*fz));
  194.   if (fabs(d2) > 0.0001)
  195.   {
  196.    t1[1][1] = d1/d2;
  197.    t1[2][2] = d1/d2;
  198.    t1[1][2] = fz/d2;
  199.    t1[2][1] = -fz/d2;
  200.    multMat(t2, view, t1);
  201.    for (i = 0; i < 4; i++)
  202.     for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  203.   }
  204.   initMat(t1);
  205.  
  206.   /* rotate about z-axis to rotate horizon */
  207.   horizRotn *= PI/180.0; /* convert degrees to radians */
  208.   t1[0][0] = t1[1][1] = (float)cos((double)horizRotn);
  209.   t1[0][1] = (float)sin((double)horizRotn);
  210.   t1[1][0] = -t1[0][1];
  211.   multMat(t2, view, t1);
  212.   for (i = 0; i < 4; i++)
  213.    for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  214.   initMat(t1);
  215.  
  216.   /* invert the z-axis */
  217.   t1[2][2] = -1.0;
  218.   /* and scale according to D/S ratio */
  219.   t1[0][0] = ds;
  220.   t1[1][1] = ds;
  221.   multMat(t2, view, t1);
  222.   for (i = 0; i < 4; i++)
  223.    for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  224. }
  225.  
  226. void initStuff()
  227. {
  228.  /* Whatever needs to be initialized; may be device-dependent;
  229.   * may be implementation-dependent.  Includes fixed parameters for
  230.   * this example.
  231.   */
  232.  
  233.   numFaces = 6;
  234.   numVertices = 8;
  235.  
  236.  /* Write at upper left of console window */
  237.  gotoxy(0,0);
  238.  puts("Example 1.  Cube.");
  239.  
  240.  /* Initial position of eye */
  241.  eyez = -10.0;
  242.  eyex = 7.50;
  243.  eyey = 13.0;
  244.  
  245.    /* Horizon rotation */
  246.    horizRotn = 0.0;
  247.    /* Scaling factor */
  248.    ds = 1.5;
  249. }
  250.  
  251. void finishStuff()
  252. {
  253.  /* Whatever needs to be closed, etc.  May be device-dependent;
  254.   * may be implementation-dependent.
  255.   *
  256.   * Nothing to do in this example.
  257.   */
  258. }
  259.  
  260. void transform(px, py, pz)
  261. float *px, *py, *pz;
  262. {
  263.  /* Transforms a point, pointed to by px, py, pz, by view transform */
  264.  
  265.  float temp1, temp2, temp3;
  266.  temp1 = *px, temp2 = *py, temp3 = *pz;
  267.  *px = view[0][0]*temp1+view[1][0]*temp2+view[2][0]*temp3+view[3][0];
  268.  *py = view[0][1]*temp1+view[1][1]*temp2+view[2][1]*temp3+view[3][1];
  269.  *pz = view[0][2]*temp1+view[1][2]*temp2+view[2][2]*temp3+view[3][2];
  270. }
  271.  
  272. void transformAll()
  273. {
  274.  /* Transforms all points */
  275.  int i;
  276.  for (i = 0; i < numVertices; i++) transform(&xt[i],&yt[i],&zt[i]);
  277. }
  278.  
  279. void getCrossProduct(nv1, nv2, nv3)
  280. int nv1,nv2,nv3;
  281. {
  282.  /* Computes cross-product of vectors representing two sides of a face;
  283.   * the two sides are the vectors from vertex nv2-nv1 and nv3-nv1.  The
  284.   * cross-product is the outward normal to this face; its three
  285.   * components are stored in the global variables n1, n2, n3.
  286.   */
  287.  float v1, v2, v3, w1, w2, w3;
  288.  
  289.  v1 = xt[nv2] - xt[nv1];
  290.  v2 = yt[nv2] - yt[nv1];
  291.  v3 = zt[nv2] - zt[nv1];
  292.  w1 = xt[nv3] - xt[nv1];
  293.  w2 = yt[nv3] - yt[nv1];
  294.  w3 = zt[nv3] - zt[nv1];
  295.  n1 = v2*w3 - v3*w2;
  296.  n2 = v3*w1 - v1*w3;
  297.  n3 = v1*w2 - v2*w1;
  298. }
  299.  
  300. void getDotProduct(pdot, nv1)
  301. float *pdot;      /* the dot product */
  302. int nv1;       /* which vertex */
  303. {
  304.  /* Computes the dot product of the outbound normal from a face
  305.   * with vector from eye to face.
  306.   */
  307.  *pdot = n1*xt[nv1] + n2*yt[nv1] + n3*zt[nv1];
  308. }
  309.  
  310. void eyeToScreen(x, y, z, px, py)
  311. float x, y, z, *px, *py;
  312. {
  313.  /* Transforms a point from x, y, z eye coordinates to
  314.   * x, y screen coordinates.  This includes the projection
  315.   * and the use of the physical screen size in pixels
  316.   */
  317.  float xC, yC;     /* center of screen */
  318.  float xR, yR;     /* width of screen */
  319.  
  320.  /* Hardcoded for Lightspeed "stdio window" */
  321.  xC = 250, yC = 144;
  322.  xR = 500, yR = 288;
  323.  *px = xR*(x/z) + xC;
  324.  *py = yR - (yR*(y/z) + yC);
  325. }
  326.  
  327. int zcompare(pFace1, pFace2)
  328. struct faceS *pFace1, *pFace2;
  329. {
  330.  /* Comparison function used by C library function "qsort" to do
  331.   * sorting.  This function compares the minimum z coordinate of
  332.   * faces, so that faces are sorted in the order of distance from
  333.   * eye.  This is a DESCENDING sort!!
  334.   */
  335.  if (pFace1->z < pFace2->z) return(1);
  336.  else if (pFace1->z > pFace2->z) return(-1);
  337.  else return(0);
  338. }
  339.  
  340. void sortFaces()
  341. {
  342.  /* Sorts the faceList in descending order of Z for a Z-buffer
  343.   * display; uses quicksort as implemented in library.
  344.   * Requires the preceding function which compares z values for
  345.   * faces.
  346.   */
  347.  
  348.  qsort(faceList, numVisFaces, sizeof(struct faceS), zcompare);
  349.  }
  350.  
  351. void drawFace(f)
  352. int f;
  353. {
  354.  /* This procedure draws a face.  It is device- and implementation-
  355.   * dependent.  In this implementation, it uses the Lightspeed C
  356.   * "stdio" or console window, and Macintosh Quickdraw procedures.
  357.   *
  358.   * Each face is a polygon, and is developed with the sequence
  359.   * OpenPoly...MoveTo or LineTo...ClosePoly.  The "color" of a
  360.   * face is interpreted as a QuickDraw pen pattern, and is looked
  361.   * up in the system pattern list.  The system pattern list is
  362.   * presumed to be available.  It consists of 38 patterns.  The
  363.   * first six of these patterns are used for the 6 faces of a
  364.   * cube.  Each face is then "framed," that is, outlined in solid
  365.   * black.
  366.   */
  367.  PolyHandle aFace;
  368.  Pattern thePattern;
  369.  
  370.  /* Develop the 4-sided polygon which is a face */
  371.  aFace = OpenPoly();
  372.  MoveTo((int)xs[faceList[f].v[0]],(int)ys[faceList[f].v[0]]);
  373.  LineTo((int)xs[faceList[f].v[1]],(int)ys[faceList[f].v[1]]);
  374.  LineTo((int)xs[faceList[f].v[2]],(int)ys[faceList[f].v[2]]);
  375.  LineTo((int)xs[faceList[f].v[3]],(int)ys[faceList[f].v[3]]);
  376.  LineTo((int)xs[faceList[f].v[0]],(int)ys[faceList[f].v[0]]);
  377.  ClosePoly();
  378.  
  379.  /* "Color" the face */
  380.  GetIndPattern(thePattern, sysPatListID, faceList[f].color);
  381.  PenPat(thePattern);
  382.  PaintPoly(aFace);
  383.  
  384.  /* Outline or frame the face */
  385.  PenPat(black);
  386.  FramePoly(aFace);
  387.  
  388.  /* That's all for this face; dispose of the polygon */
  389.  KillPoly(aFace);
  390. }
  391.  
  392. void screenAll()
  393. {
  394.  /* Projects from eye coordinates to screen coordinates */
  395.  int i;
  396.  
  397.  for (i = 0; i < numVertices; i++)
  398.  {
  399.   eyeToScreen(xt[i], yt[i], zt[i], &xs[i], &ys[i]);
  400.  }
  401. }
  402.  
  403. void doFace(f, ff)
  404. int f, ff;
  405. {
  406.  /* Adds a face to the visible face list and computes its z */
  407.  float zmin;
  408.  int i;
  409.  
  410.  zmin = HUGE_VAL;
  411.  for (i = 0; i < NVF; i++)
  412.  {
  413.   faceList[ff].v[i] = v[f][i];
  414.   if (zt[v[f][i]] < zmin) zmin = zt[v[f][i]];
  415.  }
  416.  faceList[ff].z = zmin;
  417.  faceList[ff].color = f + 1;  /* first six Mac patterns */
  418. }
  419.  
  420. void copyData()
  421. {
  422.  /* Copies the original data so we can transform it without
  423.   * destroying the original
  424.   */
  425.  int i;
  426.  
  427.  for (i = 0; i < numVertices; i++)
  428.   xt[i] = x0[i], yt[i] = y0[i], zt[i] = z0[i];
  429. }
  430.  
  431. void drawPicture()
  432. {
  433.  /* This prcoedure draws the scene, with hidden surfaces removed */
  434.  int i;
  435.  float dot;
  436.  
  437.  transformAll();     /* Transformation to eye coords */
  438.  screenAll();     /* And to screen coords */
  439.  numVisFaces = 0;
  440.  for (i = 0; i < numFaces; i++)
  441.  {
  442.   /* ******  HERE IS THE HIDDEN SURFACE REMOVAL ALGORITHM!!!  ******
  443.    * Compute the cross-product of any two sides of a face (we use
  444.    * the sides 1-0 and 2-0).  This gets an outbound normal from the
  445.    * face. Take the dot product of the outbound normal with a vector
  446.    * from the eye to the face (we use vector from eye to vertex 0).
  447.    * If the dot product is non-negative, the face is visible.
  448.    * ************************************************************ */
  449.   getCrossProduct(v[i][0], v[i][1], v[i][2]);
  450.   getDotProduct(&dot, i);
  451.   if (dot >= 0.0)
  452.   {
  453.    doFace(i, numVisFaces);
  454.    numVisFaces++;
  455.   }
  456.  }
  457.  
  458.  /* Arrange the faces in decreasing order of distance-from-eye,
  459.   * so that the last face to be drawn is the one nearest the viewer.
  460.   * This extends the basic algorithm to allow scenes to be made up
  461.   * of more than one solid figure, in some cases.  It is called a
  462.   * z-buffer algorithm, because the faces to be drawn are buffered
  463.   * in order of their "z" value.
  464.   */
  465.  sortFaces();
  466.  
  467.  /* Erase screen before drawing */
  468.  eraseplot();
  469.  
  470.  /* ... and draw all visible faces */
  471.  for (i = 0; i < numVisFaces; i++) drawFace(i);
  472. }
  473.  
  474.  main()
  475.  {
  476.   int ok;
  477.   initStuff();     /* Any and all initializations */
  478.  
  479.   ok = TRUE;
  480.  do
  481.  {
  482.    ok = readFaceData();  /* Get faces and make safe copy */
  483.    copyData();
  484.    if (ok)
  485.    {
  486.     ok = getParams();  /* Get parameters for this picture */
  487.     if (ok)
  488.     {
  489.      calcViewMatrix(); /* Calculate viewing transformation */
  490.      drawPicture();  /* Draw this picture */
  491.     }
  492.    }
  493.   } while (ok);
  494.  
  495.   finishStuff();     /* Any cleanup and closing */
  496.  }
  497.  
  498.