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