home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_06_06 / v6n6060a.txt < prev    next >
Text File  |  1989-09-28  |  15KB  |  504 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;
  19.  *     implemented in 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    /* 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
  49.  {
  50.   float z;    /* smallest Z, eye coords, for face */
  51.   int color;    /* "color" of this face; a Mac gray pattern */
  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 or viewer */
  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.  FILE *theFile;        /* points to data file */
  70.  
  71.  int readFaceData()
  72.  {
  73.   /* Hardcoded to read from a file 9 cubes:  72 vertices and
  74.    * 54 faces.  The name of the file is "cubedata," and it is
  75.    * presumed to be in the same folder as this project.  Standard
  76.    * C-library I/O is used, rather than Macintosh Toolbox I/O.
  77.    * File is opened in "initStuff" and closed in "finishStuff".
  78.    */
  79.  
  80.   int i;
  81.  
  82.  for (i = 0; i < numVertices; i++)
  83.   fscanf(theFile, "%f %f %f",&x0[i],&y0[i],&z0[i]);
  84.  for (i = 0; i < numFaces; i++)
  85.   fscanf(theFile, "%d %d %d %d",&v[i][0],&v[i][1],&v[i][2],&v[i][3]);
  86.  fseek(theFile, 0L, 0); /* rewind the file */
  87.  if (ferror(theFile))
  88.  {
  89.   puts("error reading CUBEDATA file");
  90.   return(FALSE);
  91.  }
  92.  else
  93.  {
  94.   return(TRUE);
  95.  }
  96.  }
  97.  
  98.  int getParams()
  99.  {
  100.    /* Hardcoded for one reasonable view of the scene of 9 cubes. */
  101.  
  102.    /* Position of eye */
  103.   eyex = 20.0; eyey = 25.0; eyez = 25.0;
  104.   /* Focus point; where eye is looking */
  105.    fx = fy = fz = 0.0;
  106.  
  107.    return(TRUE);
  108.  }
  109.  
  110.  void initMat(M)
  111.  MATRIX M;
  112.  {
  113.   /* Construct a 4x4 idenity matrix */
  114.   int i, j;       /* subscript; loop index */
  115.  
  116.   for (i = 0; i < 4; i++)
  117.    for (j = 0; j < 4; j++)
  118.     M[i][j] = (i != j) ? 0.0 : 1.0;
  119.  }
  120.  
  121.  void multMat(M3, M1, M2)
  122.  MATRIX M1, M2, M3;
  123.  {
  124.   /* Multiply M1 x M2 and put result in M3; 4x4 square matrices */
  125.   int i, j, k;
  126.  
  127.   for (i = 0; i < 4; i++)
  128.    for (j = 0; j < 4; j++)
  129.    {
  130.     M3[i][j] = 0.0;
  131.     for (k = 0; k < 4; k++) M3[i][j] += M1[i][k]*M2[k][j];
  132.    }
  133.  }
  134.  
  135.  void calcViewMatrix()
  136.  {
  137.   /* Calculates the viewing transformation matrix */
  138.   int i, j;      /* subscript; loop index */
  139.   MATRIX t1, t2;     /* temp matrices for transformation */
  140.   double d1, d2;     /* temp results */
  141.  
  142.   initMat(view);
  143.  
  144.   /* translate origin to eye position */
  145.   view[3][0] = -eyex;
  146.   view[3][1] = -eyey;
  147.   view[3][2] = -eyez;
  148.   initMat(t1);
  149.  
  150.   /* rotate about x-axis by 90 degrees */
  151.   t1[1][1] = 0.0;
  152.   t1[2][2] = 0.0;
  153.   t1[1][2] = -1.0;
  154.   t1[2][1] = 1.0;
  155.   multMat(t2, view, t1);
  156.   for (i = 0; i < 4; i++)
  157.    for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  158.  initMat(t1);
  159.  
  160.   /* rotate about y-axis by an angle dependent on focus point */
  161.   fx = eyex - fx;
  162.   fy = eyey - fy;
  163.   fz = eyez - fz;
  164.   d1 = sqrt((double)(fx*fx + fy*fy));
  165.   if (fabs(d1) > 0.0001)
  166.   {
  167.    t1[0][0] = -fy/d1;
  168.    t1[2][2] = -fy/d1;
  169.    t1[0][2] =  fx/d1;
  170.    t1[2][0] = -fx/d1;
  171.    multMat(t2, view, t1);
  172.    for (i = 0; i < 4; i++)
  173.     for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  174.   }
  175.   initMat(t1);
  176.  
  177.   /* rotate about x-axis by angle dependent on focus point */
  178.   d2 = sqrt((double)(fx*fx + fy*fy  + fz*fz));
  179.   if (fabs(d2) > 0.0001)
  180.   {
  181.    t1[1][1] = d1/d2;
  182.    t1[2][2] = d1/d2;
  183.    t1[1][2] = fz/d2;
  184.    t1[2][1] = -fz/d2;
  185.    multMat(t2, view, t1);
  186.    for (i = 0; i < 4; i++)
  187.     for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  188.   }
  189.   initMat(t1);
  190.  
  191.   /* rotate about z-axis to rotate horizon */
  192.   horizRotn *= PI/180.0; /* convert degrees to radians */
  193.   t1[0][0] = t1[1][1] = (float)cos((double)horizRotn);
  194.   t1[0][1] = (float)sin((double)horizRotn);
  195.   t1[1][0] = -t1[0][1];
  196.   multMat(t2, view, t1);
  197.   for (i = 0; i < 4; i++)
  198.    for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  199.   initMat(t1);
  200.  
  201.   /* invert the z-axis */
  202.   t1[2][2] = -1.0;
  203.   /* and scale according to D/S ratio */
  204.   t1[0][0] = ds;
  205.   t1[1][1] = ds;
  206.   multMat(t2, view, t1);
  207.   for (i = 0; i < 4; i++)
  208.    for (j = 0; j < 4; j++) view[i][j] = t2[i][j];
  209. }
  210.  
  211. void initStuff()
  212. {
  213.  /* Whatever needs to be initialized; may be device-dependent;
  214.   * may be implementation-dependent.  Includes fixed parameters
  215.   * for this example.
  216.   */
  217.  
  218.  numVertices = 72;
  219.  numFaces = 54;
  220.  
  221.  /* Write at upper left of console window */
  222.  gotoxy(0,0);
  223.  puts("Example 2.  Cube of cubes.");
  224.  
  225.  /* Open the data file */
  226.  theFile = fopen("cubedata","r");
  227.  if (theFile == NULL)
  228.  {
  229.   puts("error opening CUBEDATA file");
  230.  }
  231.  
  232.    /* Horizon rotation */
  233.    horizRotn = 0.0;
  234.    /* Scaling factor */
  235.    ds = 1.0;
  236.  
  237. }
  238.  
  239. void finishStuff()
  240. {
  241.  /* Whatever needs to be closed, etc.  May be device-dependent;
  242.   * may be implementation-dependent.
  243.   * In this example, close the data file.
  244.   */
  245.  fclose(theFile);
  246. }
  247.  
  248. void transform(px, py, pz)
  249. float *px, *py, *pz;
  250. {
  251.  /* Transforms a point, pointed to be px, py, pz, by the view transf. */
  252.  
  253.  float temp1, temp2, temp3;
  254.  /* Transforms a point, pointed to by px, py, pz, by view transform */
  255.  temp1 = *px, temp2 = *py, temp3 = *pz;
  256.  *px = view[0][0]*temp1+view[1][0]*temp2+view[2][0]*temp3+view[3][0];
  257.  *py = view[0][1]*temp1+view[1][1]*temp2+view[2][1]*temp3+view[3][1];
  258.  *pz = view[0][2]*temp1+view[1][2]*temp2+view[2][2]*temp3+view[3][2];
  259.  
  260. }
  261.  
  262. void transformAll()
  263. {
  264.  /* Transforms all points */
  265.  int i;
  266.  for (i = 0; i < numVertices; i++) transform(&xt[i],&yt[i],&zt[i]);
  267. }
  268.  
  269. void getCrossProduct(nv1,nv2,nv3)
  270. int nv1,nv2,nv3;
  271. {
  272.  /* Computes cross-product of vectors representing two sides of a face;
  273.   * the two sides are the vectors from nv2-nv1 and nv3-nv1.  The
  274.   * cross-product is the outward normal to this face; its three
  275.   * components are stored in the global variables n1, n2, n3.
  276.   */
  277.  float v1, v2, v3, w1, w2, w3;
  278.  
  279.  v1 = xt[nv2] - xt[nv1];
  280.  v2 = yt[nv2] - yt[nv1];
  281.  v3 = zt[nv2] - zt[nv1];
  282.  w1 = xt[nv3] - xt[nv1];
  283.  w2 = yt[nv3] - yt[nv1];
  284.  w3 = zt[nv3] - zt[nv1];
  285.  n1 = v2*w3 - v3*w2;
  286.  n2 = v3*w1 - v1*w3;
  287.  n3 = v1*w2 - v2*w1;
  288. }
  289.  
  290. void getDotProduct(pdot, nv1)
  291. float *pdot;       /* the dot product */
  292. int nv1;        /* which vertex */
  293. {
  294.  /* Computes the dot product of the outbound normal from a face,
  295.   * kept in the global variables n1, n2, n3, with a vector from
  296.   * the eye to the face, using a vector from the eye to vertex nv1.
  297.   */
  298.  *pdot = n1*xt[nv1] + n2*yt[nv1] + n3*zt[nv1];
  299. }
  300.  
  301. void eyeToScreen(x, y, z, px, py)
  302. float x, y, z, *px, *py;
  303. {
  304.  /* Transforms a point from x, y, z eye coordinates to
  305.   * x, y screen coordinates.  This includes the projection
  306.   * and the use of the physical screen size in pixels
  307.   */
  308.  float xC, yC;     /* center of screen */
  309.  float xR, yR;     /* width of screen */
  310.  
  311.  /* hardcoded for Lightspeed "stdio window" for now */
  312.  xC = 250, yC = 144;
  313.  xR = 500, yR = 288;
  314.  *px = xR*(x/z) + xC;
  315.  *py = yR - (yR*(y/z) + yC);
  316. }
  317.  
  318. int zcompare(pFace1, pFace2)
  319. struct faceS *pFace1, *pFace2;
  320. {
  321.  /* Comparison function used by C library function "qsort" to do
  322.   * sorting.  This function compares the minimum z coordinate of
  323.   * the faces, so that faces are sorted in the order of distance
  324.   * from the eye.  This is a DESCENDING sort!!
  325.   */
  326.  if (pFace1->z < pFace2->z) return(1);
  327.  else if (pFace1->z > pFace2->z) return(-1);
  328.       else return(0);
  329. }
  330.  
  331. void sortFaces()
  332. {
  333.  /* Sorts the faceList in ascending order of Z for a Z-buffer
  334.   * display; uses quicksort as implemented in library.
  335.   * Requires the preceding function which compares z values for
  336.   * faces.
  337.   */
  338.  
  339.  qsort(faceList, numVisFaces, sizeof(struct faceS), zcompare);
  340.  }
  341.  
  342. /* ******************** QUICKDRAW GRAPHICS PROCEDURES *****************
  343. */
  344. void drawFace(f)
  345. int f;
  346. {
  347.  /* This procedure draws a face.  It is device- and implementation-
  348.   * dependent.  In this implementation, it uses the Lightspeed C
  349.   * "stdio" or console window, and Macintosh Quickdraw procedures.
  350.   *
  351.   * Each face is a polygon, and is developed with the sequence
  352.   * OpenPoly...MoveTo or LineTo...ClosePoly.  The "color" of a
  353.   * face is interpreted as a QuickDraw pen pattern, and is looked
  354.   * up in the system pattern list.  The system pattern list is
  355.   * presumed to be available.  It consists of 38 patterns.  The
  356.   * first six of these patterns are used for the six faces of
  357.   * the cubes.  Each face is then "framed," that is, outlined
  358.   * in solid black.
  359.   *
  360.   * In this example, a transparent face is marked with color 0.
  361.   * Transparent faces are not filled with pattern.
  362.   */
  363.  PolyHandle aFace;
  364.  Pattern thePattern;
  365.  
  366.  aFace = OpenPoly();
  367.  MoveTo((int)xs[faceList[f].v[0]],(int)ys[faceList[f].v[0]]);
  368.  LineTo((int)xs[faceList[f].v[1]],(int)ys[faceList[f].v[1]]);
  369.  LineTo((int)xs[faceList[f].v[2]],(int)ys[faceList[f].v[2]]);
  370.  LineTo((int)xs[faceList[f].v[3]],(int)ys[faceList[f].v[3]]);
  371.  LineTo((int)xs[faceList[f].v[0]],(int)ys[faceList[f].v[0]]);
  372.  ClosePoly();
  373.  if (faceList[f].color > 0)
  374.  {
  375.   GetIndPattern(thePattern, sysPatListID, faceList[f].color);
  376.   PenPat(thePattern);
  377.   PaintPoly(aFace);
  378.  }
  379.  PenPat(black);
  380.  FramePoly(aFace);
  381.  KillPoly(aFace);
  382. }
  383.  
  384. void screenAll()
  385. {
  386.  /* Projects from eye coordinates to screen coordinates */
  387.  int i;
  388.  
  389.  for (i = 0; i < numVertices; i++)
  390.  {
  391.   eyeToScreen(xt[i], yt[i], zt[i], &xs[i], &ys[i]);
  392.  }
  393. }
  394.  
  395. void doFace(f, ff, opaque)
  396. int f,      /* index into vertex list */
  397.     ff,      /* index into faceList */
  398.     opaque;     /* TRUE/FALSE: is face opaque? */
  399. {
  400.  /* Adds a face to the visible face list and computes its z */
  401.  float zmin;
  402.  int i;
  403.  
  404.  zmin = HUGE_VAL;
  405.  for (i = 0; i < NVF; i++)
  406.  {
  407.   faceList[ff].v[i] = v[f][i];
  408.   if (zt[v[f][i]] < zmin) zmin = zt[v[f][i]];
  409.  }
  410.  faceList[ff].z = zmin;
  411.  /* If the face is opaque, fill it with one of the first six
  412.   * Macintosh patterns.  Otherwise, set its color to 0 for
  413.   * transparency.
  414.   */
  415.  if (opaque) faceList[ff].color = (f%6) + 1;
  416.  else faceList[ff].color = 0;
  417. }
  418.  
  419. void copyData()
  420. {
  421.  /* Copies the original data so we can transform it without
  422.   * destroying the original
  423.   */
  424.  int i;
  425.  
  426.  for (i = 0; i < numVertices; i++)
  427.   xt[i] = x0[i], yt[i] = y0[i], zt[i] = z0[i];
  428. }
  429.  
  430. void drawPicture()
  431. {
  432.  /* This prcoedure draws the scene, with hidden surfaces removed */
  433.  int i;      /* subscript; loop index */
  434.  float dot;     /* the dot product */
  435.  
  436.  transformAll();
  437.  screenAll();
  438.  
  439.  /* First, do the opaque faces (8 cubes on the 8 corners) */
  440.  numVisFaces = 0;
  441.  for (i = 0; i < numFaces - 6; i++)
  442.  {
  443.   /* ***** HERE IS THE HIDDEN SURFACE REMOVAL ALGORITHM!! *****
  444.    * Compute the cross-product of any two sides of a face (we use
  445.    * the sides 1-0 and 2-0).  This gets an outbound normal from
  446.    * the face.  Then take the dot product of the outbound normal
  447.    * with a vector from the eye to the face (we use the vector from
  448.    * the eye to vertex 0).  If the dot product is non-negative,
  449.    * the face is visible.
  450.    * ********************************************************** */
  451.   getCrossProduct(v[i][0], v[i][1], v[i][2]);
  452.   getDotProduct(&dot, i);
  453.   if (dot >= 0.0)
  454.   {
  455.    doFace(i, numVisFaces, TRUE);
  456.    numVisFaces++;
  457.   }
  458.  }
  459.  
  460.  /* Now do the transparent faces (1 large cube); all faces are
  461.   * visible and uncolored!
  462.   */
  463.  for (i = numFaces - 6; i < numFaces; i++)
  464.  {
  465.   doFace(i, numVisFaces, FALSE);
  466.   numVisFaces++;
  467.  }
  468.  
  469.  /* Arrange the faces in decreasing order of distance-from-eye, so
  470.   * that the last face drawn is the one nearest the viewer.  This
  471.   * extends the basic algorithm to allow sences to be made up
  472.   * of more than one solid figure, in some cases.  It is called a
  473.   * z-buffer algorithm, because the faces to be drawn are buffered
  474.   * in order of their "z" value.  Notice that the z-buffer algorithm
  475.   * fails (partly) in this case, because the faces of the one
  476.   * large transparent cube penetrate the faces of the eight small
  477.   * opaque cubes.  The algorithm cannot accomodate penetrating
  478.   * surfaces.
  479.   */
  480.  sortFaces();
  481.  for (i = 0; i < numFaces; i++) drawFace(i);
  482. }
  483.  
  484.  main()
  485.  {
  486.   int ok;
  487.   int i,j;
  488.   initStuff();
  489.  
  490.   ok = readFaceData();
  491.   copyData();
  492.   if (ok)
  493.   {
  494.    ok = getParams();
  495.    if (ok)
  496.    {
  497.     calcViewMatrix();
  498.     drawPicture();
  499.    }
  500.   }
  501.   finishStuff();
  502.  }
  503.  
  504.