/***************************************************************************** * "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 Boolean operation between two polygons in the XY plane. * * The Z coords. are totally ignored. Input polygons are assumed to be convex.* *****************************************************************************/ #include #include #include #include #include "irit_sm.h" #include "allocate.h" #include "bool_loc.h" #include "geom_lib.h" #ifdef DEBUG IRIT_SET_DEBUG_PARAMETER(_DebugCoplanar, FALSE); #endif/* DEBUG */ #define Z_CROSS_PROD(V1, V2) (V1[0] * V2[1] - V1[1] * V2[0]) #define GET_FRAC(r) ((r) - ((int) (r))) static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2); static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2); static int IsInterValid(RealType t1, RealType t2, IPVertexStruct *V1, IPVertexStruct *V1Prev, IPVertexStruct *V2, IPVertexStruct *V2Prev); static void SortParam(Bool2DInterStruct **Bool2D, int First); static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2, Bool2DInterStruct **Bool2D, int Pl1First, int ComputeOut, BoolOperType BoolOper); static int Bool2DIsContainedEdge(IPVertexStruct *V, IPPolygonStruct *Pl); #ifdef DEBUG static void PrintVrtxList(IPVertexStruct *V); #endif /* DEBUG */ /***************************************************************************** * DESCRIPTION: M * Given two polygons assumed to be in the same plane, compute their 2D M * Boolean operation BoolOper and return it as a new polygon(s). M * NULL is returned if an error occur (No intersection or invalid BoolOper). M * * * PARAMETERS: M * Pl1: First polygon to compute 2D Boolean for. M * Pl2: Second polygon to compute 2D Boolean for. M * BoolOper: Boolean operation requested (and, or, etc.) M * * * RETURN VALUE: M * IPPolygonStruct *: The resulting Boolean operation. M * * * SEE ALSO: M * BooleanOR, BooleanAND, BooleanSUB, BooleanCUT, BooleanMERGE, BooleanNEG, M * BoolSetHandleCoplanarPoly, BoolSetOutputInterCurve, M * Boolean2DComputeInters M * * * KEYWORDS: M * Boolean2D, Booleans M *****************************************************************************/ IPPolygonStruct *Boolean2D(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2, BoolOperType BoolOper) { IPPolygonStruct *Pls, *Pl, *RetVal = NULL; Bool2DInterStruct *Bool2D; if (BoolOper == BOOL_OPER_SUB) { /* A - B == A * (-B). */ Pl2 = IPAllocPolygon(0, IPCopyVertexList(Pl2 -> PVertex), NULL); IPReverseVrtxList(Pl2); IPUpdatePolyPlane(Pl2); } Bool2D = Boolean2DComputeInters(Pl1, Pl2, TRUE, FALSE); #ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugCoplanar) { fprintf(stderr, "Poly1:\n"); PrintVrtxList(Pl1 -> PVertex); fprintf(stderr, "Poly2:\n"); PrintVrtxList(Pl2 -> PVertex); } #endif /* DEBUG */ if (Bool2D == NULL) { IPPolygonStruct *PlOut, *PlIn; PointType Mid1, Mid2; PT_BLEND(Mid1, Pl1 -> PVertex -> Coord, Pl1 -> PVertex -> Pnext -> Coord, BOOL_MID_BLEND); PT_BLEND(Mid2, Pl2 -> PVertex -> Coord, Pl2 -> PVertex -> Pnext -> Coord, BOOL_MID_BLEND); /* Coplanar polygons have no intersection. Test for inclusion. */ if ((GMPolygonRayInter(Pl1, Mid2, 0) & 0x01) == 1) { /* Pl2 is enclosed within Pl1 */ PlOut = Pl1; PlIn = Pl2; } else if ((GMPolygonRayInter(Pl2, Mid1, 0) & 0x01) == 1) { /* Pl1 is enclosed within Pl2 */ PlOut = Pl2; PlIn = Pl1; } else { PlOut = NULL; PlIn = NULL; } Pls = NULL; switch (BoolOper) { case BOOL_OPER_OR: if (PlOut != NULL) { Pls = IPAllocPolygon(PlOut -> Tags, IPCopyVertexList(PlOut -> PVertex), NULL); PLANE_COPY(Pls -> Plane, PlOut -> Plane); } break; case BOOL_OPER_AND: if (PlIn != NULL) { Pls = IPAllocPolygon(PlIn -> Tags, IPCopyVertexList(PlIn -> PVertex), NULL); PLANE_COPY(Pls -> Plane, PlIn -> Plane); } break; case BOOL_OPER_SUB: if (PlOut == Pl1) { /* Merge the two polygons PlOut as is and PlIn reversed. */ Pls = MergeTwoPolygons( IPAllocPolygon(PlOut -> Tags, IPCopyVertexList(PlOut -> PVertex), NULL), IPAllocPolygon(PlIn -> Tags, IPCopyVertexList(PlIn -> PVertex), NULL)); PLANE_COPY(Pls -> Plane, PlOut -> Plane); } break; default: BOOL_FATAL_ERROR(BOOL_ERR_NO_2D_OP_SUPPORT); Pls = NULL; break; } if (BoolOper == BOOL_OPER_SUB) IPFreePolygon(Pl2); return Pls; } switch (BoolOper) { case BOOL_OPER_OR: Pls = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D, TRUE, TRUE, BoolOper), Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D, FALSE, TRUE, BoolOper)); break; case BOOL_OPER_AND: case BOOL_OPER_SUB: Pls = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D, TRUE, FALSE, BoolOper), Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D, FALSE, FALSE, BoolOper)); break; default: BOOL_FATAL_ERROR(BOOL_ERR_NO_2D_OP_SUPPORT); Pls = NULL; break; } while (Bool2D) { Bool2DInterStruct *NextBool2D = Bool2D -> Pnext; IritFree(Bool2D); Bool2D = NextBool2D; } while (Pls != NULL) { Pl = Pls; Pls = Pls -> Pnext; BoolFilterCollinearities(Pl); # ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugCoplanar) { fprintf(stderr, "Returned Polygon:\n"); if (Pl -> PVertex) PrintVrtxList(Pl->PVertex); else fprintf(stderr, "\tEmpty Polygon:\n"); } # endif /* DEBUG */ if (Pl -> PVertex == NULL) { IPFreePolygon(Pl); } else LIST_PUSH(Pl, RetVal); } if (BoolOper == BOOL_OPER_SUB) IPFreePolygon(Pl2); return RetVal; } /***************************************************************************** * DESCRIPTION: M * Filters out collinear edges and duplicated vertices, in the given M * polygon. M * * * PARAMETERS: M * Pl: To filter, in place. The polygon is assumed to have a circular M * vertex list. M * * * RETURN VALUE: M * int: TRUE if the polygon has been modified, FALSE otherwise. M * * * KEYWORDS: M * BoolFilterCollinearities M *****************************************************************************/ int BoolFilterCollinearities(IPPolygonStruct *Pl) { int NumOfVertices = 0, VerticesRemoved = 0, Count = 0, AnyChange = FALSE; IPVertexStruct *VHead = Pl -> PVertex, *V = VHead; /* Count how many vertices we have. */ do { NumOfVertices++; V = V -> Pnext; } while (V != VHead && V != NULL); /* Loop on the vertex list until we iterate NumOfVertices times without */ /* any vertex removal. */ V = VHead; while (Count <= NumOfVertices) { RealType Size1, Size2; VectorType V1, V2; IPVertexStruct *VTmp, *VNext = V -> Pnext; if (NumOfVertices - VerticesRemoved < 3) { /* This whole polygon is zero area - purge it completely. */ IPFreeVertexList(Pl -> PVertex); Pl -> PVertex = NULL; return TRUE; } PT_SUB(V1, V -> Coord, VNext -> Coord); if ((Size1 = PT_LENGTH(V1)) < IRIT_EPS) { /* V and VNext are identical vertices - purge VNext. */ V -> Pnext = VNext -> Pnext; IPFreeVertex(VNext); AnyChange = TRUE; VerticesRemoved++; Count = 0; } else { PT_SUB(V2, VNext -> Coord, VNext -> Pnext -> Coord); if ((Size2 = PT_LENGTH(V2)) < IRIT_EPS) { /* VNext and VNext->Pnext are identical vertices. */ /* Purge VNext->Pnext. */ VTmp = VNext -> Pnext; VNext -> Pnext = VTmp -> Pnext; IPFreeVertex(VTmp); AnyChange = TRUE; VerticesRemoved++; Count = 0; } else { Size1 = 1.0 / Size1; Size2 = 1.0 / Size2; PT_SCALE(V1, Size1); PT_SCALE(V2, Size2); if (FABS(Z_CROSS_PROD(V1, V2)) < IRIT_EPS) { /* V, VNext and VNext->Pnext are all collinear. */ /* Purge VNext. */ V -> Pnext = VNext -> Pnext; IPFreeVertex(VNext); AnyChange = TRUE; VerticesRemoved++; Count = 0; } else { V = VNext; Count++; } } } } Pl -> PVertex = V; /* Note we might have purged P -> PVertex! */ return AnyChange; } /***************************************************************************** * DESCRIPTION: * * Merges the two provided polygons. Pl1 is assumed to fully contain Pl2. * * Pl1/2 are assumed to be convex. Pl2 vertex list is reversed and the two * * polygon's vertex lists are connected via the maximum X vertices. * * This function is destructive and Pl1/2 are modifed in place. * * * * PARAMETERS: * * Pl1, Pl2: The two polygons to merge into one. * * * * RETURN VALUE: * * IPPolygonStruct: The merged polygon. * *****************************************************************************/ static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2) { RealType MaxX; IPVertexStruct *V, *Vnext, *VMaxX = NULL; #ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugCoplanar) { fprintf(stderr, "MERGING:\nPoly1:\n"); PrintVrtxList(Pl1->PVertex); fprintf(stderr, "Poly2:\n"); PrintVrtxList(Pl2->PVertex); } #endif /* DEBUG */ IPUpdatePolyPlane(Pl1); /* Make sure polygon has plane definition. */ /* Find the vertex in Pl2 with the maximum X value. */ V = Pl2 -> PVertex; MaxX = -IRIT_INFNTY; do { if (V -> Coord[0] > MaxX) { VMaxX = V; MaxX = V -> Coord[0]; } V = V -> Pnext; } while (V != NULL && V != Pl2 -> PVertex); V = BoolCutPolygonAtRay(Pl1, VMaxX -> Coord); PT_COPY(V -> Normal, Pl1 -> Plane); Vnext = V -> Pnext; PT_COPY(Vnext -> Normal, Pl1 -> Plane); /* Duplicate VMaxX vertex. */ VMaxX -> Pnext = IPAllocVertex(VMaxX -> Tags, NULL, VMaxX -> Pnext); PT_COPY(VMaxX -> Pnext -> Coord, VMaxX -> Coord); PT_COPY(VMaxX -> Pnext -> Normal, VMaxX -> Normal); /* And exchange pointers. */ V -> Pnext = VMaxX -> Pnext; IP_SET_INTERNAL_VRTX(V); VMaxX -> Pnext = Vnext; IP_SET_INTERNAL_VRTX(VMaxX); Pl2 -> PVertex = NULL; IPFreePolygon(Pl2); IP_RST_CONVEX_POLY(Pl1); #ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugCoplanar) { fprintf(stderr, "RESULT OF MERGING:\n"); PrintVrtxList(Pl1->PVertex); } #endif /* DEBUG */ return Pl1; } /***************************************************************************** * DESCRIPTION: * * Connects the two provided lists of polylines into a closed polygon. * * Pl1/2 are being used by this routine and being destroyed. * * * * PARAMETERS: * * Pl1, Pl2: The two lists of polylines to merge into one closed polygon. * * * * RETURN VALUE: * * IPPolygonStruct: The constructed polygon. * *****************************************************************************/ static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2) { IPVertexStruct *VTail; IPPolygonStruct *Pl, *PlLast, *PlOut = NULL; /* Chain the two lists into one: */ if ((Pl1 = IPAppendPolyLists(Pl1, Pl2)) == NULL) return NULL; VTail = IPGetLastVrtx(Pl1 -> PVertex); while (Pl1 != NULL) { for (PlLast = Pl1, Pl = Pl1 -> Pnext; Pl != NULL && !BOOL_PT_APX_EQ(Pl -> PVertex -> Coord, VTail -> Coord); PlLast = Pl, Pl = Pl -> Pnext); if (Pl == NULL) { IPVertexStruct *V = Pl1 -> PVertex; /* If Pl1 is a zero length list of vertices, we better ignore. */ for ( ; V -> Pnext != NULL; V = V -> Pnext) { if (!BOOL_PT_APX_EQ(V -> Coord, V -> Pnext -> Coord)) break; } if (V -> Pnext == NULL) { Pl = Pl1 -> Pnext; IPFreePolygon(Pl1); Pl1 = Pl; continue; } else { BOOL_FATAL_ERROR(BOOL_ERR_NO_PLLN_MATCH); return NULL; } } VTail -> Pnext = Pl -> PVertex -> Pnext; /* Free the merged polyline (with its first vertex). */ PlLast -> Pnext = Pl -> Pnext; Pl -> PVertex -> Pnext = NULL; IPFreePolygon(Pl); /* Update the Tail pointer. */ VTail = IPGetLastVrtx(VTail); if (BOOL_PT_APX_EQ(VTail -> Coord, Pl1 -> PVertex -> Coord)) { /* We closed a loop here. Add to output list. */ Pl = Pl1 -> Pnext; Pl1 -> Pnext = PlOut; PlOut = Pl1; /* Close the loop and remove the duplicate vertex. */ VTail -> Pnext = Pl1 -> PVertex -> Pnext; IPFreeVertex(Pl1 -> PVertex); Pl1 -> PVertex = VTail; /* Continue with next polygon. */ if ((Pl1 = Pl) != NULL) { for (VTail = Pl1 -> PVertex; VTail -> Pnext != NULL; VTail = VTail -> Pnext); } } } return PlOut; } /***************************************************************************** * DESCRIPTION: M * Given two polygons/lines, Detect all edges in Pl1 that intersect with M * edges in Pl2. Returned is the information about all intersections as a M * Bool2DInter structure list. M * * * PARAMETERS: M * Poly1, Poly2: The two polygons/lines to intersect. M * HandlePolygons: If polygons, needs to handle normals etc. M * DetectIntr: If TRUE, return non NULL dummy pointer if the two polys M * do indeed intersect. For detection of intersection! M * * * RETURN VALUE: M * Bool2DInterStruct *: Intersection information. M * * * SEE ALSO: M * Boolean2D M * * * KEYWORDS: M * Boolean2DComputeInters, Booleans M *****************************************************************************/ Bool2DInterStruct *Boolean2DComputeInters(IPPolygonStruct *Poly1, IPPolygonStruct *Poly2, int HandlePolygons, int DetectIntr) { RealType Pl1Param, Pl2Param, *Pl1, *Pl2, t1, t2; PointType Pt1, Pt2; VectorType Vl1, Vl2; Bool2DInterStruct *Bool2D, *Bool2DTmp, *Bool2DHead = NULL; IPVertexStruct *V1, *V2, *V1Prev, *V2Prev, *V1Head = Poly1 -> PVertex, *V2Head = Poly2 -> PVertex; /* If this poly list is not circular, no previous vertex to first one. */ V1 = V1Head; V1Prev = IPGetLastVrtx(V1); if (V1Prev -> Pnext != V1) V1Prev = NULL; Pl1Param = 0.0; do { if (V1 == NULL || V1 -> Pnext == NULL) break; Pl1 = V1 -> Coord; PT_SUB(Vl1, V1 -> Pnext -> Coord, Pl1); /* If poly list is not circular, no previous vertex to first one. */ V2 = V2Head; V2Prev = IPGetLastVrtx(V2); if (V2Prev -> Pnext != V2) V2Prev = NULL; Pl2Param = 0.0; do { if (V2 == NULL || V2 -> Pnext == NULL) break; Pl2 = V2 -> Coord; PT_SUB(Vl2, V2 -> Pnext -> Coord, Pl2); if (GM2PointsFromLineLine(Pl1, Vl1, Pl2, Vl2, Pt1, &t1, Pt2, &t2) && t1 > -IRIT_UEPS && t1 < 1.0 + IRIT_UEPS && t2 > -IRIT_UEPS && t2 < 1.0 + IRIT_UEPS) { /* We detected an intersection here. */ t1 = BOUND(t1, 0.0, 1.0); t2 = BOUND(t2, 0.0, 1.0); if (DetectIntr) return ((Bool2DInterStruct *) TRUE); /* Validate the intersection on vertices. */ if (IsInterValid(t1, t2, V1, V1Prev, V2, V2Prev)) { /* Make sure it is a new intersection. */ for (Bool2DTmp = Bool2DHead; Bool2DTmp != NULL; Bool2DTmp = Bool2DTmp -> Pnext) { if ((APX_EQ(Bool2DTmp -> Param1, Pl1Param + t1) || APX_EQ(FABS(Bool2DTmp -> Param1 - (Pl1Param + t1)), 4.0)) && (APX_EQ(Bool2DTmp -> Param2, Pl2Param + t2) || APX_EQ(FABS(Bool2DTmp -> Param2 - (Pl2Param + t2)), 4.0))) break; } if (Bool2DTmp == NULL) { /* A new intersection! */ Bool2D = (Bool2DInterStruct *) IritMalloc(sizeof(Bool2DInterStruct)); PT_COPY(Bool2D -> InterPt, Pt1); if (HandlePolygons) GMInterpVrtxNrmlBetweenTwo2(Pt1, Bool2D -> Normal, V1, V2); Bool2D -> Poly1Vrtx = V1; Bool2D -> Param1 = Pl1Param + t1; Bool2D -> Poly2Vrtx = V2; Bool2D -> Param2 = Pl2Param + t2; Bool2D -> DualInter = FALSE; LIST_PUSH(Bool2D, Bool2DHead); } else { /* Keep this intersection in addition to old one. */ Bool2DTmp -> Poly1Vrtx2 = V1; Bool2DTmp -> Poly2Vrtx2 = V2; Bool2DTmp -> DualInter = TRUE; } } } Pl2Param += 1.0; V2Prev = V2; V2 = V2 -> Pnext; } while (V2 != NULL && V2 != V2Head); Pl1Param += 1.0; V1Prev = V1; V1 = V1 -> Pnext; } while (V1 != NULL && V1 != V1Head); if (HandlePolygons && Bool2DHead != NULL && Bool2DHead -> Pnext == NULL) { /* If only one intersection - ignore it (point intersection). */ IritFree(Bool2DHead); Bool2DHead = NULL; } return Bool2DHead; } /***************************************************************************** * DESCRIPTION: * * Validates an intersection location. Looks for intersection on vertices * * that occurs so that the edge before and the edge after are having the same * * directions as the other polygon. * * * * PARAMETERS: * * t1: Betweeon zero and one where intersection occur on (V1, V1->Pnext). * * t2: Betweeon zero and one where intersection occur on (V2, V2->Pnext). * * V1: Edge of intersection on first polygon. * * V1Prev: Vertex previous to V2, or NULL if none. * * V2: Edge of intersection on second polygon. * * V2Prev: Vertex previous to V2, or NULL if none. * * * * RETURN VALUE: * * int: TRUE if intersection is valid, FALSE otherwise. * *****************************************************************************/ static int IsInterValid(RealType t1, RealType t2, IPVertexStruct *V1, IPVertexStruct *V1Prev, IPVertexStruct *V2, IPVertexStruct *V2Prev) { VectorType Dir1Prev, Dir1Next, Dir2Prev, Dir2Next; IPVertexStruct *V1Next, *V2Next; /* Both intersections are interior to edge - this intersection is fine. */ if ((t1 < 1.0 - IRIT_UEPS && t1 > IRIT_UEPS) && (t2 < 1.0 - IRIT_UEPS && t2 > IRIT_UEPS)) return TRUE; /* Only one polygon intersects on its vertex and the other is interior. */ /* Validate only if vertex intersection occurs at the beginning of edge. */ if ((t1 >= 1.0 - IRIT_UEPS || t1 <= IRIT_UEPS) && (t2 < 1.0 - IRIT_UEPS && t2 > IRIT_UEPS)) { if (t1 <= IRIT_UEPS) return TRUE; /* If previous edges are coplanar, we still need to validate this. */ if ((V1Prev = IPGetPrevVrtx(V1 -> Pnext, V1)) == NULL) return FALSE; VEC_SUB(Dir1Prev, V1 -> Coord, V1Prev -> Coord); if ((V2Next = V2 -> Pnext) == NULL) return FALSE; VEC_SUB(Dir2Prev, V2Next -> Coord, V2 -> Coord); PT_NORMALIZE(Dir1Prev); PT_NORMALIZE(Dir2Prev); return FABS(DOT_PROD(Dir1Prev, Dir2Prev)) > 1.0 - IRIT_UEPS; } if ((t2 >= 1.0 - IRIT_UEPS || t2 <= IRIT_UEPS) && (t1 < 1.0 - IRIT_UEPS && t1 > IRIT_UEPS)) { if (t1 <= IRIT_UEPS) return TRUE; /* If previous edges are coplanar, we still need to validate this. */ if (V2Prev == NULL) return TRUE; VEC_SUB(Dir2Prev, V2 -> Coord, V2Prev -> Coord); V1Next = V1 -> Pnext; VEC_SUB(Dir1Prev, V1Next -> Coord, V1 -> Coord); PT_NORMALIZE(Dir1Prev); PT_NORMALIZE(Dir2Prev); return FABS(DOT_PROD(Dir1Prev, Dir2Prev)) > 1.0 - IRIT_UEPS; } /* If we are here, then both polygons intersect on a vertex. */ /* Eval directions of prev/next edges to intersection. */ V1Next = V1 -> Pnext; if (t1 < IRIT_UEPS) { if (V1Prev == NULL) return TRUE; VEC_SUB(Dir1Prev, V1 -> Coord, V1Prev -> Coord); VEC_SUB(Dir1Next, V1Next -> Coord, V1 -> Coord); } else { /* t1 ~= 1.0. */ VEC_SUB(Dir1Prev, V1Next -> Coord, V1 -> Coord); VEC_SUB(Dir1Next, V1Next -> Pnext-> Coord, V1Next -> Coord); } PT_NORMALIZE(Dir1Prev); PT_NORMALIZE(Dir1Next); V2Next = V2 -> Pnext; if (t2 < IRIT_UEPS) { if (V2Prev == NULL) return TRUE; VEC_SUB(Dir2Prev, V2 -> Coord, V2Prev -> Coord); VEC_SUB(Dir2Next, V2Next -> Coord, V2 -> Coord); } else { /* t2 ~= 1.0. */ VEC_SUB(Dir2Prev, V2Next -> Coord, V2 -> Coord); VEC_SUB(Dir2Next, V2Next -> Pnext -> Coord, V2Next -> Coord); } PT_NORMALIZE(Dir2Prev); PT_NORMALIZE(Dir2Next); /* Two previous edges and two next edges are identical. */ if (FABS(DOT_PROD(Dir1Prev, Dir2Prev)) > 1.0 - IRIT_UEPS && FABS(DOT_PROD(Dir1Next, Dir2Next)) > 1.0 - IRIT_UEPS) return FALSE; /* Prev edge of one poly is same as next of other poly and vice versa. */ if (FABS(DOT_PROD(Dir1Prev, Dir2Next)) > 1.0 - IRIT_UEPS && FABS(DOT_PROD(Dir1Next, Dir2Prev)) > 1.0 - IRIT_UEPS) return FALSE; return TRUE; } /***************************************************************************** * DESCRIPTION: * * Sorts the provided list with according to Param1 (First == TRUE) or * * Param2 (First == FALSE). Bool2D is sorted in place. * * * * PARAMETERS: * * Bool2D: List of intersection locations to sort. * * First: TRUE if sort according to first, FALSE otherwise. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void SortParam(Bool2DInterStruct **Bool2D, int First) { Bool2DInterStruct *BTmp, *Bool2DSorted = NULL; while (*Bool2D != NULL) { Bool2DInterStruct *B = *Bool2D; *Bool2D = (*Bool2D) -> Pnext; B -> Pnext = NULL; if (Bool2DSorted) { if ((First && Bool2DSorted -> Param1 > B -> Param1) || (!First && Bool2DSorted -> Param2 > B -> Param2)) { /* Put it as first in list. */ B -> Pnext = Bool2DSorted; Bool2DSorted = B; } else { for (BTmp = Bool2DSorted; BTmp -> Pnext != NULL; BTmp = BTmp -> Pnext) if ((First && BTmp -> Pnext -> Param1 > B -> Param1) || (!First && BTmp -> Pnext -> Param2 > B -> Param2)) break; B -> Pnext = BTmp -> Pnext; BTmp -> Pnext = B; } } else Bool2DSorted = B; } *Bool2D = Bool2DSorted; } /***************************************************************************** * DESCRIPTION: * * Given two polygons, Computes the region(s) of Pl1 in or out of Pl2. * * * * PARAMETERS: * * Pl1, Pl2: Polygons to compute Pl1 in or out Pl2 for. * * Bool2D: List of intersection locations. * * Pl1First: If in fact Pl1 is second in Bool2D. * * ComputeOut: TRUE for Pl1 Out Pl2, FALSE for Pl1 in Pl2. * * BoolOper: Boolean operation requested (and, or, etc.) * * * * RETURN VALUE: * * IPPolygonStruct: Resulting inside/outside * *****************************************************************************/ static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2, Bool2DInterStruct **Bool2D, int Pl1First, int ComputeOut, BoolOperType BoolOper) { int PrevPolyUsed = FALSE; VectorType V1, V2; IPVertexStruct *V, *VTail, *VTmp, *VTmp2, *VHead = Pl1 -> PVertex; IPPolygonStruct *Pl, *PlOut = NULL; Bool2DInterStruct *B, *NextB, *TmpB; SortParam(Bool2D, Pl1First); /* Go over all intersections and search for one not dual intersection. */ for (B = *Bool2D; B != NULL; B = B -> Pnext) if (!B -> DualInter) break; if (B == NULL) { /* All intersections are dual - the two polygons are identical. */ PlOut = IPAllocPolygon(0, IPCopyVertexList(Pl1 -> PVertex), NULL); PLANE_COPY(PlOut -> Plane, Pl1 -> Plane); return PlOut; } if (B != *Bool2D) { /* Make the non dual intersection the first one. */ for (TmpB = *Bool2D; TmpB -> Pnext != B; TmpB = TmpB -> Pnext); TmpB -> Pnext = NULL; for (TmpB = B; TmpB -> Pnext != NULL; TmpB = TmpB -> Pnext); TmpB -> Pnext = *Bool2D; *Bool2D = B; } while (B != NULL) { NextB = B -> Pnext ? B -> Pnext : *Bool2D; /* Decide if the first pair (B, NextB) is indeed in the output set. */ VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx; PT_SUB(V1, VTmp -> Pnext -> Coord, VTmp -> Coord); VTmp2 = Pl1First ? B -> Poly2Vrtx : B -> Poly1Vrtx; PT_SUB(V2, VTmp2 -> Pnext -> Coord, VTmp2 -> Coord); if ((B -> DualInter && !PrevPolyUsed) || (!B -> DualInter && ((Z_CROSS_PROD(V1, V2) < 0.0) ^ (ComputeOut != FALSE)))) { RealType Ft1 = Pl1First ? B -> Param1 : B -> Param2, Ft2 = Pl1First ? NextB -> Param1 : NextB -> Param2; VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx; VHead = VTail = IPAllocVertex(VTmp -> Tags, NULL, NULL); PT_COPY(VHead -> Coord, B -> InterPt); PT_COPY(VHead -> Normal, B -> Normal); VTmp2 = Pl1First ? NextB -> Poly1Vrtx : NextB -> Poly2Vrtx; if (VTmp != VTmp2 || Ft1 > Ft2) { V = VTmp -> Pnext; do { VTail -> Pnext = IPAllocVertex(V -> Tags, NULL, NULL); VTail = VTail -> Pnext; PT_COPY(VTail -> Coord, V -> Coord); PT_COPY(VTail -> Normal, V -> Normal); V = V -> Pnext; } while (V != VTmp2 -> Pnext); } VTail -> Pnext = IPAllocVertex(VTmp2 -> Tags, NULL, NULL); VTail = VTail -> Pnext; PT_COPY(VTail -> Coord, NextB -> InterPt); PT_COPY(VTail -> Normal, NextB -> Normal); if (BoolOper == BOOL_OPER_SUB && Bool2DIsContainedEdge(VHead, Pl1) && Bool2DIsContainedEdge(VHead, Pl2)) { /* No shared edges in subtractive operation. */ IPFreeVertexList(VHead); PrevPolyUsed = FALSE; } else { Pl = IPAllocPolygon(0, VHead, NULL); PLANE_COPY(Pl -> Plane, Pl1 -> Plane); LIST_PUSH(Pl, PlOut); PrevPolyUsed = TRUE; } } else PrevPolyUsed = FALSE; B = B -> Pnext; } #ifdef DEBUG IRIT_IF_DEBUG_ON_PARAMETER(_DebugCoplanar) { fprintf(stderr, "Polyline extracted:\n"); if (PlOut == NULL) fprintf(stderr, "\tNo Polyline\n"); else { for (Pl = PlOut; Pl != NULL; Pl = Pl->Pnext) { fprintf(stderr, "\t Polyline\n"); PrintVrtxList(Pl->PVertex); } } } #endif /* DEBUG */ return PlOut; } /***************************************************************************** * DESCRIPTION: * * Tests if the given edge is completely contained in the given polygon. * * * * PARAMETERS: * * V: First vertex of edge (with V->Pnext). * * Pl: To check if (V, V->Pnext) is contained in. * * * * RETURN VALUE: * * int: TRUE if contained, FALSE otherwise. * *****************************************************************************/ static int Bool2DIsContainedEdge(IPVertexStruct *V, IPPolygonStruct *Pl) { IPVertexStruct *VPoly = Pl -> PVertex; do { VectorType Dir; PT_SUB(Dir, VPoly -> Pnext -> Coord, VPoly -> Coord); if (GMDistPointLine(V -> Coord, VPoly -> Coord, Dir) < IRIT_EPS && GMDistPointLine(V -> Pnext -> Coord, VPoly -> Coord, Dir) < IRIT_EPS) { VectorType Dir1, Dir2; /* (V, V->Pnext) sits on the line through (VPoly, VPoly->Pnext). */ PT_SUB(Dir1, V -> Coord, VPoly -> Coord); PT_SUB(Dir2, V -> Pnext -> Coord, VPoly -> Coord); if (DOT_PROD(Dir, Dir1) > -IRIT_EPS && DOT_PROD(Dir, Dir) > DOT_PROD(Dir1, Dir1) - IRIT_EPS && DOT_PROD(Dir, Dir2) > -IRIT_EPS && DOT_PROD(Dir, Dir) > DOT_PROD(Dir2, Dir2) - IRIT_EPS) { /* (V, V->Pnext) is inside (VPoly, VPoly->Pnext). */ return TRUE; } } VPoly = VPoly -> Pnext; } while (VPoly != Pl -> PVertex); return FALSE; } #ifdef DEBUG /***************************************************************************** * DESCRIPTION: * * Print the content of the given vertex list, to standard output. * * * * PARAMETERS: * * V: Vertex list to print. * * * * RETURN VALUE: * * void * *****************************************************************************/ static void PrintVrtxList(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); } #endif /* DEBUG */