home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / POLY3DHS.ZIP / OUT-EDGE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  15.3 KB  |  415 lines
  1. /*****************************************************************************
  2. *   Routines to    test all edges for visibility relative to the global polygon *
  3. * list,    and output the visible ones, to    graphics screen    or as text file         *
  4. *                                         *
  5. * Written by:  Gershon Elber                Ver 2.0, Jan. 1989   *
  6. *****************************************************************************/
  7.  
  8. #ifdef __MSDOS__
  9. #include <conio.h>
  10. #endif /* __MSDOS__ */
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <setjmp.h>
  15. #include <time.h>
  16. #include "program.h"
  17. #include "genmat.h"
  18. #include "parser.h"
  19.  
  20. static struct EdgeStruct *OutEdgeHashTable[EDGE_HASH_TABLE_SIZE];
  21.  
  22. static void OutputEdge(EdgeStruct *PEtemp);
  23. static int EmitOutEdgeHashTable(void);
  24. static struct EdgeStruct *FoundMatchEdge(int *Colinear, EdgeStruct *PEdge);
  25. static int FuzzSamePoints(float Pt1[3], float Pt2[3]);
  26. static int ColinearPoints(float Pt1[3], float Pt2[3], float Pt3[3]);
  27. static int VisibleEdge(int EdgeMinY, EdgeStruct *PEdge,
  28.                     PolygonStruct *PolyHashTable[]);
  29. static int VisibleEdgeOnePoly(EdgeStruct *PEdge, PolygonStruct *PPoly);
  30. static int InverseMatrix(MatrixType A);
  31. static void SwapDouble(double *D1, double *D2);
  32.  
  33. /*****************************************************************************
  34. * Routine to test for visibility all edges in EdgeHashTable and    display    or   *
  35. * output the visible ones only.    It is assumed that only    totally    visible    or   *
  36. * invisible edges are in table (Pass 3 broke all other kind of edges).         *
  37. *****************************************************************************/
  38. void OutVisibleEdges(void)
  39. {
  40.     int    i, PolyLineCount = 0;
  41.     long SaveTime = time(NULL);
  42.     struct EdgeStruct *PEtemp, *PEtail;
  43.  
  44.     fprintf(stderr, "\nPass 4, Edges [%5d] =      ", EdgeCount);
  45.     for (i=0; i<EDGE_HASH_TABLE_SIZE; i++) OutEdgeHashTable[i] =
  46.                             (EdgeStruct *) NULL;
  47.     if (!InverseMatrix(GlblViewMat)) {
  48.     fprintf(stderr,
  49.             "\nNo inverse for matrix transformation, output is in screen space\n");
  50.     GenUnitMat(GlblViewMat);         /* No inverse transform at all. */
  51.     }
  52.     printf("Automatic Hidden Line generator\t\tGershon Elber\t\tJan. 1989\n");
  53.  
  54.     EdgeCount =    0;
  55.  
  56.     for (i=0; i<EDGE_HASH_TABLE_SIZE; i++)
  57.     if ((PEtemp = EdgeHashTable[i]) != NULL)/* If any edge in that list. */
  58.         while (PEtemp) {
  59.         EdgeCount++;
  60.         fprintf(stderr, "\b\b\b\b\b%5d", EdgeCount);
  61.         PEtail = PEtemp    -> Pnext;       /* OutputEdge destroy it. */
  62.         if ((!PEtemp -> Internal || InternalFlag) &&
  63.             VisibleEdge(i, PEtemp, PolyHashTable))
  64.             OutputEdge(PEtemp);
  65.         PEtemp = PEtail;
  66.         }
  67.  
  68.     PolyLineCount =    EmitOutEdgeHashTable();     /* Output all polylines. */
  69.     printf("[OBJECT Hidden");           /* Output the OBJECT keyword: */
  70.     for (i=0; i<PolyLineCount; i++)    {
  71.     if (i % 10 == 0) printf("\n\t");
  72.     printf("P%-3d ", i);
  73.     }
  74.     printf("]\n");
  75.     fprintf(stderr, ",  %d seconds.", time(NULL) - SaveTime);
  76. }
  77.  
  78. /*****************************************************************************
  79. * Routine to output one    edge to    the OutEdgeHashTable.                 *
  80. * The edge is inserted into OutEdgeHashTable to    be able    to match it into     *
  81. * the longest path possible - connecting edges into edge sequence.         *
  82. * Each edge is inserted    by its Ymin, which will    cause the paths    be in         *
  83. * increased Y order...                                 *
  84. *****************************************************************************/
  85. static void OutputEdge(EdgeStruct *PEtemp)
  86. {
  87.     int    Level;
  88.  
  89.     Level = (int) ((PEtemp -> Vertex[0]    -> Coord[1] + 1.0) *
  90.                             EDGE_HASH_TABLE_SIZE2);
  91.     PEtemp -> Pnext = OutEdgeHashTable[Level];
  92.     OutEdgeHashTable[Level] = PEtemp;
  93. }
  94.  
  95. /*****************************************************************************
  96. * Routine to scan the OutEdgeHashTable,    and Emit the longest paths found in  *
  97. * it by    searching for consecutive edges    and combining colinear edges.         *
  98. *****************************************************************************/
  99. static int EmitOutEdgeHashTable(void)
  100. {
  101.     int    i, j, Colinear, VertexCount = 0, VertexBaseCount, PolylineCount = 0;
  102.     double Vec[3];
  103.     struct EdgeStruct *PEtemp, *PEnext;
  104.  
  105.     for    (i=0; i<EDGE_HASH_TABLE_SIZE; i++)     /* Scan all the hash table. */
  106.     while (OutEdgeHashTable[i]) {         /* Scan all edges in entry. */
  107.         PEtemp = OutEdgeHashTable[i];      /* Take edge out of table. */
  108.         OutEdgeHashTable[i]    = OutEdgeHashTable[i] -> Pnext;
  109.         VertexBaseCount = VertexCount;
  110.  
  111.         /* Print first vertex of polyline: */
  112.         MultVecby4by4(Vec, PEtemp -> Vertex[0] -> Coord, GlblViewMat);
  113.         printf("[VERTEX V%-4d %11lf %11lf %11lf]\n", VertexCount++,
  114.         Vec[0], Vec[1], Vec[2]);
  115.  
  116.         while ((PEnext = FoundMatchEdge(&Colinear, PEtemp)) != NULL) {
  117.         if (!Colinear) {       /* Print PEtemp only if not colinear! */
  118.             /* Print next vertices of polyline:    */
  119.             for    (j=0; j<3; j++)    Vec[j] =
  120.             PEtemp -> Vertex[1] -> Coord[j];
  121.             MultVecby4by4(Vec, PEtemp -> Vertex[1] -> Coord,
  122.                                 GlblViewMat);
  123.             printf("[VERTEX V%-4d %11lf %11lf %11lf]\n", VertexCount++,
  124.             Vec[0], Vec[1], Vec[2]);
  125.         }
  126.         PEtemp = PEnext;
  127.         }
  128.  
  129.         /* Print last vertex of polyline: */
  130.         MultVecby4by4(Vec, PEtemp -> Vertex[1] -> Coord, GlblViewMat);
  131.         printf("[VERTEX V%-4d %11lf %11lf %11lf]\n", VertexCount++,
  132.         Vec[0], Vec[1], Vec[2]);
  133.  
  134.         printf("[POLYLINE P%-4d", PolylineCount++);
  135.         for    (j=VertexBaseCount; j<VertexCount; j++)    {
  136.         if ((j-VertexBaseCount)    % 10 ==    0) printf("\n\t");
  137.         printf("V%-4d ", j);
  138.         }
  139.         printf("]\n");
  140.     }
  141.     return PolylineCount;
  142. }
  143.  
  144. /*****************************************************************************
  145. * Routine to scan the OutEdgeHashTable for a match edge    if any,    delete it    *
  146. * from HashTable and return it.    if colinear with PEdge set Colinear to TRUE. *
  147. * return FALSE if no match found (end of polyline).                 *
  148. *****************************************************************************/
  149. static struct EdgeStruct *FoundMatchEdge(int *Colinear, EdgeStruct *PEdge)
  150. {
  151.     int    Level;
  152.     struct EdgeStruct *PEtemp, *PElast;
  153.  
  154.     Level = (int) ((PEdge -> Vertex[1] -> Coord[1] + 1.0) *
  155.                             EDGE_HASH_TABLE_SIZE2);
  156.     PEtemp = PElast = OutEdgeHashTable[Level];
  157.     while (PEtemp) {                /* First scan for colinear edge. */
  158.     if (FuzzSamePoints(PEdge -> Vertex[1] -> Coord,
  159.                PEtemp -> Vertex[0] -> Coord) &&
  160.         ColinearPoints(PEdge -> Vertex[0] -> Coord,
  161.                PEdge -> Vertex[1] -> Coord,
  162.                PEtemp -> Vertex[1] -> Coord)) {
  163.         *Colinear =    TRUE;
  164.         /* Delete that edge    from hash table    structure: */
  165.         if (PEtemp == PElast)
  166.          OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
  167.         else PElast    -> Pnext = PEtemp -> Pnext;
  168.  
  169.         if (FuzzSamePoints(PEtemp -> Vertex[0] -> Coord,
  170.                    PEtemp -> Vertex[1] -> Coord))
  171.          return    FoundMatchEdge(Colinear, PEdge);/* Call recursively! */
  172.         else return    PEtemp;
  173.     }
  174.     PElast = PEtemp;
  175.     PEtemp = PEtemp    -> Pnext;
  176.     }
  177.  
  178.     PEtemp = PElast = OutEdgeHashTable[Level];
  179.     while (PEtemp) {                /* Next scan for any match edge. */
  180.     if (FuzzSamePoints(PEdge -> Vertex[1] -> Coord,
  181.                PEtemp -> Vertex[0] -> Coord)) {
  182.         *Colinear =    FALSE;
  183.         /* Delete that edge    from hash table    structure: */
  184.         if (PEtemp == PElast)
  185.          OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
  186.         else PElast    -> Pnext = PEtemp -> Pnext;
  187.  
  188.         if (FuzzSamePoints(PEtemp -> Vertex[0] -> Coord,
  189.                    PEtemp -> Vertex[1] -> Coord))
  190.          return    FoundMatchEdge(Colinear, PEdge);/* Call    recursively! */
  191.         else return    PEtemp;
  192.     }
  193.     PElast = PEtemp;
  194.     PEtemp = PEtemp    -> Pnext;
  195.     }
  196.  
  197.     return (EdgeStruct *) NULL;              /* No match - end of polyline. */
  198. }
  199.  
  200. /*****************************************************************************
  201. * Routine to test if two points    are almost the same, and returns TRUE if so. *
  202. *****************************************************************************/
  203. static int FuzzSamePoints(float Pt1[3], float Pt2[3])
  204. {
  205.     return (APX_EQ(Pt1[0], Pt2[0]) &&
  206.         APX_EQ(Pt1[1], Pt2[1]) &&
  207.         APX_EQ(Pt1[2], Pt2[2]));
  208. }
  209.  
  210. /*****************************************************************************
  211. * Routine to test if three points are colinear,    and returns TRUE if so...    *
  212. * Algorithm: cross product should be zero if colinear...             *
  213. * Note this routine does not return TRUE if Pt2    is not between Pt1..Pt3.     *
  214. *****************************************************************************/
  215. static int ColinearPoints(float Pt1[3], float Pt2[3], float Pt3[3])
  216. {
  217.     int    i;
  218.     float Xout, Yout, Zout, U[3], V[3], temp;
  219.  
  220.     for    (i=0; i<3; i++)    {
  221.     U[i] = Pt2[i] -    Pt1[i];
  222.     V[i] = Pt3[i] -    Pt2[i];
  223.     }
  224.     temp = sqrt(SQR(U[0]) + SQR(U[1]) + SQR(U[2]));
  225.     if (APX_EQ(temp, 0.0)) return TRUE;
  226.     for    (i=0; i<3; i++)    U[i] = U[i] / temp;
  227.  
  228.     temp = sqrt(SQR(V[0]) + SQR(V[1]) + SQR(V[2]));
  229.     if (APX_EQ(temp, 0.0)) return TRUE;
  230.     for    (i=0; i<3; i++)    V[i] = V[i] / temp;
  231.  
  232.     /* Xoutput = Uy * Vz - Uz *    Vy. */
  233.     Xout = U[1]    /* Uy */  * V[2] /* Vz */  -
  234.        U[2]    /* Uz */  * V[1] /* Vy */;
  235.  
  236.     /* Youtput = Uz * Vx - Ux *    Vz. */
  237.     Yout = U[2]    /* Uz */  * V[0] /* Vx */  -
  238.        U[0]    /* Ux */  * V[2] /* Vz */;
  239.  
  240.     /* Zoutput = Ux * Vy - Uy *    Vx. */
  241.     Zout = U[0]    /* Ux */  * V[1] /* Vy */  -
  242.        U[1]    /* Uy */  * V[0] /* Vx */;
  243.  
  244.     if (APX_EQ(Xout, 0.0) && APX_EQ(Yout, 0.0) && APX_EQ(Zout, 0.0) &&
  245.     ((MIN(Pt1[0], Pt3[0]) < Pt2[0]) && (MAX(Pt1[0], Pt3[0]) > Pt2[0]) &&
  246.      (MIN(Pt1[1], Pt3[1]) < Pt2[1]) && (MAX(Pt1[1], Pt3[1]) > Pt2[1])))
  247.      return    TRUE;
  248.     else return    FALSE;
  249. }
  250.  
  251. /*****************************************************************************
  252. * Routine to test the visibility of the    given edge relative to all polygons  *
  253. * in polygon list. return TRUE if the edge is visible. It is assumed that    *
  254. * the edge is whole visible or whole invisible (Pass 3 broke the edge if     *
  255. * that whas not    true). Also it is assumed the polygons are all convex.         *
  256. * A short cut is made to test the edge only against the    needed polygons         *
  257. * only, using the polygon hash table and Y level sorting.             *
  258. *****************************************************************************/
  259. static int VisibleEdge(int EdgeMinY, EdgeStruct * PEdge,
  260.                         PolygonStruct *PolyHashTable[])
  261. {
  262.     int    EdgeMaxY, i;
  263.     PolygonStruct *PPolyList, *PPolyLast;
  264.  
  265.     EdgeMaxY = MIN((MAX(PEdge -> Vertex[0] -> Coord[1],
  266.             PEdge -> Vertex[1] -> Coord[1]) + 1.0) *
  267.                         EDGE_HASH_TABLE_SIZE2,
  268.            EDGE_HASH_TABLE_SIZE1);
  269.  
  270.     /* Test the    edge only in the interval 0..EdgeMaxY as these are the only  */
  271.     /* which might hide    that edge. Also    polygons with MaxY less    than         */
  272.     /* EdgeMinY    are deleted from PolyHashTable as it is    assumed    the edges    */
  273.     /* are scanned in increasing order of the EdgeHashTable.             */
  274.     for    (i=0; i<=EdgeMaxY; i++) {
  275.     PPolyList = PPolyLast =    PolyHashTable[i];
  276.     while (PPolyList) {
  277.         if ((PPolyList -> Ymax + 1.0) * EDGE_HASH_TABLE_SIZE2 < EdgeMinY)
  278.         /* Delete this polygon!    */
  279.         if (PPolyList == PPolyLast) {
  280.             PolyHashTable[i] = PPolyLast = PPolyList -> Pnext;
  281.             PPolyList =    PPolyList -> Pnext;
  282.         }
  283.         else {
  284.             PPolyList =    PPolyList -> Pnext;
  285.             PPolyLast -> Pnext = PPolyList;
  286.         }
  287.         else {         /* Polygon still active - test edge against it. */
  288.         /* If found one    polygon    that hides this    edge return FALSE... */
  289.  
  290.         if (!VisibleEdgeOnePoly(PEdge, PPolyList)) return FALSE;
  291.         PPolyLast = PPolyList;
  292.         PPolyList = PPolyList -> Pnext;
  293.         }
  294.     }
  295.     }
  296.  
  297.     return TRUE;
  298. }
  299.  
  300. /*****************************************************************************
  301. * Routine to test the visibility of the    given edge relative to one polygon   *
  302. * return TRUE if the edge is visible. It is assumed that the edge is whole   *
  303. * visible or whole invisible (Pass 3 broke the edge if that whas not true).  *
  304. * Also it is assumed the polygons are all convex.                 *
  305. *****************************************************************************/
  306. static int VisibleEdgeOnePoly(EdgeStruct *PEdge, PolygonStruct *PPoly)
  307. {
  308.     int    i;
  309.     float MidPt[3], Temp;
  310.     struct VertexStruct *PList;
  311.  
  312.     for    (i=0; i<3; i++)    MidPt[i] =        /* Calc a mid point on the edge: */
  313.         (PEdge -> Vertex[0] -> Coord[i] +
  314.          PEdge -> Vertex[1] -> Coord[i]) / 2.0;
  315.  
  316.     /* Test if edges is    out of polygon boundary    box: */
  317.     if (MidPt[0] > PPoly -> Xmax || MidPt[0] < PPoly ->    Xmin ||
  318.     MidPt[1] > PPoly -> Ymax || MidPt[1] < PPoly ->    Ymin) return TRUE;
  319.  
  320.     Temp = PPoly -> Plane[0] * MidPt[0]    +
  321.        PPoly -> Plane[1] * MidPt[1]    +
  322.        PPoly -> Plane[2] * MidPt[2]    +
  323.        PPoly -> Plane[3];
  324.     if ((Temp >= 0) || (APX_EQ(Temp, 0.0)))
  325.     return TRUE;                /* Edge in front of polygon. */
  326.  
  327.     /* We cannt    escape it - we now must    find if    the point is included in */
  328.     /* polygon area. We    assume the polygon is convex and use the fact     */
  329.     /* that the    polygon    list is    ordered    such that the cross product     */
  330.     /* of two consecutive vertices and the point is positive for all     */
  331.     /* consecutive vertices pairs iff the point    is in the polygon.     */
  332.     PList = PPoly -> PVertex;
  333.     while (PList -> Pnext) {
  334.     if (CrossProd(PList -> Coord, PList -> Pnext -> Coord, MidPt) < 0)
  335.         return TRUE;                  /* Out of polygon! */
  336.     PList =    PList -> Pnext;
  337.     }
  338.     /* Now test    last polygon edge (last    point, first point in poly list) */
  339.     if (CrossProd(PList -> Coord, PPoly -> PVertex -> Coord, MidPt) < 0)
  340.     return TRUE;                      /* Out of polygon! */
  341.  
  342.     return FALSE;
  343. }
  344.  
  345. /*****************************************************************************
  346. * Procedure to calculate the INVERSE of    a given    MatrixType matrix A which is *
  347. * modified to the inverted matrix. Return TRUE if inverse exists.         *
  348. *****************************************************************************/
  349. static int InverseMatrix(MatrixType A)
  350. {
  351.     MatrixType InvA;
  352.     int    i, j, k;
  353.     double V;
  354.  
  355.     GenUnitMat(InvA);
  356.  
  357.     for    (i=0; i<4; i++)    {
  358.     V = A[i][i];                      /* Find the new pivot. */
  359.     k = i;
  360.     for (j=i+1; j<4; j++) if (A[j][i] > V) {
  361.         /* Find maximum on col i, row i+1..4. */
  362.         V =    A[j][i];
  363.         k =    j;
  364.     }
  365.     j = k;
  366.  
  367.     if (i != j) for    (k=0; k<4; k++)    {
  368.         SwapDouble(&A[i][k], &A[j][k]);
  369.         SwapDouble(&InvA[i][k], &InvA[j][k]);
  370.     }
  371.  
  372.         for (j=i+1; j<4; j++) {         /* Eliminate col i from row i+1..4. */
  373.         V =    A[j][i]    / A[i][i];
  374.         for    (k=0; k<4; k++)    {
  375.         A[j][k]       -= V    * A[i][k];
  376.         InvA[j][k] -= V    * InvA[i][k];
  377.         }
  378.     }
  379.     }
  380.  
  381.     for    (i=4-1;    i>=0; i--) {                   /* Back Substitution. */
  382.     if (A[i][i] == 0) return FALSE;       /* Error */
  383.  
  384.     for (j=0; j<i; j++) {         /* Eliminate col i from row 1..i-1. */
  385.         V =    A[j][i]    / A[i][i];
  386.         for    (k=0; k<4; k++)    {
  387.         /* A ->    [j][k] -= V * A[i][k]; */
  388.         InvA[j][k] -= V    * InvA[i][k];
  389.         }
  390.     }
  391.     }
  392.  
  393.     for    (i=0; i<4; i++)                /* Normalize the inverse Matrix. */
  394.     for (j=0; j<4; j++)
  395.         InvA[i][j] /= A[i][i];
  396.     for    (i=0; i<4; i++)                   /* Copy inverted    matrix to A. */
  397.     for (j=0; j<4; j++)
  398.         A[i][j] = InvA[i][j];
  399.  
  400.     return TRUE;
  401. }
  402.  
  403. /*****************************************************************************
  404. * Procedure to swap two    double parameters:                     *
  405. *****************************************************************************/
  406. static void SwapDouble(double *D1, double *D2)
  407. {
  408.     double D;
  409.  
  410.     D =    (*D1);
  411.     *D1    = (*D2);
  412.     *D2    = D;
  413. }
  414.  
  415.