home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / IRITS.ZIP / BOOL2LOW.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  35.6 KB  |  902 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see Irit.h)!             *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersection polyline between the oper.    *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. * Note we said mainly has routines CAN call one another!             *
  18. *****************************************************************************/
  19.  
  20. /* #define DEBUG        If defined, return intersection POLYLINE object. */
  21. /* #define DEBUG2             If defined, defines some printing routines. */
  22. /* #define DEBUG3             Print messages to entry/exit from routines. */
  23.  
  24. #ifdef __MSDOS__
  25. #include <alloc.h>
  26. #include <dos.h>
  27. #endif /* __MSDOS__ */
  28.  
  29. #include <stdio.h>
  30. #include <ctype.h>
  31. #include <math.h>
  32. #include <string.h>
  33. #include "program.h"
  34. #include "allocatg.h"
  35. #include "convexg.h"
  36. #include "objects.h"
  37. #include "booleang.h"
  38. #include "booleanl.h"
  39. #include "geomat3d.h"
  40.  
  41. static int TestAinB(VertexStruct *V, PolygonStruct *Pl, int AinB);
  42. static struct PolygonStruct *ClipOpenLoopFromPoly(PolygonStruct *Pl,
  43.                     InterSegListStruct *OLoop, int AinB);
  44. static void ClosedLoopsToPolys(InterSegListStruct *PClosed, PolygonStruct *Pl);
  45. static VertexStruct *CutPolygonAtRay(PolygonStruct *Pl, PointType Pt);
  46. static CombineClosedLoops(PolygonStruct *Pl, InterSegListStruct *PClosed,
  47.                                 int AinB);
  48. static void PushAdjOnStack(PolygonStruct *Pl, PolygonStruct *AdjStack[],
  49.                              int *StackPointer);
  50. static struct PolygonStruct *ChainPolyLists(PolygonStruct *Pl1,
  51.                             PolygonStruct *Pl2);
  52.  
  53. #ifdef DEBUG2
  54. static void PrintVrtxList(VertexStruct *V);
  55. static void PrintInterList(InterSegmentStruct *PInt);
  56. #endif /* DEBUG2 */
  57.  
  58. /*****************************************************************************
  59. *   Test on which side of polygon Pl, given Point V is, and according to     *
  60. * the requiremnet (AinB) returns TRUE/FALSE.                     *
  61. *   If test on V fails, we tries the next one V -> Pnext until success...    *
  62. *****************************************************************************/
  63. static int TestAinB(VertexStruct *V, PolygonStruct *Pl, int AinB)
  64. {
  65.     int In;
  66.     RealType Distance;
  67.     VertexStruct *VHead = V;
  68.  
  69.     do {
  70.     Distance = Pl -> Plane[0] * V -> Pt[0] +
  71.            Pl -> Plane[1] * V -> Pt[1] +
  72.            Pl -> Plane[2] * V -> Pt[2] + Pl -> Plane[3];
  73.     In = Distance > 0.0;
  74.     V = V -> Pnext;
  75.     }
  76.     while (ABS(Distance) < EPSILON && V != NULL && V != VHead);
  77.  
  78.     return (In && AinB) || (!In && !AinB);   /* I wish I has logical XOR ... */
  79. }
  80.  
  81. /*****************************************************************************
  82. *   Convert an inter loop into an open vertex list.                 *
  83. *****************************************************************************/
  84. struct VertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead)
  85. {
  86.     VertexStruct *VHead, *V;
  87.  
  88.     VHead = V = AllocVertex(0, 0, NULL, NULL);
  89.  
  90.     PT_COPY(VHead -> Pt, PIHead -> PtSeg[0]);
  91.  
  92.     while (PIHead != NULL) {
  93.     V -> Pnext = AllocVertex(0, 0, NULL, NULL);
  94.     V = V -> Pnext;
  95.     PT_COPY(V -> Pt, PIHead -> PtSeg[1]);
  96.  
  97.     PIHead = PIHead -> Pnext;
  98.     }
  99.  
  100.     V -> Pnext = NULL;
  101.  
  102.     return VHead;
  103. }
  104.  
  105. /*****************************************************************************
  106. *   Clip an open loop from a polygon:                         *
  107. * 1. Clip the section (S) of the polygon between the two loop end points and *
  108. *    replace it by the loop itself.                         *
  109. * 2. If the polygon formed from S and the loop should be in the output       *
  110. *    (as tested by AinB) return that polygon. Otherwise return NULL.         *
  111. *   The open loop itself (excluding the header OLoop) is freed.             *
  112. * Note it is assumed (ordered by the sorting routines above) that the open   *
  113. * loop starts from the second end back to first:                 *
  114. *                                         *
  115. *                   L1-----------------------L2             *
  116. *                |            |             *
  117. *                |L0            |L3             *
  118. *    *---------------*-------+----*-------------*----+-----------*         *
  119. *    P0        P1         P2           P3            P0         *
  120. *****************************************************************************/
  121. static struct PolygonStruct *ClipOpenLoopFromPoly(PolygonStruct *Pl,
  122.                     InterSegListStruct *OLoop, int AinB)
  123. {
  124.     int GenClipPoly;        /* TRUE if needs to form polygon from S & OLoop. */
  125.     PointType Pt;
  126.     VertexStruct *VStart,  *VEnd, *VEnd1,     /* Corresponds to L0 and L3... */
  127.          *ClipPoly,        /* The clipped element from polygon. */
  128.          *PLoop, *PRevLoop,      /* The loop itself as vertex list. */
  129.          *PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2;
  130.     InterSegmentStruct *PISeg, *PItemp;
  131.     PolygonStruct *ClipPl;
  132.  
  133. #ifdef DEBUG3
  134.     printf("Enter ClipOpenLoopFromPoly\n");
  135. #endif /* DEBUG3 */
  136.  
  137.     PISeg = OLoop -> PISeg;
  138.     VStart = PISeg -> V[0];
  139.     while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext;
  140.     VEnd = PISeg -> V[1];
  141.     if (VStart == NULL || VEnd == NULL)
  142.     FatalError("ClipOpenLoopFromPoly: None open loop\n");
  143.     VEnd1 = VEnd;           /* Find the pointer thats points on VEnd. */
  144.     while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext;
  145.  
  146.     PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/
  147.     PLoopEnd = PLoop;              /* Prepare pointer on last vertex. */
  148.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  149.     PLoopEnd1 = PLoop;
  150.     while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext;
  151.  
  152.     if (VStart != VEnd) {
  153.     /* Now we test if we need to create a polygon formed from S & open   */
  154.     /* loop by testing on which side of the polygon that caused         */
  155.     /* intersection L0L1, point P2 is, and compare with requirement AinB.*/
  156.     GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB);
  157.  
  158.     /* Keep the clipped VertexList P2, P3 & substitute with open loop:   */
  159.     /* Note we must keep vertex VEnd in the polygon as another InterSeg. */
  160.     /* may point on it, so we replace InterSeg point (L3) by (P3) and    */
  161.     /* leave VEnd intact.                             */
  162.     Ptemp1 = VEnd -> Pnext;             /* Save that pointer temporary. */
  163.     VEnd -> Pnext = NULL;           /* Close the clipped vertex list. */
  164.  
  165.     PT_COPY(Pt, VEnd -> Pt);
  166.     PT_COPY(VEnd -> Pt, PLoopEnd -> Pt);
  167.     PT_COPY(PLoopEnd -> Pt, Pt);
  168.     VEnd1 -> Pnext = PLoopEnd;
  169.     PLoopEnd1 -> Pnext = VEnd;
  170.     PLoopEnd -> Count = VEnd -> Count;
  171.     PLoopEnd -> Tags = VEnd -> Tags;
  172.  
  173.     Ptemp2 = VEnd;
  174.     VEnd = PLoopEnd;
  175.     PLoopEnd = Ptemp2;
  176.  
  177.     ClipPoly = VStart -> Pnext;
  178.  
  179.     /* New ClipPoly is isolated (Open loop of P2, P3 only). Save         */
  180.     /* reversed list of open loop if we need to form an S/OLoop polygon, */
  181.     /* otherwise free ClipPoly. Chain the OLoop instead of S.         */
  182.     if (GenClipPoly) PRevLoop = GenReverseVrtxList(PLoop);
  183.     else MyFree((char *) ClipPoly, VERTEX_TYPE);
  184.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  185.     PLoopEnd -> Pnext = Ptemp1;
  186.     }
  187.     else { /* VStart == VEnd */
  188.     /* Now we test if we need to create a polygon formed from S & open   */
  189.     /* loop by testing on which side of the polygon that caused         */
  190.     /* intersection L0L1, point L3 is, and compare with requirement AinB.*/
  191.     GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB);
  192.  
  193.     /* In this case the clipped part is empty, so its simpler: */
  194.     ClipPoly = NULL;
  195.  
  196.     /* Save reversed list of open loop if we need to form an S/OLoop     */
  197.     /* polygon. Chain the OLoop instead of S.                 */
  198.     if (GenClipPoly) PRevLoop = GenReverseVrtxList(PLoop);
  199.  
  200.     PLoopEnd -> Pnext = VEnd -> Pnext;
  201.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  202.     }
  203.  
  204.     /* Time to free the InterSegment list pointed by OLoop: */
  205.     PISeg = OLoop -> PISeg;
  206.     while (PISeg != NULL) {
  207.     PItemp = PISeg;
  208.     PISeg = PISeg -> Pnext;
  209.     MyFree((char *) PItemp, OTHER_TYPE);
  210.     }
  211.     OLoop -> PISeg = NULL;            /* To be on the safe side... */
  212.  
  213.     /* There is a chance that Pl -> V will point on vertex in the clipped    */
  214.     /* part so we update it to point on VStart, which for sure is in polygon.*/
  215.     Pl -> V = VStart;
  216.     if (GenClipPoly) {       /* Generate the polygon from ClipPoly & PRevLoop: */
  217.     PLoopEnd = PRevLoop;
  218.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  219.  
  220.     if (ClipPoly == NULL) {
  221.         PLoopEnd -> Pnext = PRevLoop;  /* Close that loop and return it. */
  222.         ClipPl = AllocPolygon(0, 0, PRevLoop, NULL);
  223.         PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  224.         RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  225.         return ClipPl;
  226.     }
  227.  
  228.     PLoopEnd -> Pnext = ClipPoly;
  229.     PLoopEnd -> Tags = VStart -> Tags;
  230.     PLoopEnd -> Count = VStart -> Count;
  231.     Ptemp1 = ClipPoly;
  232.     while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext;
  233.     Ptemp1 -> Pnext = PRevLoop;
  234.  
  235.     ClipPl = AllocPolygon(0, 0, ClipPoly, NULL);
  236.     PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  237.     RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  238.     return ClipPl;
  239.     }
  240.     else return NULL;
  241. }
  242.  
  243. /*****************************************************************************
  244. * Find the intersection of the ray fired from Pt to +X direction with the    *
  245. * given polygon. Note Pt MUST be in the polygon. Two vertices equal to         *
  246. * ray/polygon intersection point are added to polygon vertex list, and a     *
  247. * pointer to the first one is also returned. This routine is exclusively     *
  248. * used by the CombineClosedLoops below.                         *
  249. * The polygon is NOT assumed to be convex and we look for the minimum X      *
  250. * intersection. The polygon might not be convex as a result of combinning    *
  251. * some other closed loop before the current one...                 *
  252. *****************************************************************************/
  253. static VertexStruct *CutPolygonAtRay(PolygonStruct *Pl, PointType Pt)
  254. {
  255.     int OnVertex;
  256.     RealType MinX = INFINITY, X;
  257.     VertexStruct *V, *Vnext, *VMinX = NULL;
  258.  
  259.     V = Pl -> V;
  260.     do {
  261.     Vnext = V -> Pnext;
  262.  
  263.     /* A polygon edge might intersect the ray iff one of the following:  */
  264.     /* 1. The first vertex is exactly on the ray Y level. (if this is    */
  265.     /*    true for the second edge, it will be detected next iteration). */
  266.     /* 2. The first vertex is below ray Y level, and second is above.    */
  267.     /* 3. The first vertex is above ray Y level, and second is below.    */
  268.     if (APX_EQ(V -> Pt[1], Pt[1])) {            /* Case 1 above. */
  269.         if (MinX > V -> Pt[0] && Pt[0] < V -> Pt[0]) {
  270.         OnVertex = TRUE;
  271.         MinX = V -> Pt[0];
  272.         VMinX = V;
  273.         }
  274.     }
  275.     else
  276.     if ((V -> Pt[1] < Pt[1] && Vnext -> Pt[1] > Pt[1]) ||/* Case 2 above.*/
  277.         (V -> Pt[1] > Pt[1] && Vnext -> Pt[1] < Pt[1])) {/* Case 3 above.*/
  278.         X = ((Vnext -> Pt[1] - Pt[1]) * V -> Pt[0] +
  279.          (Pt[1] - V -> Pt[1]) * Vnext -> Pt[0]) /
  280.         (Vnext -> Pt[1] - V -> Pt[1]);
  281.         if (MinX > X && Pt[0] < X) {
  282.         OnVertex = FALSE;
  283.         MinX = X;
  284.         VMinX = V;
  285.         }
  286.  
  287.     }
  288.  
  289.     V = Vnext;
  290.     }
  291.     while (V != NULL && V != Pl -> V);
  292.  
  293.     if ((V = VMinX) == NULL)
  294.     FatalError("CutPolygonAtRay: fail to find intersection");
  295.  
  296.     /* Now that we have the intersection point - create two new vertices     */
  297.     /* (one if OnVertex), insert them (it) after V and return the first.     */
  298.     if (OnVertex) {
  299.     V -> Pnext = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  300.     PT_COPY(V -> Pnext -> Pt, V -> Pt);
  301.     V -> Tags = V -> Count = 0;
  302.     }
  303.     else {
  304.     V -> Pnext = AllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  305.     Vnext = V -> Pnext;
  306.     Vnext -> Pt[0] = MinX;         /* X - as intersection point found. */
  307.     Vnext -> Pt[1] = Pt[1];              /* Y - must be as ray Y level. */
  308.     Vnext -> Pt[2] = V -> Pt[2];    /* Z - all polygon has same Z value. */
  309.  
  310.     V -> Pnext = AllocVertex(0, 0, NULL, V -> Pnext);
  311.     V = V -> Pnext;
  312.     PT_COPY(V -> Pt, Vnext -> Pt);
  313.     }
  314.  
  315.     return V;
  316. }
  317.  
  318. /*****************************************************************************
  319. *   Convert the given closed loop list to polygons, and return them. the     *
  320. * original given polygon vertex list is freed, and the first loop is subst.  *
  321. * instead.                                     *
  322. *****************************************************************************/
  323. static void ClosedLoopsToPolys(InterSegListStruct *PClosed, PolygonStruct *Pl)
  324. {
  325.     int LoopNum = 0;
  326.     VertexStruct *V, *VHead;
  327.     InterSegmentStruct *PISeg, *PItemp;
  328.     InterSegListStruct *PClosedTemp;
  329.  
  330.     MyFree((char *) Pl -> V, VERTEX_TYPE);
  331.     Pl -> Pnext = NULL;
  332.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  333.  
  334.     while (PClosed != NULL) {
  335.     /* Convert the InterList to vertex list and free the first: */
  336.     V = VHead = InterLoopToVrtxList(PClosed -> PISeg);
  337.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  338.         FatalError("ClosedLoopsToPolys: Closed loop with less than 3 vertices");
  339.  
  340.     PISeg = PClosed -> PISeg;      /* Time to free the InterSegmentList: */
  341.     while (PISeg != NULL) {
  342.         PItemp = PISeg;
  343.         PISeg = PISeg -> Pnext;
  344.         MyFree((char *) PItemp, OTHER_TYPE);
  345.     }
  346.  
  347.     while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt */
  348.     MyFree((char *) V -> Pnext, VERTEX_TYPE);/* and free - same as first.*/
  349.     V -> Pnext = VHead;               /* Make vertex list circular. */
  350.  
  351.     if (LoopNum++) {
  352.         Pl -> Pnext = AllocPolygon(0, 0, VHead, Pl -> Pnext);
  353.         PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane);
  354.     }
  355.     else {
  356.         Pl -> V = VHead;
  357.     }
  358.  
  359.     PClosedTemp = PClosed;
  360.     PClosed = PClosed -> Pnext;
  361.     MyFree((char *) PClosedTemp, OTHER_TYPE);
  362.     }
  363. }
  364.  
  365. /*****************************************************************************
  366. *   This routines cuts the given polygon into its interior closed loops by   *
  367. * adding an edge from the polygon boundary to each of its closed loops.      *
  368. *   For example:                                 *
  369. *                                         *
  370. * +-----------------------+      +-----------------------+             *
  371. * |                       |     |                       |             *
  372. * |  / \         / \      |     |  / \________ / \      |             *
  373. * |  \ /        |   |     |     |  \ /        |   |_____|             *
  374. * |      _       \ /      | -->  |      _       \ /      |             *
  375. * |     / \_              | -->  |     / \_              |             *
  376. * |    |    |             |     |    |    |_____________|             *
  377. * |     \__/              |     |     \__/              |             *
  378. * |                       |      |                       |             *
  379. * +-----------------------+      +-----------------------+             *
  380. *                                         *
  381. *   Algorithm:                                     *
  382. * 1. Transform the polygon and the closed loops to a plane parallel to XY    *
  383. *    plane (Z = Const plane).                             *
  384. * 2. For each loop find its MaxX while keeping the information on the        *
  385. *    vertex on that extremum.                             *
  386. * 3. For the loop with the biggest MaxX:                     *
  387. *    3.1. Use that extremum vertex (which must be non concave corner) to     *
  388. *         test if loop is in the reverse direction the polygon itself is,    *
  389. *         and reverse it if not.                         *
  390. *    3.2. Fire a ray from the extremum vertex, to the +X direction outside   *
  391. *         of the loop till it intersect the polygon, break the polygon at    *
  392. *         that point and add two edges to beginning of loop from breaking    *
  393. *         point and from end of loop to breaking point (beginning/end point  *
  394. *      of loop is the extremum vertex point).                 *
  395. * 4. Repeat step 3, with all loops.                         *
  396. * 5. Transfrom the new polygon back (using the inverse matrix of step 1)     *
  397. *    to its original orientation.                         *
  398. *                                         *
  399. * Returns TRUE iff the original polygon boundary is in output.             *
  400. *                                         *
  401. *****************************************************************************/
  402. static int CombineClosedLoops(PolygonStruct *Pl, InterSegListStruct *PClosed,
  403.                                 int AinB)
  404. {
  405.     RealType MaxX;
  406.     PointType V1, V2, Normal, PlNormal;
  407.     MatrixType RotMat;
  408.     VertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct;
  409.     InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast,
  410.     *PClosedMaxXLast;
  411.     InterSegmentStruct *PISeg, *PItemp, *PISegMaxX;
  412.  
  413.     Pl -> Pnext = NULL;          /* Make sure this polygon is disconnected. */
  414.  
  415.     /* Stage 1 - Transform the vertices to a plane parallel to XY plane: */
  416.     GenRotateMatrix(RotMat, Pl -> Plane);
  417.     V = VHead = Pl -> V;
  418.     do {                    /* Transform the polygon itself. */
  419.     MatMultVecby4by4(V -> Pt, V -> Pt, RotMat);
  420.     V = V -> Pnext;
  421.     }
  422.     while (V != NULL && V != VHead);
  423.  
  424.     PClosedTemp = PClosed;
  425.     while (PClosedTemp != NULL) {        /* And transform the loops also. */
  426.     PISeg = PClosed -> PISeg;
  427.     while (PISeg != NULL) {
  428.         MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  429.         MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  430.  
  431.         PISeg = PISeg -> Pnext;
  432.     }
  433.  
  434.     PClosedTemp = PClosedTemp -> Pnext;
  435.     }
  436.     if (!MatInverseMatrix(RotMat, RotMat))     /* Find the inverse matrix. */
  437.     FatalError("CombineClosedLoops: Inverse matrix does not exits");
  438.  
  439.     /* Evalaute the normal to the polygon (which must be convex!). Note we   */
  440.     /* cannt simply use the Plane normal as the polygon was transformed.     */
  441.     V = Pl -> V;
  442.     do {
  443.     Vnext = V -> Pnext;
  444.     PT_SUB(V1, Vnext -> Pt, V -> Pt);
  445.     PT_SUB(V2, Vnext -> Pnext -> Pt, Vnext -> Pt);
  446.     VecCrossProd(PlNormal, V1, V2);
  447.     V = Vnext;
  448.     }
  449.     while (PT_LENGTH(PlNormal) < EPSILON);
  450.  
  451.     PClosedTemp = PClosed;
  452.     while (PClosedTemp != NULL) {
  453.     /* Stage 2 - find MaxX extremum value of given loop, test the loop   */
  454.     /* direction, and reverse it if wrong. Note we convert the loop      */
  455.     /* given as InterSegListStruct list into VertexStruct list first.    */
  456.     PISegMaxX = PISeg = PClosedTemp -> PISeg;
  457.     MaxX = PISeg -> PtSeg[0][0];          /* Get first vertex X val. */
  458.     PISeg = PISeg -> Pnext;
  459.     while (PISeg)
  460.     {
  461.         if (PISeg -> PtSeg[0][0] > MaxX) {
  462.         MaxX = PISeg -> PtSeg[0][0];
  463.         PISegMaxX = PISeg;
  464.         }
  465.         PISeg = PISeg -> Pnext;
  466.     }
  467.     PClosedTemp -> PISegMaxX = PISegMaxX;
  468.  
  469.     PClosedTemp = PClosedTemp -> Pnext;
  470.     }
  471.  
  472.     /* Stage 3/4 - find the loop with biggest MaxX and combine it with the   */
  473.     /* polygon itself. Do it for all closed loops, in list:             */
  474.     PClosedTemp = PClosed;
  475.     while (PClosed != NULL) {
  476.     /* Find the one with maximum MaxX, and delete it from PClosed list.  */
  477.     PClosedLast = PClosedMaxX = PClosedTemp = PClosed;
  478.     MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0];
  479.     while (PClosedTemp != NULL)
  480.     {
  481.         if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) {
  482.         PClosedMaxX = PClosedTemp;
  483.         PClosedMaxXLast = PClosedLast;
  484.         }
  485.         PClosedLast = PClosedTemp;
  486.         PClosedTemp = PClosedTemp -> Pnext;
  487.     }
  488.     if (PClosedMaxX == PClosed) PClosed = PClosed -> Pnext; /* Del. from */
  489.     else PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext;/* PClosed list.*/
  490.  
  491.     /* Create a vertex list from the loop: */
  492.     V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg);
  493.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  494.         FatalError("CombineClosedLoops: Closed loop with less than 3 vertices");
  495.  
  496.     V = VHead;
  497.     while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt */
  498.     MyFree((char *) V -> Pnext, VERTEX_TYPE);/* and free - same as first.*/
  499.     V -> Pnext = VHead;               /* Make vertex list circular. */
  500.  
  501.     PISegMaxX = PClosedMaxX -> PISegMaxX;
  502.  
  503.     /* Now test if the vertex list should be reversed. Find a vertex     */
  504.     /* which is below MaxX but its successor is on MaxX. The 3 vertices  */
  505.     /* V, V -> Pnext (on MaxX), V -> Pnext -> Pnext, must form convex    */
  506.     /* corner which we use to test if the loop needs to be reversed:     */
  507.     while (APX_EQ(V -> Pt[0], MaxX)) V = V -> Pnext;
  508.     while (!APX_EQ(V -> Pnext -> Pt[0], MaxX)) V = V -> Pnext;
  509.     VMaxX = V -> Pnext;
  510.     PT_COPY(VStruct.Pt, V -> Pt);  /* Prepare in point in REAL position. */
  511.     MatMultVecby4by4(VStruct.Pt, VStruct.Pt, RotMat);
  512.     if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) {
  513.         /* The Inside of the object is actually the loop itself. In that */
  514.         /* case we simply return all the loops converted into polygon.   */
  515.         /* This case is simple...                         */
  516.         MyFree((char *) VHead, VERTEX_TYPE);   /* Free loop vertex list. */
  517.         PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */
  518.         PClosedTemp = PClosed = PClosedMaxX;
  519.         while (PClosedTemp != NULL) {    /* Transform the loops back. */
  520.         PISeg = PClosed -> PISeg;
  521.         while (PISeg != NULL) {
  522.             MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  523.             MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  524.  
  525.             PISeg = PISeg -> Pnext;
  526.         }
  527.         PClosedTemp = PClosedTemp -> Pnext;
  528.         }
  529.  
  530.         ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/
  531.         return FALSE;       /* Boundary is NOT part of object result. */
  532.     }
  533.     PT_SUB(V1, VMaxX -> Pt, V -> Pt);
  534.     PT_SUB(V2, VMaxX -> Pnext -> Pt, VMaxX -> Pt);
  535.     VecCrossProd(Normal, V1, V2);
  536.     if (DOT_PROD(Normal, PlNormal) > 0) {        /* Need to reverse list. */
  537.         Vprev = VHead;
  538.         V = Vprev -> Pnext;
  539.         Vnext = V -> Pnext;
  540.         do {
  541.         V -> Pnext = Vprev;/* Reverse to point on prev instead next. */
  542.         Vprev = V;
  543.         V = Vnext;
  544.         Vnext = V -> Pnext;
  545.         }
  546.         while (Vprev != VHead);
  547.     }
  548.  
  549.     PISeg = PClosedMaxX -> PISeg;  /* Time to free the InterSegmentList: */
  550.     while (PISeg != NULL) {
  551.         PItemp = PISeg;
  552.         PISeg = PISeg -> Pnext;
  553.         MyFree((char *) PItemp, OTHER_TYPE);
  554.     }
  555.     MyFree((char *) PClosedMaxX, OTHER_TYPE);
  556.  
  557.     /* O.k. lets fire a ray from VMaxX to +X direction and see where it  */
  558.     /* intersects the polygon. The routine CutPolygonAtRay will add two  */
  559.     /* vertices at the ray intersection into polygon vertex list and     */
  560.     /* return a pointer to first one, so we can chain our loop directly  */
  561.     /* between these two new vertices.                     */
  562.     V = CutPolygonAtRay(Pl, VMaxX -> Pt);
  563.     Vnext = V -> Pnext;
  564.     /* Introduce a copy of VMaxX and successor to VMaxX: */
  565.     VMaxX -> Pnext = AllocVertex(VMaxX -> Count, VMaxX -> Tags, NULL,
  566.                                 VMaxX -> Pnext);
  567.     PT_COPY(VMaxX -> Pnext -> Pt, VMaxX -> Pt);
  568.     V -> Pnext = VMaxX -> Pnext;
  569.     SET_INTERNAL_EDGE(V);
  570.     VMaxX -> Pnext = Vnext;
  571.     SET_INTERNAL_EDGE(VMaxX);
  572.     }
  573.  
  574.     /* Stage 5 - Time to rotate polygon back to its original position. */
  575.     V = VHead = Pl -> V;
  576.     do {
  577.     MatMultVecby4by4(V -> Pt, V -> Pt, RotMat);
  578.     V = V -> Pnext;
  579.     }
  580.     while (V != NULL && V != VHead);
  581.  
  582.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  583.     RST_CONVEX_POLY(Pl);         /* This polygon is not convex any more. */
  584.  
  585.     return TRUE;
  586. }
  587.  
  588. /*****************************************************************************
  589. *   Push on the adjacency stack, all adjacent polygons which are complete    *
  590. * (no intersection) and are adjacent to complete edges (originated from         *
  591. * input polygons) of the given polygon.                         *
  592. *****************************************************************************/
  593. static void PushAdjOnStack(PolygonStruct *Pl, PolygonStruct *AdjStack[],
  594.                              int *StackPointer)
  595. {
  596.     struct VertexStruct *V = Pl -> V;
  597.  
  598.     do {
  599.     /* If you wants to propagate iff both vertices are original then     */
  600.     /* uncomment the next line.                         */
  601.     if (IS_ORIGINAL_VRTX(V) /* && IS_ORIGINAL_VRTX(V -> Pnext) */
  602.         && V -> PAdj != NULL)
  603.         AdjStack[++*StackPointer] = V -> PAdj;
  604.     if (*StackPointer >= ADJ_STACK_SIZE) {
  605.         FatalError("Adjacency stack overflow, object too big\n");
  606.     }
  607.     V = V -> Pnext;
  608.     }
  609.     while (V != Pl -> V);
  610. }
  611.  
  612. /*****************************************************************************
  613. *   Chain two Polygon lists into one. For fast processing it is prefered the *
  614. * first one to be to shorter. Returns pointer to chained list.             *
  615. *****************************************************************************/
  616. static struct PolygonStruct *ChainPolyLists(PolygonStruct *Pl1,
  617.                             PolygonStruct *Pl2)
  618. {
  619.     PolygonStruct *Ptemp;
  620.  
  621.     if (Pl1 == NULL) return Pl2;
  622.     else
  623.     if (Pl2 == NULL) return Pl1;
  624.     else {
  625.     Ptemp = Pl1;
  626.     while (Ptemp -> Pnext != NULL) Ptemp = Ptemp -> Pnext;
  627.     Ptemp -> Pnext = Pl2;
  628.     return Pl1;
  629.     }
  630. }
  631.  
  632. /*****************************************************************************
  633. *   This routine coordinates all the extraction of the polygons from the     *
  634. * intersecting lists. Does it in the following steps:                 *
  635. * 1. Mark all polygons with no intersection at all as complete polygons.     *
  636. *    (this is cause that this polygon will be totally in or out, according   *
  637. *    to inter-polygon adjacencies propagation...)                 *
  638. *    Also Mark them as undefined (if in output or undefined) yet.         *
  639. *    Uses PolygonStruct Tags to save these bits.                 *
  640. * 2. 2.1. Convert the unordered segment list of each polygon to closed loops *
  641. *         (if create a hole in polygon) or open (if crosses its boundary).   *
  642. *    2.2. Order the open loops along the perimeter of the polygon (note      *
  643. *      these loops cannt intersect. For example (5 vertices polygon):     *
  644. *             -----------------------------L3                 *
  645. *        |  ---------------L1  -----L2 |          --------L4   --L5   *
  646. *        | |               |  |     |  |         |        |   |  |    *
  647. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
  648. *         Note L1, L2 are enclosed in L3 loop, and that the order is circular*
  649. *    2.3. "Break" the polygon at each open loop that has no enclosed loops   *
  650. *      in it. For example we can start at L1, L2, L4, L5 and then L3.     *
  651. *      "Break" means - replace the vertex chain between the two loop end  *
  652. *      points, with the loops itself. Depends upon the relation required  *
  653. *      we may need to output a new polygon form from the deleted chain    *
  654. *      and that loop. In addition we may form a new polygon from last     *
  655. *      loop and was was left from the original polygon             *
  656. *      For each formed polygon, for each complete edge of it (i.e. edge   *
  657. *      which was originally in the polygon) test the adjacent polygon     *
  658. *      if it is complete (as marked in 1.) and if in or undefined (marked *
  659. *      undefined in 1.) is still undefined:                     *
  660. *      2.3.1. set it to be in.                         *
  661. *      2.3.2. push it on adjacency stack.                     *
  662. *    2.4. For each closed loop - find in which polygon (from polygons         *
  663. *      created in 2.3.) it is enclosed, and decompose it.             *
  664. * 3. While adjacencies stack not empty do:                     *
  665. *    3.1. pop top polygon from stack and output it.                 *
  666. *    3.2. For each of its edges (which obviousely must be complete edges)    *
  667. *      if adjacent polygon is complete and undefined:             *
  668. *      3.3.1. set it to be in.                         *
  669. *      3.3.2. push it on adjacency stack.                     *
  670. *    3.3  go back to 3.                                 *
  671. *                                         *
  672. *   The above algorithm defines in as in output, but dont be confused with   *
  673. * the required inter-object AinB (or AoutB if FALSE), which used to         *
  674. * determine which side of the trimming loop should be output.             *
  675. *   Note this routine may return non-convex polygons (but marked as so) even *
  676. * though the input for the booleans must be convex polygons only!         *
  677. *   In order to keep the given object unchanged, a whole new copy off the    *
  678. * polygon list is made. The polygons of the list that are not in the output  *
  679. * are freed: a global list of all polygons (pointers) is used to scan them   *
  680. * in the end and free the unused ones (list PolysPtr).                 *
  681. *****************************************************************************/
  682. ObjectStruct *ExtractPolygons(ObjectStruct *PObj, int AinB)
  683. {
  684.     int NumOfPolys = 0, StackPointer = -1;
  685.     struct PolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr,
  686.         *Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl;
  687.     struct VertexStruct *V, *Vnext;
  688.     struct InterSegListStruct *PClosed, *POpen, *Ptemp;
  689.  
  690. #ifdef DEBUG3
  691.     printf("Enter ExtractPolygons\n");
  692. #endif /* DEBUG3 */
  693.  
  694.     TestBooleanCtrlBrk();
  695.     
  696.     /* Stage 1. - mark all polygons as needed: */
  697.     PlHead = Pl = PObj -> U.Pl;
  698.     /* Gen. a copy of Pl, so we can modify the original polygon list: */
  699.     PObj -> U.Pl = CopyPolygonList(Pl);
  700.  
  701.     while (Pl != NULL) {
  702.     NumOfPolys++;         /* Count number of polygons in original object. */
  703.     if (Pl -> PAux != NULL) {     /* The intersection list is not empty! */
  704.         RST_COMPLETE_POLY(Pl);     /* Mark it as non complete polygon. */
  705.         V = Pl -> V;
  706.         do {
  707.         SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */
  708.         V = V -> Pnext;
  709.         }
  710.         while (V != Pl -> V);
  711.     }
  712.     else {
  713.         SET_COMPLETE_POLY(Pl);         /* Mark it as complete polygon. */
  714.         RST_INOUTPUT_POLY(Pl);     /* And as undefined (if in output). */
  715.         RST_ADJPUSHED_POLY(Pl);     /* And as not pushed on adj. stack. */
  716.     }
  717.     Pl = Pl -> Pnext;
  718.     }
  719.  
  720.     /* Stage 2. - scan the polygons and subdivide the intersecting ones: */
  721.     Pl = PlHead;
  722.  
  723.     /* We will save pointers to ALL polygons in list so we could free in the */
  724.     /* end the ones that are not in the output list, and therefore unused.   */
  725.     PolysPtr = (PolygonStruct **)
  726.         MyMalloc(sizeof(PolygonStruct *) * NumOfPolys, OTHER_TYPE);
  727.     NumOfPolys = 0;
  728.  
  729.     while (Pl != NULL) {
  730.     TestBooleanCtrlBrk();
  731.  
  732.     PolysPtr[NumOfPolys++] = Pl;        /* Save pointer to this polygon. */
  733.  
  734.     PlNext = Pl -> Pnext;
  735.  
  736.     if (!IS_COMPLETE_POLY(Pl)) {/* They are intersections with this one. */
  737.         /* Convert the intersecting segments into open/closed loops. */
  738.         LoopsFromInterList(Pl, &PClosed, &POpen);
  739.  
  740.         if (PClosed != NULL && POpen != NULL)
  741.         FatalError("ExtractPolygons: Polygon with both open & closed loops - not supported\n");
  742.  
  743.         if (POpen != NULL) {
  744.         /* Sort the Open loops into an order we can handle... */
  745.         SortOpenInterList(Pl, &POpen);
  746.         SplPl = NewPl = NULL;     /* Keep the list of split polygons. */
  747.  
  748.         while (POpen != NULL) {    /* Clip the open loops from polygon: */
  749.             /* Note ClipOpenLoopFromPoly also frees the InterSegment */
  750.             /* list pointed by POpen (but not POpen itself).          */
  751.             NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB);
  752.             if (NewPl != NULL) {   /* If loop clipped a new polygon, */
  753.             NewPl -> Pnext = SplPl;/* add to split polygon list. */
  754.             SplPl = NewPl;
  755.             /* And push adj. polygons of complete edges on stack.*/
  756.             PushAdjOnStack(NewPl, AdjStack, &StackPointer);
  757.             }
  758.             Ptemp = POpen;
  759.             POpen = POpen -> Pnext;
  760.             MyFree((char *) Ptemp, OTHER_TYPE);
  761.         }
  762.         /* Last clip generated nothing (NewPl == NULL) so part that  */
  763.         /* left from Pl (PlCopy) is IN output list! Add this poly:   */
  764.         if (NewPl == NULL) {
  765.             Pl -> Pnext = SplPl; /* And chain what was left from it. */
  766.             SplPl = Pl;
  767.             /* And push adjacent polygons of complete edges on stack.*/
  768.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  769.             SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */
  770.             RST_CONVEX_POLY(Pl);       /* May be not convex now. */
  771.         }
  772.         OutputPl = ChainPolyLists(SplPl, OutputPl);
  773.         }
  774.         else { /* PClosed != NULL */
  775.         /* Make a "cut" from the loop(s)  +-------+      +---+---+   */
  776.         /* to boundary if possible, and   |       |      |       |   */
  777.         /* converting Pl to a nonconvex   |  / \  |  ->  |  / \__|   */
  778.         /* polygon, that has an edge (the |  \ /  |  ->  |  \ /  |   */
  779.         /* cut) which is shared twice in  |       |      |       |   */
  780.         /* the same polygon          +-------+      +-------+   */
  781.         if (CombineClosedLoops(Pl, PClosed, AinB)) {
  782.             /* If returned with TRUE - the polygon boundary is in    */
  783.             /* output, so add all its neighbours to adj. stack.      */
  784.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  785.         }
  786.  
  787.         OutputPl = ChainPolyLists(Pl, OutputPl);
  788.         }
  789.     }
  790.     Pl = PlNext;
  791.     }
  792.  
  793.     /* Stage 3. - handling adjacencies and propagate them in polygons:         */
  794.     /* Pop off the elements from the stack, and propagate them using their   */
  795.     /* adjacencies.                                 */
  796.     while (StackPointer >= 0) {
  797.     Pl = AdjStack[StackPointer--];             /* Pop top element. */
  798.     if (!IS_COMPLETE_POLY(Pl) ||        /* Ignore non complete polygons. */
  799.          IS_INOUTPUT_POLY(Pl)) continue;          /* If already handled. */
  800.  
  801.     SET_INOUTPUT_POLY(Pl);      /* Mark this one as handled for next time. */
  802.  
  803.     V = Pl -> V;         /* Push all adjacent ones that not handled yet. */
  804.     do {
  805.         if (V -> PAdj &&
  806.         IS_COMPLETE_POLY(V -> PAdj) &&
  807.         !IS_INOUTPUT_POLY(V -> PAdj) &&
  808.         !IS_ADJPUSHED_POLY(V -> PAdj)) {
  809.         SET_ADJPUSHED_POLY(V -> PAdj);
  810.         AdjStack[++StackPointer] = V -> PAdj;   /* Push it on stack. */
  811.         if (StackPointer >= ADJ_STACK_SIZE)
  812.             FatalError("Adjacency stack overflow, object too big\n");
  813.         }
  814.         V = V -> Pnext;
  815.     }
  816.     while (V != Pl -> V);
  817.  
  818.     Pl -> Pnext = OutputPl;           /* And chain it into output list. */
  819.     OutputPl = Pl;
  820.     }
  821.  
  822.     /* Free all polygons which are not in the output list: */
  823.     while (--NumOfPolys >= 0) {
  824.     if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) {
  825.         PolysPtr[NumOfPolys] -> Pnext = NULL; /* Free only this polygon. */
  826.         MyFree((char *) (PolysPtr[NumOfPolys]), POLYGON_TYPE);
  827.     }
  828.     }
  829.     MyFree((char *) PolysPtr, OTHER_TYPE);
  830.  
  831.     /* Another floating point kludge: a polygon may have zero length edge so */
  832.     /* search for those and remove them - someone may die because of one...  */
  833.     Pl = OutputPl;
  834.     while (Pl != NULL) {
  835.     V = Pl -> V;
  836.     do {
  837.         Vnext = V -> Pnext;
  838.         if (PT_EQ(V -> Pt, Vnext -> Pt)) {
  839.         /* Ahh - we got you. Simply skip Vnext vertex and free it: */
  840.         V -> Pnext = Vnext -> Pnext;
  841.         /* Update polygon vertex pointer if point on freed vertex: */
  842.         if (Pl -> V == Vnext) Pl -> V = Vnext -> Pnext;
  843.         Vnext -> Pnext = NULL;              /* Dont free too much! */
  844.         MyFree((char *) Vnext, VERTEX_TYPE);
  845.         Vnext = V -> Pnext;
  846.         }
  847.         V = Vnext;
  848.     }
  849.     while (V != Pl -> V && V != NULL);
  850.  
  851.     Pl = Pl -> Pnext;
  852.     }
  853.  
  854. #ifdef DEBUG3
  855.     printf("Exit ExtractPolygons\n");
  856. #endif /* DEBUG3 */
  857.  
  858.     return GenGeomObject("", OutputPl, NULL);     /* Return resulting object. */
  859. }
  860.  
  861. #ifdef DEBUG2
  862.  
  863. /*****************************************************************************
  864. *   Print the content of the given polygon, to standard output.             *
  865. *****************************************************************************/
  866. static void PrintVrtxList(VertexStruct *V)
  867. {
  868.     struct VertexStruct *VHead = V;
  869.  
  870.     do {
  871.     printf("    %12lf %12lf %12lf", V -> Pt[0], V -> Pt[1], V -> Pt[2]);
  872.     if (IS_INTERNAL_EDGE(V))
  873.          printf(" (Internal)\n");
  874.     else printf("\n");
  875.     V = V -> Pnext;
  876.     }
  877.     while (V!= NULL && V != VHead);
  878. }
  879.  
  880. /*****************************************************************************
  881. *   Print the content of the given InterSegment list, to standard output.    *
  882. *****************************************************************************/
  883. static void PrintInterList(InterSegmentStruct *PInt)
  884. {
  885.     printf("INTER SEGMENT LIST:\n");
  886.  
  887.     if (PInt) printf("Entry vertex pointer %p\n", PInt -> V[0]);
  888.     while (PInt) {
  889.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  890.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  891.         FP_SEG(PInt->V[0]),
  892.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  893.         FP_SEG(PInt->V[1]));
  894.     if (PInt -> Pnext == NULL)
  895.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  896.  
  897.     PInt = PInt -> Pnext;
  898.     }
  899. }
  900.  
  901. #endif /* DEBUG2 */
  902.