home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / IRITS.ZIP / BOOL1LOW.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  31.3 KB  |  870 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 DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #ifdef __MSDOS__
  24. #include <alloc.h>
  25. #include <dos.h>
  26. #endif /* __MSDOS__ */
  27.  
  28. #include <stdio.h>
  29. #include <ctype.h>
  30. #include <math.h>
  31. #include <string.h>
  32. #include "program.h"
  33. #include "allocatg.h"
  34. #include "adjcncyg.h"
  35. #include "objects.h"
  36. #include "geomat3d.h"
  37. #include "booleang.h"
  38. #include "booleanl.h"
  39.  
  40. static int ObjectsIntersect;
  41.  
  42. static ObjectStruct *BooleanLowGenInOut(ObjectStruct *PObj1, int InOut);
  43. static void BooleanLowInterAll(ObjectStruct *PObj1, ObjectStruct *PObj2);
  44. static void BooleanLowInterOne(PolygonStruct *Pl1, PolygonStruct *Pl2);
  45. static InterSegmentStruct *InterSegmentPoly(PolygonStruct *Pl,
  46.                 PolygonStruct *SegPl, PointType Segment[2]);
  47. static void SwapPointInterList(InterSegmentStruct *PSeg);
  48. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  49.                         InterSegmentStruct **PSegList);
  50. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  51.                         InterSegmentStruct **PSegList);
  52. static void SortOpenReverseLoop(SortOpenStruct *PSHead);
  53. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  54.        SortOpenStruct *PSTemp, PointType Pt, VertexStruct *V, PolygonStruct *Pl);
  55. static ObjectStruct *PolylineFromInterSeg(ObjectStruct *PObj);
  56.  
  57. #ifdef DEBUG2
  58. static void PrintVrtxList(VertexStruct *V);
  59. static void PrintInterList(InterSegmentStruct *PInt);
  60. #endif /* DEBUG2 */
  61.  
  62. /*****************************************************************************
  63. *   Routine to find the part of PObj1 which is out of PObj2:             *
  64. *****************************************************************************/
  65. ObjectStruct *BooleanLow1Out2(ObjectStruct *PObj1, ObjectStruct *PObj2)
  66. {
  67. #ifdef DEBUG3
  68.     printf("Enter BooleanLow1Out2\n");
  69. #endif /* DEBUG3 */
  70.  
  71.     GenAdjacencies(PObj1);
  72.  
  73.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  74.     ObjectsIntersect = FALSE;
  75.     BooleanLowInterAll(PObj1, PObj2);
  76.  
  77.     /* Generate all the polygons in PObj1 which are out of PObj2. */
  78.     if (!ObjectsIntersect) {
  79.     FatalBooleanError(FTL_BOOL_NO_INTER);
  80.     }
  81.     return BooleanLowGenInOut(PObj1, FALSE);
  82. }
  83.  
  84. /*****************************************************************************
  85. *   Routine to find the part of PObj1 which is in PObj2:             *
  86. *****************************************************************************/
  87. ObjectStruct *BooleanLow1In2(ObjectStruct *PObj1, ObjectStruct *PObj2)
  88. {
  89. #ifdef DEBUG3
  90.     printf("Enter BooleanLow1In2\n");
  91. #endif /* DEBUG3 */
  92.  
  93.     GenAdjacencies(PObj1);
  94.  
  95.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  96.     ObjectsIntersect = FALSE;
  97.     BooleanLowInterAll(PObj1, PObj2);
  98.  
  99.     /* Generate all the polygons in PObj1 which are in PObj2. */
  100.     if (!ObjectsIntersect) {
  101.     FatalBooleanError(FTL_BOOL_NO_INTER);
  102.     }
  103.     return BooleanLowGenInOut(PObj1, TRUE);
  104. }
  105.  
  106. /*****************************************************************************
  107. *   Scan the InterSegmentList of each polygon and decide using Intersection  *
  108. * list, if it is IN relative to the other object. Note that for polygons     *
  109. * that does not intersect at all, we use the polygon adjacencies to decide   *
  110. * if they are IN or not.                             *
  111. *****************************************************************************/
  112. static ObjectStruct *BooleanLowGenInOut(ObjectStruct *PObj, int InOut)
  113. {
  114.     if (BooleanOutputInterCurve) {
  115.     /* Return a polyline object - extract the InterSegment list of each  */
  116.     /* polygon into open/closed polyline loops object.             */
  117.     return PolylineFromInterSeg(PObj);
  118.     }
  119.     else
  120.     return ExtractPolygons(PObj, InOut);
  121. }
  122.  
  123. /*****************************************************************************
  124. *   Create a polyline object out of the intersection list of the polygons.   *
  125. *****************************************************************************/
  126. static ObjectStruct *PolylineFromInterSeg(ObjectStruct *PObj)
  127. {
  128.     struct ObjectStruct *PObjRet;
  129.     struct PolygonStruct *PlTemp, *PlHead = NULL, *PlObj;
  130.     struct InterSegmentStruct *PInter, *PInterNext;
  131.     struct InterSegListStruct *PClosed, *POpen, *PClosedNext, *POpenNext;
  132.     struct VertexStruct *V;
  133.  
  134.     PlObj = PObj -> U.Pl;
  135.     while (PlObj != NULL) {
  136.     LoopsFromInterList(PlObj, &PClosed, &POpen);
  137.     while (POpen != NULL) {
  138.         /* Make one polyline from each loop in list: */
  139.         PInter = POpen -> PISeg;
  140.         POpenNext = POpen -> Pnext;
  141.  
  142.         PlTemp = AllocPolygon(0, 0, NULL, NULL);
  143.         PlTemp -> V = V = AllocVertex(0, 0, NULL, NULL);
  144.         PT_COPY(V -> Pt, PInter -> PtSeg[0]);
  145.         while (PInter) {
  146.         PInterNext = PInter -> Pnext;
  147.  
  148.         V -> Pnext = AllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  149.         PT_COPY(V -> Pt, PInter -> PtSeg[1]);
  150.  
  151.         MyFree((char *) PInter, OTHER_TYPE);
  152.         PInter = PInterNext;
  153.         }
  154.         PlTemp -> Pnext = PlHead;
  155.         PlHead = PlTemp;
  156.  
  157.         MyFree((char *) POpen, OTHER_TYPE);
  158.         POpen = POpenNext;
  159.     }
  160.     while (PClosed != NULL) {
  161.         /* Make one polyline from each loop in list: */
  162.         PInter = PClosed -> PISeg;
  163.         PClosedNext = PClosed -> Pnext;
  164.  
  165.         PlTemp = AllocPolygon(0, 0, NULL, NULL);
  166.         PlTemp -> V = V = AllocVertex(0, 0, NULL, NULL);
  167.         PT_COPY(V -> Pt, PInter -> PtSeg[0]);
  168.         while (PInter) {
  169.         V -> Pnext = AllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  170.         PT_COPY(V -> Pt, PInter -> PtSeg[1]);
  171.         PInter = PInter -> Pnext;
  172.         }
  173.         PlTemp -> Pnext = PlHead;
  174.         PlHead = PlTemp;
  175.  
  176.         MyFree((char *) PClosed, OTHER_TYPE);
  177.         PClosed = PClosedNext;
  178.     }
  179.     PlObj = PlObj -> Pnext;
  180.     }
  181.  
  182.     PObjRet = GenGeomObject("", PlHead, NULL);
  183.     SET_POLYLINE_GEOM_OBJ(PObjRet);          /* Mark it as polyline object. */
  184.     return PObjRet;
  185. }
  186.  
  187. /*****************************************************************************
  188. *   Routine to find all the intersections between all PObj1 polygons with    *
  189. * PObj2 polygons. The intersections are saved as a list of segments (struct  *
  190. * InterSegmentStruct) in each of PObj1 polygons using the PAux pointer (see  *
  191. * PolygonStruct). Note PObj2 is not modified at all, and in PObj1, only PAux *
  192. * of each polygon is set to the segment list, or NULL if none             *
  193. *****************************************************************************/
  194. static void BooleanLowInterAll(ObjectStruct *PObj1, ObjectStruct *PObj2)
  195. {
  196.     struct PolygonStruct *Pl1, *Pl2;
  197.  
  198. #ifdef DEBUG3
  199.     printf("Enter BooleanLowInterAll\n");
  200. #endif /* DEBUG3 */
  201.  
  202.     Pl1 = PObj1 -> U.Pl;
  203.     while (Pl1 != NULL) {
  204.     Pl1 -> PAux = NULL;       /* Empty InterSegment list to start with: */
  205.  
  206.     Pl2 = PObj2 -> U.Pl;
  207.     while (Pl2 != NULL) {
  208.         BooleanLowInterOne(Pl1, Pl2);
  209.         Pl2 = Pl2 -> Pnext;
  210.     }
  211.     ObjectsIntersect |= (Pl1 -> PAux != NULL);   /* If any intersection. */
  212.  
  213.     Pl1 = Pl1 -> Pnext;
  214.     }
  215.  
  216. #ifdef DEBUG3
  217.     printf("Exit BooleanLowInterAll\n");
  218. #endif /* DEBUG3 */
  219. }
  220.  
  221. /*****************************************************************************
  222. *   Routine to intersect polygon Pl1, with polygon Pl2. If found common      *
  223. * intersection, that segment will be added to the InterSegmentStruct list    *
  224. * saved in Pl1 PAux list.                             *
  225. *   Note that as the two polygons convex, only one segment can result from   *
  226. * such intersection.                                 *
  227. *   Algorithm: intersect all Pl2 edges with Pl1 plane. If found that         *
  228. * (exactly) two vertices (one segment) of Pl2 do intersect Pl1 plane then:   *
  229. * Perform clipping of the segment against Pl1. If result is not empty, add   *
  230. * the result segment to Pl1 InterSegmentStruct list (saved at PAux of         *
  231. * polygon - see PolygonStruct).                             *
  232. *****************************************************************************/
  233. static void BooleanLowInterOne(PolygonStruct *Pl1, PolygonStruct *Pl2)
  234. {
  235.     int NumOfInter = 0;
  236.     RealType TInter[2],
  237.     *Plane = Pl1 -> Plane;                   /* For faster access. */
  238.     PointType Inter[2], Dir;
  239.     VertexStruct *Vnext, *V = Pl2 -> V;
  240.     InterSegmentStruct *PSeg, *PLSeg;
  241.  
  242. #ifdef DEBUG3
  243.     printf("Enter BooleanLowInterOne\n");
  244. #endif /* DEBUG3 */
  245.  
  246.     TestBooleanCtrlBrk();
  247.  
  248.     do {
  249.     Vnext = V -> Pnext;
  250.     PT_SUB(Dir, Vnext -> Pt, V -> Pt);
  251.     if (CGPointFromLinePlane01(V -> Pt, Dir, Plane, Inter[NumOfInter],
  252.                             &TInter[NumOfInter]) &&
  253.         ((NumOfInter == 0) || (NumOfInter == 1 &&
  254.                    !PT_EQ(Inter[0], Inter[1]))))
  255.         NumOfInter++;
  256.     if (NumOfInter == 2) break;       /* Cannt have more intersections. */
  257.  
  258.     V = Vnext;
  259.     }
  260.     while (V != NULL && V != Pl2 -> V);
  261.  
  262.     switch (NumOfInter) {
  263.     case 0:
  264.         break;
  265.     case 1:
  266.         /* One intersection is possible if only one vertex of Pl2 is in  */
  267.         /* the plane of Pl1, all other vertices are on one side of plane.*/
  268.         break;
  269.     case 2:
  270.         /* Clip the segment against the polygon and insert if not empty: */
  271.         if ((PSeg = InterSegmentPoly(Pl1, Pl2, Inter)) != NULL) {
  272.         /* insert that segment to list of Pl1. Note however that the */
  273.         /* intersection may be exactly on 2 other polygons boundary, */
  274.         /* And therefore creates the same intersection edge TWICE!   */
  275.         /* Another possiblity is on same case, the other polygon     */
  276.         /* will have that inter. edge on its edge, and its ignored.  */
  277.         /* We therefore test for duplicates and ignore edge if so    */
  278.         if (PSeg -> V[0] != NULL && PSeg -> V[0] == PSeg -> V[1]) {
  279.             MyFree((char *) PSeg, OTHER_TYPE);           /* Ignore it! */
  280.             return;
  281.         }
  282.         PLSeg = (InterSegmentStruct *) Pl1 -> PAux;
  283.         while (PLSeg != NULL) {
  284.             if ((PT_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[0]) &&
  285.              PT_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[1])) ||
  286.             (PT_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[1]) &&
  287.              PT_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[0]))) {
  288.             MyFree((char *) PSeg, OTHER_TYPE);     /* Ignore it! */
  289.             return;
  290.             }
  291.             PLSeg = PLSeg -> Pnext;
  292.         }
  293.  
  294.         PSeg -> Pnext = (InterSegmentStruct *) Pl1 -> PAux;
  295.         Pl1 -> PAux = (VoidPtr) PSeg;
  296.         }
  297.         break;
  298.     }
  299.  
  300. #ifdef DEBUG3
  301.     printf("Exit BooleanLowInterOne\n");
  302. #endif /* DEBUG3 */
  303. }
  304.  
  305. /*****************************************************************************
  306. *   Intersects the given segment (given as two end points), with the given   *
  307. * polygon (which must be convex). Upto two intersections are possible, as    *
  308. * again, the polygon is convex. Note Segment polygon is given as SegPl.      *
  309. *****************************************************************************/
  310. static InterSegmentStruct *InterSegmentPoly(PolygonStruct *Pl,
  311.                 PolygonStruct *SegPl, PointType Segment[2])
  312. {
  313.     int i, NumOfInter = 0, Reverse, Res;
  314.     RealType TInter[2], temp, Min, Max, *PtSeg0, *PtSeg1;
  315.     PointType Dir, Inter[2], SegDir, Pt1, Pt2;
  316.     VertexStruct *VInter[2], *V = Pl -> V, *Vnext;
  317.     InterSegmentStruct *PSeg;
  318.  
  319.     /* Find the segment direction vector: */
  320.     PT_SUB(SegDir, Segment[1], Segment[0]);
  321.  
  322. #ifdef DEBUG3
  323.     printf("Enter InterSegmentPoly\n");
  324. #endif /* DEBUG3 */
  325.  
  326.     do {
  327.     Vnext = V -> Pnext;
  328.     PT_SUB(Dir, Vnext -> Pt, V -> Pt);
  329.     /* Find the intersection of the segment with all the polygon edges: */
  330.     /* Note the t parameter value of the edge (temp) must be in [0..1]. */
  331.     if ((Res = CG2PointsFromLineLine(Segment[0], SegDir,
  332.         V -> Pt, Dir, Pt1, &TInter[NumOfInter], Pt2, &temp)) != 0 &&
  333.         (temp > 0.0 || APX_EQ(temp, 0.0)) &&
  334.         (temp < 1.0 || APX_EQ(temp, 1.0)) && PT_EQ(Pt1, Pt2) &&
  335.         (NumOfInter == 0 ||
  336.          (NumOfInter == 1 && !APX_EQ(TInter[0], TInter[1])))) {
  337.         PT_COPY(Inter[NumOfInter], Pt1);
  338.         VInter[NumOfInter++] = V;   /* Save pointer to intersected edge. */
  339.     }
  340.     else {
  341.         /* If Res == 0 its parallel to edge. If distance is zero then    */
  342.         /* line is on the edge line itself - quit from this one!         */
  343.         if (!Res && CGDistPointPoint(Pt1, Pt2) < EPSILON) {
  344.         /* Wipe out adjacency of this vertex as we dont want to      */
  345.         /* propagate through this one nothing - its on in/out border.*/
  346.         VertexStruct *Vtemp;
  347.  
  348.         if (V -> PAdj == NULL) return NULL;
  349.  
  350.         Vtemp = V -> PAdj -> V;
  351.         do {/* Find the edge on the other polygon to wipe out first. */
  352.             if (Vtemp -> PAdj == Pl) {
  353.             Vtemp -> PAdj = NULL;
  354.             break;
  355.             }
  356.             Vtemp = Vtemp -> Pnext;
  357.         }
  358.         while (Vtemp != NULL && Vtemp != V -> PAdj -> V);
  359.         V -> PAdj = NULL;        /* And wipe out ours also... */
  360.         return NULL;
  361.         }
  362.     }
  363.  
  364.     V = Vnext;
  365.     }
  366.     while (V != NULL && V != Pl -> V);
  367.  
  368.     switch (NumOfInter) {
  369.     case 0:
  370.         return NULL;
  371.     case 1:
  372.         /* One intersection is possible if segment intersects one vertex */
  373.         /* of polygon and all other vertices are on same side of segment.*/
  374.         return NULL;
  375.     case 2:
  376.         /* In order the segment to really intersect the polygon, it must */
  377.         /* at list part of t in [0..1] in the polygon. Test it:         */
  378.         Min = MIN(TInter[0], TInter[1]);
  379.         Max = MAX(TInter[0], TInter[1]);
  380.         Reverse = TInter[0] > TInter[1];
  381.         if (Min >= 1.0 || APX_EQ(Min, 1.0) ||
  382.         Max <= 0.0 || APX_EQ(Max, 0.0)) return NULL;
  383.  
  384.         PSeg = (InterSegmentStruct *) MyMalloc(sizeof(InterSegmentStruct),
  385.                                    OTHER_TYPE);
  386.         PSeg -> Pl = SegPl;     /* Pointer to other (intersect) polygon. */
  387.  
  388.         /* Handle the Min end point: */
  389.         if (APX_EQ(Min, 0.0)) {
  390.         PtSeg0 = Segment[0];
  391.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  392.         }
  393.         else if (Min < 0.0) {
  394.         PtSeg0 = Segment[0];
  395.         PSeg -> V[0] = NULL;             /* End is internal. */
  396.         }
  397.         else { /* Min > 0.0 */
  398.         PtSeg0 = (Reverse ? Inter[1] : Inter[0]);
  399.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  400.         }
  401.  
  402.         /* Handle the Max end point: */
  403.         if (APX_EQ(Max, 1.0)) {
  404.         PtSeg1 = Segment[1];
  405.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  406.         }
  407.         else if (Max > 1.0) {
  408.         PtSeg1 = Segment[1];
  409.         PSeg -> V[1] = NULL;             /* End is internal. */
  410.         }
  411.         else { /* Max < 1.0 */
  412.         PtSeg1 = (Reverse ? Inter[0] : Inter[1]);
  413.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  414.         }
  415.  
  416.         PT_COPY(PSeg -> PtSeg[0], PtSeg0); /* The two segment end point. */
  417.             PT_COPY(PSeg -> PtSeg[1], PtSeg1);
  418.  
  419.         for (i=0; i<3; i++) {         /* Make zeros look nicer... */
  420.         if (ABS(PSeg -> PtSeg[0][i]) < EPSILON)
  421.             PSeg -> PtSeg[0][i] = 0.0;
  422.         if (ABS(PSeg -> PtSeg[1][i]) < EPSILON)
  423.             PSeg -> PtSeg[1][i] = 0.0;
  424.         }
  425.         if (PT_EQ(PSeg -> PtSeg[0], PSeg -> PtSeg[1])) {
  426.         MyFree((char *) PSeg, OTHER_TYPE);
  427.         return NULL;
  428.         }
  429.         return PSeg;
  430.     }
  431.     return NULL;                    /* Makes warning silent. */
  432. }
  433.  
  434. /*****************************************************************************
  435. *   Given a polygon with the intersection list, create the polylines loop(s) *
  436. * out of it, which can be one of the two:                     *
  437. * 1. Closed loop - all the intersection create a loop in one polygon.         *
  438. * 2. Open polyline - if the intersection crosses the polygon boundary. In    *
  439. *    this case the two end point of the polyline, must lay on polygon         *
  440. *    boundary.                                     *
  441. * In both cases, the polyline will be as follows:                 *
  442. * First point at first list element at PtSeg[0] (see InterSegmentStruct).    *
  443. * Second point at first list element at PtSeg[1] (see InterSegmentStruct).   *
  444. * Point i at list element (i-1) at PtSeg[0] (PtSeg[1] is not used!).         *
  445. * In the closed loop case the last point is equal to first.             *
  446. * Both cases returns NULL terminated list.                     *
  447. *****************************************************************************/
  448. void LoopsFromInterList(PolygonStruct *Pl,
  449.         InterSegListStruct **PClosed, InterSegListStruct **POpen)
  450. {
  451.     InterSegmentStruct *PSeg, *PSegHead, *PSegTemp, *PSegNewTemp;
  452.     InterSegListStruct *PSLTemp;
  453.  
  454. #ifdef DEBUG3
  455.     printf("Enter LoopsFromInterList\n");
  456. #endif /* DEBUG3 */
  457.  
  458.     *PClosed = (*POpen) = NULL;
  459.  
  460.     if ((PSeg = (InterSegmentStruct *) Pl -> PAux) == NULL) {
  461.     return;
  462.     }
  463.     else {
  464.     /* Do intersect - find if there are closed loops and/or open ones:   */
  465.     Pl -> PAux = NULL;
  466.     while (TRUE) {
  467.         /* First, we look for open loops - scans linearly (maybe should  */
  468.         /* be done more efficiently) for segment on boundary and start   */
  469.         /* build chain from it (up to the other end, on the boundary).   */
  470.         PSegHead = PSeg;
  471.         while (PSegHead) {
  472.         if (PSegHead -> V[0] != NULL || PSegHead -> V[1] != NULL) {
  473.             /* Found one - make it in correct order, del. from list: */
  474.             if (PSegHead -> V[0] == NULL) SwapPointInterList(PSegHead);
  475.             DeleteSegInterList(PSegHead, &PSeg);
  476.             break;
  477.         }
  478.         else PSegHead = PSegHead -> Pnext;
  479.         }
  480.         if (PSegHead == NULL) break;    /* No more open segments here... */
  481.  
  482.         PSegTemp = PSegHead;
  483.         while (PSegTemp -> V[1] == NULL) {
  484.         /* Search for matching to the second boundary end: */
  485.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  486.         PSegTemp -> Pnext = PSegNewTemp;
  487.         PSegTemp = PSegNewTemp;
  488.         }
  489.         PSegTemp -> Pnext = NULL;
  490.         PSLTemp = (InterSegListStruct *)
  491.         MyMalloc(sizeof(InterSegListStruct), OTHER_TYPE);
  492.         PSLTemp -> PISeg = PSegHead;
  493.         PSLTemp -> Pnext = (*POpen);
  494.         *POpen = PSLTemp;
  495.     }
  496.  
  497.     while (TRUE) {
  498.         /* Now, we look for closed loops - pick one segment and search   */
  499.         /* for matching until you close the loop.                 */
  500.         PSegHead = PSeg;
  501.         if (PSegHead == NULL) break;  /* No more closed segments here... */
  502.         DeleteSegInterList(PSegHead, &PSeg);
  503.  
  504.         PSegTemp = PSegHead;
  505.         while (!PT_EQ(PSegTemp -> PtSeg[1], PSegHead -> PtSeg[0])) {
  506.         /* Search for matching until we back at first point: */
  507.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  508.         PSegTemp -> Pnext = PSegNewTemp;
  509.         PSegTemp = PSegNewTemp;
  510.         }
  511.         PSegTemp -> Pnext = NULL;
  512.         PSLTemp = (InterSegListStruct *)
  513.         MyMalloc(sizeof(InterSegListStruct), OTHER_TYPE);
  514.         PSLTemp -> PISeg = PSegHead;
  515.         PSLTemp -> Pnext = (*PClosed);
  516.         *PClosed = PSLTemp;
  517.     }
  518.     }
  519.  
  520. #ifdef DEBUG3
  521.     printf("Exit LoopsFromInterList\n");
  522. #endif /* DEBUG3 */
  523. }
  524.  
  525. /*****************************************************************************
  526. * Swap the two points in the InterSegmentStruct (modifies PtSeg & V entries) *
  527. *****************************************************************************/
  528. static void SwapPointInterList(InterSegmentStruct *PSeg)
  529. {
  530.     PointType Pt;
  531.     VertexStruct *V;
  532.  
  533.     PT_COPY(Pt,              PSeg -> PtSeg[0]);
  534.     PT_COPY(PSeg -> PtSeg[0], PSeg -> PtSeg[1]);
  535.     PT_COPY(PSeg -> PtSeg[1], Pt);
  536.  
  537.     V         = PSeg -> V[0];
  538.     PSeg -> V[0] = PSeg -> V[1];
  539.     PSeg -> V[1] = V;
  540. }
  541.  
  542. /*****************************************************************************
  543. * Delete one InterSegment PSeg, from InterSegmentList PSegList:             *
  544. *****************************************************************************/
  545. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  546.                         InterSegmentStruct **PSegList)
  547. {
  548.     InterSegmentStruct *PSegTemp;
  549.  
  550.     if (*PSegList == PSeg) { /* Its the first one - simply advance list ptr: */
  551.     *PSegList = (*PSegList) -> Pnext;
  552.     }
  553.     else {
  554.     PSegTemp = (*PSegList);
  555.     while (PSegTemp -> Pnext != NULL && PSegTemp -> Pnext != PSeg)
  556.         PSegTemp = PSegTemp -> Pnext;
  557.     if (PSegTemp -> Pnext == PSeg)
  558.         PSegTemp -> Pnext = PSegTemp -> Pnext -> Pnext;
  559.     else FatalError("DeleteSegInterList: element to delete not found\n");
  560.     }
  561. }
  562.  
  563. /*****************************************************************************
  564. * Search for matching point, in the given inter segment list. Returns the    *
  565. * pointer to that element after swapping its points if needed (the match     *
  566. * must be with point 0 of new segment returned), and deleting it from list   *
  567. *****************************************************************************/
  568. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  569.                         InterSegmentStruct **PSegList)
  570. {
  571.     InterSegmentStruct *PSegTemp = (*PSegList);
  572.  
  573. #ifdef DEBUG3
  574.     printf("Enter FindMatchInterList\n");
  575. #endif /* DEBUG3 */
  576.  
  577.     while (PSegTemp != NULL) {
  578.     if (PT_EQ(Pt, PSegTemp -> PtSeg[0])) {
  579.         DeleteSegInterList(PSegTemp, PSegList);
  580.         return PSegTemp;
  581.     }
  582.     if (PT_EQ(Pt, PSegTemp -> PtSeg[1])) {
  583.         DeleteSegInterList(PSegTemp, PSegList);
  584.         SwapPointInterList(PSegTemp);
  585.         return PSegTemp;
  586.     }
  587.     PSegTemp = PSegTemp -> Pnext;
  588.     }
  589.  
  590.     FatalError("FindMatchInterList: No match found - Empty Object Result\n");
  591.     return NULL;
  592. }
  593.  
  594. /*****************************************************************************
  595. *   Sort the open loops of the given polygon to an order that can be used in *
  596. * subdividing the polygons later (see comments for ExtractPolygons).         *
  597. *   This order is such that each loops will have no other loop between its   *
  598. * end points, if we walk along the polygon in the (linked list direction)    *
  599. * perimeter from one end to the other, before it. For example:             *
  600. *             -----------------------------L3                 *
  601. *        |  ---------------L1  -----L2 |          --------L4   --L5   *
  602. *        | |               |  |     |  |         |        |   |  |    *
  603. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
  604. * In this case, any order such that L1, L2 are before L3 will do. Obviously  *
  605. * this is not a total order, and they are few correct ways to sort it.         *
  606. * Algorithm:                                     *
  607. *   For each open loop, for each of its two end, evaluate a RealType key for *
  608. * the end point P between segment P(i) .. P(i+1) to be i + t, where:         *
  609. * t is the ratio  (P - P(i)) / (P(i+1) - P(i)) . This maps the all perimeter *
  610. * of the polygon onto 0..N-1, where N is number of vertices of that polygon. *
  611. *   Sort the keys, and while they are keys in data sturcture, search and     *
  612. * remove a consecutive pair of keys assosiated with same loop, and output it *
  613. *   Note that each open loop point sequence is tested to be such that it     *
  614. * starts on the first point (first and second along vertex list) on polygon  *
  615. * perimeter, and the sequence end is on the second point, and the sequence   *
  616. * is reversed if not so. This order will make the replacement of the         *
  617. * perimeter from first to second points by the open loop much easier.         *
  618. *   This may be real problem if there are two intersection points almost     *
  619. * identical - floating point errors may cause it to loop forever. We use     *
  620. * some reordering heuristics in this case, and return fatal error if fail!   *
  621. *****************************************************************************/
  622. void SortOpenInterList(PolygonStruct *Pl, InterSegListStruct **POpen)
  623. {
  624.     int Found = TRUE, ReOrderFirst = FALSE, NumOfReOrders = 0;
  625.     RealType Key1, Key2;
  626.     InterSegmentStruct *PSeg;
  627.     InterSegListStruct *PResHead = NULL, *PResTemp, *PLSeg, *PLNext;
  628.     SortOpenStruct *PSHead = NULL, *PSTemp, *PSTemp1, *PSTemp2;
  629.  
  630. #ifdef DEBUG3
  631.     printf("Enter SortOpenInterList\n");
  632. #endif /* DEBUG3 */
  633.  
  634.     PLSeg = (*POpen);
  635.     while (PLSeg != NULL) {    /* Evaluate the two end keys and insert them: */
  636.         PSeg = PLSeg -> PISeg;
  637.     PLNext = PLSeg -> Pnext;
  638.     PLSeg -> Pnext = NULL;
  639.  
  640.     PSTemp1 = (SortOpenStruct *) MyMalloc(sizeof(SortOpenStruct),
  641.                           OTHER_TYPE);
  642.     PSTemp1 -> PLSeg = PLSeg;
  643.     /* Insert PSTemp1 into PLHead list according to position of Pt in Pl.*/
  644.     Key1 = SortOpenInsertOne(&PSHead, PSTemp1, PSeg -> PtSeg[0],
  645.                            PSeg -> V[0], Pl);
  646.  
  647.     while (PSeg -> Pnext != NULL) PSeg = PSeg -> Pnext; /* Go other end. */
  648.     PSTemp2 = (SortOpenStruct *) MyMalloc(sizeof(SortOpenStruct),
  649.                           OTHER_TYPE);
  650.     PSTemp2 -> PLSeg = PLSeg;
  651.     /* Insert PSTemp2 into PLHead list according to position of Pt in Pl.*/
  652.     Key2 = SortOpenInsertOne(&PSHead, PSTemp2, PSeg -> PtSeg[1],
  653.                            PSeg -> V[1], Pl);
  654.  
  655.     if (Key1 > Key2)          /* Reverse the open loop points order: */
  656.         SortOpenReverseLoop(PSTemp1);
  657.  
  658.     PLSeg = PLNext;
  659.     }
  660.  
  661.     while (PSHead != NULL) {    /* Search for consecutive pair of same loop. */
  662.     if (NumOfReOrders++ > 10)
  663.         FatalError("SortOpenInterList: fail to sort intersection list\n");
  664.     if (Found) NumOfReOrders = 0;
  665.  
  666.     Found = FALSE;
  667.     PSTemp = PSHead;
  668.     if (PSTemp -> PLSeg == PSTemp -> Pnext -> PLSeg) { /* First is pair! */
  669.         if (PResHead == NULL) PResHead = PResTemp = PSTemp -> PLSeg;
  670.         else {
  671.         PResTemp -> Pnext = PSTemp -> PLSeg;
  672.         PResTemp = PSTemp -> PLSeg;
  673.         }
  674.         PSHead = PSHead -> Pnext -> Pnext;         /* Skip the first pair. */
  675.         MyFree((char *) PSTemp -> Pnext, OTHER_TYPE);
  676.         MyFree((char *) PSTemp, OTHER_TYPE);
  677.         Found = TRUE;
  678.         continue;
  679.     }
  680.     /* If we are here, first pair is not of same loop - search on: */
  681.     while (PSTemp -> Pnext -> Pnext != NULL) {
  682.         if (PSTemp -> Pnext -> PLSeg == PSTemp -> Pnext -> Pnext -> PLSeg) {
  683.         if (PResHead == NULL) PResHead = PResTemp =
  684.             PSTemp -> Pnext -> PLSeg;
  685.         else {
  686.             PResTemp -> Pnext = PSTemp -> Pnext -> PLSeg;
  687.             PResTemp = PSTemp -> Pnext -> PLSeg;
  688.         }
  689.         PSTemp2 = PSTemp -> Pnext;
  690.         PSTemp -> Pnext = PSTemp -> Pnext -> Pnext -> Pnext;
  691.         MyFree((char *) PSTemp2 -> Pnext, OTHER_TYPE);
  692.         MyFree((char *) PSTemp2, OTHER_TYPE);
  693.         Found = TRUE;
  694.         break;
  695.         }
  696.         PSTemp = PSTemp -> Pnext;
  697.     }
  698.     /* The only way we might found nothing is in floating point round */
  699.     /* off error - two curve ends has almost the same Key...      */
  700.     /* Note, obviously, that there are at list 4 entries in list.     */
  701.     if (!Found) {
  702.         if (!ReOrderFirst &&
  703.         APX_EQ(PSHead -> Pnext -> Key, PSHead -> Key)) {
  704.         ReOrderFirst = TRUE;
  705.         PSTemp1 = PSHead -> Pnext;
  706.         PSHead -> Pnext = PSTemp1 -> Pnext;
  707.         PSTemp1 -> Pnext = PSHead;
  708.         PSHead = PSTemp1;
  709.         continue;
  710.         }
  711.         else ReOrderFirst = FALSE;
  712.         PSTemp = PSHead;
  713.         while (PSTemp -> Pnext -> Pnext != NULL) {
  714.         if (APX_EQ(PSTemp -> Pnext -> Key,
  715.                PSTemp -> Pnext -> Pnext -> Key)) {
  716.             PSTemp1 = PSTemp -> Pnext;
  717.             PSTemp2 = PSTemp1 -> Pnext;
  718.             PSTemp1 -> Pnext = PSTemp2 -> Pnext;
  719.             PSTemp2 -> Pnext = PSTemp1;
  720.             PSTemp -> Pnext = PSTemp2;
  721.             break;
  722.         }
  723.         PSTemp = PSTemp -> Pnext;
  724.         }
  725.     }
  726.     }
  727.  
  728.     *POpen = PResHead;
  729.  
  730. #ifdef DEBUG3
  731.     printf("Exit SortOpenInterList\n");
  732. #endif /* DEBUG3 */
  733. }
  734.  
  735. /*****************************************************************************
  736. *   Reverse the order of the open loop pointed by PSHead.             *
  737. *****************************************************************************/
  738. static void SortOpenReverseLoop(SortOpenStruct *PSHead)
  739. {
  740.     InterSegmentStruct *PINewHead = NULL, *PIHead, *PITemp;
  741.  
  742.     PIHead = PSHead -> PLSeg -> PISeg;
  743.  
  744.     while (PIHead != NULL) {
  745.     PITemp = PIHead;
  746.     PIHead = PIHead -> Pnext;
  747.     SwapPointInterList(PITemp);
  748.     PITemp -> Pnext = PINewHead;
  749.     PINewHead = PITemp;
  750.     }
  751.  
  752.     PSHead -> PLSeg -> PISeg = PINewHead;
  753. }
  754.  
  755. /*****************************************************************************
  756. *   Insert new loop PSTemp, defines key by Pt and V (V defines the vertex    *
  757. * and P is the points on it), into (decreasing) ordered list PSHead.         *
  758. *****************************************************************************/
  759. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  760.        SortOpenStruct *PSTemp, PointType Pt, VertexStruct *V, PolygonStruct *Pl)
  761. {
  762.     int i = 0;
  763.     RealType Key;
  764.     PointType Pt1, Pt2;
  765.     VertexStruct *VTemp = Pl -> V;
  766.     SortOpenStruct *PSTail;
  767.  
  768.     PSTemp -> Pnext = NULL;
  769.  
  770.     while (VTemp != V && VTemp != NULL) {
  771.     i++;
  772.     VTemp = VTemp -> Pnext;
  773.     }
  774.     if (VTemp == NULL) FatalError("SortOpenInsertOne: fail to find vertex\n");
  775.  
  776.     PT_SUB(Pt1, V -> Pnext -> Pt, V -> Pt);
  777.     PT_SUB(Pt2, Pt, V -> Pt);
  778.     Key = PSTemp -> Key = i + PT_LENGTH(Pt2) / PT_LENGTH(Pt1);
  779.  
  780.     /* Now insert PSTemp into the ordered list: */
  781.     if (*PSHead == NULL) {
  782.     *PSHead = PSTemp;
  783.     return Key;
  784.     }
  785.     if (PSTemp -> Key > (*PSHead) -> Key) {         /* Insert as first? */
  786.     PSTemp -> Pnext = (*PSHead);
  787.     *PSHead = PSTemp;
  788.     return Key;
  789.     }
  790.     PSTail = (*PSHead);
  791.     while (PSTail -> Pnext != NULL && PSTemp -> Key < PSTail -> Pnext -> Key)
  792.     PSTail = PSTail -> Pnext;
  793.     PSTemp -> Pnext = PSTail -> Pnext;
  794.     PSTail -> Pnext = PSTemp;
  795.  
  796.     return Key;
  797. }
  798.  
  799. /*****************************************************************************
  800. *   Create a new vertex list, in reverse order. The original is not modified.*
  801. *****************************************************************************/
  802. struct VertexStruct *GenReverseVrtxList(VertexStruct *VIn)
  803. {
  804.     VertexStruct *VOutHead, *VOut;
  805.  
  806.     VOutHead = AllocVertex(0, 0, NULL, NULL);
  807.  
  808.     PT_COPY(VOutHead -> Pt, VIn -> Pt);
  809.     VIn = VIn -> Pnext;
  810.  
  811.     while (VIn != NULL) {
  812.     VOut = AllocVertex(0, 0, NULL, NULL);
  813.     PT_COPY(VOut -> Pt, VIn -> Pt);
  814.  
  815.     VOut -> Pnext = VOutHead;         /* Chain them in reverse order. */
  816.     VOutHead = VOut;
  817.  
  818.     VIn = VIn -> Pnext;
  819.     }
  820.  
  821.     return VOutHead;
  822. }
  823.  
  824. #ifdef DEBUG2
  825.  
  826. /*****************************************************************************
  827. *   Print the content of the given polygon, to standard output.             *
  828. *****************************************************************************/
  829. static void PrintVrtxList(VertexStruct *V)
  830. {
  831.     struct VertexStruct *VHead = V;
  832.  
  833.     do {
  834.     printf("    %12lf %12lf %12lf\n", V -> Pt[0], V -> Pt[1], V -> Pt[2]);
  835.     V = V -> Pnext;
  836.     }
  837.     while (V!= NULL && V != VHead);
  838. }
  839.  
  840. /*****************************************************************************
  841. *   Print the content of the given InterSegment list, to standard output.    *
  842. *****************************************************************************/
  843. static void PrintInterList(InterSegmentStruct *PInt)
  844. {
  845.     printf("INTER SEGMENT LIST:\n");
  846.  
  847.     if (PInt) printf("Entry vertex pointer %p\n", PInt -> V[0]);
  848.     while (PInt) {
  849.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  850.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  851. #ifdef __MSDOS__
  852.         FP_SEG(PInt->V[0]),
  853. #else
  854.         PInt->V[0],
  855. #endif /* __MSDOS__ */
  856.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  857. #ifdef __MSDOS__
  858.         FP_SEG(PInt->V[1]));
  859. #else
  860.         PInt->V[1]);
  861. #endif /* __MSDOS__ */
  862.     if (PInt -> Pnext == NULL)
  863.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  864.  
  865.     PInt = PInt -> Pnext;
  866.     }
  867. }
  868.  
  869. #endif /* DEBUG2 */
  870.