home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / i / iritsm3s.zip / poly3d-h / prepdata.c < prev    next >
C/C++ Source or Header  |  1991-09-11  |  26KB  |  704 lines
  1. /*****************************************************************************
  2. *   Routines to    prepare objects according to view file matrix:             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 1.0, Jan. 1989   *
  5. *****************************************************************************/
  6.  
  7. #ifdef __MSDOS__
  8. #include <stdlib.h>
  9. #endif /* __MSDOS__ */
  10.  
  11. #include <math.h>
  12. #include <stdio.h>
  13. #include <time.h>
  14. #include "program.h"
  15. #include "genmat.h"
  16. #include "iritprsr.h"
  17.  
  18. /* #define DEBUG               /* Print edge/hash table content. */
  19.  
  20. #define SAME_VERTEX(V1, V2)    (APX_EQ(V1 -> Coord[0], V2 -> Coord[0]) && \
  21.                  APX_EQ(V1 -> Coord[1], V2 -> Coord[1]) && \
  22.                  APX_EQ(V1 -> Coord[2], V2 -> Coord[2]))
  23.  
  24. #ifdef DEBUG
  25. static void PrintEdgeContent(EdgeStruct *PEdge);
  26. static void DrawEdgeHashTable(void);
  27. #endif /* DEBUG */
  28.  
  29. static int MinYLevel, MaxYLevel, CrntYLevel, PrintYLevel;
  30.  
  31. static void PrepareAllObjects(IPObjectStruct *PObjects);
  32. static void PrepareOneObject(IPObjectStruct *PObject);
  33. static int PrepareOnePolygon(IPPolygonStruct *PPolygon);
  34. static void UpdateBBoxPolygon(IPPolygonStruct *PPolygon);
  35. static int UpdateEqnPolygon(IPPolygonStruct *PPolygon, int *ReversePoly);
  36. static IPVertexStruct *ReverseLinList(IPVertexStruct *VList);
  37. static void GenEdgesFromPoly(IPPolygonStruct *PPolygon);
  38. static void InsertEdgeToHashTbl1(EdgeStruct *PEdge);
  39. static void IntersectAllEdges(void);
  40. static void InsertEdgeToHashTbl2(EdgeStruct *PEdge);
  41. static int IntersectEdgeList(EdgeStruct *PEdge, EdgeStruct *PEList,
  42.                                 int TestYMin);
  43. static int IntersectEdgeEdge(EdgeStruct *PEdge1, EdgeStruct *PEdge2,
  44.             EdgeStruct **PEdgeNew1, EdgeStruct **PEdgeNew2);
  45. static void PrintPolyContent(IPPolygonStruct *PPoly);
  46.  
  47. /*****************************************************************************
  48. * Routine to prepare to draw NumOfObjects given in Objects from             *
  49. * FileDescription FD according to view matrix Mat. If NumOfObjects == 0    then *
  50. * all the objects defined by the data sturcture    are drawn.             *
  51. * If GlblNumEdge != 0 then only GlblNumEdge first edges of each polygons are *
  52. * tested for visibility    (usefull in case in input polygons has known         *
  53. * repitition edges sequence which is redundent).                 *
  54. *****************************************************************************/
  55. void PrepareViewData(IPObjectStruct *PObjects)
  56. {
  57.     int    i;
  58.     long
  59.     SaveTime = time(NULL);
  60.  
  61.     for    (i = 0; i < EDGE_HASH_TABLE_SIZE; i++) EdgeHashTable[i] = NULL;
  62.     for    (i = 0; i < POLY_HASH_TABLE_SIZE; i++) PolyHashTable[i] = NULL;
  63.  
  64.     fprintf(stderr, "\nPass 2, Edges =      ");
  65.  
  66.     PrepareAllObjects(PObjects);
  67.  
  68.     fprintf(stderr, ",  %ld seconds.", time(NULL) - SaveTime);
  69.  
  70.     IntersectAllEdges();       /* Break edges to visibily uniform sub-edges. */
  71. }
  72.  
  73. /*****************************************************************************
  74. * Scan all objects.                                 *
  75. *****************************************************************************/
  76. static void PrepareAllObjects(IPObjectStruct *PObjects)
  77. {
  78.     while (PObjects) {
  79.     PrepareOneObject(PObjects);
  80.     PObjects = PObjects -> Pnext;
  81.     }
  82. }
  83.  
  84. /*****************************************************************************
  85. * Routine to prepare one object PObject.                     *
  86. *****************************************************************************/
  87. static void PrepareOneObject(IPObjectStruct *PObject)
  88. {
  89.     int Level;
  90.     IPPolygonStruct *Ptemp,
  91.     *PList = PObject -> U.PPolygon;
  92.  
  93.     while (PList) {
  94.     Ptemp = PList -> Pnext;
  95.  
  96.     if (PrepareOnePolygon(PList)) {
  97.         /* And add polygon into polygon hash table sorted by Ymin: */
  98.         Level = (PList -> Ymin + 1.0) * POLY_HASH_TABLE_SIZE2;
  99.         Level = BOUND(Level, 0, POLY_HASH_TABLE_SIZE1); /* Be 100% safe. */
  100.         PList -> Pnext = PolyHashTable[Level];
  101.         PolyHashTable[Level] = PList;   /* Concat it to poly hash table. */
  102.     }
  103.  
  104.     PList =    Ptemp;
  105.     }
  106. }
  107.  
  108. /*****************************************************************************
  109. * Routine to prepare one polygon PPolygon.                     *
  110. * Returns TRUE iff this object is a valid POLYGON (not a POLYLINE!).         *
  111. *****************************************************************************/
  112. static int PrepareOnePolygon(IPPolygonStruct *PPolygon)
  113. {
  114.     int    i, Reverse;
  115.     RealType CpCoord[3];
  116.     IPVertexStruct
  117.     *PList = PPolygon -> PVertex;
  118.  
  119.     /* Make a circluar polygon list inlt a linear list by breaking the end.  */
  120.     while (PList != NULL && PList -> Pnext != PPolygon -> PVertex)
  121.     PList = PList -> Pnext;
  122.     if (PList) PList -> Pnext = NULL;
  123.     PList = PPolygon -> PVertex;
  124.  
  125.     while (PList) {
  126.     /* Convert the coordinate to screen space (in RealType pres.). */
  127.     MultVecby4by4(CpCoord, PList -> Coord, GlblViewMat);
  128.     for (i = 0; i < 3; i++) PList -> Coord[i] = CpCoord[i];
  129.  
  130.     PList =    PList -> Pnext;
  131.     }
  132.     switch (PPolygon -> Type) {
  133.     case IP_POLYGON:
  134.         /* Find plane equation of poly, and let know if need to reverse. */
  135.         if (!UpdateEqnPolygon(PPolygon, &Reverse))
  136.         return FALSE;
  137.         UpdateBBoxPolygon(PPolygon);/* Find X, Y extrem in screen space. */
  138.         GenEdgesFromPoly(PPolygon);          /* Generate all its edges. */
  139.         if (Reverse)
  140.                 PPolygon -> PVertex = ReverseLinList(PPolygon -> PVertex);
  141.         return TRUE;
  142.     case IP_POLYLINE:
  143.         GenEdgesFromPoly(PPolygon);          /* Generate all its edges. */
  144.         return FALSE;
  145.     }
  146.  
  147.     return FALSE;
  148. }
  149.  
  150. /*****************************************************************************
  151. * Routine to update polygon boundary box in screen space:             *
  152. * Note this routine is called after the    polygons was checked for validity -  *
  153. * all the list of objects was found to be vertices only.             *
  154. *****************************************************************************/
  155. static void UpdateBBoxPolygon(IPPolygonStruct *PPolygon)
  156. {
  157.     RealType *Coord, Xmin, Xmax, Ymin, Ymax;    /* Bounding box of the polygon. */
  158.     IPVertexStruct
  159.     *PList = PPolygon -> PVertex;
  160.  
  161.     Xmin = Xmax    = PList -> Coord[0];
  162.     Ymin = Ymax    = PList    -> Coord[1];
  163.     PList = PList -> Pnext;
  164.     while (PList) {
  165.     Coord = PList -> Coord;
  166.     if (Coord[0] > Xmax) Xmax = Coord[0];
  167.     if (Coord[0] < Xmin) Xmin = Coord[0];
  168.     if (Coord[1] > Ymax) Ymax = Coord[1];
  169.     if (Coord[1] < Ymin) Ymin = Coord[1];
  170.     PList =    PList -> Pnext;
  171.     }
  172.     PPolygon ->    Xmin = Xmin;
  173.     PPolygon -> Xmax = Xmax;
  174.     PPolygon ->    Ymin = Ymin;
  175.     PPolygon -> Ymax = Ymax;
  176. }
  177.  
  178. /*****************************************************************************
  179. * Routine to update plane equation of the given    polygon:             *
  180. *   It is assumed that at list 3 points in polygon do exists, and pick the   *
  181. * tuple that has biggest length for maximum accuracy.                 *
  182. *   Note we IGNORE PLANE if was in data file.                     *
  183. *   In addition a test is made if all polygon vertices are ordered such that *
  184. * the cross product of each 3 consecutive vertices (projected to Z=0 plane)  *
  185. * is allways positive. Note the    polygon    must be    convex,    so result might    be   *
  186. * all positive or all negative.    In the later case the order is reversed         *
  187. *****************************************************************************/
  188. static int UpdateEqnPolygon(IPPolygonStruct *PPolygon, int *ReversePoly)
  189. {
  190.     static int
  191.     PolygonCount = 0;
  192.     int    i;
  193.     RealType V1[3], V2[3], *Coord, *CoordNext, *CoordNextNext,
  194.     Plane[3], Len, MaxPlane[3],
  195.     MaxLen = 0.0;
  196.     IPVertexStruct
  197.     *PList = PPolygon -> PVertex;
  198.  
  199.     PolygonCount++;
  200.  
  201.     *ReversePoly = FALSE;
  202.  
  203.     do {    /* Search for 3 consequtive non-colinear point from polygon: */
  204.     Coord = PList -> Coord;
  205.     CoordNext = PList -> Pnext -> Coord;
  206.     CoordNextNext = PList -> Pnext -> Pnext -> Coord;
  207.     for (i = 0; i < 3; i++) {   /* Prepare two vectors on polygon plane. */
  208.         V1[i] = Coord[i] - CoordNext[i];
  209.         V2[i] = CoordNext[i] - CoordNextNext[i];
  210.     }
  211.  
  212.     /* Find plane normal by a cross product of the two vectors on plane: */
  213.     Plane[0] = V1[1] * V2[2] - V1[2] * V2[1];
  214.     Plane[1] = V1[2] * V2[0] - V1[0] * V2[2];
  215.     Plane[2] = V1[0] * V2[1] - V1[1] * V2[0];
  216.  
  217.     /* Find vector Len. - we are looking for the biggest: */
  218.     Len = sqrt(SQR(Plane[0]) + SQR(Plane[1]) + SQR(Plane[2]));
  219.     if (Len > MaxLen) {
  220.         for (i = 0; i < 3; i++) MaxPlane[i] = Plane[i];
  221.         MaxLen = Len;
  222.     }
  223.     PList = PList -> Pnext;                  /* Try next tuple. */
  224.     } while (PList -> Pnext -> Pnext != NULL);
  225.  
  226.     if (ABS(MaxLen) < SQR(EPSILON)) { /* Fail to find 3 non-colinear points. */
  227.     if (GlblMore) {
  228.         fprintf(stderr,
  229.             "\nError: Invalid polygon (%d) found in file (zero edge length/colinear vertices):\n",
  230.         PolygonCount);
  231.         PrintPolyContent(PPolygon);
  232.     }
  233.     return FALSE;
  234.     }
  235.  
  236.     for (i = 0; i < 3; i++) PPolygon -> Plane[i] = MaxPlane[i] / MaxLen;
  237.  
  238.     /* Make sure the Z component of the    plane is positive: */
  239.     if (PPolygon -> Plane[2] < 0.0) {
  240.     for (i = 0; i < 3; i++) PPolygon -> Plane[i] = (-PPolygon -> Plane[i]);
  241.     *ReversePoly = TRUE;
  242.     }
  243.     else
  244.         if (GlblBackFacing) return FALSE;
  245.  
  246.     PPolygon ->    Plane[3] =
  247.     (- Coord[0] * PPolygon -> Plane[0]
  248.      - Coord[1] * PPolygon -> Plane[1]
  249.      - Coord[2] * PPolygon -> Plane[2]);
  250.  
  251.     return TRUE;
  252. }
  253.  
  254. /*****************************************************************************
  255. * Routine to evaluate the cross    product    of 3 points projected to Z = 0 plane *
  256. * and return the sign of the result (Only Z component).                 *
  257. *****************************************************************************/
  258. int CrossProd(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3])
  259. {
  260.     RealType Zout;
  261.  
  262.     /* U = Pt2 - Pt1,  V = Pt3 - Pt2,        Zoutput    = Ux * Vy - Uy * Vx. */
  263.     Zout = (Pt2[0] - Pt1[0]) /*    Ux */  * (Pt3[1] - Pt2[1]) /* Vy */  -
  264.        (Pt2[1] - Pt1[1]) /*    Uy */  * (Pt3[0] - Pt2[0]) /* Vx */;
  265.     if (APX_EQ(Zout, 0.0)) return 0;
  266.     if (Zout < 0.0)
  267.     return -1;
  268.     else
  269.     return 1;
  270. }
  271.  
  272. /*****************************************************************************
  273. * Routine to reverse linear list PList - return    pointer    to the reversed    list *
  274. * Although this routine is basically generic, it should be called on the     *
  275. * VertexStruct only as it updates their Internal flags as well.             *
  276. *****************************************************************************/
  277. static IPVertexStruct *ReverseLinList(IPVertexStruct *VList)
  278. {
  279.     int i;
  280.     IPVertexStruct *VLtemp,
  281.     *VLreverse = NULL;
  282.  
  283.     while (VList != NULL) {
  284.     VLtemp = VList -> Pnext;/* Save pointer to next element in old list. */
  285.  
  286.     VList -> Pnext = VLreverse; /* Add old element in front of new list. */
  287.     VLreverse = VList;
  288.  
  289.     VList =    VLtemp;            /* Continue to next element in old list. */
  290.     }
  291.  
  292.     VLtemp = VLreverse;
  293.     i = VLtemp -> VTags;
  294.     while (VLtemp != NULL) {
  295.     if (VLtemp -> Pnext != NULL) {
  296.         VLtemp -> VTags = VLtemp -> Pnext -> VTags;
  297.     }
  298.     else {
  299.         VLtemp -> VTags = i;
  300.     }
  301.  
  302.     VLtemp = VLtemp -> Pnext;
  303.     }
  304.  
  305.     return VLreverse;
  306. }
  307.  
  308. /*****************************************************************************
  309. * Routine to generate all the edges from the given polygon in screen space.  *
  310. * The polygon must be valid - only vertices in its list.             *
  311. * Edges    are inserted to    an edge    hash table of EDGE_HASH_TABLE_SIZE entries.  *
  312. * If global variable GlblNumEdge != 0 then only the first PGlblNumEdge edges *
  313. * are generated.                                 *
  314. * If edge is INTERNAL it is marked as so.                     *
  315. * If this is polyline, the last edge is NOT generated.                 *
  316. *****************************************************************************/
  317. static void GenEdgesFromPoly(IPPolygonStruct *PPolygon)
  318. {
  319.     int    CountEdges = GlblNumEdge;
  320.     EdgeStruct *PEdge;
  321.     IPVertexStruct
  322.     *PList = PPolygon -> PVertex;
  323.  
  324.     if (!PList || !PList -> Pnext) return;     /* If less than 2 vertices. */
  325.  
  326.     while (PList -> Pnext) {
  327.     PEdge =    (EdgeStruct *) MyMalloc(sizeof(EdgeStruct));
  328.     PEdge -> Vertex[0] = PList;
  329.     PEdge -> Vertex[1] = PList -> Pnext;
  330.     PEdge -> Internal = IP_IS_VRTX_INTERNAL(PList);
  331.     PEdge -> Pnext = NULL;
  332.     InsertEdgeToHashTbl1(PEdge);
  333.  
  334.     if (!--CountEdges) return;
  335.  
  336.     PList =    PList -> Pnext;
  337.     }
  338.     /* Close the contour to first vertex in list (if not polyline): */
  339.     if (PPolygon -> Type == IP_POLYGON) {
  340.     PEdge = (EdgeStruct *) MyMalloc(sizeof(EdgeStruct));
  341.     PEdge -> Vertex[0] = PList;
  342.     PEdge -> Vertex[1] = PPolygon -> PVertex;
  343.     PEdge -> Internal = IP_IS_VRTX_INTERNAL(PList);
  344.     PEdge -> Pnext = NULL;
  345.     InsertEdgeToHashTbl1(PEdge);
  346.     }
  347. }
  348.  
  349. /*****************************************************************************
  350. * Routine to insert new    edge to    edge hash table    structure sorted (hashed) by *
  351. * the edge Y min value.    The edge is tested for duplicated entry    (if         *
  352. * interior edge    - entered twice    and ignored in this case.             *
  353. * Also the edge    is updated such    that Ymin will be Vertex[0], Ymax Vertex[1]. *
  354. *****************************************************************************/
  355. static void InsertEdgeToHashTbl1(EdgeStruct *PEdge)
  356. {
  357.     int    Level;
  358.     RealType Ymin, Ymax;
  359.     IPVertexStruct *PVertex;
  360.     EdgeStruct *PEtemp;
  361.  
  362.     if (PEdge -> Vertex[0] -> Coord[1] > PEdge -> Vertex[1] -> Coord[1]) {
  363.     PVertex    = PEdge    -> Vertex[0];
  364.     PEdge -> Vertex[0] = PEdge -> Vertex[1];
  365.     PEdge -> Vertex[1] = PVertex;
  366.     }
  367.     Ymin = PEdge -> Vertex[0] -> Coord[1];
  368.     Ymax = PEdge -> Vertex[1] -> Coord[1];
  369.  
  370.     if ((Ymin >    1.0) ||    (Ymax <    -1.0))
  371.     free((char *) PEdge);                   /* Out of screen. */
  372.     else {
  373.     /* Normalize [-1..1] to    [0..EDGE_HASH_TABLE_SIZE]: */
  374.     Level =    (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  375.     Level =    BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);     /* To be 100% safe. */
  376.  
  377.     /* Look    for duplicate entry - it must have the same two    vertices: */
  378.     PEtemp = EdgeHashTable[Level];
  379.     while (PEtemp) {
  380.         /* Test to see if same edge    by comparing vertices pointers.    */
  381.         if ((SAME_VERTEX(PEdge -> Vertex[0], PEtemp -> Vertex[0]) &&
  382.          SAME_VERTEX(PEdge -> Vertex[1], PEtemp -> Vertex[1])) ||
  383.         (SAME_VERTEX(PEdge -> Vertex[0], PEtemp -> Vertex[1]) &&
  384.          SAME_VERTEX(PEdge -> Vertex[1], PEtemp -> Vertex[0]))) {
  385.         free((char *) PEdge);
  386.         return;                    /* Ignore new entry! */
  387.         }
  388.         PEtemp = PEtemp -> Pnext;
  389.     }
  390.  
  391.     fprintf(stderr, "\b\b\b\b\b%5d", ++EdgeCount);
  392.     PEdge -> Pnext = EdgeHashTable[Level];         /* Concat to main list. */
  393.     EdgeHashTable[Level] = PEdge;
  394.     }
  395. }
  396.  
  397. /*****************************************************************************
  398. * Routine to collect all edges in hash table into one big list and intersect *
  399. * them among themselves. In any    intersection both edges    are broken into    two. *
  400. * The resulting    edges are inserted back    into the hash table:             *
  401. *****************************************************************************/
  402. static void IntersectAllEdges(void)
  403. {
  404.     RealType Ymin;
  405.     int    i, Level;
  406.     long SaveTime = time(NULL);
  407.     EdgeStruct *PEmain = NULL, *PEtemp;
  408.  
  409.     EdgeCount =    0;
  410.     MinYLevel =    EDGE_HASH_TABLE_SIZE; /* Set "clip" levels in table entries. */
  411.     MaxYLevel =    0;
  412.  
  413.     /* Clear the hash table and    collect    all edges into one big list: */
  414.     for    (i = EDGE_HASH_TABLE_SIZE1; i >= 0; i--)
  415.     if ((PEtemp = EdgeHashTable[i]) != NULL) {
  416.         while (PEtemp -> Pnext) PEtemp = PEtemp -> Pnext;
  417.         PEtemp -> Pnext = PEmain;
  418.         PEmain = EdgeHashTable[i];
  419.         EdgeHashTable[i] = NULL;
  420.         if (i > MaxYLevel) MaxYLevel = i;
  421.         if (i < MinYLevel) MinYLevel = i;
  422.     }
  423.  
  424.     PrintYLevel    = CrntYLevel = 0;     /* Have to start from some place... */
  425.     fprintf(stderr, "\nPass 3, Level [%5d] =      ", MaxYLevel);
  426.  
  427.     while (PEmain) { /* Insert back after intersecting with all other edges. */
  428.     PEtemp = PEmain    -> Pnext;      /* As PEmain->Pnext might be changed. */
  429.     InsertEdgeToHashTbl2(PEmain);
  430.     PEmain = PEtemp;
  431.  
  432.     /* Now test to see if we can update current y level: */
  433.     if (CrntYLevel < MaxYLevel) {
  434.         Ymin = MIN(PEmain -> Vertex[0] -> Coord[1],
  435.                PEmain -> Vertex[1] -> Coord[1]);
  436.         /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  437.         Level = (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  438.         Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1); /* Be 100% safe. */
  439.         if (Level > CrntYLevel) CrntYLevel = Level;
  440.     }
  441.     }
  442.     fprintf(stderr, ",  %d seconds.", time(NULL) - SaveTime);
  443. }
  444.  
  445. /*****************************************************************************
  446. * Routine to insert old    edge to    edge hash table    structure sorted (hashed) by *
  447. * the edge Y min value.    The edge is tested for intersections with other         *
  448. * edges    allready in structure and both edges are broken    if found one.         *
  449. *****************************************************************************/
  450. static void InsertEdgeToHashTbl2(EdgeStruct *PEdge)
  451. {
  452.     int    i, Level, UpperLevel,
  453.     FoundIntersection = FALSE;
  454.     RealType Ymin, Ymax;
  455.     EdgeStruct *PEtemp;
  456.  
  457.     Ymin = PEdge -> Vertex[0] -> Coord[1];
  458.     Ymax = PEdge -> Vertex[1] -> Coord[1];
  459.  
  460.     /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  461.     Level = (int) ((Ymin + 1.0)    * EDGE_HASH_TABLE_SIZE2);
  462.     Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);      /* To be 100% safe. */
  463.     UpperLevel = 1 + (int) ((Ymax + 1.0) * EDGE_HASH_TABLE_SIZE2);
  464.     UpperLevel = BOUND(UpperLevel, 0, EDGE_HASH_TABLE_SIZE1);
  465.  
  466.     if (CrntYLevel > PrintYLevel) {
  467.     PrintYLevel = CrntYLevel;
  468.     fprintf(stderr, "\b\b\b\b\b%5d", PrintYLevel);
  469.     }
  470.  
  471.     /* Test for    intersections while we find intersections... */
  472.     for    (i=MinYLevel; i<=UpperLevel; i++) if (EdgeHashTable[i])
  473.     if ((FoundIntersection =
  474.          IntersectEdgeList(PEdge, EdgeHashTable[i], i == MinYLevel)) != 0)
  475.         break;
  476.  
  477.     if (FoundIntersection) {       /* Call recursively with the edge pieces: */
  478.     while (PEdge) {
  479.         PEtemp = PEdge -> Pnext;  /* As Pedge->Pnext might point to new. */
  480.         InsertEdgeToHashTbl2(PEdge);   /* Place after the recursive ins. */
  481.         PEdge = PEtemp;
  482.     }
  483.     }
  484.     else {              /* Its a single edge - insert it in its place: */
  485.     EdgeCount++;
  486.     PEdge -> Pnext = EdgeHashTable[Level];         /* Concat to main list. */
  487.     EdgeHashTable[Level] = PEdge;
  488.     }
  489. }
  490.  
  491. /*****************************************************************************
  492. * Routine to scan all edges in list and    intersect everything against         *
  493. * the given edge. intersected edges are    broken into two    parts each. The    edge *
  494. * is updated to    a list of 2 pieces, and    the list edge is broken    and inserted *
  495. * to the hash table (one piece in same entry as    it has the same    Ymin).         *
  496. * Note this routine returns TRUE after the first intersection found - no     *
  497. * test is made for ALL intersections if    more than one exists.             *
  498. * A test is made if MinYLevel can be updated if    TestYMin == TRUE.         *
  499. *****************************************************************************/
  500. static int IntersectEdgeList(EdgeStruct *PEdge, EdgeStruct *PEList,
  501.                                 int TestYMin)
  502. {
  503.     int    Level,
  504.     UpdateYMin = TRUE;
  505.     RealType Ymin, Ymax;
  506.     EdgeStruct *PEdgeNew, *PEListNew;
  507.  
  508.     if (!PEdge || !PEList) return FALSE;           /* NULL entry - quit. */
  509.  
  510.     while (PEList) {
  511.     if (IntersectEdgeEdge(PEdge, PEList, &PEdgeNew,    &PEListNew)) {
  512.         PEdge -> Pnext = PEdgeNew;
  513.         /* PEListNew can be    inserted to the    hash table with    no check as  */
  514.         /* its cannt intersect anything - it is part of checked edge!    */
  515.         if (PEListNew) {
  516.         Ymin = PEListNew -> Vertex[0] -> Coord[1];
  517.         /* Normalize [-1..1] to    [0..EDGE_HASH_TABLE_SIZE]: */
  518.         Level =    (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  519.         Level =    BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  520.         EdgeCount++;
  521.         PEListNew -> Pnext = EdgeHashTable[Level];
  522.         EdgeHashTable[Level] = PEListNew;
  523.         }
  524.         return TRUE;
  525.     }
  526.     if (TestYMin &&    UpdateYMin) {
  527.         Ymax = PEList -> Vertex[1] -> Coord[1];
  528.         /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  529.         Level = (int) ((Ymax + 1.0)    * EDGE_HASH_TABLE_SIZE2);
  530.         Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  531.         if (Level >= CrntYLevel) UpdateYMin    = FALSE;
  532.     }
  533.     PEList = PEList    -> Pnext;
  534.     }
  535.     if (TestYMin && UpdateYMin)            /* No need to test any more. */
  536.     do MinYLevel++;
  537.     while (!EdgeHashTable[MinYLevel]);
  538.  
  539.     return FALSE;
  540. }
  541.  
  542. /*****************************************************************************
  543. * Routine to test if two edges intersects. If they do, it brakes the bottom  *
  544. * edge into two pieces, leaving the lower part (with the same Ymin) in         *
  545. * original struct and allocated and updates new struct with upper edge part. *
  546. * Returns TRUE if found intersection, FALSE otherwise.                 *
  547. * Note the intersection    is tested in the XY axes (Z is ignored!).         *
  548. *****************************************************************************/
  549. static int IntersectEdgeEdge(EdgeStruct *PEdge1, EdgeStruct *PEdge2,
  550.                  EdgeStruct **PEdgeNew1, EdgeStruct **PEdgeNew2)
  551. {
  552.     int    i, OneInter1, OneInter2;
  553.     RealType Xmin1, Xmax1, Ymin1, Ymax1, Xmin2, Xmax2, Ymin2, Ymax2,
  554.       a1, b11, b12, a2, b21, b22, det, t1, t2, Z1, Z2;
  555.     /* To speed    up the intensive access    of the coordinates: */
  556.     RealType
  557.     *Crd10 = PEdge1 -> Vertex[0] -> Coord,
  558.     *Crd11 = PEdge1 -> Vertex[1] -> Coord,
  559.     *Crd20 = PEdge2 -> Vertex[0] -> Coord,
  560.     *Crd21 = PEdge2 -> Vertex[1] -> Coord;
  561.  
  562.     Xmin1 = MIN(Crd10[0], Crd11[0]);
  563.     Xmax1 = MAX(Crd10[0], Crd11[0]);
  564.     Ymin1 = Crd10[1];
  565.     Ymax1 = Crd11[1];
  566.  
  567.     Xmin2 = MIN(Crd20[0], Crd21[0]);
  568.     Xmax2 = MAX(Crd20[0], Crd21[0]);
  569.     Ymin2 = Crd20[1];
  570.     Ymax2 = Crd21[1];
  571.     if ((Xmin1 > Xmax2)    || (Xmax1 < Xmin2) ||/* Test if out of Boundary Box. */
  572.     (Ymin1 > Ymax2)    || (Ymax1 < Ymin2)) return FALSE;
  573.  
  574.     /* Let the line equations of the two edges be defined as:             */
  575.     /* L1 = p11    + t1 * (pt12 - pt11) , t1 = [0..1]                 */
  576.     /* L2 = p21    + t2 * (pt22 - pt21) , t2 = [0..1]                 */
  577.     /* at intersection point (if any) we have:                     */
  578.     /* pt11 + t1 * (pt12 - pt11) == pt21 + t2 *    (pt22 -    pt21)  for x, y         */
  579.     /* or two equations    (for x, y) with two unknown (t1, t2) to solve:         */
  580.     /* a1 = b11    * t1 + b12 * t2        from x                     */
  581.     /* a2 = b21    * t1 + b22 * t2        from y                     */
  582.     /* and we have interesection if both t1, t2    in the range [0..1]         */
  583.     a1 =  Crd10[0] - Crd20[0];
  584.     b11    = Crd10[0] - Crd11[0];
  585.     b12    = Crd21[0] - Crd20[0];
  586.     a2 =  Crd10[1] - Crd20[1];
  587.     b21    = Crd10[1] - Crd11[1];
  588.     b22    = Crd21[1] - Crd20[1];
  589.  
  590.     /* If the detereminant is zero, the    two lines are parellel - no inter. */
  591.     if (APX_EQ((det = b11 * b22 - b21 * b12), 0.0)) return FALSE;
  592.  
  593.     t1 = (a1 * b22 - a2    * b12) / det;
  594.     t2 = (b11 *    a2 - b21 * a1) / det;
  595.  
  596.     /* Test if intersection is happening in one    edge END - in that case    */
  597.     /* we break    only the second    edge into two parts.            */
  598.     OneInter1 =    ((t1 < 1.0) && (t1 > 0.0) &&
  599.          !(APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0)) &&
  600.           (APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0)));
  601.     OneInter2 =    ((t2 < 1.0) && (t2 > 0.0) &&
  602.          !(APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0)) &&
  603.           (APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0)));
  604.  
  605.     /* If out of 0..1 range in one of edges - no intersection: */
  606.     if ((!(OneInter1 ||    OneInter2)) &&
  607.     ((t1 >=    1.0) ||    (t1 <= 0.0) || (t2 >= 1.0) || (t2 <= 0.0) ||
  608.      APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0) ||
  609.      APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0))) return FALSE;
  610.  
  611.     /* If we are here, we have intersection - find the bottom edge and split */
  612.     /* it - allocated new edge struct and update to new upper (in Y) part.   */
  613.     Z1 = Crd10[2] * (1.0 - t1) + Crd11[2] * t1;
  614.     Z2 = Crd20[2] * (1.0 - t2) + Crd21[2] * t2;
  615.     if (!OneInter2 && Z1 < Z2) {
  616.     *PEdgeNew1 = (EdgeStruct *) MyMalloc(sizeof(EdgeStruct));
  617.     (*PEdgeNew1) -> Pnext = NULL;
  618.     (*PEdgeNew1) -> Internal = PEdge1 -> Internal;
  619.     (*PEdgeNew1) ->    Vertex[0] = IritPrsrNewVertexStruct();
  620.     for (i = 0; i < 2; i++)
  621.         (*PEdgeNew1) -> Vertex[0] -> Coord[i] =
  622.         Crd10[i] * (1.0    - t1) +    Crd11[i] * t1;
  623.     (*PEdgeNew1) -> Vertex[0] -> Coord[2] = Z1;
  624.     /* Now update the second vertex    of both    PEdge1 & PEdgeNew1:       */
  625.     /* Note    we assume Vertex[0] -> Coord[1]    < Vertex[1] -> Coord[1]    as */
  626.     /* all input edges are sorted this way when entered to hash table. */
  627.     (*PEdgeNew1) ->    Vertex[1] = PEdge1 -> Vertex[1];
  628.     PEdge1 -> Vertex[1] = (*PEdgeNew1) -> Vertex[0];
  629.  
  630.     }
  631.     else
  632.     *PEdgeNew1 = NULL;
  633.  
  634.     if (!OneInter1 && Z2 < Z1) {
  635.     *PEdgeNew2 = (EdgeStruct *) MyMalloc(sizeof(EdgeStruct));
  636.     (*PEdgeNew2) -> Pnext = NULL;
  637.     (*PEdgeNew2) -> Internal = PEdge2 -> Internal;
  638.     (*PEdgeNew2) ->    Vertex[0] = IritPrsrNewVertexStruct();
  639.     for (i=0; i<2; i++)
  640.         (*PEdgeNew2) -> Vertex[0] -> Coord[i] =
  641.         Crd20[i] * (1.0    - t2) +    Crd21[i] * t2;
  642.     (*PEdgeNew2) -> Vertex[0] -> Coord[2] = Z2;
  643.     /* Now update the second vertex    of both    PEdge2 & PEdgeNew2: */
  644.     (*PEdgeNew2) ->    Vertex[1] = PEdge2 -> Vertex[1];
  645.     PEdge2 -> Vertex[1] = (*PEdgeNew2) -> Vertex[0];
  646.     }
  647.     else
  648.     *PEdgeNew2 = NULL;
  649.  
  650.     return (*PEdgeNew1 != NULL) || (*PEdgeNew2 != NULL);
  651. }
  652.  
  653. /*****************************************************************************
  654. * Routine to print the content of a given edge:                     *
  655. *****************************************************************************/
  656. static void PrintPolyContent(IPPolygonStruct *PPoly)
  657. {
  658.     IPVertexStruct
  659.     *PList = PPoly -> PVertex;
  660.  
  661.     while (PList) {
  662.     fprintf(stderr, "   %12f %12f %12f\n",
  663.         PList -> Coord[0],
  664.         PList -> Coord[1],
  665.         PList -> Coord[2]);
  666.     PList =    PList -> Pnext;
  667.     }
  668. }
  669.  
  670. #ifdef DEBUG
  671.  
  672. /*****************************************************************************
  673. * Routine to print the content of a given edge:                     *
  674. *****************************************************************************/
  675. static void PrintEdgeContent(EdgeStruct *PEdge)
  676. {
  677.     fprintf(stderr, "   %11f %11f %11f : %11f %11f %11f\n",
  678.     PEdge -> Vertex[0] -> Coord[0],
  679.     PEdge -> Vertex[0] -> Coord[1],
  680.     PEdge -> Vertex[0] -> Coord[2],
  681.     PEdge -> Vertex[1] -> Coord[0],
  682.     PEdge -> Vertex[1] -> Coord[1],
  683.     PEdge -> Vertex[1] -> Coord[2]);
  684. }
  685.  
  686. /*****************************************************************************
  687. * Routine to draw all the segments in the EdgeHashTable:             *
  688. *****************************************************************************/
  689. static void DrawEdgeHashTable(void)
  690. {
  691.     int    i;
  692.     EdgeStruct *PEtemp;
  693.  
  694.     for    (i=0; i<EDGE_HASH_TABLE_SIZE; i++) {
  695.     PEtemp = EdgeHashTable[i];
  696.     while(PEtemp) {
  697.         DrawEdge(PEtemp);
  698.         PEtemp = PEtemp -> Pnext;
  699.     }
  700.     }
  701. }
  702.  
  703. #endif /* DEBUG */
  704.