/***************************************************************************** * "Irit" - the 3d (not only polygonal) solid modeller. * * * * Written by: Gershon Elber Ver 0.2, Mar. 1990 * ****************************************************************************** * (C) Gershon Elber, Technion, Israel Institute of Technology * ****************************************************************************** * Module to handle the low level boolean operations. The routines in this * * module should be accessed from "bool-hi.c" module only. * * Note the polygons of the two given objects may not be convex, and must * * be subdivided into convex ones in the boolean upper level routines (module * * bool-hi.c). All the routines of this module expects objects with convex * * polygons only although they might return objects with non convex polygons, * * but marked as so (via polygons CONVEX tags - see IPPolygonStruct def.)! * * Because Bool-low.c module was too big, it was subdivided to two: * * Bool1Low.c - mainly handles the intersecting polyline between the oprnds. * * Bool2Low.c - mainly handles the polygon extraction from operands given the * * polyline of intersection and the adjacencies (see ADJACNCY.C) * *****************************************************************************/ /* #define DEBUG If defined, return intersection POLYLINE object. */ /* #define DEBUG2 If defined, defines some printing routines. */ /* #define DEBUG3 Print messages to entry/exit from routines. */ #include #include #include #include #include "irit_sm.h" #include "allocate.h" #include "bool_loc.h" #include "convex.h" #include "geomat3d.h" #include "intrnrml.h" static IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead); static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB); static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl, InterSegListStruct *OLoop, int AinB); static void ClosedLoopsToPolys(InterSegListStruct *PClosed, IPPolygonStruct *Pl); static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn); static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt); static int CombineClosedLoops(IPPolygonStruct *Pl, InterSegListStruct *PClosed, int AinB); static void PushAdjOnStack(IPPolygonStruct *Pl, IPPolygonStruct *AdjStack[], int *StackPointer); static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2); #ifdef DEBUG void BoolPrintVrtxList(IPVertexStruct *V); void BoolPrintInterList(InterSegmentStruct *PInt); #endif /* DEBUG */ /***************************************************************************** * DESCRIPTION: * * Test on which side of polygon Pl, given Point V is, and according to * * the requirement (AinB) returns TRUE/FALSE. * * If test on V fails, we tries the next one V -> Pnext until success... * * * * PARAMETERS: * * V: Is V inside/outside polygon Pl? * * Pl: The polygon to test for inclusion. * * AinB: Either test for inclusion (TRUE) or exclusion (FALSE). * * * * RETURN VALUE: * * int: TRUE if V relates to PL as AinB, FALSE otherwise. * *****************************************************************************/ static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB) { int In; RealType Distance; IPVertexStruct *VHead = V; do { Distance = Pl -> Plane[0] * V -> Coord[0] + Pl -> Plane[1] * V -> Coord[1] + Pl -> Plane[2] * V -> Coord[2] + Pl -> Plane[3]; In = Distance > 0.0; V = V -> Pnext; } while (ABS(Distance) < BOOL_IRIT_EPS && V != NULL && V != VHead); if (ABS(Distance) < BOOL_IRIT_EPS) IritFatalError("TestAInB: Failed to find non coplanar point."); return (In && AinB) || (!In && !AinB); /* I wish I had logical XOR ... */ } /***************************************************************************** * DESCRIPTION: * * Converts an intersection loop into an open vertex list. * * * * PARAMETERS: * * PIHead: Intersection list to be converted. * * * * RETURN VALUE: * * IPVertexStruct *: The same loop as a vertex list. * * * * KEYWORDS: * * InterLoopToVrtxList * *****************************************************************************/ static IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead) { IPVertexStruct *VHead, *V; VHead = V = IPAllocVertex(0, NULL, NULL); PT_COPY(VHead -> Coord, PIHead -> PtSeg[0]); while (PIHead != NULL) { V -> Pnext = IPAllocVertex(0, NULL, NULL); V = V -> Pnext; PT_COPY(V -> Coord, PIHead -> PtSeg[1]); PIHead = PIHead -> Pnext; } V -> Pnext = NULL; return VHead; } /***************************************************************************** * DESCRIPTION: * * Clip an open loop from a polygon: * * 1. Clip the section (S) of the polygon between the two end points of the * * loop end points and replace it by the loop itself. * * 2. If the polygon formed from S and the loop should be in the output * * (as tested by AinB) returns that polygon. Otherwise returns NULL. * * The open loop itself (excluding the header OLoop) is freed. * * Note it is assumed (ordered by the sorting routines above) that the open * * loop starts from the second end back to first end: * * * * L1-----------------------L2 * * | | * * |L0 |L3 * * *---------------*-------+----*-------------*----+-----------* * * P0 P1 P2 P3 P0 * * * * PARAMETERS: * * Pl: To clip against the given open loop. * * OLoop: The given open loop (must start/end on Pl's boundary). * * AinB: TRUE for inclusion, FALSE for exclusion. * * * * RETURN VALUE: * * IPPolygonStruct: The newly created clipped polygon if AinB, or NULL * * otherwise. * *****************************************************************************/ static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl, InterSegListStruct *OLoop, int AinB) { int GenClipPoly; /* TRUE if needs to form polygon from S & OLoop. */ IPVertexStruct *VStart, *VEnd, *VEnd1, /* Corresponds to L0 and L3... */ *ClipPoly, /* The clipped element from polygon. */ *PLoop, /* The loop itself as vertex list. */ *PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2, *PRevLoop = NULL; InterSegmentStruct *PISeg, *PItemp; IPPolygonStruct *ClipPl; #ifdef DEBUG3 printf("Enter ClipOpenLoopFromPoly\n"); #endif /* DEBUG3 */ PISeg = OLoop -> PISeg; VStart = PISeg -> V[0]; while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext; VEnd = PISeg -> V[1]; if (VStart == NULL || VEnd == NULL) IritFatalError("ClipOpenLoopFromPoly: None open loop"); VEnd1 = VEnd; /* Find the pointer thats points on VEnd. */ while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext; PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/ PLoopEnd = PLoop; /* Prepare pointer on last vertex. */ while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext; PLoopEnd1 = PLoop; while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext; if (VStart != VEnd) { /* Now we test if we need to create a polygon formed from S & open */ /* loop by testing on which side of the polygon that caused */ /* intersection L0L1, point P2 is, and compare with requirement AinB.*/ GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB); /* Keep the clipped VertexList P2, P3 & substitute with open loop: */ /* Note we must keep vertex VEnd in the polygon as another InterSeg. */ /* may point on it, so we replace InterSeg point (L3) by (P3) and */ /* leave VEnd intact. */ Ptemp1 = VEnd -> Pnext; /* Save that pointer temporary. */ VEnd -> Pnext = NULL; /* Close the clipped vertex list. */ PT_SWAP(VEnd -> Coord, PLoopEnd -> Coord); PT_SWAP(VEnd -> Normal, PLoopEnd -> Normal); VEnd1 -> Pnext = PLoopEnd; PLoopEnd1 -> Pnext = VEnd; PLoopEnd -> Tags = VEnd -> Tags; Ptemp2 = VEnd; VEnd = PLoopEnd; PLoopEnd = Ptemp2; ClipPoly = VStart -> Pnext; /* New ClipPoly is isolated (Open loop of P2, P3 only). Save */ /* reversed list of open loop if we need to form an S/OLoop polygon, */ /* otherwise free ClipPoly. Chain the OLoop instead of S. */ if (GenClipPoly) PRevLoop = GenReverseVrtxList(PLoop); else IPFreeVertexList(ClipPoly); VStart -> Pnext = PLoop; /* Chain the OLoop instead of S. */ PLoopEnd -> Pnext = Ptemp1; } else { /* VStart == VEnd */ /* Now we test if we need to create a polygon formed from S & open */ /* loop by testing on which side of the polygon that caused */ /* intersection L0L1, point L3 is, and compare with requirement AinB.*/ GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB); /* In this case the clipped part is empty, so its simpler: */ ClipPoly = NULL; /* Save reversed list of open loop if we need to form an S/OLoop */ /* polygon. Chain the OLoop instead of S. */ if (GenClipPoly) PRevLoop = GenReverseVrtxList(PLoop); PLoopEnd -> Pnext = VEnd -> Pnext; PLoopEnd -> Tags = VEnd -> Tags; VStart -> Pnext = PLoop; /* Chain the OLoop instead of S. */ } /* Time to free the InterSegment list pointed by OLoop: */ PISeg = OLoop -> PISeg; while (PISeg != NULL) { PItemp = PISeg; PISeg = PISeg -> Pnext; IritFree((VoidPtr) PItemp); } OLoop -> PISeg = NULL; /* To be on the safe side... */ /* There is a chance that Pl -> PVertex will point on vertex in clipped */ /* part so we update it to point on VStart, which for sure is in polygon.*/ Pl -> PVertex = VStart; if (GenClipPoly) { /* Generate the polygon from ClipPoly & PRevLoop: */ PLoopEnd = PRevLoop; while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext; if (ClipPoly == NULL) { PLoopEnd -> Pnext = PRevLoop; /* Close that loop and return it. */ ClipPl = IPAllocPolygon((ByteType) (IS_COPLANAR_POLY(Pl)), PRevLoop, NULL); PLANE_COPY(ClipPl -> Plane, Pl -> Plane); IP_RST_CONVEX_POLY(ClipPl); /* May be not convex now. */ return ClipPl; } PLoopEnd -> Pnext = ClipPoly; PLoopEnd -> Tags = VStart -> Tags; Ptemp1 = ClipPoly; while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext; Ptemp1 -> Pnext = PRevLoop; ClipPl = IPAllocPolygon((ByteType) (IS_COPLANAR_POLY(Pl)), ClipPoly, NULL); PLANE_COPY(ClipPl -> Plane, Pl -> Plane); IP_RST_CONVEX_POLY(ClipPl); /* May be not convex now. */ return ClipPl; } else return NULL; } /***************************************************************************** * DESCRIPTION: * * Creates a new vertex list, in reverse order. The original list is not * * modified. * * * * PARAMETERS: * * VIn: To create a reversed list for. * * * * RETURN VALUE: * * IPVertexStruct *: The newly created reversed list. * *****************************************************************************/ static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn) { IPVertexStruct *VOutHead, *VOut; VOutHead = IPAllocVertex(0, NULL, NULL); PT_COPY(VOutHead -> Coord, VIn -> Coord); VIn = VIn -> Pnext; while (VIn != NULL) { VOut = IPAllocVertex(0, NULL, NULL); PT_COPY(VOut -> Coord, VIn -> Coord); PT_COPY(VOut -> Normal, VIn -> Normal); VOut -> Pnext = VOutHead; /* Chain them in reverse order. */ VOutHead = VOut; VIn = VIn -> Pnext; } return VOutHead; } /***************************************************************************** * DESCRIPTION: * * Finds the intersection of the ray fired from Pt to +X direction with the * * given polygon. Note Pt MUST be in the polygon. Two vertices equal to * * ray/polygon intersection point are added to polygon vertex list, and a * * pointer to the first one is also returned. This routine is exclusively * * used by the CombineClosedLoops below. * * The polygon is NOT assumed to be convex and we look for the minimum X * * intersection. The polygon might not be convex as a result of combinning * * some other closed loop before we got to do this test. * * * * PARAMETERS: * * Pl: The polygon to compute the ray intersection with. * * Pt: The origin of the ray point. * * * * RETURN VALUE: * * IPVertexStruct *: The added vertex on Pl where the intersection with * * the ray occured. * *****************************************************************************/ static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt) { int OnVertex = FALSE; RealType X, MinX = IRIT_INFNTY; IPVertexStruct *V, *Vnext, *VMinX = NULL; V = Pl -> PVertex; do { Vnext = V -> Pnext; /* A polygon edge might intersect the ray iff one of the following: */ /* 1. The first vertex is exactly on the ray Y level. (if this is */ /* true for the second edge, it will be detected next iteration). */ /* 2. The first vertex is below ray Y level, and second is above. */ /* 3. The first vertex is above ray Y level, and second is below. */ if (BOOL_APX_EQ(V -> Coord[1], Pt[1])) { /* Case 1 above. */ if (MinX > V -> Coord[0] && Pt[0] < V -> Coord[0]) { OnVertex = TRUE; MinX = V -> Coord[0]; VMinX = V; } } else if ((V -> Coord[1] < Pt[1] && Vnext -> Coord[1] > Pt[1]) || /* Case 2. */ (V -> Coord[1] > Pt[1] && Vnext -> Coord[1] < Pt[1])) { /* Case 3. */ X = ((Vnext -> Coord[1] - Pt[1]) * V -> Coord[0] + (Pt[1] - V -> Coord[1]) * Vnext -> Coord[0]) / (Vnext -> Coord[1] - V -> Coord[1]); if (MinX > X && Pt[0] < X) { OnVertex = FALSE; MinX = X; VMinX = V; } } V = Vnext; } while (V != NULL && V != Pl -> PVertex); if ((V = VMinX) == NULL) IritFatalError("CutPolygonAtRay: fail to find intersection"); /* Now that we have the intersection point - create two new vertices */ /* (one if OnVertex), insert them (it) after V and return the first. */ if (OnVertex) { V -> Pnext = IPAllocVertex(V -> Tags, NULL, V -> Pnext); PT_COPY(V -> Pnext -> Coord, V -> Coord); PT_CLEAR(V -> Pnext -> Normal); V -> Tags = 0; } else { V -> Pnext = IPAllocVertex(V -> Tags, NULL, V -> Pnext); Vnext = V -> Pnext; Vnext -> Coord[0] = MinX; /* X - as intersection point found. */ Vnext -> Coord[1] = Pt[1]; /* Y - must be as ray Y level. */ Vnext -> Coord[2] = V -> Coord[2];/* Z - all polys has same Z value. */ V -> Pnext = IPAllocVertex(0, NULL, V -> Pnext); V = V -> Pnext; PT_COPY(V -> Coord, Vnext -> Coord); PT_CLEAR(V -> Normal); } return V; } /***************************************************************************** * DESCRIPTION: * * Converts the given closed loop list to polygons, and returns them. The * * original given polygon's vertex list is freed, and the first loop is * * substituted instead. * * * * PARAMETERS: * * PClosed: To substitute into polygon Pl. * * Pl: Polygon whose vertices are to be replaced by PClosed loops. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void ClosedLoopsToPolys(InterSegListStruct *PClosed, IPPolygonStruct *Pl) { int LoopNum = 0; IPVertexStruct *V, *VHead; InterSegmentStruct *PISeg, *PItemp; InterSegListStruct *PClosedTemp; IPFreeVertexList(Pl -> PVertex); SET_INOUTPUT_POLY(Pl); /* Mark the polygon as in output. */ while (PClosed != NULL) { /* Convert the InterList to vertex list and free the first: */ V = VHead = InterLoopToVrtxList(PClosed -> PISeg); if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL) IritFatalError("ClosedLoopsToPolys: Closed loop with fewer than 3 vertices"); PISeg = PClosed -> PISeg; /* Time to free the InterSegmentList: */ while (PISeg != NULL) { PItemp = PISeg; PISeg = PISeg -> Pnext; IritFree((VoidPtr) PItemp); } while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt. */ IPFreeVertex(V -> Pnext); /* and free - same as first. */ V -> Pnext = VHead; /* Make vertex list circular. */ if (LoopNum++) { Pl -> Pnext = IPAllocPolygon((ByteType) (IS_COPLANAR_POLY(Pl)), VHead, Pl -> Pnext); PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane); } else { Pl -> PVertex = VHead; } PClosedTemp = PClosed; PClosed = PClosed -> Pnext; IritFree((VoidPtr) PClosedTemp); } } /***************************************************************************** * DESCRIPTION: * * This routines cuts the given polygon into its interior closed loops by * * adding an edge from the polygon boundary to each of its closed loops. * * For example: * * * * +-----------------------+ +-----------------------+ * * | | | | * * | / \ / \ | | / \________ / \ | * * | \ / | | | | \ / | |_____| * * | _ \ / | --> | _ \ / | * * | / \_ | --> | / \_ | * * | | | | | | |_____________| * * | \__/ | | \__/ | * * | | | | * * +-----------------------+ +-----------------------+ * * * * Algorithm: * * 1. Transform the polygon and the closed loops to a plane parallel to XY * * plane (Z = Const plane). * * 2. For each loop find its MaxX while keeping the information on the * * vertex on that extremum. * * 3. For the loop with the biggest MaxX: * * 3.1. Use that extremum vertex (which must be non concave corner) to * * test if loop is in the reverse direction the polygon itself is, * * and reverse it if not. * * 3.2. Fire a ray from the extremum vertex, to the +X direction outside * * of the loop till it intersect the polygon, break the polygon at * * that point and add two edges to beginning of loop from breaking * * point and from end of loop to breaking point (beginning/end point * * of loop is the extremum vertex point). * * 4. Repeat step 3, with all loops. * * 5. Transfrom the new polygon back (using the inverse matrix of step 1) * * to its original orientation. * * * * PARAMETERS: * * Pl: Polygon to comine with the given closed loops, in place. * * PClosed: Closed loops in polygon Pl. * * AinB: Do we want inclusion or exclusion? * * * * RETURN VALUE: * * int: TRUE iff the original polygon boundary is in output. * *****************************************************************************/ static int CombineClosedLoops(IPPolygonStruct *Pl, InterSegListStruct *PClosed, int AinB) { RealType MaxX; PointType V1, V2, Normal, PlNormal; MatrixType RotMat; IPVertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct; InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast, *PClosedMaxXLast = NULL; InterSegmentStruct *PISeg, *PItemp, *PISegMaxX; /* Stage 1 - Transform the vertices to a plane parallel to XY plane: */ GenRotateMatrix(RotMat, Pl -> Plane); V = VHead = Pl -> PVertex; do { /* Transform the polygon itself. */ MatMultVecby4by4(V -> Coord, V -> Coord, RotMat); V = V -> Pnext; } while (V != NULL && V != VHead); PClosedTemp = PClosed; while (PClosedTemp != NULL) { /* And transform the loops also. */ PISeg = PClosed -> PISeg; while (PISeg != NULL) { MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat); MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat); PISeg = PISeg -> Pnext; } PClosedTemp = PClosedTemp -> Pnext; } if (!MatInverseMatrix(RotMat, RotMat)) /* Find the inverse matrix. */ IritFatalError("CombineClosedLoops: Inverse matrix does not exists"); /* Evalaute the normal to the polygon (which must be convex!). Note we */ /* cannt simply use the Plane normal as the polygon was transformed. */ V = Pl -> PVertex; do { Vnext = V -> Pnext; PT_SUB(V1, Vnext -> Coord, V -> Coord); PT_SUB(V2, Vnext -> Pnext -> Coord, Vnext -> Coord); GMVecCrossProd(PlNormal, V1, V2); V = Vnext; } while (PT_LENGTH(PlNormal) < BOOL_IRIT_EPS); PClosedTemp = PClosed; while (PClosedTemp != NULL) { /* Stage 2 - find MaxX extremum value of given loop, test the loop */ /* direction, and reverse it if wrong. Note we convert the loop */ /* given as InterSegListStruct list into IPVertexStruct list first. */ PISegMaxX = PISeg = PClosedTemp -> PISeg; MaxX = PISeg -> PtSeg[0][0]; /* Get first vertex X val. */ PISeg = PISeg -> Pnext; while (PISeg) { if (PISeg -> PtSeg[0][0] > MaxX) { MaxX = PISeg -> PtSeg[0][0]; PISegMaxX = PISeg; } PISeg = PISeg -> Pnext; } PClosedTemp -> PISegMaxX = PISegMaxX; PClosedTemp = PClosedTemp -> Pnext; } /* Stage 3/4 - find the loop with biggest MaxX and combine it with the */ /* polygon itself. Do it for all closed loops, in list: */ while (PClosed != NULL) { /* Find the one with maximum MaxX, and delete it from PClosed list. */ PClosedLast = PClosedMaxX = PClosedTemp = PClosed; MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0]; while (PClosedTemp != NULL) { if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) { PClosedMaxX = PClosedTemp; PClosedMaxXLast = PClosedLast; } PClosedLast = PClosedTemp; PClosedTemp = PClosedTemp -> Pnext; } if (PClosedMaxX == PClosed) PClosed = PClosed -> Pnext; /* Del. from */ else PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext; /* PClosed list.*/ /* Create a vertex list from the loop: */ V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg); if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL) IritFatalError("CombineClosedLoops: Closed loop with fewer than 3 vertices"); V = VHead; while (V -> Pnext -> Pnext != NULL) V = V -> Pnext; /* Go to last pt. */ IPFreeVertex(V -> Pnext); /* and free - same as first. */ V -> Pnext = VHead; /* Make vertex list circular. */ PISegMaxX = PClosedMaxX -> PISegMaxX; /* Now test if the vertex list should be reversed. Find the vertices */ /* which form the PISegMaxX segment, so V -> Pnext is the first */ /* vertex in PISegMaxX segment. Then the 3 vertices V , V -> Pnext */ /* (on PISegMaxX), V -> Pnext -> Pnext (on PISegMaxX), must form */ /* convex corner which we use to test if loop needs to be reversed: */ while (!BOOL_PT_APX_EQ(V -> Pnext -> Coord, PISegMaxX -> PtSeg[0])) V = V -> Pnext; VMaxX = V -> Pnext; /* Prepare in point in REAL position. */ PT_COPY(VStruct.Coord, V -> Coord); MatMultVecby4by4(VStruct.Coord, VStruct.Coord, RotMat); VStruct.Pnext = NULL; if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) { /* The Inside of the object is actually the loop itself. In that */ /* case we simply return all the loops converted into polygon. */ /* This case is simple... */ IPFreeVertexList(VHead); /* Free loop vertex list. */ PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */ PClosedTemp = PClosed = PClosedMaxX; while (PClosedTemp != NULL) { /* Transform the loops back. */ PISeg = PClosed -> PISeg; while (PISeg != NULL) { MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat); MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat); PISeg = PISeg -> Pnext; } PClosedTemp = PClosedTemp -> Pnext; } ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/ return FALSE; /* Boundary is NOT part of object result. */ } PT_SUB(V1, VMaxX -> Coord, V -> Coord); PT_SUB(V2, VMaxX -> Pnext -> Coord, VMaxX -> Coord); GMVecCrossProd(Normal, V1, V2); if (DOT_PROD(Normal, PlNormal) > 0) { /* Need to reverse list. */ Vprev = VHead; V = Vprev -> Pnext; Vnext = V -> Pnext; do { V -> Pnext = Vprev;/* Reverse to point on prev instead next. */ Vprev = V; V = Vnext; Vnext = V -> Pnext; } while (Vprev != VHead); } PISeg = PClosedMaxX -> PISeg; /* Time to free the InterSegmentList: */ while (PISeg != NULL) { PItemp = PISeg; PISeg = PISeg -> Pnext; IritFree((VoidPtr) PItemp); } IritFree((VoidPtr) PClosedMaxX); /* O.k. lets fire a ray from VMaxX to +X direction and see where it */ /* intersects the polygon. The routine CutPolygonAtRay will add two */ /* vertices at the ray intersection into polygon vertex list and */ /* return a pointer to first one, so we can chain our loop directly */ /* between these two new vertices. */ V = CutPolygonAtRay(Pl, VMaxX -> Coord); Vnext = V -> Pnext; /* Introduce a copy of VMaxX and successor to VMaxX: */ VMaxX -> Pnext = IPAllocVertex(VMaxX -> Tags, NULL, VMaxX -> Pnext); PT_COPY(VMaxX -> Pnext -> Coord, VMaxX -> Coord); PT_CLEAR(VMaxX -> Pnext -> Normal); V -> Pnext = VMaxX -> Pnext; IP_SET_INTERNAL_VRTX(V); VMaxX -> Pnext = Vnext; IP_SET_INTERNAL_VRTX(VMaxX); } /* Stage 5 - Time to rotate polygon back to its original position. */ V = VHead = Pl -> PVertex; do { MatMultVecby4by4(V -> Coord, V -> Coord, RotMat); V = V -> Pnext; } while (V != NULL && V != VHead); SET_INOUTPUT_POLY(Pl); /* Mark the polygon as in output. */ IP_RST_CONVEX_POLY(Pl); /* This polygon is not convex any more. */ return TRUE; } /***************************************************************************** * DESCRIPTION: * * Pushes on the adjacency stack, all adjacent polygons which are complete * * (no intersection) and are adjacent to complete edges (originated from * * input polygons) of the given polygon. * * * * PARAMETERS: * * Pl: To be added to the adjacency stack. * * AdjStack: The adjacency stack to put Pl in. * * StackPointer: Where exactly in the stack Pl is going to be pushed? * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PushAdjOnStack(IPPolygonStruct *Pl, IPPolygonStruct *AdjStack[], int *StackPointer) { IPVertexStruct *V = Pl -> PVertex; do { if (V -> PAdj != NULL && BoolVerifyShareEdge(V, V -> PAdj)) AdjStack[++*StackPointer] = V -> PAdj; if (*StackPointer >= ADJ_STACK_SIZE) { IritFatalError("Adjacency stack overflow, object too big"); } V = V -> Pnext; } while (V != Pl -> PVertex); } /***************************************************************************** * DESCRIPTION: M * Test if the edge [V - V->Pnext] is indeed on the boundary of Pl. M * * * PARAMETERS: M * V: First vertex of edge to verify. M * Pl: Polygon to verify the edge shares its boundary. M * * * RETURN VALUE: M * int: TRUE if [V - V->Pnext] is on Pl's boundary, FALSE otherwise. M * * * KEYWORDS: M * BoolVerifyShareEdge, Booleans M *****************************************************************************/ int BoolVerifyShareEdge(IPVertexStruct *V, IPPolygonStruct *Pl) { IPVertexStruct *Vl = Pl -> PVertex; VectorType Dir; int InterNum = 0; RealType InterVal[2], Dist; PT_SUB(Dir, V -> Pnext -> Coord, V -> Coord); if ((Dist = PT_LENGTH(Dir)) == 0) Dist = IRIT_UEPS; do { PointType Ptemp; CGPointFromPointLine(Vl -> Coord, V -> Coord, Dir, Ptemp); if (CGDistPointPoint(Vl -> Coord, Ptemp) < IRIT_UEPS) { VectorType Dir2; RealType Dist2 = CGDistPointPoint(V -> Coord, Ptemp); PT_SUB(Dir2, Ptemp, V -> Coord); Dist2 = PT_LENGTH(Dir2); InterVal[InterNum] = Dist2 / Dist; if (DOT_PROD(Dir2, Dir) < 0) InterVal[InterNum] = -InterVal[InterNum]; if (++InterNum == 2) { if (MIN(InterVal[0], InterVal[1]) < 1.0 && MAX(InterVal[0], InterVal[1]) > 0.0) return TRUE; /* Save the second intersection as first one for next time. */ InterVal[0] = InterVal[1]; InterNum = 1; } } else InterNum = 0; Vl = Vl -> Pnext; } while (Vl != Pl -> PVertex); return FALSE; } /***************************************************************************** * DESCRIPTION: * * Chains two polygonal lists into one. For fast processing it is prefered * * that the first one is shorter. Returns pointer to chained list. * * * * PARAMETERS: * * Pl1, Pl2: The two polygonal objects to be chained together. * * * * RETURN VALUE: * * IPPolygonStruct *: The combined/chained together polygonal list. * *****************************************************************************/ static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2) { IPPolygonStruct *Ptemp; if (Pl1 == NULL) return Pl2; else if (Pl2 == NULL) return Pl1; else { Ptemp = Pl1; while (Ptemp -> Pnext != NULL) Ptemp = Ptemp -> Pnext; Ptemp -> Pnext = Pl2; return Pl1; } } /***************************************************************************** * DESCRIPTION: M * This routine coordinates all the extraction of the polygons from the M * intersecting lists. Does it in the following steps: M * 1. Mark all polygons with no intersection at all as complete polygons. M * (this is because this polygon will be totally in or out, according M * to inter-polygon adjacencies propagation...) M * Also mark them as undefined (if in output or undefined) yet. M * Uses IPPolygonStruct Tags to save these bits. M * 2. do M * 2.1. Convert the unordered segment list of each polygon to closed loops M * (if create a hole in polygon) or open (if crosses its boundary). M * 2.2. Order the open loops along the perimeter of the polygon (note M * these loops cannt intersect. For example (5 vertices polygon): M * -----------------------------L3 V * | ---------------L1 -----L2 | --------L4 --L5 V * | | | | | | | | | | V * P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 V * Note L1, L2 are enclosed in L3 loop, and that the order is M * circular. M * 2.3. "Break" the polygon at each open loop that has no enclosed loops M * in it. For example we can start at L1, L2, L4, L5 and then L3. M * "Break" means - replace the vertex chain between the two loop end M * points, with the loops itself. Depends upon the relation required M * we may need to output a new polygon form from the deleted chain M * and that loop. In addition we may form a new polygon from last M * loop and was was left from the original polygon M * For each formed polygon, for each complete edge of it (i.e. edge M * which was originally in the polygon) test the adjacent polygon M * if it is complete (as marked in 1.) and if in or undefined (marked M * undefined in 1.) is still undefined: M * 2.3.1. set it to be in. M * 2.3.2. push it on adjacency stack. M * 2.4. For each closed loop - find in which polygon (from polygons M * created in 2.3.) it is enclosed, and decompose it. M * 3. While adjacencies stack not empty do: M * 3.1. pop top polygon from stack and output it. M * 3.2. For each of its edges (which obviousely must be complete edges) M * if adjacent polygon is complete and undefined: M * 3.3.1. set it to be in. M * 3.3.2. push it on adjacency stack. M * 3.3 go back to 3. M * M * The above algorithm defines in as in output, but dont be confused with M * the required inter-object AinB (or AoutB if FALSE), which used to M * determine which side of the trimming loop should be output. M * Note this routine may return non-convex polygons (but marked as so) even M * though the input for the booleans must be convex polygons only! M * In order to keep the given object unchanged, a whole new copy off the M * polygon list is made. The polygons of the list that are not in the output M * are freed: a global list of all polygons (pointers) is used to scan them M * in the end and free the unused ones (list PolysPtr). M * * * PARAMETERS: M * PObj: Object that need to be rebuilt according to the intersection M * curves that were found, both closed and open loops. M * AinB: Type of inclusion/exclusion requested. M * * * RETURN VALUE: M * IPObjectStruct *: The newly created clipped object. M * * * KEYWORDS: M * BoolExtractPolygons, Booleans M *****************************************************************************/ IPObjectStruct *BoolExtractPolygons(IPObjectStruct *PObj, int AinB) { int NumOfPolys = 0, StackPointer = -1; IPPolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr, *OriginalPl, *Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl; IPVertexStruct *V, *Vnext; InterSegListStruct *PClosed, *POpen, *Ptemp; #ifdef DEBUG3 printf("Enter BoolExtractPolygons\n"); #endif /* DEBUG3 */ /* Stage 1. - mark all polygons as needed: */ PlHead = Pl = PObj -> U.Pl; /* Gen. a copy of Pl, so we can modify the original polygon list: */ PObj -> U.Pl = CopyPolygonList(Pl); while (Pl != NULL) { NumOfPolys++; /* Count number of polygons in original object. */ if (Pl -> PAux != NULL) { /* The intersection list is not empty! */ RST_COMPLETE_POLY(Pl); /* Mark it as non complete polygon. */ IP_RST_CONVEX_POLY(Pl); /* Mark it as possibly concave. */ V = Pl -> PVertex; do { SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */ V = V -> Pnext; } while (V != Pl -> PVertex); } else { SET_COMPLETE_POLY(Pl); /* Mark it as complete polygon. */ RST_INOUTPUT_POLY(Pl); /* And as undefined (if in output). */ RST_ADJPUSHED_POLY(Pl); /* And as not pushed on adj. stack. */ } Pl = Pl -> Pnext; } /* Stage 2. - scan the polygons and subdivide the intersecting ones: */ Pl = PlHead; /* We will save pointers to ALL polygons in list so we could free in the */ /* end the ones that are not in the output list, and therefore unused. */ PolysPtr = (IPPolygonStruct **) IritMalloc(sizeof(IPPolygonStruct *) * NumOfPolys); NumOfPolys = 0; while (Pl != NULL) { PolysPtr[NumOfPolys++] = Pl; /* Save pointer to this polygon. */ PlNext = Pl -> Pnext; Pl -> Pnext = NULL; if (!IS_COMPLETE_POLY(Pl) && BoolLoopsFromInterList(Pl, &PClosed, &POpen)) { /* They are intersections with this polygon - convert the */ /* intersecting segments into open/closed loops. */ /* Save copy of original polygon vertex list as we need its */ /* normals to interpolate for the internal ones. */ OriginalPl = IPAllocPolygon(Pl -> Tags, CopyVertexList(Pl -> PVertex), NULL); IP_RST_BBOX_POLY(OriginalPl); PLANE_COPY(OriginalPl -> Plane, Pl -> Plane); if (POpen != NULL) { /* Sort the Open loops into an order we can handle... */ BoolSortOpenInterList(Pl, &POpen); SplPl = NewPl = NULL; /* Keep the list of split polygons. */ while (POpen != NULL) { /* Clip the open loops from polygon: */ /* Note ClipOpenLoopFromPoly also frees the InterSegment */ /* list pointed by POpen (but not POpen itself). */ NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB); if (NewPl != NULL) { /* If loop clipped a new polygon, */ PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane); NewPl -> Pnext = SplPl;/* add to split polygon list. */ SplPl = NewPl; /* And push adj. polygons of complete edges on stack.*/ PushAdjOnStack(NewPl, AdjStack, &StackPointer); } Ptemp = POpen; POpen = POpen -> Pnext; IritFree((VoidPtr) Ptemp); } /* Last clip generated nothing (NewPl == NULL) so part that */ /* left from Pl (PlCopy) is IN output list! Add this poly: */ if (NewPl == NULL) { PLANE_COPY(Pl -> Plane, OriginalPl -> Plane); Pl -> Pnext = SplPl; /* And chain what was left from it. */ SplPl = Pl; /* And push adjacent polygons of complete edges on stack.*/ PushAdjOnStack(Pl, AdjStack, &StackPointer); SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */ IP_RST_CONVEX_POLY(Pl); /* May be not convex now. */ } UpdateVerticesNormals(SplPl, OriginalPl); } else SplPl = Pl; if (PClosed != NULL) { for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) Pl -> PAux = NULL; /* Classify the closed loops into the appropriate polygon. */ while (PClosed != NULL) { Ptemp = PClosed -> Pnext; for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) { if (CGPolygonRayInter3D(Pl, PClosed -> PISeg -> PtSeg[0], 0) % 2 == 1) { /* This closed loop is contained in this polygon.*/ PClosed -> Pnext = (InterSegListStruct *) Pl -> PAux; Pl -> PAux = (VoidPtr) PClosed; break; } } if (Pl == NULL) { /* This closed loop is part of a trimmed out by open */ /* loop region. It should be only the island formed */ /* by this closed loop then. */ /* Make a new polygon - a copy of the original and */ /* Put this loop in it. */ NewPl = IPAllocPolygon(OriginalPl -> Tags, CopyVertexList(OriginalPl -> PVertex), NULL); IP_RST_BBOX_POLY(NewPl); PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane); NewPl -> PAux = (VoidPtr) PClosed; NewPl -> Pnext = SplPl; SplPl = NewPl; } PClosed = Ptemp; } for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) { /* Make a "cut" from the loop(s) +-------+ +-------+ */ /* to boundary if possible, and | | | | */ /* converting Pl to a nonconvex | / \ | -> | / \__| */ /* polygon, that has an edge (the | \ / | -> | \ / | */ /* cut) which is shared twice in | | | | */ /* the same polygon +-------+ +-------+ */ PClosed = (InterSegListStruct *) Pl -> PAux; Pl -> PAux = NULL; if (CombineClosedLoops(Pl, PClosed, AinB)) { /* If returned with TRUE - polygon boundary is in */ /* output, so add all its neighbours to adj. stack. */ PushAdjOnStack(Pl, AdjStack, &StackPointer); } UpdateVerticesNormals(Pl, OriginalPl); } } OutputPl = ChainPolyLists(SplPl, OutputPl); /* Free the original polygon vertex list. */ IPFreePolygon(OriginalPl); } Pl = PlNext; } /* Stage 3. - handling adjacencies and propagate them in polygons: */ /* Pop off the elements from the stack, and propagate them using their */ /* adjacencies. */ while (StackPointer >= 0) { Pl = AdjStack[StackPointer--]; /* Pop top element. */ if (!IS_COMPLETE_POLY(Pl) || /* Ignore non complete polygons. */ IS_INOUTPUT_POLY(Pl)) continue; /* If already handled. */ SET_INOUTPUT_POLY(Pl); /* Mark this one as handled for next time. */ V = Pl -> PVertex; /* Push all adjacent ones that not handled yet. */ do { if (V -> PAdj && IS_COMPLETE_POLY(V -> PAdj) && !IS_INOUTPUT_POLY(V -> PAdj) && !IS_ADJPUSHED_POLY(V -> PAdj)) { SET_ADJPUSHED_POLY(V -> PAdj); AdjStack[++StackPointer] = V -> PAdj; /* Push it on stack. */ if (StackPointer >= ADJ_STACK_SIZE) IritFatalError("Adjacency stack overflow, object too big"); } V = V -> Pnext; } while (V != Pl -> PVertex); Pl -> Pnext = OutputPl; /* And chain it into output list. */ OutputPl = Pl; } /* Free all polygons which are not in the output list: */ while (--NumOfPolys >= 0) { if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) { IPFreePolygon(PolysPtr[NumOfPolys]); } } IritFree((VoidPtr) PolysPtr); /* Another floating point kludge: a polygon may have zero length edge so */ /* search for those and remove them - someone may die because of one... */ Pl = OutputPl; while (Pl != NULL) { V = Pl -> PVertex; do { Vnext = V -> Pnext; if (BOOL_PT_APX_EQ(V -> Coord, Vnext -> Coord)) { /* Ahh - we got you. Simply skip Vnext vertex and free it: */ V -> Pnext = Vnext -> Pnext; /* Update polygon vertex pointer if point on freed vertex: */ if (Pl -> PVertex == Vnext) Pl -> PVertex = Vnext -> Pnext; IPFreeVertex(Vnext); Vnext = V -> Pnext; } V = Vnext; } while (V != Pl -> PVertex && V != NULL); Pl = Pl -> Pnext; } #ifdef DEBUG3 printf("Exit BoolExtractPolygons\n"); #endif /* DEBUG3 */ return GenPolyObject("", OutputPl, NULL); /* Return resulting object. */ } #ifdef DEBUG /***************************************************************************** * DESCRIPTION: * * Print the content of the given vertex list, to standard output. * * * * PARAMETERS: * * V: The vertex list to be printed. * * * * RETURN VALUE: * * void * *****************************************************************************/ void BoolPrintVrtxList(IPVertexStruct *V) { IPVertexStruct *VHead = V; do { printf(" %12lf %12lf %12lf", V -> Coord[0], V -> Coord[1], V -> Coord[2]); if (IP_IS_INTERNAL_VRTX(V)) printf(" (Internal)\n"); else printf("\n"); V = V -> Pnext; } while (V!= NULL && V != VHead); } /***************************************************************************** * DESCRIPTION: * * Print the content of the given InterSegment list, to standard output. * * * * PARAMETERS: * * PInt: The InterSegment list to be printed. * * * * RETURN VALUE: * * void * *****************************************************************************/ void BoolPrintInterList(InterSegmentStruct *PInt) { printf("INTER SEGMENT LIST:\n"); if (PInt) printf("Entry vertex pointer %p\n", PInt -> V[0]); while (PInt) { printf("%9lg %9lg %9lg (%04ld), %9lg %9lg %9lg (%04ld)\n", PInt -> PtSeg[0][0], PInt -> PtSeg[0][1], PInt -> PtSeg[0][2], PInt -> V[0], PInt -> PtSeg[1][0], PInt -> PtSeg[1][1], PInt -> PtSeg[1][2], PInt -> V[1]); if (PInt -> Pnext == NULL) printf("Exit vertex pointer %p\n", PInt -> V[1]); PInt = PInt -> Pnext; } } #endif /* DEBUG */