From: emv <emv@opencascade.com>
Date: Tue, 23 Apr 2019 09:31:23 +0000 (+0300)
Subject: 0030670: Modeling Algorithms - Performance improvement of Boolean Operations algorithm
X-Git-Tag: V7_4_0_beta~139
X-Git-Url: http://git.dev.opencascade.org/gitweb/?p=occt.git;a=commitdiff_plain;h=47cd8af2d2187e16bb358dc2f30a1a54d7ab2dfa

0030670: Modeling Algorithms - Performance improvement of Boolean Operations algorithm

The following improvements have been made in Boolean operations algorithm:
1. Added possibility to update FaceInfo structure for many faces at once which helps to avoid nested loops.
2. Improve Point-Face classification procedure by caching the FaceExplorer for a face.
---

diff --git a/src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx b/src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx
index 5a8aa81184..c6b43cfc9a 100644
--- a/src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx
+++ b/src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx
@@ -469,12 +469,8 @@ void BOPAlgo_PaveFiller::PerformEF()
   PerformNewVertices(aMVCPB, aAllocator, Standard_False);
   //
   // Update FaceInfoIn for all faces having EF common parts
-  TColStd_MapIteratorOfMapOfInteger aItMI;
-  aItMI.Initialize(aMIEFC);
-  for (; aItMI.More(); aItMI.Next()) {
-    nF=aItMI.Value();
-    myDS->UpdateFaceInfoIn(nF);
-  }
+  myDS->UpdateFaceInfoIn (aMIEFC);
+
   //-----------------------------------------------------scope t
   aMIEFC.Clear();
   aMVCPB.Clear();
diff --git a/src/BOPAlgo/BOPAlgo_PaveFiller_6.cxx b/src/BOPAlgo/BOPAlgo_PaveFiller_6.cxx
index 7cfdeeab36..871d738e06 100644
--- a/src/BOPAlgo/BOPAlgo_PaveFiller_6.cxx
+++ b/src/BOPAlgo/BOPAlgo_PaveFiller_6.cxx
@@ -200,36 +200,18 @@ void BOPAlgo_PaveFiller::PerformFF()
   for (; myIterator->More(); myIterator->Next()) {
     myIterator->Value(nF1, nF2);
 
-    // Update/Initialize FaceInfo structure for first face
-    if (myDS->HasFaceInfo(nF1))
-    {
-      if (aMIFence.Add(nF1))
-      {
-        myDS->UpdateFaceInfoOn(nF1);
-        myDS->UpdateFaceInfoIn(nF1);
-      }
-    }
-    else if (myDS->HasInterfShapeSubShapes(nF2, nF1))
-    {
-      myDS->ChangeFaceInfo(nF1);
-      aMIFence.Add(nF1);
-    }
+    aMIFence.Add (nF1);
+    aMIFence.Add (nF2);
+  }
+  // Update face info
+  myDS->UpdateFaceInfoOn (aMIFence);
+  myDS->UpdateFaceInfoIn (aMIFence);
+
+  // Initialize interferences
+  myIterator->Initialize(TopAbs_FACE, TopAbs_FACE);
+  for (; myIterator->More(); myIterator->Next()) {
+    myIterator->Value(nF1, nF2);
 
-    // Update/Initialize FaceInfo structure for second face
-    if (myDS->HasFaceInfo(nF2))
-    {
-      if (aMIFence.Add(nF2))
-      {
-        myDS->UpdateFaceInfoOn(nF2);
-        myDS->UpdateFaceInfoIn(nF2);
-      }
-    }
-    else if (myDS->HasInterfShapeSubShapes(nF1, nF2))
-    {
-      myDS->ChangeFaceInfo(nF2);
-      aMIFence.Add(nF2);
-    }
-    //
     if (myGlue == BOPAlgo_GlueOff)
     {
       const TopoDS_Face& aF1 = (*(TopoDS_Face *)(&myDS->Shape(nF1)));
diff --git a/src/BOPDS/BOPDS_DS.cxx b/src/BOPDS/BOPDS_DS.cxx
index b5471753fc..aefaeeebe5 100644
--- a/src/BOPDS/BOPDS_DS.cxx
+++ b/src/BOPDS/BOPDS_DS.cxx
@@ -1203,9 +1203,33 @@ void BOPDS_DS::InitFaceInfo(const Standard_Integer theI)
   aSI.SetReference(iRef);
   //
   aFI.SetIndex(theI);
-  UpdateFaceInfoIn(theI);
+  InitFaceInfoIn(theI);
   UpdateFaceInfoOn(theI);
 }
+//=======================================================================
+//function : InitFaceInfoIn
+//purpose  : 
+//=======================================================================
+void BOPDS_DS::InitFaceInfoIn (const Standard_Integer theI)
+{
+  BOPDS_ShapeInfo& aSI = ChangeShapeInfo (theI);
+  if (aSI.HasReference())
+  {
+    BOPDS_FaceInfo& aFI = myFaceInfoPool (aSI.Reference());
+    const TopoDS_Shape& aF = Shape (theI);
+    for (TopoDS_Iterator itS (aF); itS.More(); itS.Next())
+    {
+      const TopoDS_Shape& aV = itS.Value();
+      if (aV.ShapeType() == TopAbs_VERTEX)
+      {
+        Standard_Integer nV = Index (aV);
+        HasShapeSD (nV, nV);
+        aFI.ChangeVerticesIn().Add (nV);
+      }
+    }
+  }
+}
+
 //=======================================================================
 //function : UpdateFaceInfoIn
 //purpose  : 
@@ -1356,6 +1380,105 @@ void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
   }// for (i=0; i<aNbEF; ++i) {
 }
 
+//=======================================================================
+//function : UpdateFaceInfoIn
+//purpose  : 
+//=======================================================================
+void BOPDS_DS::UpdateFaceInfoIn (const TColStd_MapOfInteger& theFaces)
+{
+  for (TColStd_MapOfInteger::Iterator itM (theFaces); itM.More(); itM.Next())
+  {
+    const Standard_Integer nF = itM.Value();
+    BOPDS_ShapeInfo& aSI = ChangeShapeInfo (nF);
+    if (!aSI.HasReference())
+    {
+      myFaceInfoPool.Appended().SetIndex (nF);
+      aSI.SetReference (myFaceInfoPool.Length() - 1);
+    }
+    BOPDS_FaceInfo& aFI = myFaceInfoPool (aSI.Reference());
+    aFI.ChangePaveBlocksIn().Clear();
+    aFI.ChangeVerticesIn().Clear();
+
+    // 1. Add pure internal vertices on the face
+    InitFaceInfoIn (nF);
+  }
+
+  // 2. Analyze Vertex-Face interferences
+  BOPDS_VectorOfInterfVF& aVFs = InterfVF();
+  const Standard_Integer aNbVF = aVFs.Length();
+  for (Standard_Integer iVF = 0; iVF < aNbVF; ++iVF)
+  {
+    BOPDS_InterfVF& aVF = aVFs (iVF);
+    const Standard_Integer nF = aVF.Index2();
+    if (theFaces.Contains (nF))
+    {
+      Standard_Integer nV = aVF.Index1();
+      HasShapeSD (nV, nV);
+      myFaceInfoPool (ShapeInfo (nF).Reference()).ChangeVerticesIn().Add (nV);
+    }
+  }
+  //
+  // 3. Analyze Edge-Face interferences
+  BOPDS_VectorOfInterfEF& aEFs = InterfEF();
+  const Standard_Integer aNbEF = aEFs.Length();
+  for (Standard_Integer iEF = 0; iEF < aNbEF; ++iEF)
+  {
+    BOPDS_InterfEF& aEF = aEFs (iEF);
+    const Standard_Integer nF = aEF.Index2();
+    if (theFaces.Contains (nF))
+    {
+      BOPDS_FaceInfo& aFI = myFaceInfoPool (ShapeInfo (nF).Reference());
+      Standard_Integer nVNew;
+      if (aEF.HasIndexNew (nVNew))
+      {
+        HasShapeSD (nVNew, nVNew);
+        aFI.ChangeVerticesIn().Add (nVNew);
+      }
+      else
+      {
+        const Standard_Integer nE = aEF.Index1();
+        const BOPDS_ListOfPaveBlock& aLPB = PaveBlocks (nE);
+        for (BOPDS_ListOfPaveBlock::Iterator itPB (aLPB); itPB.More(); itPB.Next())
+        {
+          const Handle(BOPDS_PaveBlock)& aPB = itPB.Value();
+          const Handle(BOPDS_CommonBlock)& aCB = CommonBlock (aPB);
+          if (!aCB.IsNull())
+          {
+            if (aCB->Contains (nF))
+            {
+              const Handle(BOPDS_PaveBlock)& aPBR = aCB->PaveBlock1();
+              aFI.ChangePaveBlocksIn().Add(aPBR);
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+//=======================================================================
+//function : UpdateFaceInfoOn
+//purpose  : 
+//=======================================================================
+void BOPDS_DS::UpdateFaceInfoOn (const TColStd_MapOfInteger& theFaces)
+{
+  for (TColStd_MapOfInteger::Iterator itM (theFaces); itM.More(); itM.Next())
+  {
+    const Standard_Integer nF = itM.Value();
+    BOPDS_ShapeInfo& aSI = ChangeShapeInfo (nF);
+    if (!aSI.HasReference())
+    {
+      myFaceInfoPool.Appended().SetIndex (nF);
+      aSI.SetReference (myFaceInfoPool.Length() - 1);
+    }
+    BOPDS_FaceInfo& aFI = myFaceInfoPool (aSI.Reference());
+    aFI.ChangePaveBlocksOn().Clear();
+    aFI.ChangeVerticesOn().Clear();
+
+    FaceInfoOn (nF, aFI.ChangePaveBlocksOn(), aFI.ChangeVerticesOn());
+  }
+}
+
 //=======================================================================
 //function : RefineFaceInfoOn
 //purpose  : 
diff --git a/src/BOPDS/BOPDS_DS.hxx b/src/BOPDS/BOPDS_DS.hxx
index d51d7757cc..418a4b9fe4 100644
--- a/src/BOPDS/BOPDS_DS.hxx
+++ b/src/BOPDS/BOPDS_DS.hxx
@@ -274,10 +274,14 @@ Standard_EXPORT virtual ~BOPDS_DS();
   //! Update the state In of face with index theIndex
   Standard_EXPORT void UpdateFaceInfoIn (const Standard_Integer theIndex);
   
+  //! Update the state IN for all faces in the given map
+  Standard_EXPORT void UpdateFaceInfoIn (const TColStd_MapOfInteger& theFaces);
 
   //! Update the state On of face with index theIndex
   Standard_EXPORT void UpdateFaceInfoOn (const Standard_Integer theIndex);
   
+  //! Update the state ON for all faces in the given map
+  Standard_EXPORT void UpdateFaceInfoOn (const TColStd_MapOfInteger& theFaces);
 
   //! Selector
   //! Returns the state On
@@ -479,6 +483,10 @@ protected:
 
   //! Initializes the state of face with index theIndex
   Standard_EXPORT void InitFaceInfo (const Standard_Integer theIndex);
+
+  //! Initializes the FaceInfo structure for face with index theIndex with elements
+  //! having IN state for the face
+  Standard_EXPORT void InitFaceInfoIn (const Standard_Integer theIndex);
   
   Standard_EXPORT void InitShape (const Standard_Integer theIndex, const TopoDS_Shape& theS);
   
diff --git a/src/BRepClass/BRepClass_FaceClassifier.cxx b/src/BRepClass/BRepClass_FaceClassifier.cxx
index 8d1ba8cb9e..b593eb0cb0 100644
--- a/src/BRepClass/BRepClass_FaceClassifier.cxx
+++ b/src/BRepClass/BRepClass_FaceClassifier.cxx
@@ -97,7 +97,7 @@ void  BRepClass_FaceClassifier::Perform(const TopoDS_Face& aF,
   aMaxDist=RealLast();
   aIndice=0;
   //
-  BRepAdaptor_Surface aSurf(aF);
+  BRepAdaptor_Surface aSurf(aF, Standard_False);
   BRepTools::UVBounds(aF, aU1, aU2, aV1, aV2);
   aExtrema.Initialize(aSurf, aU1, aU2, aV1, aV2, aTol, aTol);
   //
@@ -128,10 +128,3 @@ void  BRepClass_FaceClassifier::Perform(const TopoDS_Face& aF,
     Perform(aF, aPuv, aTol);
   }
 }
-
-
-
-
-
-
-
diff --git a/src/BRepClass/BRepClass_FaceExplorer.cxx b/src/BRepClass/BRepClass_FaceExplorer.cxx
index 3fb9b5baf5..b2255c4cdc 100644
--- a/src/BRepClass/BRepClass_FaceExplorer.cxx
+++ b/src/BRepClass/BRepClass_FaceExplorer.cxx
@@ -40,45 +40,61 @@ static const Standard_Real Probing_Step = 0.2111;
 BRepClass_FaceExplorer::BRepClass_FaceExplorer(const TopoDS_Face& F) :
        myFace(F),
        myCurEdgeInd(1),
-       myCurEdgePar(Probing_Start)
+       myCurEdgePar(Probing_Start),
+       myUMin (Precision::Infinite()),
+       myUMax (-Precision::Infinite()),
+       myVMin (Precision::Infinite()),
+       myVMax (-Precision::Infinite())
 {
   myFace.Orientation(TopAbs_FORWARD);
 }
 
+//=======================================================================
+//function : ComputeFaceBounds
+//purpose  : 
+//=======================================================================
+void BRepClass_FaceExplorer::ComputeFaceBounds()
+{
+  TopLoc_Location aLocation;
+  const Handle(Geom_Surface)& aSurface = BRep_Tool::Surface (myFace, aLocation);
+  aSurface->Bounds (myUMin, myUMax, myVMin, myVMax);
+  if (Precision::IsInfinite (myUMin) || Precision::IsInfinite (myUMax) ||
+      Precision::IsInfinite (myVMin) || Precision::IsInfinite (myVMax))
+  {
+    BRepTools::UVBounds(myFace, myUMin, myUMax, myVMin, myVMax);
+  }
+}
+
 //=======================================================================
 //function : CheckPoint
 //purpose  : 
 //=======================================================================
 
-Standard_Boolean  BRepClass_FaceExplorer::CheckPoint(gp_Pnt2d& thePoint)
+Standard_Boolean BRepClass_FaceExplorer::CheckPoint(gp_Pnt2d& thePoint)
 {
-  Standard_Real anUMin = 0.0, anUMax = 0.0, aVMin = 0.0, aVMax = 0.0;
-  TopLoc_Location aLocation;
-  const Handle(Geom_Surface)& aSurface = BRep_Tool::Surface(myFace, aLocation);
-  aSurface->Bounds(anUMin, anUMax, aVMin, aVMax);
-  if (Precision::IsInfinite(anUMin) || Precision::IsInfinite(anUMax) ||
-      Precision::IsInfinite(aVMin) || Precision::IsInfinite(aVMax))
+  if (myUMin > myUMax)
   {
-    BRepTools::UVBounds(myFace, anUMin, anUMax, aVMin, aVMax);
-    if (Precision::IsInfinite(anUMin) || Precision::IsInfinite(anUMax) ||
-        Precision::IsInfinite(aVMin) || Precision::IsInfinite(aVMax))
-    {
-      return Standard_True;
-    }
+    ComputeFaceBounds();
+  }
+
+  if (Precision::IsInfinite(myUMin) || Precision::IsInfinite(myUMax) ||
+      Precision::IsInfinite(myVMin) || Precision::IsInfinite(myVMax))
+  {
+    return Standard_True;
   }
 
-  gp_Pnt2d aCenterPnt(( anUMin + anUMax ) / 2, ( aVMin + aVMax ) / 2);
+  gp_Pnt2d aCenterPnt(( myUMin + myUMax ) / 2, ( myVMin + myVMax ) / 2);
   Standard_Real aDistance = aCenterPnt.Distance(thePoint);
   if (Precision::IsInfinite(aDistance))
   {
-    thePoint.SetCoord(anUMin - ( anUMax - anUMin ),
-                       aVMin - ( aVMax - aVMin ));
+    thePoint.SetCoord (myUMin - (myUMax - myUMin ),
+                       myVMin - (myVMax - myVMin ));
     return Standard_False;
   }
   else
   {
     Standard_Real anEpsilon = Epsilon(aDistance);
-    if (anEpsilon > Max(anUMax - anUMin, aVMax - aVMin))
+    if (anEpsilon > Max (myUMax - myUMin, myVMax - myVMin))
     {
       gp_Vec2d aLinVec(aCenterPnt, thePoint);
       gp_Dir2d aLinDir(aLinVec);
diff --git a/src/BRepClass/BRepClass_FaceExplorer.hxx b/src/BRepClass/BRepClass_FaceExplorer.hxx
index 3e404b8df4..bdb14b1d72 100644
--- a/src/BRepClass/BRepClass_FaceExplorer.hxx
+++ b/src/BRepClass/BRepClass_FaceExplorer.hxx
@@ -99,8 +99,8 @@ public:
 
 protected:
 
-
-
+  //! Computes UV bounds of a face
+  Standard_EXPORT void ComputeFaceBounds();
 
 
 private:
@@ -113,7 +113,10 @@ private:
   Standard_Integer myCurEdgeInd;
   Standard_Real myCurEdgePar;
 
-
+  Standard_Real myUMin;
+  Standard_Real myUMax;
+  Standard_Real myVMin;
+  Standard_Real myVMax;
 };
 
 
diff --git a/src/BRepClass/BRepClass_Intersector.cxx b/src/BRepClass/BRepClass_Intersector.cxx
index 847d877329..a141f56d05 100644
--- a/src/BRepClass/BRepClass_Intersector.cxx
+++ b/src/BRepClass/BRepClass_Intersector.cxx
@@ -37,7 +37,7 @@
 
 static 
 void RefineTolerance(const TopoDS_Face& aF,
-                     const BRepAdaptor_Curve2d& aC,
+                     const Geom2dAdaptor_Curve& aC,
                      const Standard_Real aT,
                      Standard_Real& aTolZ);
 
@@ -72,7 +72,7 @@ void  BRepClass_Intersector::Perform(const gp_Lin2d& L,
     return;
   }
   //
-  BRepAdaptor_Curve2d C(EE, F);
+  Geom2dAdaptor_Curve C(aC2D, deb, fin);
   //
   deb = C.FirstParameter();
   fin = C.LastParameter();
@@ -185,7 +185,7 @@ void  BRepClass_Intersector::LocalGeometry(const BRepClass_Edge& E,
 //purpose  : 
 //=======================================================================
 void RefineTolerance(const TopoDS_Face& aF,
-                     const BRepAdaptor_Curve2d& aC,
+                     const Geom2dAdaptor_Curve& aC,
                      const Standard_Real aT,
                      Standard_Real& aTolZ)
 {
diff --git a/src/IntTools/IntTools_FClass2d.cxx b/src/IntTools/IntTools_FClass2d.cxx
index 33833d944b..49dd72bf3d 100644
--- a/src/IntTools/IntTools_FClass2d.cxx
+++ b/src/IntTools/IntTools_FClass2d.cxx
@@ -67,7 +67,7 @@ IntTools_FClass2d::IntTools_FClass2d()
 //=======================================================================
 IntTools_FClass2d::IntTools_FClass2d(const TopoDS_Face& aFace,
 				     const Standard_Real TolUV) 
-: Toluv(TolUV), Face(aFace)  
+: Toluv(TolUV), Face(aFace)
 {
   Init(Face, Toluv);
 }
@@ -662,8 +662,12 @@ TopAbs_State IntTools_FClass2d::Perform
 	aFCTol = (!bUIn) ? aURes : aVRes;
       }
       //
-      BRepClass_FaceClassifier aClassifier;
-      aClassifier.Perform(Face,Puv,aFCTol);
+
+      if (myFExplorer.get() == NULL)
+        myFExplorer.reset (new BRepClass_FaceExplorer (Face));
+
+      BRepClass_FClassifier aClassifier;
+      aClassifier.Perform(*myFExplorer, Puv, aFCTol);
       aStatus = aClassifier.State();
     }
     
@@ -779,8 +783,12 @@ TopAbs_State IntTools_FClass2d::TestOnRestriction
       }
     }
     else {  //-- TabOrien(1)=-1  Wrong  Wire 
-      BRepClass_FaceClassifier aClassifier;
-      aClassifier.Perform(Face,Puv,Tol);
+
+      if (myFExplorer.get() == NULL)
+        myFExplorer.reset (new BRepClass_FaceExplorer (Face));
+
+      BRepClass_FClassifier aClassifier;
+      aClassifier.Perform(*myFExplorer, Puv, Tol);
       aStatus = aClassifier.State();
     }
     
diff --git a/src/IntTools/IntTools_FClass2d.hxx b/src/IntTools/IntTools_FClass2d.hxx
index 1d0b0a4af0..bc838fd7fb 100644
--- a/src/IntTools/IntTools_FClass2d.hxx
+++ b/src/IntTools/IntTools_FClass2d.hxx
@@ -21,16 +21,18 @@
 #include <Standard_DefineAlloc.hxx>
 #include <Standard_Handle.hxx>
 
+#include <BRepClass_FaceExplorer.hxx>
 #include <BRepTopAdaptor_SeqOfPtr.hxx>
 #include <TColStd_SequenceOfInteger.hxx>
 #include <Standard_Real.hxx>
 #include <TopoDS_Face.hxx>
 #include <Standard_Boolean.hxx>
 #include <TopAbs_State.hxx>
+#include <memory>
+
 class TopoDS_Face;
 class gp_Pnt2d;
 
-
 //! Class provides an algorithm to classify a 2d Point
 //! in 2d space of face using boundaries of the face.
 class IntTools_FClass2d 
@@ -108,6 +110,15 @@ private:
   Standard_Real Vmax;
   Standard_Boolean myIsHole;
 
+#ifdef _MSC_VER
+#if _MSC_VER < 1600
+  mutable std::auto_ptr<BRepClass_FaceExplorer> myFExplorer;
+#else
+  mutable std::unique_ptr<BRepClass_FaceExplorer> myFExplorer;
+#endif
+#else
+  mutable std::unique_ptr<BRepClass_FaceExplorer> myFExplorer;
+#endif
 
 };
 
diff --git a/tests/perf/modalg/bug30670 b/tests/perf/modalg/bug30670
new file mode 100644
index 0000000000..ab2d39ec56
--- /dev/null
+++ b/tests/perf/modalg/bug30670
@@ -0,0 +1,32 @@
+puts "==============================================================="
+puts "0030670: Modeling Algorithms - Performance improvement of Boolean Operations algorithm"
+puts "==============================================================="
+puts ""
+
+autodisplay 0
+restore [locate_data_file bug30670_prisms.brep] c
+
+bglue 1
+bfuzzyvalue 0
+set exp [explode c]
+bclearobjects
+bcleartools
+baddobjects c_1
+eval baddtools [lrange $exp 1 end]
+
+dchrono fillds reset
+dchrono fillds start
+bfillds 
+dchrono fillds stop counter FILLER
+
+dchrono fuse reset
+dchrono fuse start
+bbop result 1
+dchrono fuse stop counter BUILDER
+
+bglue 0
+
+checknbshapes result -wire 12686 -face 12598 -shell 1 -solid 1 -t
+checkprops result -s 1.34932e+06 -v 2.60155e+07
+
+checkview -display result -2d -path ${imagedir}/${test_image}.png