0026310: Very slow boolean cut operations on cylinders
[occt.git] / src / IntPatch / IntPatch_Intersection.cxx
index c9cfb06..0dec3fe 100644 (file)
 #define DEBUG 0 
 static const Standard_Integer aNbPointsInALine = 200;
 
+//=======================================================================
+//function : MinMax
+//purpose  : Replaces theParMIN = MIN(theParMIN, theParMAX),
+//                    theParMAX = MAX(theParMIN, theParMAX).
+//=======================================================================
+static inline void MinMax(Standard_Real& theParMIN, Standard_Real& theParMAX)
+{
+  if(theParMIN > theParMAX)
+  {
+    const Standard_Real aTmp = theParMAX;
+    theParMAX = theParMIN;
+    theParMIN = aTmp;
+  }
+}
+
+//=======================================================================
+//function : IsSeam
+//purpose  : Returns:
+//            0 - if interval [theU1, theU2] does not intersect the "seam-edge"
+//                or if "seam-edge" do not exist;
+//            1 - if interval (theU1, theU2) intersect the "seam-edge".
+//            2 - if theU1 or/and theU2 lie ON the "seam-edge"
+//
+//ATTENTION!!!
+//  If (theU1 == theU2) then this function will return only both 0 or 2.
+//=======================================================================
+static Standard_Integer IsSeam( const Standard_Real theU1,
+                                const Standard_Real theU2,
+                                const Standard_Real thePeriod)
+{
+  if(IsEqual(thePeriod, 0.0))
+    return 0;
+
+  //If interval [theU1, theU2] intersect seam-edge then there exists an integer
+  //number N such as 
+  //    (theU1 <= T*N <= theU2) <=> (theU1/T <= N <= theU2/T),
+  //where T is the period.
+  //I.e. the inerval [theU1/T, theU2/T] must contain at least one
+  //integer number. In this case, Floor(theU1/T) and Floor(theU2/T)
+  //return different values or theU1/T is strictly integer number.
+  //Examples:
+  //  1. theU1/T==2.8, theU2/T==3.5 => Floor(theU1/T) == 2, Floor(theU2/T) == 3.
+  //  2. theU1/T==2.0, theU2/T==2.6 => Floor(theU1/T) == Floor(theU2/T) == 2.
+
+  const Standard_Real aVal1 = theU1/thePeriod,
+                      aVal2 = theU2/thePeriod;
+  const Standard_Integer aPar1 = static_cast<Standard_Integer>(Floor(aVal1));
+  const Standard_Integer aPar2 = static_cast<Standard_Integer>(Floor(aVal2));
+  if(aPar1 != aPar2)
+  {//Interval (theU1, theU2] intersects seam-edge
+    if(IsEqual(aVal2, static_cast<Standard_Real>(aPar2)))
+    {//aVal2 is an integer number => theU2 lies ON the "seam-edge"
+      return 2;
+    }
+
+    return 1;
+  }
+
+  //Here, aPar1 == aPar2. 
+
+  if(IsEqual(aVal1, static_cast<Standard_Real>(aPar1)))
+  {//aVal1 is an integer number => theU1 lies ON the "seam-edge"
+    return 2;
+  }
+
+  //If aVal2 is a true integer number then always (aPar1 != aPar2).
+
+  return 0;
+}
+
 //=======================================================================
 //function : IsSeamOrBound
-//purpose  : Returns TRUE if point thePt1 lies in seam-edge
-//            (if it exists) or surface boundaries;
+//purpose  : Returns TRUE if segment [thePtf, thePtl] intersects "seam-edge"
+//            (if it exist) or surface boundaries and both thePtf and thePtl do
+//            not match "seam-edge" or boundaries.
+//           Point thePtmid lies in this segment. If thePtmid match
+//            "seam-edge" or boundaries strictly (without any tolerance) then
+//            the function will return TRUE.
+//            See comments in function body for detail information.
 //=======================================================================
-static Standard_Boolean IsSeamOrBound(const IntSurf_PntOn2S& thePt1,
+static Standard_Boolean IsSeamOrBound(const IntSurf_PntOn2S& thePtf,
+                                      const IntSurf_PntOn2S& thePtl,
+                                      const IntSurf_PntOn2S& thePtmid,
                                       const Standard_Real theU1Period,
                                       const Standard_Real theU2Period,
                                       const Standard_Real theV1Period,
@@ -56,26 +133,112 @@ static Standard_Boolean IsSeamOrBound(const IntSurf_PntOn2S& thePt1,
                                       const Standard_Real theVlSurf2)
 {
   Standard_Real aU11 = 0.0, aU12 = 0.0, aV11 = 0.0, aV12 = 0.0;
-  thePt1.Parameters(aU11, aV11, aU12, aV12);
+  Standard_Real aU21 = 0.0, aU22 = 0.0, aV21 = 0.0, aV22 = 0.0;
+  thePtf.Parameters(aU11, aV11, aU12, aV12);
+  thePtl.Parameters(aU21, aV21, aU22, aV22);
+
+  MinMax(aU11, aU21);
+  MinMax(aV11, aV21);
+  MinMax(aU12, aU22);
+  MinMax(aV12, aV22);
+
+  if((aU11 - theUfSurf1)*(aU21 - theUfSurf1) < 0.0)
+  {//Interval [aU11, aU21] intersects theUfSurf1
+    return Standard_True;
+  }
+
+  if((aU11 - theUlSurf1)*(aU21 - theUlSurf1) < 0.0)
+  {//Interval [aU11, aU21] intersects theUlSurf1
+    return Standard_True;
+  }
+
+  if((aV11 - theVfSurf1)*(aV21 - theVfSurf1) < 0.0)
+  {//Interval [aV11, aV21] intersects theVfSurf1
+    return Standard_True;
+  }
+
+  if((aV11 - theVlSurf1)*(aV21 - theVlSurf1) < 0.0)
+  {//Interval [aV11, aV21] intersects theVlSurf1
+    return Standard_True;
+  }
+
+  if((aU12 - theUfSurf2)*(aU22 - theUfSurf2) < 0.0)
+  {//Interval [aU12, aU22] intersects theUfSurf2
+    return Standard_True;
+  }
+
+  if((aU12 - theUlSurf2)*(aU22 - theUlSurf2) < 0.0)
+  {//Interval [aU12, aU22] intersects theUlSurf2
+    return Standard_True;
+  }
+
+  if((aV12 - theVfSurf2)*(aV22 - theVfSurf2) < 0.0)
+  {//Interval [aV12, aV22] intersects theVfSurf2
+    return Standard_True;
+  }
+
+  if((aV12 - theVlSurf2)*(aV22 - theVlSurf2) < 0.0)
+  {//Interval [aV12, aV22] intersects theVlSurf2
+    return Standard_True;
+  }
+
+  if(IsSeam(aU11, aU21, theU1Period))
+    return Standard_True;
+
+  if(IsSeam(aV11, aV21, theV1Period))
+    return Standard_True;
+
+  if(IsSeam(aU12, aU22, theU2Period))
+    return Standard_True;
+
+  if(IsSeam(aV12, aV22, theV2Period))
+    return Standard_True;
+
+  /*
+    The segment [thePtf, thePtl] does not intersect the boundaries and
+    the seam-edge of the surfaces.
+    Nevertheless, following situation is possible:
+
+                  seam or
+                   bound
+                     |
+        thePtf  *    |
+                     |
+                     * thePtmid
+          thePtl  *  |
+                     |
+
+    This case must be processed, too.
+  */
+
+  Standard_Real aU1 = 0.0, aU2 = 0.0, aV1 = 0.0, aV2 = 0.0;
+  thePtmid.Parameters(aU1, aV1, aU2, aV2);
+
+  if(IsEqual(aU1, theUfSurf1) || IsEqual(aU1, theUlSurf1))
+    return Standard_True;
+
+  if(IsEqual(aU2, theUfSurf2) || IsEqual(aU2, theUlSurf2))
+    return Standard_True;
+
+  if(IsEqual(aV1, theVfSurf1) || IsEqual(aV1, theVlSurf1))
+    return Standard_True;
+
+  if(IsEqual(aV2, theVfSurf2) || IsEqual(aV2, theVlSurf2))
+    return Standard_True;
 
-  Standard_Boolean aCond = Standard_False;
-  aCond = aCond || (!IsEqual(theU1Period, 0.0) &&
-                    IsEqual(fmod(aU11, theU1Period), 0.0));
+  if(IsSeam(aU1, aU1, theU1Period))
+    return Standard_True;
 
-  aCond = aCond || (!IsEqual(theU2Period, 0.0) &&
-                    IsEqual(fmod(aU12, theU2Period), 0.0));
+  if(IsSeam(aU2, aU2, theU2Period))
+    return Standard_True;
 
-  aCond = aCond || (!IsEqual(theV1Period, 0.0) &&
-                    IsEqual(fmod(aV11, theV1Period), 0.0));
+  if(IsSeam(aV1, aV1, theV1Period))
+    return Standard_True;
 
-  aCond = aCond || (!IsEqual(theV2Period, 0.0) &&
-                    IsEqual(fmod(aV12, theV2Period), 0.0));
+  if(IsSeam(aV2, aV2, theV2Period))
+    return Standard_True;
 
-  return  aCond ||
-          IsEqual(aU11, theUfSurf1) || IsEqual(aU11, theUlSurf1) ||
-          IsEqual(aU12, theUfSurf2) || IsEqual(aU12, theUlSurf2) ||
-          IsEqual(aV11, theVfSurf1) || IsEqual(aV11, theVlSurf1) ||
-          IsEqual(aV12, theVfSurf2) || IsEqual(aV12, theVlSurf2);
+  return Standard_False;
 }
 
 //=======================================================================
@@ -139,7 +302,6 @@ static void JoinWLines(IntPatch_SequenceOfLine& theSlin,
     {
       Handle(IntPatch_WLine) aWLine2 (Handle(IntPatch_WLine)::DownCast(theSlin.Value(aNumOfLine2)));
 
-      const Standard_Integer aNbPntsWL1 = aWLine1->NbPnts();
       const Standard_Integer aNbPntsWL2 = aWLine2->NbPnts();
 
       const IntSurf_PntOn2S& aPntFWL1 = aWLine1->Point(1);
@@ -150,7 +312,9 @@ static void JoinWLines(IntPatch_SequenceOfLine& theSlin,
 
       if(aPntFWL1.IsSame(aPntFWL2, Precision::Confusion()))
       {
-        if(!IsSeamOrBound(aPntFWL1, theU1Period, theU2Period,
+        const IntSurf_PntOn2S& aPt1 = aWLine1->Point(2);
+        const IntSurf_PntOn2S& aPt2 = aWLine2->Point(2);
+        if(!IsSeamOrBound(aPt1, aPt2, aPntFWL1, theU1Period, theU2Period,
                           theV1Period, theV2Period, theUfSurf1, theUlSurf1,
                           theVfSurf1, theVlSurf1, theUfSurf2, theUlSurf2,
                           theVfSurf2, theVlSurf2))
@@ -174,7 +338,9 @@ static void JoinWLines(IntPatch_SequenceOfLine& theSlin,
 
       if(aPntFWL1.IsSame(aPntLWL2, Precision::Confusion()))
       {
-        if(!IsSeamOrBound(aPntFWL1, theU1Period, theU2Period,
+        const IntSurf_PntOn2S& aPt1 = aWLine1->Point(2);
+        const IntSurf_PntOn2S& aPt2 = aWLine2->Point(aNbPntsWL2-1);
+        if(!IsSeamOrBound(aPt1, aPt2, aPntFWL1, theU1Period, theU2Period,
                           theV1Period, theV2Period, theUfSurf1, theUlSurf1,
                           theVfSurf1, theVlSurf1, theUfSurf2, theUlSurf2,
                           theVfSurf2, theVlSurf2))
@@ -198,7 +364,9 @@ static void JoinWLines(IntPatch_SequenceOfLine& theSlin,
 
       if(aPntLWL1.IsSame(aPntFWL2, Precision::Confusion()))
       {
-        if(!IsSeamOrBound(aPntLWL1, theU1Period, theU2Period,
+        const IntSurf_PntOn2S& aPt1 = aWLine1->Point(aNbPntsWL1-1);
+        const IntSurf_PntOn2S& aPt2 = aWLine2->Point(2);
+        if(!IsSeamOrBound(aPt1, aPt2, aPntLWL1, theU1Period, theU2Period,
                           theV1Period, theV2Period, theUfSurf1, theUlSurf1,
                           theVfSurf1, theVlSurf1, theUfSurf2, theUlSurf2,
                           theVfSurf2, theVlSurf2))
@@ -222,7 +390,9 @@ static void JoinWLines(IntPatch_SequenceOfLine& theSlin,
 
       if(aPntLWL1.IsSame(aPntLWL2, Precision::Confusion()))
       {
-        if(!IsSeamOrBound(aPntLWL1, theU1Period, theU2Period,
+        const IntSurf_PntOn2S& aPt1 = aWLine1->Point(aNbPntsWL1-1);
+        const IntSurf_PntOn2S& aPt2 = aWLine2->Point(aNbPntsWL2-1);
+        if(!IsSeamOrBound(aPt1, aPt2, aPntLWL1, theU1Period, theU2Period,
                           theV1Period, theV2Period, theUfSurf1, theUlSurf1,
                           theVfSurf1, theVlSurf1, theUfSurf2, theUlSurf2,
                           theVfSurf2, theVlSurf2))