0029301: Improve performance of Boolean Operations
authoremv <emv@opencascade.com>
Wed, 8 Nov 2017 06:16:35 +0000 (09:16 +0300)
committerbugmaster <bugmaster@opencascade.com>
Tue, 14 Nov 2017 12:57:00 +0000 (15:57 +0300)
Improve performance of Boolean operations algorithm by:
- Improving the check of Same Domain faces (BOPAlgo_Builder::FillSameDomainFaces());
- Faster rejection of outer faces for solids using Bounding Box classification first (BOPAlgo_Builder::FillIn3DParts());
- Using IncAllocator for local containers.

Quality improvement has been made in BOPAlgo_PaveFiller class:
1. Method IsExistingPaveBlock() has been corrected to provide the correct edge tolerance and to obtain valid intermediate results in the test case "boolean gdml_private ZH3".
   New test case have been added to verify this improvement (bugs modalg_7 bug29301).
2. Method PutClosingPaveOnCurve() has been corrected to use the tolerance of the pave put on the bound for checking curve on closeness.
   Additional check for the curve to have valid range after addition of the pave on the other end has been added to prevent considering the small curves (covered by vertex tolerance) as closed ones.
   As a result of this modification the test case boolean gdml_public B2 has been fixed (TODO removed).

Adjustment of the test cases to current behavior:
- boolean bopcommon_complex J1 - the produced result was incorrect as it was self-interfered. There should be no common in this case.
- offset shape_type_i_c ZZ1 - the incorrect result is now produced instead of null shape.

src/BOPAlgo/BOPAlgo_Builder_2.cxx
src/BOPAlgo/BOPAlgo_Builder_3.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_6.cxx
tests/boolean/bopcommon_complex/J1
tests/boolean/gdml_public/B2
tests/bugs/modalg_7/bug29301 [new file with mode: 0644]
tests/offset/shape_type_i_c/ZZ1

index b067c2b..1a6ec70 100644 (file)
@@ -49,6 +49,7 @@
 #include <BRep_Tool.hxx>
 #include <GeomAdaptor_Surface.hxx>
 #include <GeomLib.hxx>
+#include <NCollection_IncAllocator.hxx>
 #include <Precision.hxx>
 #include <IntTools_Context.hxx>
 #include <TopExp_Explorer.hxx>
 #include <TopoDS_Shape.hxx>
 #include <TopoDS_Vertex.hxx>
 
-//
-static
-  Standard_Boolean HasPaveBlocksOnIn(const BOPDS_FaceInfo& aFI1,
-                                     const BOPDS_FaceInfo& aFI2);
+#include <algorithm>
 //
 static
   TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
                              const BOPCol_DataMapOfShapeListOfShape& theImages,
                              Handle(IntTools_Context)& theCtx);
-//
-typedef BOPCol_NCVector<TopoDS_Shape> BOPAlgo_VectorOfShape;
-//
-typedef BOPCol_NCVector<BOPAlgo_VectorOfShape> \
-  BOPAlgo_VectorOfVectorOfShape;
-//
-typedef NCollection_IndexedDataMap\
-  <BOPTools_Set, Standard_Integer, BOPTools_SetMapHasher> \
-    BOPAlgo_IndexedDataMapOfSetInteger;
-//
+
 //=======================================================================
 //class    : BOPAlgo_PairOfShapeBoolean
 //purpose  : 
@@ -480,176 +469,199 @@ void BOPAlgo_Builder::BuildSplitFaces()
   //
   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope t
 }
+
+//=======================================================================
+//function : AddEdgeSet
+//purpose  : 
+//=======================================================================
+typedef
+  NCollection_IndexedDataMap<BOPTools_Set,
+                             BOPCol_ListOfShape,
+                             BOPTools_SetMapHasher> BOPAlgo_IndexedDataMapOfSetListOfShape;
+
+static void AddEdgeSet(const TopoDS_Shape& theS,
+                       BOPAlgo_IndexedDataMapOfSetListOfShape& theMap,
+                       const Handle(NCollection_BaseAllocator)& theAllocator)
+{
+  // Make set
+  BOPTools_Set aSE;
+  aSE.Add(theS, TopAbs_EDGE);
+  // Add set to the map, keeping connection to the shape
+  BOPCol_ListOfShape* pLF = theMap.ChangeSeek(aSE);
+  if (!pLF)
+    pLF = &theMap(theMap.Add(aSE, BOPCol_ListOfShape(theAllocator)));
+  pLF->Append(theS);
+}
+
 //=======================================================================
 //function : FillSameDomainFaces
 //purpose  : 
 //=======================================================================
 void BOPAlgo_Builder::FillSameDomainFaces()
 {
-  Standard_Boolean bFlag;
-  Standard_Integer i, j, k, aNbFFs, nF1, nF2;
-  Handle(NCollection_BaseAllocator) aAllocator;
-  BOPCol_ListIteratorOfListOfShape aItF;
-  BOPCol_MapOfShape aMFence;
-  BOPAlgo_IndexedDataMapOfSetInteger aIDMSS;
-  BOPAlgo_VectorOfVectorOfShape aVVS;
-  //
-  const BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
-  //
-  aNbFFs=aFFs.Extent();
-  if (!aNbFFs) {
+  // It is necessary to analyze all Face/Face intersections
+  // and find all faces with equal sets of edges
+  const BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
+  Standard_Integer aNbFFs = aFFs.Extent();
+  if (!aNbFFs)
     return;
+
+  Handle(NCollection_BaseAllocator) aAllocator = new NCollection_IncAllocator;
+
+  // Vector to store the indices of faces for future sorting
+  // for making the SD face for the group from the face with
+  // smallest index in Data structure
+  BOPCol_NCVector<Standard_Integer> aFIVec(256, aAllocator);
+  // Fence map to avoid repeated checks of the same face.
+  BOPCol_MapOfInteger aMFence(1, aAllocator);
+
+  // Fill the vector with indices of faces
+  for (Standard_Integer i = 0; i < aNbFFs; ++i)
+  {
+    const BOPDS_InterfFF& aFF = aFFs(i);
+    // get indices
+    Standard_Integer nF[2];
+    aFF.Indices(nF[0], nF[1]);
+    // store indices to the vector
+    for (Standard_Integer j = 0; j < 2; ++j)
+    {
+      if (!myDS->HasFaceInfo(nF[j]))
+        continue;
+
+      if (!aMFence.Add(nF[j]))
+        continue;
+
+      aFIVec.Append1() = nF[j];
+    }
   }
-  //
-  for (i=0; i<aNbFFs; ++i) {
-    const BOPDS_InterfFF& aFF=aFFs(i);
-    aFF.Indices(nF1, nF2);
-    //
-    if (!myDS->HasFaceInfo(nF1) || !myDS->HasFaceInfo(nF2) ) {
-      continue;
+
+  // Sort the indices
+  std::sort(aFIVec.begin(), aFIVec.end());
+
+  // Data map of set of edges with all faces having this set
+  NCollection_IndexedDataMap<BOPTools_Set,
+                             BOPCol_ListOfShape,
+                             BOPTools_SetMapHasher> anESetFaces(1, aAllocator);
+  // Map of planar bounded faces. If such faces have the same Edge set
+  // they are considered Same domain, without additional check.
+  BOPCol_MapOfShape aMFPlanar(1, aAllocator);
+
+  Standard_Integer aNbF = aFIVec.Extent();
+  for (Standard_Integer i = 0; i < aNbF; ++i)
+  {
+    const Standard_Integer nF = aFIVec(i);
+    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
+    const TopoDS_Shape& aF = aSI.Shape();
+
+    Standard_Boolean bCheckPlanar = Standard_False;
+    {
+      // At this stage, context should contain adaptor for all intersected faces,
+      // so getting a type of the underlying surface should be done at no cost.
+      if (myContext->SurfaceAdaptor(TopoDS::Face(aF)).GetType() == GeomAbs_Plane)
+      {
+        // Check bounding box of the face - it should not be open in any side
+        const Bnd_Box& aBox = aSI.Box();
+        bCheckPlanar = !(aBox.IsOpenXmin() || aBox.IsOpenXmax() ||
+                         aBox.IsOpenYmin() || aBox.IsOpenYmax() ||
+                         aBox.IsOpenZmin() || aBox.IsOpenZmax());
+      }
     }
-    //
-    const BOPDS_FaceInfo& aFI1=myDS->FaceInfo(nF1);
-    const BOPDS_FaceInfo& aFI2=myDS->FaceInfo(nF2);
-    //
-    const TopoDS_Shape& aF1=myDS->Shape(nF1);
-    const TopoDS_Shape& aF2=myDS->Shape(nF2);
-    //
-    bFlag=HasPaveBlocksOnIn(aFI1, aFI2);
-    bFlag=bFlag && (mySplits.IsBound(aF1) && mySplits.IsBound(aF2));
-    //
-    if (bFlag) {
-      for (k=0; k<2; ++k) {
-        const TopoDS_Shape& aF=(!k) ? aF1 : aF2;
-        const BOPCol_ListOfShape& aLF=mySplits.Find(aF);
-        //
-        aItF.Initialize(aLF);
-        for (; aItF.More(); aItF.Next()) {
-          const TopoDS_Shape& aFx=aItF.Value();
-          //
-          if (aMFence.Add(aFx)) {
-            BOPTools_Set aSTx;
-            //
-            aSTx.Add(aFx, TopAbs_EDGE);
-            //
-            if (!aIDMSS.Contains(aSTx)) {
-              BOPAlgo_VectorOfShape& aVS=aVVS.Append1(); 
-              aVS.Append(aFx);
-              //
-              j=aVVS.Extent()-1;
-              aIDMSS.Add (aSTx, j);
-            }
-            else {
-              j=aIDMSS.ChangeFromKey(aSTx);
-              BOPAlgo_VectorOfShape& aVS=aVVS(j);
-              aVS.Append(aFx);
-            }
-          }
-        }
+
+    const BOPCol_ListOfShape* pLFSp = mySplits.Seek(aF);
+    if (pLFSp)
+    {
+      BOPCol_ListIteratorOfListOfShape aItLF(*pLFSp);
+      for (; aItLF.More(); aItLF.Next())
+      {
+        AddEdgeSet(aItLF.Value(), anESetFaces, aAllocator);
+        if (bCheckPlanar)
+          aMFPlanar.Add(aItLF.Value());
       }
-    }// if (bFlag) {
-    else {// if (!bFlag) 
-      BOPTools_Set aST1, aST2;
-      //
-      aST1.Add(aF1, TopAbs_EDGE);
-      aST2.Add(aF2, TopAbs_EDGE);
-      //
-      if (aST1.IsEqual(aST2)) {
-        if (!aIDMSS.Contains(aST1)) {
-          BOPAlgo_VectorOfShape& aVS=aVVS.Append1(); 
-          if (aMFence.Add(aF1)) {
-            aVS.Append(aF1);
-          }
-          if (aMFence.Add(aF2)) {
-            aVS.Append(aF2);
-          }
-          //
-          k=aVVS.Extent()-1;
-          aIDMSS.Add (aST1, k);
-        }
-        else {
-          k=aIDMSS.ChangeFromKey(aST1);
-          BOPAlgo_VectorOfShape& aVS=aVVS(k);
-          if (aMFence.Add(aF1)) {
-            aVS.Append(aF1);
-          }
-          if (aMFence.Add(aF2)) {
-            aVS.Append(aF2);
-          }
-        }
-      }//if (aST1.IsEqual(aST2)) {
-    }// else {// if (!bFlag) 
-    //
-  }// for (i=0; i<aNbFFs; ++i) {
-  //
-  aIDMSS.Clear();
-  //
-  Standard_Boolean bFlagSD;
-  Standard_Integer aNbVPSB, aNbVVS, aNbF, aNbF1;
+    }
+    else
+    {
+      AddEdgeSet(aF, anESetFaces, aAllocator);
+      if (bCheckPlanar)
+        aMFPlanar.Add(aF);
+    }
+  }
+
+  // Store pairs of faces with equal set of edges to check if they are really Same Domain
   BOPAlgo_VectorOfPairOfShapeBoolean aVPSB;
-  //
-  aNbVVS=aVVS.Extent();
-  for (i=0; i<aNbVVS; ++i) {
-    const BOPAlgo_VectorOfShape& aVS=aVVS(i);
-    aNbF=aVS.Extent();
-    if (aNbF<2) {
+
+  // Back and forth map of SD faces to make the blocks
+  BOPCol_IndexedDataMapOfShapeListOfShape aDMSLS(1, aAllocator);
+
+  Standard_Integer aNbSets = anESetFaces.Extent();
+  for (Standard_Integer i = 1; i <= aNbSets; ++i)
+  {
+    const BOPCol_ListOfShape& aLF = anESetFaces(i);
+    if (aLF.Extent() < 2)
       continue;
-    }
-    //
-    aNbF1=aNbF-1;
-    for (j=0; j<aNbF1; ++j) {
-      const TopoDS_Shape& aFj=aVS(j);
-      for (k=j+1; k<aNbF; ++k) {
-        const TopoDS_Shape& aFk=aVS(k);
-        BOPAlgo_PairOfShapeBoolean& aPSB=aVPSB.Append1();
-        aPSB.Shape1()=aFj;
-        aPSB.Shape2()=aFk;
+
+    // All possible pairs from <aLF> should be checked
+    BOPCol_ListIteratorOfListOfShape aIt1(aLF);
+    for (; aIt1.More(); aIt1.Next())
+    {
+      const TopoDS_Shape& aF1 = aIt1.Value();
+      Standard_Boolean bCheckPlanar = aMFPlanar.Contains(aF1);
+
+      BOPCol_ListIteratorOfListOfShape aIt2 = aIt1;
+      for (aIt2.Next(); aIt2.More(); aIt2.Next())
+      {
+        const TopoDS_Shape& aF2 = aIt2.Value();
+        if (bCheckPlanar && aMFPlanar.Contains(aF2))
+        {
+          // Consider planar bounded faces as Same Domain without additional check
+          BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>(aF1, aF2, aDMSLS, aAllocator);
+          continue;
+        }
+        // Add pair for analysis
+        BOPAlgo_PairOfShapeBoolean& aPSB = aVPSB.Append1();
+        aPSB.Shape1() = aF1;
+        aPSB.Shape2() = aF2;
         aPSB.SetFuzzyValue(myFuzzyValue);
         aPSB.SetProgressIndicator(myProgressIndicator);
       }
     }
   }
+
   //================================================================
+  // Perform analysis
   BOPAlgo_BuilderSDFaceCnt::Perform(myRunParallel, aVPSB, myContext);
   //================================================================
-  aAllocator=
-    NCollection_BaseAllocator::CommonBaseAllocator();
-  BOPCol_IndexedDataMapOfShapeListOfShape aDMSLS(100, aAllocator);
+
   NCollection_List<BOPCol_ListOfShape> aMBlocks(aAllocator);
-  //
-  aNbVPSB=aVPSB.Extent();
-  for (i=0; i<aNbVPSB; ++i) {
-    BOPAlgo_PairOfShapeBoolean& aPSB=aVPSB(i);
-    bFlagSD=aPSB.Flag();
-    if (bFlagSD) {
-      const TopoDS_Shape& aFj=aPSB.Shape1();
-      const TopoDS_Shape& aFk=aPSB.Shape2();
-      BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>(aFj, aFk, aDMSLS, aAllocator);
-    }
+  // Fill map with SD faces to make the blocks
+  Standard_Integer aNbPairs = aVPSB.Extent();
+  for (Standard_Integer i = 0; i < aNbPairs; ++i)
+  {
+    BOPAlgo_PairOfShapeBoolean& aPSB = aVPSB(i);
+    if (aPSB.Flag())
+      BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>
+       (aPSB.Shape1(), aPSB.Shape2(), aDMSLS, aAllocator);
   }
   aVPSB.Clear();
-  //
-  // 2. Make blocks
-  BOPAlgo_Tools::MakeBlocks<TopoDS_Shape, TopTools_ShapeMapHasher>(aDMSLS, aMBlocks, aAllocator);
-  //
-  // 3. Fill same domain faces map -> aMSDF
+
+  // Make blocks of SD faces using the back and forth map
+  BOPAlgo_Tools::MakeBlocks<TopoDS_Shape, TopTools_ShapeMapHasher>
+    (aDMSLS, aMBlocks, aAllocator);
+
+  // Fill same domain faces map
   NCollection_List<BOPCol_ListOfShape>::Iterator aItB(aMBlocks);
-  for (; aItB.More(); aItB.Next()) {
+  for (; aItB.More(); aItB.Next())
+  {
     const BOPCol_ListOfShape& aLSD = aItB.Value();
-    //
-    const TopoDS_Shape& aFSD1=aLSD.First();
-    aItF.Initialize(aLSD);
-    for (; aItF.More(); aItF.Next()) {
-      const TopoDS_Shape& aFSD=aItF.Value();
+    // First face will be SD face for all faces in the group
+    const TopoDS_Shape& aFSD1 = aLSD.First();
+    BOPCol_ListIteratorOfListOfShape aItLF(aLSD);
+    for (; aItLF.More(); aItLF.Next())
+    {
+      const TopoDS_Shape& aFSD = aItLF.Value();
       myShapesSD.Bind(aFSD, aFSD1);
-      //
-      // If the face has no splits but are SD face,
-      // it is considered as splitted face
-      if (!mySplits.IsBound(aFSD)) {
-        BOPCol_ListOfShape aLS;
-        aLS.Append(aFSD);
-        mySplits.Bind(aFSD, aLS);
-      }
+      // If the face has no splits but have an SD face, it is considered as being split
+      if (!mySplits.IsBound(aFSD))
+        mySplits.Bound(aFSD, BOPCol_ListOfShape())->Append(aFSD);
     }
   }
   aMBlocks.Clear();
@@ -760,42 +772,6 @@ void BOPAlgo_Builder::FillImagesFaces1()
   }
 }
 //=======================================================================
-//function :HasPaveBlocksOnIn
-//purpose  : 
-//=======================================================================
-Standard_Boolean HasPaveBlocksOnIn(const BOPDS_FaceInfo& aFI1,
-                                   const BOPDS_FaceInfo& aFI2)
-{
-  Standard_Boolean bRet;
-  Standard_Integer i, aNbPB;
-  //
-  bRet=Standard_False;
-  const BOPDS_IndexedMapOfPaveBlock& aMPBOn1 = aFI1.PaveBlocksOn();
-  const BOPDS_IndexedMapOfPaveBlock& aMPBIn1 = aFI1.PaveBlocksIn();
-  //
-  const BOPDS_IndexedMapOfPaveBlock& aMPBOn2 = aFI2.PaveBlocksOn();
-  aNbPB = aMPBOn2.Extent();
-  for (i = 1; i <= aNbPB; ++i) {
-    const Handle(BOPDS_PaveBlock)& aPB = aMPBOn2(i);
-    bRet = aMPBOn1.Contains(aPB) || aMPBIn1.Contains(aPB);
-    if (bRet) {
-      return bRet;
-    }
-  }
-  //
-  const BOPDS_IndexedMapOfPaveBlock& aMPBIn2 = aFI2.PaveBlocksIn();
-  aNbPB = aMPBIn2.Extent();
-  for (i = 1; i <= aNbPB; ++i) {
-    const Handle(BOPDS_PaveBlock)& aPB = aMPBIn2(i);
-    bRet = aMPBOn1.Contains(aPB) || aMPBIn1.Contains(aPB);
-    if (bRet) {
-      return bRet;
-    }
-  }
-  return bRet;
-}
-
-//=======================================================================
 //function : BuildDraftFace
 //purpose  : Build draft faces, updating the bounding edges,
 //           according to the information stored into the <theImages> map
index a572861..31ff3a3 100644 (file)
@@ -65,6 +65,7 @@
 //
 #include <BOPAlgo_BuilderSolid.hxx>
 #include <NCollection_Array1.hxx>
+#include <NCollection_IncAllocator.hxx>
 
 #include <algorithm>
 #include <BOPAlgo_Algo.hxx>
@@ -251,99 +252,128 @@ class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo  {
 //=======================================================================
 void BOPAlgo_FillIn3DParts::Perform() 
 {
-  Handle(NCollection_BaseAllocator) aAlr1;
   BOPAlgo_Algo::UserBreak();
-  //  
-  Standard_Integer aNbFP, k, nFP, iIsIN;
-  Standard_Real aTolPC;
-  BOPCol_ListIteratorOfListOfInteger aItLI;
-  BOPCol_ListIteratorOfListOfShape aItLS;
-  BOPCol_BoxBndTreeSelector aSelector; 
-  //
-  aAlr1=
-    NCollection_BaseAllocator::CommonBaseAllocator();
-  //
-  BOPCol_ListOfShape aLCBF(aAlr1);
-  BOPCol_MapOfShape aMFDone(100, aAlr1);
-  BOPCol_IndexedMapOfShape aME(100, aAlr1);
-  BOPCol_IndexedMapOfShape aMF(100, aAlr1);
-  BOPCol_IndexedDataMapOfShapeListOfShape aMEFP(100, aAlr1);
-  BOPCol_IndexedDataMapOfShapeListOfShape aMEF(100, aAlr1);
-  //
-  aTolPC=Precision::Confusion();
+
   myLFIN.Clear();
-  BOPAlgo_VectorOfShapeBox& aVSB=*myVSB;
-  //
-  // 1. aMEF - EF map for myDraftSolid
-  BOPTools::MapShapesAndAncestors(myDraftSolid, 
-                                  TopAbs_EDGE, 
-                                  TopAbs_FACE, 
-                                  aMEF); 
-  
-  //
-  // 2. Faces from myDraftSolid and its own internal faces => aMF 
-  BOPTools::MapShapes(myDraftSolid, TopAbs_FACE, aMF);
-  aItLS.Initialize(myLIF);
-  for (; aItLS.More(); aItLS.Next()) {
-    const TopoDS_Shape& aFI=aItLS.Value();
-    aMF.Add(aFI);
-  }
-  // aME - Edges from DraftSolid [i.e. edges to stop]
+
+  Handle(NCollection_BaseAllocator) aAlr1 = new NCollection_IncAllocator;
+
+  BOPAlgo_VectorOfShapeBox& aVSB = *myVSB;
+
+  // 1. Fill maps of edges and faces of myDraftSolid
+  BOPCol_IndexedMapOfShape aME(1, aAlr1), aMF(1, aAlr1);
   BOPTools::MapShapes(myDraftSolid, TopAbs_EDGE, aME);
-  //
-  // 3. Select boxes of faces that are not out of aBoxS
-  aSelector.Clear();
+  BOPTools::MapShapes(myDraftSolid, TopAbs_FACE, aMF);
+  // Check if the Draft Solid contains any faces
+  Standard_Boolean bIsEmpty = aMF.IsEmpty();
+  // Add own internal faces of myDraftSolid into aMF
+  BOPCol_ListIteratorOfListOfShape aItLS(myLIF);
+  for (; aItLS.More(); aItLS.Next())
+    aMF.Add(aItLS.Value());
+
+  // 2. Select boxes of faces that are not out of aBoxS
+  BOPCol_BoxBndTreeSelector aSelector;
   aSelector.SetBox(myBoxS);
   //
-  aNbFP=myBBTree->Select(aSelector);
-  const BOPCol_ListOfInteger& aLIFPx=aSelector.Indices();
+  myBBTree->Select(aSelector);
+  const BOPCol_ListOfInteger& aLIFP = aSelector.Indices();
   //
-  // 4. aIVec, aLIFP -  faces to process
-  BOPCol_ListOfInteger aLIFP(aAlr1); 
+  // 3. aIVec - faces to process.
+  //    Filter the selected faces with faces of the solid.
   BOPCol_NCVector<Standard_Integer> aIVec(256, aAlr1);
-  //
-  k=0;
-  aItLI.Initialize(aLIFPx);
+
+  BOPCol_ListIteratorOfListOfInteger aItLI(aLIFP);
   for (; aItLI.More(); aItLI.Next()) {
-    nFP=aItLI.Value();
-    const TopoDS_Shape& aFP=aVSB(nFP).Shape();
-    if (!aMF.Contains(aFP)) {
-      MapEdgesAndFaces(aFP, aMEFP, aAlr1);
-      aLIFP.Append(nFP);
-      aIVec.Append1()=nFP;
-      ++k;
-    }
+    Standard_Integer nFP = aItLI.Value();
+    const TopoDS_Shape& aFP = aVSB(nFP).Shape();
+    if (!aMF.Contains(aFP))
+      aIVec.Append1() = nFP;
   }
-  aNbFP=k;
-  //
-  // sort indices
-  std::sort(aIVec.begin(), aIVec.end());
-  //
-  // 5. Collect faces that are IN mySolid [ myLFIN ]
-  for (k=0; k<aNbFP; ++k) {
-    nFP = aIVec(k);
-    const BOPAlgo_ShapeBox& aSBF=aVSB(nFP);
-    const TopoDS_Face& aFP=(*(TopoDS_Face*)&aSBF.Shape());
-    //
-    if (!aMFDone.Add(aFP)) {
+
+  // 4. Classify faces relatively solid.
+  //    Store faces that are IN mySolid into <myLFIN>
+
+  Standard_Integer k, aNbFP = aIVec.Extent();
+  // Sort indices if necessary
+  if (aNbFP > 1)
+    std::sort(aIVec.begin(), aIVec.end());
+
+  if (bIsEmpty)
+  {
+    // The Draft solid is empty as it does not contain any faces.
+    // It could happen when the input solid consists of INTERNAL faces only.
+    // Classification of any point relatively empty solid would always give IN status.
+    // Thus, we consider all selected faces as IN without real classification.
+    for (k = 0; k < aNbFP; ++k)
+      myLFIN.Append(aVSB(aIVec(k)).Shape());
+
+    return;
+  }
+
+  // Prepare EF map of faces to process for building connexity blocks
+  BOPCol_IndexedDataMapOfShapeListOfShape aMEFP(1, aAlr1);
+  if (aNbFP > 1)
+  {
+    for (k = 0; k < aNbFP; ++k)
+      MapEdgesAndFaces(aVSB(aIVec(k)).Shape(), aMEFP, aAlr1);
+  }
+
+  // Map of Edge-Face connection, necessary for solid classification.
+  // It will be filled when first classification is performed.
+  BOPCol_IndexedDataMapOfShapeListOfShape aMEFDS(1, aAlr1);
+
+  // Fence map to avoid processing of the same faces twice
+  BOPCol_MapOfShape aMFDone(1, aAlr1);
+
+  for (k = 0; k < aNbFP; ++k)
+  {
+    Standard_Integer nFP = aIVec(k);
+    const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVSB(nFP).Shape());
+    if (!aMFDone.Add(aFP))
       continue;
-    }
-    //
-    iIsIN=BOPTools_AlgoTools::IsInternalFace
-      (aFP, myDraftSolid, aMEF, aTolPC, myContext);
-    //
+
     // Make connexity blocks of faces, avoiding passing through the
-    // borders of the solid.
-    // It helps to reduce significantly the number of classified faces.
-    aLCBF.Clear();
+    // borders of the solid. It helps to reduce significantly the
+    // number of classified faces.
+    BOPCol_ListOfShape aLCBF(aAlr1);
     MakeConnexityBlock(aFP, aME, aMEFP, aMFDone, aLCBF);
-    //
-    if (iIsIN) {
+
+    // First, try fast classification of the whole block by additional
+    // check on bounding boxes - check that bounding boxes of all vertices
+    // of the block interfere with the box of the solid.
+    // If not, the faces are out.
+    Standard_Boolean bOut = Standard_False;
+    aItLS.Initialize(aLCBF);
+    for (; aItLS.More() && !bOut; aItLS.Next())
+    {
+      TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
+      for (; anExpV.More() && !bOut; anExpV.Next())
+      {
+        const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
+        Bnd_Box aBBV;
+        aBBV.Add(BRep_Tool::Pnt(aV));
+        aBBV.SetGap(BRep_Tool::Tolerance(aV));
+        bOut = myBoxS.IsOut(aBBV);
+      }
+    }
+
+    if (bOut)
+      continue;
+
+    if (aMEFDS.IsEmpty())
+      // Fill EF map for myDraftSolid
+      BOPTools::MapShapesAndAncestors(myDraftSolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
+
+    // All vertices are interfere with the solids box, run classification.
+    Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
+      (aFP, myDraftSolid, aMEFDS, Precision::Confusion(), myContext);
+    if (bIsIN)
+    {
       aItLS.Initialize(aLCBF);
       for (; aItLS.More(); aItLS.Next())
         myLFIN.Append(aItLS.Value());
     }
-  } // for (k=0; k<aNbFP; ++k) {
+  }
 }
 //=======================================================================
 // function: MapEdgesAndFaces
@@ -385,6 +415,8 @@ void BOPAlgo_FillIn3DParts::MakeConnexityBlock
 {
   // Add start element
   theLCB.Append(theFStart);
+  if (theMEF.IsEmpty())
+    return;
 
   BOPCol_ListIteratorOfListOfShape aItCB(theLCB);
   for (; aItCB.More(); aItCB.Next())
@@ -404,8 +436,10 @@ void BOPAlgo_FillIn3DParts::MakeConnexityBlock
         if (theMEAvoid.Contains(aE))
           continue;
 
-        const BOPCol_ListOfShape& aLF = theMEF.FindFromKey(aE);
-        BOPCol_ListIteratorOfListOfShape aItLF(aLF);
+        const BOPCol_ListOfShape* pLF = theMEF.Seek(aE);
+        if (!pLF)
+          continue;
+        BOPCol_ListIteratorOfListOfShape aItLF(*pLF);
         for (; aItLF.More(); aItLF.Next())
         {
           const TopoDS_Shape& aFx = aItLF.Value();
index b469921..664ff65 100644 (file)
@@ -48,6 +48,7 @@
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
 #include <BRep_TEdge.hxx>
+#include <BRepLib.hxx>
 #include <BRepAdaptor_Curve.hxx>
 #include <BRepAdaptor_Surface.hxx>
 #include <BRepBndLib.hxx>
@@ -1348,6 +1349,9 @@ Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
       aTolCheck = Max(aTolE, aTol) + myFuzzyValue;
       iFlag = myContext->ComputePE(aPm, aTolCheck, aE, aTx, aDist);
       if (!iFlag) {
+        if (aDist > aTolE)
+          // Update tolerance of the edge
+          UpdateEdgeTolerance(nE, aDist);
         return bRet;
       }
     }
@@ -2460,54 +2464,74 @@ void BOPAlgo_PaveFiller::UpdateExistingPaveBlocks
 //=======================================================================
 void BOPAlgo_PaveFiller::PutClosingPaveOnCurve(BOPDS_Curve& aNC)
 {
-  Standard_Boolean bIsClosed, bHasBounds, bAdded;
-  Standard_Integer nVC, j;
-  Standard_Real aT[2], aTC, dT, aTx;
-  gp_Pnt aP[2] ; 
-  BOPDS_Pave aPVx;
-  BOPDS_ListIteratorOfListOfPave aItLP;
-  //
-  const IntTools_Curve& aIC=aNC.Curve();
-  const Handle(Geom_Curve)& aC3D=aIC.Curve();
-  if(aC3D.IsNull()) {
-    return;
-  }
-  //
-  bIsClosed=IntTools_Tools::IsClosed(aC3D);
-  if (!bIsClosed) {
+  const IntTools_Curve& aIC = aNC.Curve();
+  const Handle(Geom_Curve)& aC3D = aIC.Curve();
+  // check 3d curve
+  if (aC3D.IsNull())
     return;
-  }
-  //
-  bHasBounds=aIC.HasBounds ();
-  if (!bHasBounds){
+
+  // check bounds
+  if (!aIC.HasBounds())
     return;
-  }
-  // 
-  bAdded=Standard_False;
-  dT=Precision::PConfusion();
-  aIC.Bounds (aT[0], aT[1], aP[0], aP[1]);
-  //
-  Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
-  BOPDS_ListOfPave& aLP=aPB->ChangeExtPaves();
-  //
-  aItLP.Initialize(aLP);
-  for (; aItLP.More() && !bAdded; aItLP.Next()) {
-    const BOPDS_Pave& aPC=aItLP.Value();
-    nVC=aPC.Index();
-    aTC=aPC.Parameter();
-    //
-    for (j=0; j<2; ++j) {
-      if (fabs(aTC-aT[j]) < dT) {
-        aTx=(!j) ? aT[1] : aT[0];
-        aPVx.SetIndex(nVC);
-        aPVx.SetParameter(aTx);
-        aLP.Append(aPVx);
-        //
-        bAdded=Standard_True;
+
+  // check closeness
+  Standard_Real aT[2];
+  gp_Pnt aP[2];
+  aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
+
+  // Find the pave which has been put at one of the ends
+  Standard_Integer nV = -1;
+  // Keep the opposite parameter
+  Standard_Real aTOp = 0.;
+
+  Standard_Boolean bFound = Standard_False;
+
+  Handle(BOPDS_PaveBlock)& aPB = aNC.ChangePaveBlock1();
+  BOPDS_ListOfPave& aLP = aPB->ChangeExtPaves();
+  BOPDS_ListIteratorOfListOfPave aItLP(aLP);
+  for (; aItLP.More() && !bFound; aItLP.Next())
+  {
+    const BOPDS_Pave& aPC = aItLP.Value();
+    Standard_Real aTC = aPC.Parameter();
+    for (Standard_Integer j = 0; j < 2; ++j)
+    {
+      if (Abs(aTC - aT[j]) < Precision::PConfusion())
+      {
+        nV = aPC.Index();
+        aTOp = (!j) ? aT[1] : aT[0];
+        bFound = Standard_True;
         break;
       }
     }
   }
+
+  if (!bFound)
+    return;
+
+  // Check if the curve is closed using the tolerance
+  // of found vertex
+  const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
+  const Standard_Real aTolV = BRep_Tool::Tolerance(aV);
+
+  Standard_Real aDist = aP[0].Distance(aP[1]);
+  if (aDist > aTolV)
+    return;
+
+  // Check if there will be valid range on the curve
+  Standard_Real aFirst, aLast;
+  if (!BRepLib::FindValidRange(GeomAdaptor_Curve(aIC.Curve()), aIC.Tolerance(),
+                               aT[0], aP[0], aTolV,
+                               aT[1], aP[1], aTolV,
+                               aFirst, aLast))
+  {
+    return;
+  }
+
+  // Add closing pave to the curve
+  BOPDS_Pave aPave;
+  aPave.SetIndex(nV);
+  aPave.SetParameter(aTOp);
+  aLP.Append(aPave);
 }
 //=======================================================================
 //function : PreparePostTreatFF
index cff26c5..1a41242 100755 (executable)
@@ -4,5 +4,4 @@ restore [locate_data_file b148] b
 bop a b
 bopcommon result
 
-checkprops result -s 0.000550102
-checkview -display result -2d -otherwise { a b } -s -path ${imagedir}/${test_image}.png
+checkprops result -s empty
index 8b4b3a2..501b2e9 100644 (file)
@@ -1,4 +1,3 @@
-puts "TODO OCC26018 ALL: Error : The area of result shape is"
 # test script for hole_full_prism_rect.prt.2.gdml file
 compound result
 
@@ -35,4 +34,5 @@ bcut sh48C48E0 sh467E330_copy sh48D1E70_copy; copy sh48C48E0 sh48C48E0_copy
 # result
 add sh48C48E0_copy result
 
-checkprops result -s 0
\ No newline at end of file
+checkprops result -s 2.13824e+006 -v 1.60388e+008
+checknbshapes result -vertex 10 -edge 15 -wire 9 -face 7 -shell 1 -solid 1
\ No newline at end of file
diff --git a/tests/bugs/modalg_7/bug29301 b/tests/bugs/modalg_7/bug29301
new file mode 100644 (file)
index 0000000..2c5c819
--- /dev/null
@@ -0,0 +1,27 @@
+puts "========"
+puts "OCC29301"
+puts "========"
+puts ""
+#################################################
+# Improve performance of Boolean Operations
+#################################################
+
+restore [locate_data_file bug29301_zh3.brep] cs
+
+explode cs
+
+bclearobjects
+bcleartools
+baddobjects cs_1
+baddtools cs_2
+bfillds
+bbuild result
+
+checkshape result
+checknbshapes result -vertex 5 -edge 10 -wire 5 -face 5 -shell 2 -solid 2
+checkprops result -s 4823.5 -v 10392.6
+if {![regexp "OK" [bopcheck result]]} {
+  puts "Error: the result is self-interfered"
+}
+
+checkview -display result -2d -path ${imagedir}/${test_image}.png
\ No newline at end of file
index f235788..8f6b93f 100755 (executable)
@@ -1,6 +1,5 @@
-puts "TODO OCC27414 ALL: Error: The command cannot be built"
-puts "TODO OCC27414 ALL: gives an empty result"
-puts "TODO OCC27414 ALL: TEST INCOMPLETE"
+puts "TODO CR27414 ALL: Error : The area of result shape is"
+puts "TODO CR27414 ALL: Error : The volume of result shape is"
 
 restore [locate_data_file bug26917_input_segfault.brep] s