0028775: Code duplication removal across the BOPAlgo_PaveFiller algorithm
authoremv <emv@opencascade.com>
Sat, 29 Apr 2017 22:09:36 +0000 (01:09 +0300)
committerbugmaster <bugmaster@opencascade.com>
Fri, 9 Jun 2017 10:01:32 +0000 (13:01 +0300)
The methods PerformVerticesEE() and PerformVerticesEF() of the class BOPAlgo_PaveFiller have been replaced with the new PerformNewVertices() method.

While splitting the Pave Blocks with extra paves, check that the new Pave Blocks have the valid intersection range. If the new Pave Block does not have such range do not create it and unify its vertices making SD vertex.

Re-computation of the Shrunk Data for the modified Pave Blocks. The new method BOPDS_DS::IsValidShrunkData(const Handle(BOPDS_PaveBlock)& thePB) has been implemented to check that the Shrunk Data of the Pave Block is still valid. It may become invalid in case the tolerance values of the vertices of the Pave Block have been modified.

The test case bugs/modalg_6/bug27448_2 has been marked as BAD, because it uses the invalid shapes as inputs for BOP.

Test cases for the issue 0028690.

22 files changed:
src/BOPAlgo/BOPAlgo_PaveFiller.cxx
src/BOPAlgo/BOPAlgo_PaveFiller.hxx
src/BOPAlgo/BOPAlgo_PaveFiller_1.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_2.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_3.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_6.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_9.cxx
src/BOPAlgo/BOPAlgo_Tools.cxx
src/BOPAlgo/BOPAlgo_Tools.hxx
src/BOPCol/BOPCol_IndexedDataMapOfShapeReal.hxx [new file with mode: 0644]
src/BOPCol/FILES
src/BOPDS/BOPDS_DS.cxx
src/BOPDS/BOPDS_DS.hxx
tests/bugs/modalg_1/bug10232
tests/bugs/modalg_2/bug472_3
tests/bugs/modalg_6/bug27448_2
tests/bugs/modalg_6/bug28690 [new file with mode: 0644]
tests/bugs/modalg_6/bug28690_1 [new file with mode: 0644]
tests/bugs/modalg_6/bug28690_2 [new file with mode: 0644]
tests/bugs/modalg_6/bug28690_3 [new file with mode: 0644]
tests/bugs/modalg_6/bug28775 [new file with mode: 0644]

index f94b89a..0ee5f44 100644 (file)
@@ -263,7 +263,6 @@ void BOPAlgo_PaveFiller::PerformInternal()
   }
   //
   UpdatePaveBlocksWithSDVertices();
-  myDS->UpdatePaveBlocks();
   // 11
   PerformEE();
   if (myErrorStatus) {
@@ -282,6 +281,7 @@ void BOPAlgo_PaveFiller::PerformInternal()
     return; 
   }
   UpdatePaveBlocksWithSDVertices();
+  UpdateInterfsWithSDVertices();
   //
   // 22
   PerformFF();
index ae0f0d8..7112894 100644 (file)
@@ -45,7 +45,9 @@
 #include <IntSurf_ListOfPntOn2S.hxx>
 #include <BOPCol_DataMapOfIntegerListOfInteger.hxx>
 #include <BOPDS_MapOfPaveBlock.hxx>
+#include <BOPDS_MapOfPair.hxx>
 #include <BOPDS_VectorOfCurve.hxx>
+#include <BOPDS_IndexedDataMapOfPaveBlockListOfInteger.hxx>
 #include <BOPCol_IndexedDataMapOfShapeInteger.hxx>
 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
 #include <BOPAlgo_GlueEnum.hxx>
@@ -147,6 +149,21 @@ protected:
   Standard_EXPORT virtual void PerformVV();
   
   Standard_EXPORT virtual void PerformVE();
+
+  //! Performs the intersection of the vertices with edges.
+  Standard_EXPORT void IntersectVE(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
+                                   const Standard_Boolean bAddInterfs = Standard_True);
+
+  //! Splits the Pave Blocks of the given edges with the extra paves.<br>
+  //! The method also builds the shrunk data for the new pave blocks and
+  //! in case there is no valid range on the pave block, the vertices of
+  //! this pave block will be united making SD vertex.<br>
+  //! Parameter <theAddInterfs> defines whether this interference will be added
+  //! into common table of interferences or not.<br>
+  //! If some of the Pave Blocks are forming the Common Blocks, the splits
+  //! of the Pave Blocks will also form a Common Block.
+  Standard_EXPORT void SplitPaveBlocks(const BOPCol_MapOfInteger& theMEdges,
+                                       const Standard_Boolean theAddInterfs);
   
   Standard_EXPORT virtual void PerformVF();
   
@@ -175,10 +192,11 @@ protected:
   Standard_EXPORT void FillShrunkData (Handle(BOPDS_PaveBlock)& thePB);
   
   Standard_EXPORT void FillShrunkData (const TopAbs_ShapeEnum theType1, const TopAbs_ShapeEnum theType2);
-  
-  Standard_EXPORT Standard_Integer PerformVerticesEE (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB, const BOPCol_BaseAllocator& theAllocator);
-  
-  Standard_EXPORT Standard_Integer PerformVerticesEF (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB, const BOPCol_BaseAllocator& theAllocator);
+
+  //! Performs intersection of new vertices, obtained in E/E and E/F intersections
+  Standard_EXPORT void PerformNewVertices(BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
+                                          const BOPCol_BaseAllocator& theAllocator,
+                                          const Standard_Boolean theIsEEIntersection = Standard_True);
   
   Standard_EXPORT Standard_Boolean CheckFacePaves (const TopoDS_Vertex& theVnew, const BOPCol_MapOfInteger& theMIF);
   
@@ -318,8 +336,9 @@ protected:
 
   //! Updates tolerance of vertex with index <nV>
   //! to make it interfere with edge
-  Standard_EXPORT void ForceInterfVE (const Standard_Integer nV, Handle(BOPDS_PaveBlock)& aPB, BOPDS_MapOfPaveBlock& aMPB);
-  
+  Standard_EXPORT void ForceInterfVE(const Standard_Integer nV,
+                                     Handle(BOPDS_PaveBlock)& aPB,
+                                     BOPCol_MapOfInteger& theMEdges);
 
   //! Updates tolerance of vertex with index <nV>
   //! to make it interfere with face with index <nF>
index 68f1214..063237e 100644 (file)
 
 #include <Bnd_Box.hxx>
 #include <BOPAlgo_PaveFiller.hxx>
-#include <BOPAlgo_SectionAttribute.hxx>
 #include <BOPAlgo_Tools.hxx>
 #include <BOPCol_DataMapOfIntegerInteger.hxx>
 #include <BOPCol_DataMapOfIntegerListOfInteger.hxx>
 #include <BOPCol_IndexedDataMapOfIntegerListOfInteger.hxx>
 #include <BOPCol_ListOfShape.hxx>
 #include <BOPCol_MapOfInteger.hxx>
-#include <BOPDS_Curve.hxx>
 #include <BOPDS_DS.hxx>
 #include <BOPDS_Iterator.hxx>
 #include <BOPDS_PaveBlock.hxx>
 #include <BOPDS_ShapeInfo.hxx>
 #include <BOPDS_VectorOfInterfVV.hxx>
 #include <BOPTools_AlgoTools.hxx>
-#include <BRepBndLib.hxx>
 #include <BRep_TVertex.hxx>
 #include <BRep_Tool.hxx>
 #include <gp_Pnt.hxx>
@@ -153,8 +150,8 @@ Standard_Integer BOPAlgo_PaveFiller::MakeSDVertices
   }
   BOPDS_ShapeInfo& aSIDS = myDS->ChangeShapeInfo(nV);
   Bnd_Box& aBox = aSIDS.ChangeBox();
-  BRepBndLib::Add(aVn, aBox);
-  aBox.SetGap(aBox.GetGap() + Precision::Confusion());
+  aBox.Add(BRep_Tool::Pnt(aVn));
+  aBox.SetGap(BRep_Tool::Tolerance(aVn) + Precision::Confusion());
   //
   // Fill ShapesSD
   BOPDS_VectorOfInterfVV& aVVs = myDS->InterfVV();
index 732667b..5dbe506 100644 (file)
 
 
 #include <BOPAlgo_PaveFiller.hxx>
-#include <BOPAlgo_SectionAttribute.hxx>
+#include <BOPAlgo_Tools.hxx>
 #include <BOPCol_NCVector.hxx>
 #include <BOPCol_Parallel.hxx>
-#include <BOPDS_Curve.hxx>
 #include <BOPDS_DS.hxx>
 #include <BOPDS_Interf.hxx>
 #include <BOPDS_Iterator.hxx>
-#include <BOPDS_MapOfPair.hxx>
 #include <BOPDS_Pair.hxx>
 #include <BOPDS_PaveBlock.hxx>
 #include <BOPDS_VectorOfInterfVE.hxx>
 #include <BOPTools_AlgoTools.hxx>
-#include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
-#include <BRepBndLib.hxx>
 #include <gp_Pnt.hxx>
 #include <IntTools_Context.hxx>
-#include <IntTools_Tools.hxx>
+#include <Precision.hxx>
+#include <TopoDS.hxx>
 #include <TopoDS_Edge.hxx>
-#include <TopoDS_Face.hxx>
 #include <TopoDS_Vertex.hxx>
-#include <Precision.hxx>
 
 //=======================================================================
-//class    : BOPAlgo_VertexEdgeEdge
+//class    : BOPAlgo_VertexEdge
 //purpose  : 
 //=======================================================================
 class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
@@ -105,6 +100,14 @@ class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
     return myContext;
   }
   //
+  void SetPaveBlock(const Handle(BOPDS_PaveBlock)& thePB) {
+    myPB = thePB;
+  }
+  //
+  const Handle(BOPDS_PaveBlock)& PaveBlock() const {
+    return myPB;
+  }
+  //
   virtual void Perform() {
     BOPAlgo_Algo::UserBreak();
     myFlag=myContext->ComputeVE (myV, myE, myT, myTolVNew, myFuzzyValue);
@@ -119,6 +122,7 @@ class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
   TopoDS_Vertex myV;
   TopoDS_Edge myE;
   Handle(IntTools_Context) myContext;
+  Handle(BOPDS_PaveBlock) myPB;
 };
 //=======================================================================
 typedef BOPCol_NCVector
@@ -141,27 +145,20 @@ typedef BOPCol_ContextCnt
 //=======================================================================
 void BOPAlgo_PaveFiller::PerformVE()
 {
-  Standard_Integer iSize, nV, nE, nVSD, iFlag, nVx,  k, aNbVE;
-  Standard_Real aT, aT1, aT2, aTS1, aTS2;
-  BOPDS_Pave aPave;
-  BOPDS_Pair aPK;
-  BOPDS_MapOfPair aMPK;
-  BOPAlgo_VectorOfVertexEdge aVVE;
-  //
   myErrorStatus=0;
   //
   FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
   //
   myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
-  iSize=myIterator->ExpectedLength();
+  Standard_Integer iSize = myIterator->ExpectedLength();
   if (!iSize) {
     return; 
   }
   //
-  BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
-  aVEs.SetIncrement(iSize);
-  //
+  // Prepare pairs for intersection
+  BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMVEPairs;
   for (; myIterator->More(); myIterator->Next()) {
+    Standard_Integer nV, nE;
     myIterator->Value(nV, nE);
     //
     const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
@@ -174,17 +171,6 @@ void BOPAlgo_PaveFiller::PerformVE()
     }
     //
     if (myDS->HasInterfShapeSubShapes(nV, nE)) {
-      myDS->ChangePaveBlocks(nE);
-      continue;
-    }
-    //
-    nVx=nV;
-    if (myDS->HasShapeSD(nV, nVSD)) {
-      nVx=nVSD;
-    }
-    //
-    aPK.SetIndices(nVx, nE);
-    if (!aMPK.Add(aPK)) {
       continue;
     }
     //
@@ -199,75 +185,311 @@ void BOPAlgo_PaveFiller::PerformVE()
       continue;
     }
     //
-    const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aSIE.Shape())); 
-    const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&myDS->Shape(nVx))); 
-    //
-    BOPAlgo_VertexEdge& aVESolver=aVVE.Append1();
-    //
-    aVESolver.SetIndices(nV, nE);
-    aVESolver.SetVertex(aV);
-    aVESolver.SetEdge(aE);
-    aVESolver.SetFuzzyValue(myFuzzyValue);
-    aVESolver.SetProgressIndicator(myProgressIndicator);
+    BOPCol_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
+    if (!pLV)
+      pLV = &aMVEPairs(aMVEPairs.Add(aPB, BOPCol_ListOfInteger()));
+    pLV->Append(nV);
+  }
+  //
+  IntersectVE(aMVEPairs);
+}
+
+//=======================================================================
+// function: IntersectVE
+// purpose: 
+//=======================================================================
+void BOPAlgo_PaveFiller::IntersectVE
+  (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
+   const Standard_Boolean theAddInterfs)
+{
+  Standard_Integer i, aNbVE = theVEPairs.Extent();
+  if (!aNbVE) {
+    return;
+  }
+  //
+  BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
+  if (theAddInterfs) {
+    aVEs.SetIncrement(aNbVE);
+  }
+  //
+  // Prepare for intersection.
+  BOPAlgo_VectorOfVertexEdge aVVE;
+  // Map to collect all SD connections to add interferences
+  // for all vertices having the same SD vertex.
+  // It will also be used as a Fence map to avoid repeated
+  // intersection of the same SD vertex with edge
+  NCollection_DataMap<BOPDS_Pair, BOPCol_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
+  //
+  for (i = 1; i <= aNbVE; ++i) {
+    const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
+    Standard_Integer nE = aPB->OriginalEdge();
     //
-  }// for (; myIterator->More(); myIterator->Next()) {
+    const BOPCol_ListOfInteger& aLV = theVEPairs(i);
+    BOPCol_ListIteratorOfListOfInteger aItLV(aLV);
+    for (; aItLV.More(); aItLV.Next()) {
+      Standard_Integer nV = aItLV.Value();
+      //
+      Standard_Integer nVSD = nV;
+      myDS->HasShapeSD(nV, nVSD);
+      //
+      BOPDS_Pair aPair(nVSD, nE);
+      BOPCol_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
+      if (pLI) {
+        // Already added
+        pLI->Append(nV);
+        continue;
+      }
+      // New pair
+      pLI = aDMVSD.Bound(aPair, BOPCol_ListOfInteger());
+      pLI->Append(nV);
+      //
+      const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
+      const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
+      //
+      BOPAlgo_VertexEdge& aVESolver = aVVE.Append1();
+      aVESolver.SetIndices(nVSD, nE);
+      aVESolver.SetVertex(aV);
+      aVESolver.SetEdge(aE);
+      aVESolver.SetPaveBlock(aPB);
+      aVESolver.SetFuzzyValue(myFuzzyValue);
+      aVESolver.SetProgressIndicator(myProgressIndicator);
+    }
+  }
   //
-  aNbVE=aVVE.Extent();
+  // Perform intersection
   //=============================================================
   BOPAlgo_VertexEdgeCnt::Perform(myRunParallel, aVVE, myContext);
   //=============================================================
   //
-  for (k=0; k < aNbVE; ++k) {
-    const BOPAlgo_VertexEdge& aVESolver=aVVE(k);
-    iFlag=aVESolver.Flag();
-    if (!iFlag) {
-      aVESolver.Indices(nV, nE);
-      aT=aVESolver.Parameter();
-      // 
-      // check if vertex hits beyond shrunk range, in such case create V-V interf
-      const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
-      const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
-      Bnd_Box aBox;
-      Standard_Boolean bIsPBSplittable;
-      aPB->Range(aT1, aT2);
-      aPB->ShrunkData(aTS1, aTS2, aBox, bIsPBSplittable);
-      IntTools_Range aPaveR[2] = { IntTools_Range(aT1, aTS1), IntTools_Range(aTS2, aT2) };
-      Standard_Real aTol = Precision::Confusion();
-      Standard_Boolean isOnPave = Standard_False;
-      for (Standard_Integer i = 0; i < 2; i++) {
-        if (!bIsPBSplittable || IntTools_Tools::IsOnPave1(aT, aPaveR[i], aTol)) {
-          Standard_Integer nV1 = (i == 0 ? aPB->Pave1().Index() : aPB->Pave2().Index());
-          if (!myDS->HasInterf(nV, nV1)) {
-            BOPCol_ListOfInteger aLI;
-            aLI.Append(nV);
-            aLI.Append(nV1);
-            MakeSDVertices(aLI);
-          }
-          isOnPave = Standard_True;
-          break;
+  // Keep the modified edges for further update
+  BOPCol_MapOfInteger aMEdges;
+  //
+  // Analyze intersections
+  aNbVE = aVVE.Extent();
+  for (i = 0; i < aNbVE; ++i) {
+    const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
+    if (aVESolver.Flag() != 0) {
+      continue;
+    }
+    //
+    Standard_Integer nV, nE;
+    aVESolver.Indices(nV, nE);
+    // Parameter of vertex on edge
+    Standard_Real aT = aVESolver.Parameter();
+    // 1. Update vertex V/E if necessary
+    Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
+    Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
+    // 2. Create new pave and add it as extra pave to pave block
+    //    for further splitting of the edge
+    const Handle(BOPDS_PaveBlock)& aPB = aVESolver.PaveBlock();
+    BOPDS_Pave aPave;
+    aPave.SetIndex(nVx);
+    aPave.SetParameter(aT);
+    aPB->AppendExtPave(aPave);
+    aMEdges.Add(nE);
+    //
+    if (theAddInterfs) {
+      // Add interferences into DS
+      BOPDS_Pair aPair(nV, nE);
+      const BOPCol_ListOfInteger& aLI = aDMVSD.Find(aPair);
+      BOPCol_ListIteratorOfListOfInteger aItLI(aLI);
+      for (; aItLI.More(); aItLI.Next()) {
+        const Standard_Integer nVOld = aItLI.Value();
+        // 3. Create interference V/E
+        BOPDS_InterfVE& aVE = aVEs.Append1();
+        aVE.SetIndices(nVOld, nE);
+        aVE.SetParameter(aT);
+        // 2. Add a pair in the whole table of interferences
+        myDS->AddInterf(nVOld, nE);
+        // 4. Set index of new vertex in the interference
+        if (myDS->IsNewShape(nVx)) {
+          aVE.SetIndexNew(nVx);
         }
       }
-      if (isOnPave)
+    }
+  }
+  //
+  // Split pave blocks of the intersected edges with the extra paves.
+  // At the same time compute shrunk data for the new pave blocks
+  // and in case there is no valid range for the pave block,
+  // the vertices of this pave block should be unified.
+  SplitPaveBlocks(aMEdges, theAddInterfs);
+}
+
+//=======================================================================
+// function: MakeNewCommonBlock
+// purpose: Make new Common Block from the given list of Pave Blocks
+//=======================================================================
+static
+  void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
+                          const BOPCol_ListOfInteger& theLFaces,
+                          BOPDS_PDS& theDS)
+{
+  // Make Common Block from the pave blocks in the list
+  Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
+  aCBNew->SetPaveBlocks(theLPB);
+  aCBNew->SetFaces(theLFaces);
+  //
+  BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
+  for (; aItLPB.More(); aItLPB.Next()) {
+    theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
+  }
+}
+
+//=======================================================================
+// function: SplitPaveBlocks
+// purpose: 
+//=======================================================================
+void BOPAlgo_PaveFiller::SplitPaveBlocks(const BOPCol_MapOfInteger& theMEdges,
+                                         const Standard_Boolean theAddInterfs)
+{
+  // Fence map to avoid unification of the same vertices twice
+  BOPDS_MapOfPair aMPairs;
+  // Map to treat the Common Blocks
+  NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
+                             BOPDS_ListOfPaveBlock,
+                             TColStd_MapTransientHasher> aMCBNewPB;
+  //
+  BOPCol_MapIteratorOfMapOfInteger aItM(theMEdges);
+  for (; aItM.More(); aItM.Next()) {
+    Standard_Integer nE = aItM.Value();
+    BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
+    //
+    BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
+    for (; aItLPB.More();) {
+      Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
+      //
+      if (!aPB->IsToUpdate()) {
+        aItLPB.Next();
         continue;
+      }
+      //
+      const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
+      //
+      // Compute new pave blocks
+      BOPDS_ListOfPaveBlock aLPBN;
+      aPB->Update(aLPBN);
+      //
+      // Make sure that each new pave block has a valid range,
+      // otherwise unify the vertices of the pave block
+      BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
+      for (; aItLPBN.More(); aItLPBN.Next()) {
+        Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
+        myDS->UpdatePaveBlockWithSDVertices(aPBN);
+        FillShrunkData(aPBN);
+        //
+        if (!aPBN->HasShrunkData()) {
+          // No valid range, unify vertices
+          Standard_Integer nV1, nV2;
+          aPBN->Indices(nV1, nV2);
+          if (nV1 != nV2) {
+            BOPDS_Pair aPair;
+            aPair.SetIndices(nV1, nV2);
+            if (aMPairs.Add(aPair)) {
+              BOPCol_ListOfInteger aLV;
+              aLV.Append(nV1);
+              aLV.Append(nV2);
+              MakeSDVertices(aLV, theAddInterfs);
+            }
+          }
+          continue;
+        }
+        //
+        // Update the list with new pave block
+        aLPB.Append(aPBN);
+        // Treat the common block
+        if (!aCB.IsNull()) {
+          // Store the new pave block to make new common block
+          BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
+          if (!pLPBCB) {
+            pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
+          }
+          pLPBCB->Append(aPBN);
+        }
+      }
+      // Remove old pave block
+      aLPB.Remove(aItLPB);
+    }
+  }
+  //
+  // Make Common Blocks
+  Standard_Integer i, aNbCB = aMCBNewPB.Extent();
+  for (i = 1; i <= aNbCB; ++i) {
+    const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
+    const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
+    //
+    // For each group of pave blocks with the same vertices make new common block
+    NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
+    BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
+    for (; aItLPB.More(); aItLPB.Next()) {
+      const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
       //
-      // 1
-      BOPDS_InterfVE& aVE=aVEs.Append1();
-      aVE.SetIndices(nV, nE);
-      aVE.SetParameter(aT);
-      // 2
-      myDS->AddInterf(nV, nE);
+      BOPDS_Pair aPair;
+      aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
       //
-      // 3 update vertex V/E if necessary
-      Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
-      nVx=UpdateVertex(nV, aTolVNew);
-      //4
-      if (myDS->IsNewShape(nVx)) {
-        aVE.SetIndexNew(nVx);
+      BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
+      if (!pLPBx) {
+        pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
       }
-      //5 append ext pave to pave block
-      aPave.SetIndex(nVx);
-      aPave.SetParameter(aT);
-      aPB->AppendExtPave(aPave);
+      pLPBx->Append(aPB);
     }
-  }//for (k=0; k < aNbVE; ++k) {
-} 
+    //
+    Standard_Integer nV1, nV2;
+    aCB->PaveBlock1()->Indices(nV1, nV2);
+    Standard_Boolean bIsClosed = (nV1 == nV2);
+    //
+    Standard_Integer j, aNbPairs = aMInds.Extent();
+    for (j = 1; j <= aNbPairs; ++j) {
+      BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
+      //
+      if (!bIsClosed) {
+        // Make Common Block from the pave blocks in the list
+        MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
+        continue;
+      }
+      //
+      // Find coinciding pave blocks
+      while (aLPB.Extent()) {
+        // Pave blocks forming the common block
+        BOPDS_ListOfPaveBlock aLPBCB;
+        // Point in the middle of the first pave block in the common block
+        gp_Pnt aPMFirst(0., 0., 0.);
+        // Tolerance of the first edge in the common block
+        Standard_Real aTolEFirst = 0.;
+        //
+        aItLPB.Initialize(aLPB);
+        for (; aItLPB.More();) {
+          const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
+          if (aLPBCB.IsEmpty()) {
+            aLPBCB.Append(aPB);
+            const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
+            aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
+            //
+            Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
+            BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
+            //
+            aLPB.Remove(aItLPB);
+            continue;
+          }
+          //
+          // Check pave blocks for coincidence
+          const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
+          Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
+          //
+          Standard_Real aTOut, aDist;
+          Standard_Integer iErr =
+            myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
+          if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
+            aLPBCB.Append(aPB);
+            aLPB.Remove(aItLPB);
+            continue;
+          }
+          aItLPB.Next();
+        }
+        //
+        // Make Common Block from the pave blocks in the list
+        MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);
+      }
+    }
+  }
+}
index d46bc08..407bc31 100644 (file)
 
 #include <Bnd_Box.hxx>
 #include <BOPAlgo_PaveFiller.hxx>
-#include <BOPAlgo_SectionAttribute.hxx>
 #include <BOPAlgo_Tools.hxx>
-#include <BOPCol_BoxBndTree.hxx>
-#include <BOPCol_DataMapOfIntegerShape.hxx>
-#include <BOPCol_DataMapOfShapeInteger.hxx>
-#include <BOPCol_DataMapOfShapeListOfShape.hxx>
-#include <BOPCol_IndexedDataMapOfShapeBox.hxx>
 #include <BOPCol_NCVector.hxx>
 #include <BOPCol_Parallel.hxx>
 #include <BOPDS_CommonBlock.hxx>
 #include <BOPDS_CoupleOfPaveBlocks.hxx>
-#include <BOPDS_Curve.hxx>
-#include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
-#include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
 #include <BOPDS_DS.hxx>
 #include <BOPDS_Interf.hxx>
 #include <BOPDS_Iterator.hxx>
@@ -42,8 +33,6 @@
 #include <BOPTools_AlgoTools.hxx>
 #include <BndLib_Add3dCurve.hxx>
 #include <BRep_Tool.hxx>
-#include <BRepBndLib.hxx>
-#include <BRepTools.hxx>
 #include <BRepAdaptor_Curve.hxx>
 #include <gp_Pnt.hxx>
 #include <IntTools_CommonPrt.hxx>
 #include <IntTools_SequenceOfRanges.hxx>
 #include <IntTools_ShrunkRange.hxx>
 #include <IntTools_Tools.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <Precision.hxx>
-#include <TopoDS_Compound.hxx>
+#include <TopoDS.hxx>
 #include <TopoDS_Edge.hxx>
-#include <TopoDS_Face.hxx>
 #include <TopoDS_Vertex.hxx>
 
 /////////////////////////////////////////////////////////////////////////
@@ -126,190 +113,6 @@ typedef BOPCol_Cnt
 //
 /////////////////////////////////////////////////////////////////////////
 //=======================================================================
-//class    : BOPAlgo_TNV
-//purpose  : 
-//=======================================================================
-class BOPAlgo_TNV;
-typedef BOPCol_NCVector
-  <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
-//
-typedef BOPCol_Functor
-  <BOPAlgo_TNV,
-  BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
-//
-typedef BOPCol_Cnt
-  <BOPAlgo_TNVFunctor,
-  BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
-//=======================================================================
-class BOPAlgo_TNV : public BOPCol_BoxBndTreeSelector{
- public:
-  BOPAlgo_TNV() 
-    : BOPCol_BoxBndTreeSelector(),
-      myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
-  };
-  //
-  ~BOPAlgo_TNV(){
-  };
-  //
-  void SetVertex(const TopoDS_Vertex& aV) {
-    myV=aV;
-    myPnt = BRep_Tool::Pnt(myV);
-  }
-  //
-  const TopoDS_Vertex& Vertex()const {
-    return myV;
-  }
-  //
-  void SetTree(BOPCol_BoxBndTree& aTree) {
-    myTree=&aTree;
-  }
-  //
-  void SetTolerance(const Standard_Real theTol) {
-    myTol = theTol;
-  }
-  //
-  Standard_Real Tolerance() const {
-    return myTol;
-  }
-  //
-  const gp_Pnt& Pnt() const {
-    return myPnt;
-  }
-  //
-  void SetFuzzyValue(const Standard_Real theFuzzyValue) {
-    myFuzzyValue = theFuzzyValue;
-  }
-  //
-  void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
-    myVecTNV = &theVec;
-  }
-  //
-  virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
-  {
-    const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
-    Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
-    aTolSum2 *= aTolSum2;
-    Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
-    if (aD2 < aTolSum2)
-      return BOPCol_BoxBndTreeSelector::Accept(theIndex);
-    return Standard_False;
-  }
-  //
-  void Perform() {
-    myTree->Select(*this);
-  }
-  //
- protected:
-  Standard_Real myTol;
-  Standard_Real myFuzzyValue;
-  gp_Pnt        myPnt;
-  TopoDS_Vertex myV;
-  BOPCol_BoxBndTree *myTree;
-  const BOPAlgo_VectorOfTNV *myVecTNV;
-};
-//
-/////////////////////////////////////////////////////////////////////////
-//=======================================================================
-//class    : BOPAlgo_PVE
-//purpose  : 
-//=======================================================================
-class BOPAlgo_PVE {
- public:
-  BOPAlgo_PVE()
-    : myIV(-1), myIE(-1), myFlag(-1), myT(-1.) {
-  };
-  //
-  ~BOPAlgo_PVE(){
-  };
-  //
-  void SetIndices(const Standard_Integer nV,
-                  const Standard_Integer nE){
-    myIV=nV;
-    myIE=nE;
-  }
-  //
-  void Indices(Standard_Integer& nV,
-               Standard_Integer& nE) const {
-    nV=myIV;
-    nE=myIE;
-  }
-  //
-  void SetVertex(const TopoDS_Vertex& aV) {
-    myV=aV;
-  }
-  //
-  const TopoDS_Vertex& Vertex()const {
-    return myV;
-  }
-  //
-  void SetEdge(const TopoDS_Edge& aE) {
-    myE=aE;
-  }
-  //
-  const TopoDS_Edge& Edge()const {
-    return myE;
-  }
-  //
-  void SetPaveBlock(const Handle(BOPDS_PaveBlock)& aPB) {
-    myPB=aPB;
-  }
-  //
-  Handle(BOPDS_PaveBlock)& PaveBlock() {
-    return myPB;
-  }
-  //
-  Standard_Integer Flag()const {
-    return myFlag;
-  }
-  //
-  Standard_Real Parameter()const {
-    return myT;
-  }
-  //
-  void SetContext(const Handle(IntTools_Context)& aContext) {
-    myContext=aContext;
-  }
-  //
-  const Handle(IntTools_Context)& Context()const {
-    return myContext;
-  }
-  //
-  void SetFuzzyValue(const Standard_Real theValue) {
-    myFuzzyValue = theValue;
-  }
-  //
-  void Perform() {
-    Standard_Real dummy;
-    myFlag = myContext->ComputeVE(myV, myE, myT, dummy, myFuzzyValue);
-  };
-  //
- protected:
-  Standard_Integer myIV;
-  Standard_Integer myIE;
-  Standard_Integer myFlag;
-  Standard_Real myT;
-  Standard_Real myFuzzyValue;
-  TopoDS_Vertex myV;
-  TopoDS_Edge myE;
-  Handle(BOPDS_PaveBlock) myPB;
-  Handle(IntTools_Context) myContext;
-};
-//=======================================================================
-typedef BOPCol_NCVector
-  <BOPAlgo_PVE> BOPAlgo_VectorOfPVE; 
-//
-typedef BOPCol_ContextFunctor 
-  <BOPAlgo_PVE,
-  BOPAlgo_VectorOfPVE,
-  Handle(IntTools_Context), 
-  IntTools_Context> BOPAlgo_PVEFunctor;
-//
-typedef BOPCol_ContextCnt 
-  <BOPAlgo_PVEFunctor,
-  BOPAlgo_VectorOfPVE,
-  Handle(IntTools_Context)> BOPAlgo_PVECnt;
-/////////////////////////////////////////////////////////////////////////
-//=======================================================================
 // function: PerformEE
 // purpose: 
 //=======================================================================
@@ -334,9 +137,10 @@ void BOPAlgo_PaveFiller::PerformEE()
   TopAbs_ShapeEnum aType;
   BOPDS_ListIteratorOfListOfPaveBlock aIt1, aIt2;
   Handle(NCollection_BaseAllocator) aAllocator;
-  BOPDS_MapOfPaveBlock aMPBToUpdate;
   BOPAlgo_VectorOfEdgeEdge aVEdgeEdge;
   BOPDS_MapIteratorOfMapOfPaveBlock aItPB; 
+  // keep modified edges for further update
+  BOPCol_MapOfInteger aMEdges;
   //
   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
   //-----------------------------------------------------scope f
@@ -532,7 +336,7 @@ void BOPAlgo_PaveFiller::PerformEE()
             if (bIsOnPave[j]) {
               //add interf VE(nV[j], nE)
               Handle(BOPDS_PaveBlock)& aPB = (j < 2) ? aPB2 : aPB1;
-              ForceInterfVE(nV[j], aPB, aMPBToUpdate);
+              ForceInterfVE(nV[j], aPB, aMEdges);
               bFlag = Standard_True;
               break;
             }
@@ -644,288 +448,132 @@ void BOPAlgo_PaveFiller::PerformEE()
   //=========================================
   // post treatment
   //=========================================
-  {
-    Standard_Integer aNbV;
-    Handle(BOPDS_PaveBlock) aPB1, aPB2;
-    //
-    aNbV=aMVCPB.Extent();
-    for (i=1; i<=aNbV; ++i) {
-      const BOPDS_CoupleOfPaveBlocks& aCPB=aMVCPB.FindFromIndex(i);
-      aCPB.PaveBlocks(aPB1, aPB2); 
+  BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
+  PerformNewVertices(aMVCPB, aAllocator);
+  //
+  if (aMEdges.Extent()) {
+    Standard_Integer aNbV = aMVCPB.Extent();
+    for (i = 1; i <= aNbV; ++i) {
+      Handle(BOPDS_PaveBlock) aPB1, aPB2;
+      const BOPDS_CoupleOfPaveBlocks& aCPB = aMVCPB.FindFromIndex(i);
+      aCPB.PaveBlocks(aPB1, aPB2);
       //
-      aMPBToUpdate.Remove(aPB1);
-      aMPBToUpdate.Remove(aPB2);
-    }
-  }
-  //
-  aItPB.Initialize(aMPBToUpdate);
-  for (; aItPB.More(); aItPB.Next()) {
-    Handle(BOPDS_PaveBlock) aPB=aItPB.Value();
-    if (!myDS->IsCommonBlock(aPB)) {
-      myDS->UpdatePaveBlock(aPB);
-    }
-    else {
-      const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
-      myDS->UpdateCommonBlock(aCB, myFuzzyValue);
+      aMEdges.Remove(aPB1->OriginalEdge());
+      aMEdges.Remove(aPB2->OriginalEdge());
     }
+    //
+    SplitPaveBlocks(aMEdges, Standard_False);
   }
   //
-  BOPAlgo_Tools::PerformCommonBlocks(aMPBLPB, aAllocator, myDS);
-  PerformVerticesEE(aMVCPB, aAllocator);
   //-----------------------------------------------------scope t
   aMPBLPB.Clear();
   aMVCPB.Clear();
-  aMPBToUpdate.Clear();
 }
 //=======================================================================
 //function : PerformVerticesEE
 //purpose  : 
 //=======================================================================
-Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEE
+void BOPAlgo_PaveFiller::PerformNewVertices
   (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
-   const Handle(NCollection_BaseAllocator)& theAllocator)
+   const Handle(NCollection_BaseAllocator)& theAllocator,
+   const Standard_Boolean bIsEEIntersection)
 {
-  Standard_Integer aNbV, iRet;
-  //
-  iRet=0;
-  aNbV=theMVCPB.Extent();
+  Standard_Integer aNbV = theMVCPB.Extent();
   if (!aNbV) {
-    return iRet;
+    return;
   }
   //
-  Standard_Integer nVx, iV, j, nE, iFlag, iX, i, aNb; 
-  Standard_Real aT;
-  BOPCol_ListIteratorOfListOfShape aItLS;
-  BOPCol_ListIteratorOfListOfInteger aItLI;
-  BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
-  BOPDS_ShapeInfo aSI;
-  BOPDS_Pave aPave;
+  Standard_Real aTolAdd = myFuzzyValue / 2.;
   //
-  BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
-  BOPCol_ListOfShape aLS(theAllocator);
-  BOPCol_IndexedDataMapOfShapeInteger aMVI(100, theAllocator);
+  // 1. Fuse the new vertices
   BOPCol_IndexedDataMapOfShapeListOfShape aImages;
-  //
-  aSI.SetShapeType(TopAbs_VERTEX);
-  BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
-  //
-  // 1 prepare arguments
-  // 2 Fuse vertices
   TreatNewVertices(theMVCPB, aImages);
   //
-  // 3 Add new vertices to myDS; 
-  //   connect indices to CPB structure
-  aNb = aImages.Extent();
-  for (i=1; i<=aNb; ++i) {
-    const TopoDS_Vertex& aV=(*(TopoDS_Vertex*)(&aImages.FindKey(i)));
-    const BOPCol_ListOfShape& aLVSD=aImages.FindFromIndex(i);
+  // 2. Add new vertices to myDS and connect indices to CPB structure
+  BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
+  BOPDS_VectorOfInterfEF& aEFs = myDS->InterfEF();
+  //
+  Standard_Integer i, aNb = aImages.Extent();
+  for (i = 1; i <= aNb; ++i) {
+    const TopoDS_Vertex& aV = TopoDS::Vertex(aImages.FindKey(i));
+    const BOPCol_ListOfShape& aLVSD = aImages.FindFromIndex(i);
     //
+    BOPDS_ShapeInfo aSI;
+    aSI.SetShapeType(TopAbs_VERTEX);
     aSI.SetShape(aV);
-    iV=myDS->Append(aSI);
+    Standard_Integer iV = myDS->Append(aSI);
     //
-    BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(iV);
-    Bnd_Box& aBox=aSIDS.ChangeBox();
-    BRepBndLib::Add(aV, aBox);
-    aBox.SetGap(aBox.GetGap() + Precision::Confusion());
+    BOPDS_ShapeInfo& aSIDS = myDS->ChangeShapeInfo(iV);
+    Bnd_Box& aBox = aSIDS.ChangeBox();
+    aBox.Add(BRep_Tool::Pnt(aV));
+    aBox.SetGap(BRep_Tool::Tolerance(aV) + aTolAdd);
     //
-    aItLS.Initialize(aLVSD);
+    BOPCol_ListIteratorOfListOfShape aItLS(aLVSD);
     for (; aItLS.More(); aItLS.Next()) {
       const TopoDS_Shape& aVx = aItLS.Value();
-      BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
+      BOPDS_CoupleOfPaveBlocks &aCPB = theMVCPB.ChangeFromKey(aVx);
       aCPB.SetIndex(iV);
-      // update EE interference
-      iX=aCPB.IndexInterf();
-      BOPDS_InterfEE& aEE=aEEs(iX);
-      aEE.SetIndexNew(iV);
+      // update interference
+      Standard_Integer iX = aCPB.IndexInterf();
+      BOPDS_Interf *aInt = bIsEEIntersection ? (BOPDS_Interf*)(&aEEs(iX)) : (BOPDS_Interf*) (&aEFs(iX));
+      aInt->SetIndexNew(iV);
     }
   }
   //
-  // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
-  {
-    Handle(BOPDS_PaveBlock) aPB[2];
+  // 3. Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
+  BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
+  for (i = 1; i <= aNbV; ++i) {
+    const BOPDS_CoupleOfPaveBlocks& aCPB = theMVCPB.FindFromIndex(i);
+    Standard_Integer iV = aCPB.Index();
     //
-    for (i=1; i<=aNbV; ++i) {
-      const BOPDS_CoupleOfPaveBlocks& aCPB=theMVCPB.FindFromIndex(i);
-      iV=aCPB.Index();
-      aCPB.PaveBlocks(aPB[0], aPB[1]);
-      for (j=0; j<2; ++j) {
-        if (aMPBLI.Contains(aPB[j])) {
-          BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB[j]);
-          aLI.Append(iV);
-        }
-        else {
-          BOPCol_ListOfInteger aLI(theAllocator);
-          aLI.Append(iV);
-          aMPBLI.Add(aPB[j], aLI);
-        }
+    Handle(BOPDS_PaveBlock) aPB[2];
+    aCPB.PaveBlocks(aPB[0], aPB[1]);
+    for (Standard_Integer j = 0; j < 2; ++j) {
+      BOPCol_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB[j]);
+      if (!pLI) {
+        pLI = &aMPBLI(aMPBLI.Add(aPB[j], BOPCol_ListOfInteger(theAllocator)));
       }
-    }
-  }
-  // 5 
-  // 5.1  Compute Extra Paves and 
-  // 5.2. Add Extra Paves to the PaveBlocks
-  //-------------------------------------------------------------
-  Standard_Integer k, aNbVPVE;
-  BOPAlgo_VectorOfPVE aVPVE;
-  //
-  aNb=aMPBLI.Extent();
-  for(i=1; i<=aNb; ++i) {
-    Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
-    nE=aPB->OriginalEdge();
-    const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
-    // 1,2
-    const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
-    aItLI.Initialize(aLI);
-    for (; aItLI.More(); aItLI.Next()) {
-      nVx=aItLI.Value();
-      const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
+      pLI->Append(iV);
       //
-      BOPAlgo_PVE& aPVE=aVPVE.Append1();
-      aPVE.SetIndices(nVx, nE);
-      aPVE.SetVertex(aVx);
-      aPVE.SetEdge(aE);
-      aPVE.SetFuzzyValue(myFuzzyValue);
-      aPVE.SetPaveBlock(aPB);
-    }
-  }
-  //
-  aNbVPVE=aVPVE.Extent();
-  //=============================================================
-  BOPAlgo_PVECnt::Perform(myRunParallel, aVPVE, myContext);
-  //=============================================================
-  //
-  for (k=0; k < aNbVPVE; ++k) {
-    BOPAlgo_PVE& aPVE=aVPVE(k);
-    iFlag=aPVE.Flag();
-    if (!iFlag) {
-      aPVE.Indices(nVx, nE);
-      aT=aPVE.Parameter();
-      Handle(BOPDS_PaveBlock)& aPB=aPVE.PaveBlock();
-      //
-      aPave.SetIndex(nVx);
-      aPave.SetParameter(aT);
-      aPB->AppendExtPave(aPave);
+      if (aPB[0] == aPB[1]) {
+        break;
+      }
     }
   }
-  // 6  Split PaveBlocksa
-  aNb=aMPBLI.Extent();
-  for(i=1; i<=aNb; ++i) {
-    Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
-    nE=aPB->OriginalEdge();
-    // 3
-    if (!myDS->IsCommonBlock(aPB)) {
-      myDS->UpdatePaveBlock(aPB);
-    }
-    else {
-      const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
-      myDS->UpdateCommonBlock(aCB, myFuzzyValue);
-    }    
-  }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
   //
-  return iRet;
+  // 4. Compute Extra Paves and split Pave blocks by the Extra paves
+  IntersectVE(aMPBLI, Standard_False);
 }
 //=======================================================================
 //function : TreatNewVertices
 //purpose  : 
 //=======================================================================
 void BOPAlgo_PaveFiller::TreatNewVertices
-(const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
+  (const BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
    BOPCol_IndexedDataMapOfShapeListOfShape& myImages)
 {
-  Standard_Integer  i, aNbV;//, aNbVSD;
-  Standard_Real aTol;
-  TopoDS_Vertex aVnew;
-  BOPCol_IndexedMapOfShape aMVProcessed;
-  BOPCol_MapOfInteger aMFence;
-  BOPCol_ListIteratorOfListOfInteger aIt;
-  NCollection_Vector<BOPCol_ListOfShape> aVecOfLVSD;
-  //
-  BOPCol_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, 
-                            Bnd_Box> aTreeFiller(aBBTree);
-  BOPAlgo_VectorOfTNV aVTNV;
   //
-  Standard_Real aTolAdd = myFuzzyValue / 2.;
-  aNbV = theMVCPB.Extent();
-  for (i=1; i<=aNbV; ++i) {
-    const TopoDS_Vertex& aV = *((TopoDS_Vertex*)&theMVCPB.FindKey(i));
-    Bnd_Box aBox;
-    //
-    aTol = theMVCPB.FindFromIndex(i).Tolerance();
-    aBox.Add(BRep_Tool::Pnt(aV));
-    aBox.SetGap(aTol + aTolAdd);
-    //
-    aTreeFiller.Add(i, aBox);
-    //
-    BOPAlgo_TNV& aTNV=aVTNV.Append1();
-    aTNV.SetTree(aBBTree);
-    aTNV.SetBox(aBox);
-    aTNV.SetVertex(aV);
-    aTNV.SetTolerance(aTol);
-    aTNV.SetFuzzyValue(myFuzzyValue);
-    aTNV.SetVectorOfTNV(aVTNV);
+  // Prepare for intersection
+  BOPCol_IndexedDataMapOfShapeReal aVerts;
+  Standard_Integer i, aNbV = theMVCPB.Extent();
+  for (i = 1; i <= aNbV; ++i) {
+    const TopoDS_Shape& aV = theMVCPB.FindKey(i);
+    Standard_Real aTol = theMVCPB.FindFromIndex(i).Tolerance();
+    aVerts.Add(aV, aTol);
   }
   //
-  aTreeFiller.Fill();
-  //
-  //===========================================
-  BOPAlgo_TNVCnt::Perform(myRunParallel, aVTNV);
-  //===========================================
+  // Perform intersection
+  BOPCol_ListOfListOfShape aChains;
+  BOPAlgo_Tools::IntersectVertices(aVerts, myRunParallel, myFuzzyValue, aChains);
   //
-  // Chains
-  for (i=1; i<=aNbV; ++i) {
-    if (!aMFence.Add(i)) {
-      continue;
-    }
-    //
-    Standard_Integer aIP, aNbIP1, aIP1;
-    BOPCol_ListOfShape aLVSD;
-    BOPCol_ListOfInteger aLIP, aLIP1, aLIPC;
-    BOPCol_ListIteratorOfListOfInteger aItLIP;
-    //
-    aLIPC.Append(i);
-    aLIP.Append(i);
-    for(;;) {
-      aItLIP.Initialize(aLIP);
-      for(; aItLIP.More(); aItLIP.Next()) {
-        aIP=aItLIP.Value();
-        //
-        BOPAlgo_TNV& aTNV=aVTNV(aIP-1);
-        const BOPCol_ListOfInteger& aLI=aTNV.Indices();
-        aIt.Initialize(aLI);
-        for (; aIt.More(); aIt.Next()) {
-          aIP1=aIt.Value();
-          if (!aMFence.Add(aIP1)) {
-            continue;
-          }
-          aLIP1.Append(aIP1);
-        } //for (; aIt.More(); aIt.Next()) {
-      }//for(; aIt1.More(); aIt1.Next()) {
-      //
-      aNbIP1=aLIP1.Extent();
-      if (!aNbIP1) {
-        break; // from for(;;) 
-      }
-      //
-      aLIP = aLIP1;
-      aLIPC.Append(aLIP1); // items of aLIP1 are moved to aLIPC
-    }// for(;;) {
+  // Treat the results - make new vertices for each chain
+  BOPCol_ListOfListOfShape::Iterator aItC(aChains);
+  for (; aItC.More(); aItC.Next()) {
+    const BOPCol_ListOfShape& aLVSD = aItC.Value();
     //
-    aItLIP.Initialize(aLIPC);
-    for(; aItLIP.More(); aItLIP.Next()) {
-      aIP=aItLIP.Value();
-      const TopoDS_Vertex& aVP=aVTNV(aIP-1).Vertex(); 
-      aLVSD.Append(aVP);
-    }
-    aVecOfLVSD.Append(aLVSD);
-  }// for (i=1; i<=aNbV; ++i) {
-
-  // Make new vertices
-  aNbV = aVecOfLVSD.Size();
-  for (i = 0; i < aNbV; ++i) {
-    const BOPCol_ListOfShape& aLVSD = aVecOfLVSD(i);
-    BOPTools_AlgoTools::MakeVertex(aLVSD, aVnew);
-    myImages.Add(aVnew, aLVSD);
+    TopoDS_Vertex aVNew;
+    BOPTools_AlgoTools::MakeVertex(aLVSD, aVNew);
+    myImages.Add(aVNew, aLVSD);
   }
 }
 //=======================================================================
@@ -975,7 +623,7 @@ void BOPAlgo_PaveFiller::FillShrunkData(Handle(BOPDS_PaveBlock)& thePB)
 //=======================================================================
 void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
                                        Handle(BOPDS_PaveBlock)& aPB,
-                                       BOPDS_MapOfPaveBlock& aMPBToUpdate)
+                                       BOPCol_MapOfInteger& theMEdges)
 {
   Standard_Integer nE, nVx, nVSD, iFlag;
   Standard_Real aT, aTolVNew;
@@ -1033,7 +681,7 @@ void BOPAlgo_PaveFiller::ForceInterfVE(const Standard_Integer nV,
     aPave.SetParameter(aT);
     aPB->AppendExtPave(aPave);
     //
-    aMPBToUpdate.Add(aPB);
+    theMEdges.Add(nE);
   }
 }
 
index 2fd94aa..e218303 100644 (file)
 // commercial license or contractual agreement.
 
 
-#include <Precision.hxx>
-
 #include <Bnd_Box.hxx>
 #include <BOPAlgo_PaveFiller.hxx>
-#include <BOPAlgo_SectionAttribute.hxx>
 #include <BOPAlgo_Tools.hxx>
 #include <BOPCol_MapOfInteger.hxx>
 #include <BOPCol_NCVector.hxx>
 #include <BOPCol_Parallel.hxx>
-#include <BOPCol_DataMapOfShapeReal.hxx>
 #include <BOPDS_CommonBlock.hxx>
 #include <BOPDS_CoupleOfPaveBlocks.hxx>
 #include <BOPDS_Curve.hxx>
-#include <BOPDS_DataMapOfPaveBlockListOfInteger.hxx>
 #include <BOPDS_DS.hxx>
 #include <BOPDS_Interf.hxx>
 #include <BOPDS_Iterator.hxx>
 #include <BOPDS_Pave.hxx>
 #include <BOPDS_PaveBlock.hxx>
 #include <BOPTools_AlgoTools.hxx>
-#include <BndLib_Add3dCurve.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
 #include <BRepAdaptor_Curve.hxx>
-#include <BRepBndLib.hxx>
-#include <GeomAPI_ProjectPointOnSurf.hxx>
 #include <gp_Pnt.hxx>
 #include <IntTools_CommonPrt.hxx>
 #include <IntTools_Context.hxx>
@@ -50,6 +42,7 @@
 #include <IntTools_Range.hxx>
 #include <IntTools_SequenceOfCommonPrts.hxx>
 #include <IntTools_Tools.hxx>
+#include <Precision.hxx>
 #include <TopoDS.hxx>
 #include <TopoDS_Edge.hxx>
 #include <TopoDS_Face.hxx>
@@ -456,7 +449,7 @@ void BOPAlgo_PaveFiller::PerformEF()
   // post treatment
   //=========================================
   BOPAlgo_Tools::PerformCommonBlocks(aMPBLI, aAllocator, myDS);
-  PerformVerticesEF(aMVCPB, aAllocator);
+  PerformNewVertices(aMVCPB, aAllocator, Standard_False);
   //
   // Update FaceInfoIn for all faces having EF common parts
   BOPCol_MapIteratorOfMapOfInteger aItMI;
@@ -472,179 +465,6 @@ void BOPAlgo_PaveFiller::PerformEF()
   ////aAllocator.Nullify();
 }
 //=======================================================================
-//function : PerformVerticesEF
-//purpose  : 
-//=======================================================================
-Standard_Integer BOPAlgo_PaveFiller::PerformVerticesEF
-  (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMVCPB,
-   const Handle(NCollection_BaseAllocator)& theAllocator)
-{
-  Standard_Integer aNbV, iRet;
-  //
-  iRet=0;
-  aNbV=theMVCPB.Extent();
-  if (!aNbV) {
-    return iRet;
-  }
-  //
-  Standard_Integer nVx, nVSD, iV, iErr, nE, iFlag, iX, i, aNbPBLI;
-  Standard_Real aT, dummy;
-  BOPCol_ListIteratorOfListOfShape aItLS;
-  BOPCol_ListIteratorOfListOfInteger aItLI;
-  BOPDS_PDS aPDS;
-  BOPDS_ShapeInfo aSI;
-  BOPDS_Pave aPave;
-  //
-  BOPCol_ListOfShape aLS(theAllocator);
-  BOPCol_DataMapOfShapeInteger aMVI(100, theAllocator);
-  BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, theAllocator);
-  BOPAlgo_PaveFiller aPF(theAllocator); 
-  BOPCol_DataMapOfShapeReal aMVIniTol;
-  //
-  aSI.SetShapeType(TopAbs_VERTEX);
-  BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
-  //
-  // 1 prepare arguments
-  for (i=1; i<=aNbV; ++i) {
-    const TopoDS_Vertex& aV = TopoDS::Vertex(theMVCPB.FindKey(i));
-    aLS.Append(aV);
-    // if an enlarged tolerance is associated with the vertex then update it 
-    // remembering its initial tolerance
-    Standard_Real aTolEnlarged = theMVCPB.FindFromIndex(i).Tolerance();
-    Standard_Real aIniTol = BRep_Tool::Tolerance(aV);
-    if (aTolEnlarged > aIniTol) {
-      aMVIniTol.Bind(aV, aIniTol);
-      BRep_Builder().UpdateVertex(aV, aTolEnlarged);
-    }
-  }
-  //
-  // 2 Fuse vertices
-  aPF.SetIsPrimary(Standard_False);
-  aPF.SetNonDestructive(myNonDestructive);
-  aPF.SetArguments(aLS);
-  aPF.Perform();
-  iErr=aPF.ErrorStatus();
-  if (iErr) {
-    iRet=1;
-    return iRet;
-  }
-  aPDS=aPF.PDS();
-  //
-  // Recompute common vertex for each SD group containing enlarged vertex;
-  // for that first fill in the map of SD vertex -> its counterparts
-  BOPCol_IndexedDataMapOfShapeListOfShape aImages;
-  aItLS.Initialize(aLS);
-  for (; aItLS.More(); aItLS.Next()) {
-    const TopoDS_Shape& aVx = aItLS.Value();
-    nVx = aPDS->Index(aVx);
-    //
-    const TopoDS_Shape& aV = (aPDS->HasShapeSD(nVx, nVSD) ? aPDS->Shape(nVSD) : aVx);
-    BOPCol_ListOfShape* pLst = aImages.ChangeSeek(aV);
-    if (!pLst) {
-      pLst = &aImages.ChangeFromIndex(aImages.Add(aV, BOPCol_ListOfShape()));
-    }
-    pLst->Append(aVx);
-  }
-  // 3 Add new vertices to theDS; 
-  for (i = 1; i <= aImages.Extent(); i++) {
-    TopoDS_Vertex aV = TopoDS::Vertex(aImages.FindKey(i));
-    const BOPCol_ListOfShape& aLVSD = aImages.FindFromIndex(i);
-    Standard_Boolean isReset = Standard_False;
-    BOPCol_ListIteratorOfListOfShape it(aLVSD);
-    for (; it.More(); it.Next()) {
-      const TopoDS_Vertex& aVx = TopoDS::Vertex(it.Value());
-      const Standard_Real* pTolIni = aMVIniTol.Seek(aVx);
-      if (pTolIni) {
-        // reset enlarged vertex tolerance to the initial value
-        reinterpret_cast<BRep_TVertex*>(aVx.TShape().operator->())->Tolerance(*pTolIni);
-        isReset = Standard_True;
-      }
-    }
-    TopoDS_Vertex aVnew = aV;
-    if (isReset && aLVSD.Extent() > 1) {
-      // make new vertex again
-      BOPTools_AlgoTools::MakeVertex(aLVSD, aVnew);
-    }
-    // index of new vertex in theDS -> iV
-    aSI.SetShape(aVnew);
-    iV = myDS->Append(aSI);
-    //
-    BOPDS_ShapeInfo& aSIDS = myDS->ChangeShapeInfo(iV);
-    Bnd_Box& aBox = aSIDS.ChangeBox();
-    BRepBndLib::Add(aVnew, aBox);
-    aBox.SetGap(aBox.GetGap() + Precision::Confusion());
-    //
-    aMVI.Bind(aV, iV);
-  }
-  //
-  // 4 Map PaveBlock/ListOfVertices to add to this PaveBlock ->aMPBLI
-  aItLS.Initialize(aLS);
-  for (; aItLS.More(); aItLS.Next()) {
-    const TopoDS_Shape& aVx=aItLS.Value();
-    nVx=aPDS->Index(aVx);
-    //
-    const TopoDS_Shape& aV = (aPDS->HasShapeSD(nVx, nVSD) ? aPDS->Shape(nVSD) : aVx);
-    iV = aMVI.Find(aV);
-    //
-    BOPDS_CoupleOfPaveBlocks &aCPB=theMVCPB.ChangeFromKey(aVx);
-    aCPB.SetIndex(iV);
-    // update EF interference
-    iX=aCPB.IndexInterf();
-    BOPDS_InterfEF& aEF=aEFs(iX);
-    aEF.SetIndexNew(iV);
-    // map aMPBLI
-    const Handle(BOPDS_PaveBlock)& aPB=aCPB.PaveBlock1();
-    if (aMPBLI.Contains(aPB)) {
-      BOPCol_ListOfInteger& aLI=aMPBLI.ChangeFromKey(aPB);
-      aLI.Append(iV);
-    }
-    else {
-      BOPCol_ListOfInteger aLI(theAllocator);
-      aLI.Append(iV);
-      aMPBLI.Add(aPB, aLI);
-    }
-  }
-  //
-  // 5 
-  // 5.1  Compute Extra Paves and 
-  // 5.2. Add Extra Paves to the PaveBlocks
-  aNbPBLI=aMPBLI.Extent();
-  for (i=1; i<=aNbPBLI; ++i) {
-    Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
-    const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromIndex(i);
-    nE=aPB->OriginalEdge();
-    const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&myDS->Shape(nE)));
-    // 
-    aItLI.Initialize(aLI);
-    for (; aItLI.More(); aItLI.Next()) {
-      nVx=aItLI.Value();
-      const TopoDS_Vertex& aVx=(*(TopoDS_Vertex *)(&myDS->Shape(nVx)));
-      //
-      iFlag=myContext->ComputeVE (aVx, aE, aT, dummy, myFuzzyValue);
-      if (!iFlag) {
-        aPave.SetIndex(nVx);
-        aPave.SetParameter(aT);
-        aPB->AppendExtPave(aPave);
-      }
-    }
-  }
-  // 6  Split PaveBlocks
-  for (i=1; i<=aNbPBLI; ++i) {
-    Handle(BOPDS_PaveBlock) aPB=aMPBLI.FindKey(i);
-    nE=aPB->OriginalEdge();
-    // 3
-    if (!myDS->IsCommonBlock(aPB)) {
-      myDS->UpdatePaveBlock(aPB);
-    }
-    else {
-      const Handle(BOPDS_CommonBlock)& aCB=myDS->CommonBlock(aPB);
-      myDS->UpdateCommonBlock(aCB, myFuzzyValue);
-    }    
-  }//for (; aItMPBLI.More(); aItMPBLI.Next()) {
-  // 
-  return iRet;
-}
-//=======================================================================
 // function: CheckFacePaves
 // purpose: 
 //=======================================================================
index a092485..8355984 100644 (file)
@@ -979,10 +979,22 @@ Standard_Integer BOPAlgo_PaveFiller::PostTreatFF
                 iV = myDS->Append(aSI);
               }
               const BOPDS_Pave& aP1 = !j ? aPB1->Pave1() : aPB1->Pave2();
-              if (aP1.Parameter() == aPave[j].Parameter() && 
-                  aP1.Index() != iV) {
-                aDMNewSD.Bind(aP1.Index(), iV);
-                myDS->AddShapeSD(aP1.Index(), iV);
+              if (aP1.Index() != iV) {
+                if (aP1.Parameter() == aPave[j].Parameter()) {
+                  aDMNewSD.Bind(aP1.Index(), iV);
+                  myDS->AddShapeSD(aP1.Index(), iV);
+                }
+                else {
+                  // check aPDS to have the SD connection between these vertices
+                  const TopoDS_Shape& aVPave = myDS->Shape(aP1.Index());
+                  Standard_Integer nVnewSD, nVnew = aPDS->Index(aVPave);
+                  if (aPDS->HasShapeSD(nVnew, nVnewSD)) {
+                    if (nVnewSD == nV) {
+                      aDMNewSD.Bind(aP1.Index(), iV);
+                      myDS->AddShapeSD(aP1.Index(), iV);
+                    }
+                  }
+                }
               }
               //
               aPave[j].SetIndex(iV);
@@ -2910,6 +2922,7 @@ void BOPAlgo_PaveFiller::CorrectToleranceOfSE()
         // fill in the map vertex index - pave blocks
         for (Standard_Integer j=0; j < 2; j++) {
           Standard_Integer nV = (j == 0 ? aPB->Pave1().Index() : aPB->Pave2().Index());
+          myDS->HasShapeSD(nV, nV);
           BOPDS_ListOfPaveBlock *pPBList = aMVIPBs.ChangeSeek(nV);
           if (!pPBList) {
             pPBList = &aMVIPBs.ChangeFromIndex(aMVIPBs.Add(nV, BOPDS_ListOfPaveBlock()));
@@ -2985,19 +2998,33 @@ void BOPAlgo_PaveFiller::CorrectToleranceOfSE()
     // compute the maximal distance from the vertex to the adjacent edges
     gp_Pnt aP = BRep_Tool::Pnt(aV);
     //
+    // Avoid repeated checks
+    BOPDS_MapOfPaveBlock aMPBFence;
+    //
     const BOPDS_ListOfPaveBlock& aLPB = aMVIPBs.FindFromIndex(i);
     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
     for (; aItLPB.More(); aItLPB.Next()) {
       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
+      if (!aMPBFence.Add(aPB)) {
+        continue;
+      }
       Standard_Integer nE = aPB->Edge();
       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
-      const BOPDS_Pave& aPave = (aPB->Pave1().Index() == nV ? aPB->Pave1() : aPB->Pave2());
       BRepAdaptor_Curve aC(aE);
-      gp_Pnt aPonE = aC.Value(aPave.Parameter());
-      Standard_Real aDist = aP.Distance(aPonE);
-      aDist += BRep_Tool::Tolerance(aE);
-      if (aDist > aMaxTol) {
-        aMaxTol = aDist;
+      for (Standard_Integer iPave = 0; iPave < 2; ++iPave) {
+        const BOPDS_Pave& aPave = !iPave ? aPB->Pave1() : aPB->Pave2();
+        Standard_Integer nVSD = aPave.Index();
+        myDS->HasShapeSD(nVSD, nVSD);
+        if (nVSD != nV) {
+          continue;
+        }
+        //
+        gp_Pnt aPonE = aC.Value(aPave.Parameter());
+        Standard_Real aDist = aP.Distance(aPonE);
+        aDist += BRep_Tool::Tolerance(aE);
+        if (aDist > aMaxTol) {
+          aMaxTol = aDist;
+        }
       }
     }
     //
index b37fc82..f5ca43a 100644 (file)
@@ -120,7 +120,7 @@ void BOPAlgo_PaveFiller::FillShrunkData(const TopAbs_ShapeEnum aType1,
       aItLPB.Initialize(aLPB);
       for (; aItLPB.More(); aItLPB.Next()) {
         const Handle(BOPDS_PaveBlock)& aPB=aItLPB.ChangeValue();
-        if (aPB->HasShrunkData()) {
+        if (aPB->HasShrunkData() && myDS->IsValidShrunkData(aPB)) {
           continue;
         }
         //
index 6b9ec2f..9647254 100644 (file)
 #include <TopoDS.hxx>
 #include <TopoDS_Edge.hxx>
 
-#include <BOPCol_MapOfShape.hxx>
+#include <BOPCol_BoxBndTree.hxx>
 #include <BOPCol_IndexedMapOfShape.hxx>
 #include <BOPCol_IndexedMapOfInteger.hxx>
 #include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
+#include <BOPCol_MapOfShape.hxx>
+#include <BOPCol_NCVector.hxx>
+#include <BOPCol_Parallel.hxx>
 
 #include <TopExp_Explorer.hxx>
 
@@ -61,6 +64,8 @@
 #include <BOPTools_AlgoTools.hxx>
 #include <BOPTools_AlgoTools2D.hxx>
 
+#include <NCollection_UBTreeFiller.hxx>
+
 #include <IntTools_Context.hxx>
 
 typedef NCollection_IndexedDataMap
@@ -910,3 +915,176 @@ Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
   }
   return Standard_False;
 }
+
+/////////////////////////////////////////////////////////////////////////
+//=======================================================================
+//class    : BOPAlgo_TNV
+//purpose  : 
+//=======================================================================
+class BOPAlgo_TNV;
+typedef BOPCol_NCVector
+  <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
+//
+typedef BOPCol_Functor
+  <BOPAlgo_TNV,
+  BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
+//
+typedef BOPCol_Cnt
+  <BOPAlgo_TNVFunctor,
+  BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
+//=======================================================================
+class BOPAlgo_TNV : public BOPCol_BoxBndTreeSelector{
+ public:
+  BOPAlgo_TNV() 
+    : BOPCol_BoxBndTreeSelector(),
+      myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
+  };
+  //
+  ~BOPAlgo_TNV(){
+  };
+  //
+  void SetVertex(const TopoDS_Vertex& aV) {
+    myV=aV;
+    myPnt = BRep_Tool::Pnt(myV);
+  }
+  //
+  const TopoDS_Vertex& Vertex()const {
+    return myV;
+  }
+  //
+  void SetTree(BOPCol_BoxBndTree& aTree) {
+    myTree=&aTree;
+  }
+  //
+  void SetTolerance(const Standard_Real theTol) {
+    myTol = theTol;
+  }
+  //
+  Standard_Real Tolerance() const {
+    return myTol;
+  }
+  //
+  const gp_Pnt& Pnt() const {
+    return myPnt;
+  }
+  //
+  void SetFuzzyValue(const Standard_Real theFuzzyValue) {
+    myFuzzyValue = theFuzzyValue;
+  }
+  //
+  void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
+    myVecTNV = &theVec;
+  }
+  //
+  virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
+  {
+    const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
+    Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
+    aTolSum2 *= aTolSum2;
+    Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
+    if (aD2 < aTolSum2)
+      return BOPCol_BoxBndTreeSelector::Accept(theIndex);
+    return Standard_False;
+  }
+  //
+  void Perform() {
+    myTree->Select(*this);
+  }
+  //
+ protected:
+  Standard_Real myTol;
+  Standard_Real myFuzzyValue;
+  gp_Pnt        myPnt;
+  TopoDS_Vertex myV;
+  BOPCol_BoxBndTree *myTree;
+  const BOPAlgo_VectorOfTNV *myVecTNV;
+};
+//
+/////////////////////////////////////////////////////////////////////////
+
+//=======================================================================
+//function : IntersectVertices
+//purpose  : Builds the chains of intersecting vertices
+//=======================================================================
+void BOPAlgo_Tools::IntersectVertices(const BOPCol_IndexedDataMapOfShapeReal& theVertices,
+                                      const Standard_Boolean theRunParallel,
+                                      const Standard_Real theFuzzyValue,
+                                      BOPCol_ListOfListOfShape& theChains)
+{
+  Standard_Integer i, j, aNbV = theVertices.Extent();
+  if (aNbV <= 1) {
+    if (aNbV == 1) {
+      theChains.Append(BOPCol_ListOfShape()).Append(theVertices.FindKey(1));
+    }
+    return;
+  }
+  //
+  // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
+  BOPCol_BoxBndTree aBBTree;
+  NCollection_UBTreeFiller <Standard_Integer, 
+                            Bnd_Box> aTreeFiller(aBBTree);
+  // Perform intersection of the vertices
+  BOPAlgo_VectorOfTNV aVTNV;
+  //
+  // Use additional tolerance for intersection
+  Standard_Real aTolAdd = theFuzzyValue / 2.;
+  // Prepare the tree
+  for (i = 1; i <= aNbV; ++i) {
+    const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
+    Standard_Real aTol = BRep_Tool::Tolerance(aV);
+    if (aTol < theVertices(i)) {
+      aTol = theVertices(i);
+    }
+    // Build bnd box for vertex
+    Bnd_Box aBox;
+    aBox.Add(BRep_Tool::Pnt(aV));
+    aBox.SetGap(aTol + aTolAdd);
+    //
+    aTreeFiller.Add(i, aBox);
+    //
+    BOPAlgo_TNV& aTNV=aVTNV.Append1();
+    aTNV.SetTree(aBBTree);
+    aTNV.SetBox(aBox);
+    aTNV.SetVertex(aV);
+    aTNV.SetTolerance(aTol);
+    aTNV.SetFuzzyValue(theFuzzyValue);
+    aTNV.SetVectorOfTNV(aVTNV);
+  }
+  // Shake the tree
+  aTreeFiller.Fill();
+  //
+  // Perform intersection
+  BOPAlgo_TNVCnt::Perform(theRunParallel, aVTNV);
+  //
+  // Fence map
+  BOPCol_MapOfInteger aMFence;
+  // Build chains of intersecting vertices
+  for (i = 1; i <= aNbV; ++i) {
+    if (!aMFence.Add(i)) {
+      continue;
+    }
+    // Start the chain
+    BOPCol_IndexedMapOfInteger aMChain;
+    aMChain.Add(i);
+    //
+    for (j = 1; j <= aMChain.Extent(); ++j) {
+      BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
+      const BOPCol_ListOfInteger& aLI = aTNV.Indices();
+      // Add these vertices into the chain
+      for (BOPCol_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
+        if (aMFence.Add(aItLI.Value())) {
+          aMChain.Add(aItLI.Value());
+        }
+      }
+    }
+    //
+    // Put vertices of the chain into the list
+    BOPCol_ListOfShape& aChain = theChains.Append(BOPCol_ListOfShape());
+    //
+    Standard_Integer aNbVChain = aMChain.Extent();
+    for (j = 1; j <= aNbVChain; ++j) {
+      const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
+      aChain.Append(aVP);
+    }
+  }
+}
index b8d4949..a43ab1f 100644 (file)
@@ -21,6 +21,8 @@
 
 #include <BOPCol_BaseAllocator.hxx>
 #include <BOPDS_IndexedDataMapOfPaveBlockListOfInteger.hxx>
+#include <BOPCol_IndexedDataMapOfShapeReal.hxx>
+#include <BOPCol_ListOfListOfShape.hxx>
 #include <BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock.hxx>
 #include <BOPDS_PDS.hxx>
 #include <Standard_Integer.hxx>
@@ -146,6 +148,13 @@ public:
   Standard_EXPORT static Standard_Boolean WiresToFaces(const TopoDS_Shape& theWires,
                                                        TopoDS_Shape& theFaces,
                                                        const Standard_Real theAngTol = 1.e-8);
+
+  //! Finds chains of intersecting vertices
+  Standard_EXPORT static void IntersectVertices(const BOPCol_IndexedDataMapOfShapeReal& theVertices,
+                                                const Standard_Boolean theRunParallel,
+                                                const Standard_Real theFuzzyValue,
+                                                BOPCol_ListOfListOfShape& theChains);
+
 };
 
 #endif // _BOPAlgo_Tools_HeaderFile
diff --git a/src/BOPCol/BOPCol_IndexedDataMapOfShapeReal.hxx b/src/BOPCol/BOPCol_IndexedDataMapOfShapeReal.hxx
new file mode 100644 (file)
index 0000000..0adcddf
--- /dev/null
@@ -0,0 +1,25 @@
+// Created by: Eugeny MALTCHIKOV
+// Copyright (c) 2017 OPEN CASCADE SAS
+//
+// This file is part of Open CASCADE Technology software library.
+//
+// This library is free software; you can redistribute it and/or modify it under
+// the terms of the GNU Lesser General Public License version 2.1 as published
+// by the Free Software Foundation, with special exception defined in the file
+// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
+// distribution for complete text of the license and disclaimer of any warranty.
+//
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
+
+#ifndef BOPCol_IndexedDataMapOfShapeReal_HeaderFile
+#define BOPCol_IndexedDataMapOfShapeReal_HeaderFile
+
+#include <TopoDS_Shape.hxx>
+#include <TopTools_ShapeMapHasher.hxx>
+  
+#include <NCollection_IndexedDataMap.hxx>
+
+typedef NCollection_IndexedDataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> BOPCol_IndexedDataMapOfShapeReal; 
+#endif
index c191dce..3f79cb9 100644 (file)
@@ -22,6 +22,7 @@ BOPCol_IndexedDataMapOfShapeListOfShape.hxx
 BOPCol_IndexedMapOfInteger.hxx
 BOPCol_IndexedMapOfShape.hxx
 BOPCol_IndexedDataMapOfShapeShape.hxx
+BOPCol_IndexedDataMapOfShapeReal.hxx
 BOPCol_IndexedMapOfOrientedShape.hxx
 BOPCol_ListOfInteger.hxx
 BOPCol_ListOfListOfShape.hxx
index 372b499..c89f7a3 100644 (file)
@@ -29,6 +29,7 @@
 #include <BOPDS_ShapeInfo.hxx>
 #include <BOPDS_VectorOfPave.hxx>
 #include <BOPTools_AlgoTools.hxx>
+#include <BRepAdaptor_Curve.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_TEdge.hxx>
 #include <BRep_TFace.hxx>
@@ -42,6 +43,7 @@
 #include <NCollection_BaseAllocator.hxx>
 #include <Precision.hxx>
 #include <Standard_Assert.hxx>
+#include <TopoDS.hxx>
 #include <TopoDS_Edge.hxx>
 #include <TopoDS_Face.hxx>
 #include <TopoDS_Iterator.hxx>
@@ -932,10 +934,9 @@ void BOPDS_DS::InitPaveBlocks(const Standard_Integer theI)
 //=======================================================================
 void BOPDS_DS::UpdatePaveBlocks()
 {
-  Standard_Boolean bIsToUpdate;
   Standard_Integer i, aNbPBP;
   BOPDS_ListOfPaveBlock aLPBN(myAllocator);
-  BOPDS_ListIteratorOfListOfPaveBlock aItPB, aItPBN;
+  BOPDS_ListIteratorOfListOfPaveBlock aItPB;
   //
   BOPDS_VectorOfListOfPaveBlock& aPBP=myPaveBlocksPool;
   //
@@ -944,21 +945,20 @@ void BOPDS_DS::UpdatePaveBlocks()
     BOPDS_ListOfPaveBlock& aLPB=aPBP(i); 
     //
     aItPB.Initialize(aLPB);
-    for (; aItPB.More(); aItPB.Next()) {
+    for (; aItPB.More();) {
       Handle(BOPDS_PaveBlock)& aPB=aItPB.ChangeValue();
       //
-      bIsToUpdate=aPB->IsToUpdate();
-      if (bIsToUpdate){
-        aLPBN.Clear();
-        aPB->Update(aLPBN);
-        
-        aItPBN.Initialize(aLPBN);
-        for (; aItPBN.More(); aItPBN.Next()) {
-          Handle(BOPDS_PaveBlock)& aPBN=aItPBN.ChangeValue();
-          aLPB.Append(aPBN);
-        }
-        aLPB.Remove(aItPB);
+      if (!aPB->IsToUpdate()) {
+        aItPB.Next();
+        continue;
       }
+      //
+      aLPBN.Clear();
+      aPB->Update(aLPBN);
+      //
+      aLPB.Remove(aItPB);
+      //
+      aLPB.Append(aLPBN);
     }// for (; aItPB.More(); aItPB.Next()) {
   }// for (i=0; i<aNbPBP; ++i) {
 }
@@ -1365,6 +1365,9 @@ void BOPDS_DS::FaceInfoIn(const Standard_Integer theF,
     BOPDS_InterfEF& aEF=aEFs(i);
     if(aEF.Contains(theF)) {
       if(aEF.HasIndexNew(nV)) {
+        if (HasShapeSD(nV, nVSD)) {
+          nV=nVSD;
+        }
         theMI.Add(nV);
       }
       else {
@@ -1594,7 +1597,8 @@ BOPCol_DataMapOfIntegerInteger& BOPDS_DS::ShapesSD()
 void BOPDS_DS::AddShapeSD(const Standard_Integer theIndex,
                           const Standard_Integer theIndexSD)
 {
-  myShapesSD.Bind(theIndex, theIndexSD);
+  if (theIndex != theIndexSD)
+    myShapesSD.Bind(theIndex, theIndexSD);
 }
 //=======================================================================
 //function : HasShapeSD
@@ -1604,13 +1608,14 @@ Standard_Boolean BOPDS_DS::HasShapeSD
   (const Standard_Integer theIndex,
    Standard_Integer& theIndexSD)const
 {
-  Standard_Boolean bRet;
-  //
-  bRet=myShapesSD.IsBound(theIndex);
-  if (bRet) {
-   theIndexSD=myShapesSD.Find(theIndex);
+  Standard_Boolean bHasSD = Standard_False;
+  const Standard_Integer *pSD = myShapesSD.Seek(theIndex);
+  while (pSD) {
+    theIndexSD = *pSD;
+    bHasSD = Standard_True;
+    pSD = myShapesSD.Seek(theIndexSD);
   }
-  return bRet;
+  return bHasSD;
 }
 //=======================================================================
 //function : Dump
@@ -2057,3 +2062,48 @@ void BOPDS_DS::ReleasePaveBlocks()
     }
   }
 }
+
+//=======================================================================
+//function : IsValidShrunkData
+//purpose  :
+//=======================================================================
+Standard_Boolean BOPDS_DS::IsValidShrunkData(const Handle(BOPDS_PaveBlock)& thePB)
+{
+  if (!thePB->HasShrunkData())
+    return Standard_False;
+
+  // Compare the distances from the bounds of the shrunk range to the vertices
+  // with the tolerance values of vertices
+
+  // Shrunk range
+  Standard_Real aTS[2];
+  Bnd_Box aBox;
+  Standard_Boolean bIsSplit;
+  //
+  thePB->ShrunkData(aTS[0], aTS[1], aBox, bIsSplit);
+  //
+  // Vertices
+  Standard_Integer nV[2];
+  thePB->Indices(nV[0], nV[1]);
+  //
+  const TopoDS_Edge& aE = TopoDS::Edge(Shape(thePB->OriginalEdge()));
+  BRepAdaptor_Curve aBAC(aE);
+  //
+  Standard_Real anEps = BRep_Tool::Tolerance(aE) * 0.01;
+  //
+  for (Standard_Integer i = 0; i < 2; ++i) {
+    const TopoDS_Vertex& aV = TopoDS::Vertex(Shape(nV[i]));
+    Standard_Real aTol = BRep_Tool::Tolerance(aV) + Precision::Confusion();
+    // Bounding point
+    gp_Pnt aP = BRep_Tool::Pnt(aV);
+    //
+    // Point on the end of shrunk range
+    gp_Pnt aPS = aBAC.Value(aTS[i]);
+    //
+    Standard_Real aDist = aP.Distance(aPS);
+    if (aTol - aDist > anEps) {
+      return Standard_False;
+    }
+  }
+  return Standard_True;
+}
\ No newline at end of file
index bfdabf7..6b19deb 100644 (file)
@@ -451,6 +451,9 @@ Standard_EXPORT virtual ~BOPDS_DS();
   //! Update the pave blocks for all shapes in data structure
   Standard_EXPORT void UpdatePaveBlocksWithSDVertices();
 
+  //! Update the pave block for all shapes in data structure
+  Standard_EXPORT void UpdatePaveBlockWithSDVertices(const Handle(BOPDS_PaveBlock)& thePB);
+
   //! Update the pave block of the common block for all shapes in data structure
   Standard_EXPORT void UpdateCommonBlockWithSDVertices(const Handle(BOPDS_CommonBlock)& theCB);
 
@@ -459,6 +462,12 @@ Standard_EXPORT virtual ~BOPDS_DS();
   //! Clears information about PaveBlocks for the untouched edges
   Standard_EXPORT void ReleasePaveBlocks();
 
+  //! Checks if the existing shrunk data of the pave block is still valid.<br>
+  //! The shrunk data may become invalid if e.g. the vertices of the pave block
+  //! have been replaced with the new one with bigger tolerances, or the tolerances
+  //! of the existing vertices have been increased.
+  Standard_EXPORT Standard_Boolean IsValidShrunkData(const Handle(BOPDS_PaveBlock)& thePB);
+
 protected:
 
   
@@ -466,9 +475,6 @@ protected:
   //! Initializes the pave blocks for the shape with index theIndex
   Standard_EXPORT void InitPaveBlocks (const Standard_Integer theIndex);
 
-  //! Update the pave block for all shapes in data structure
-  Standard_EXPORT void UpdatePaveBlockWithSDVertices(const Handle(BOPDS_PaveBlock)& thePB);
-
   //! Initializes the state of face with index theIndex
   Standard_EXPORT void InitFaceInfo (const Standard_Integer theIndex);
   
index 79669df..5fcfc87 100755 (executable)
@@ -26,5 +26,4 @@ checkprops result -l 3356.31
 checkshape result
 checksection result
 checknbshapes result -vertex 1197 -edge 1182 -wire 0 -face 0 -shell 0 -solid 0 -compsolid 0 -compound 1 -shape 2380
-checkview -display result -2d -path ${imagedir}/${test_image}.png
 
index e44151a..95a738b 100755 (executable)
@@ -1,5 +1,5 @@
 puts "TODO OCC25917 ALL: Faulty shapes in variables faulty_1 to faulty_"
-puts "TODO OCC25917 ALL: Error : The area of result shape is"
+puts "TODO ?OCC25917 ALL: Error : The area of result shape is"
 puts "TODO OCC25917 ALL: Error :  is WRONG because number of "
 puts "========================"
 puts " OCC472 "
index 0393861..b0d094e 100644 (file)
@@ -1,3 +1,8 @@
+puts "TODO OCC28786 ALL: Faulty shapes in variables faulty_1"
+#puts "TODO OCC28786 ALL: Error : The area of result shape is"
+#puts "TODO OCC28786 ALL: Error : The volume of result shape is"
+puts "TODO OCC28786 ALL: Error :  is WRONG because number of"
+
 puts "========"
 puts "0027448: BOPTools_AlgoTools::IsMicroEdge does not correspond to shape validity criteria"
 puts "Problem with Boolean CUT operation"
diff --git a/tests/bugs/modalg_6/bug28690 b/tests/bugs/modalg_6/bug28690
new file mode 100644 (file)
index 0000000..b9a356e
--- /dev/null
@@ -0,0 +1,25 @@
+puts "========"
+puts "OCC28690"
+puts "========"
+puts ""
+##########################################
+##  Section algorithm produces micro edge
+##########################################
+
+restore [locate_data_file bug28690_m8_faces.brep] a
+ttranslate a -20000 -584.41225425562368 0
+plane f 0 0 0 1 0 0
+mkface f f
+bsection r a f
+checknbshapes r -edge 3 -vertex 4
+checkshape r
+checkprops r -l 594.045
+
+# check that all edges have enough length
+foreach e [explode r] {
+  if {[validrange $e] == "edge has no valid range"} {
+    regexp {Mass : *([0-9\-+.eE]+)} [lprops $e] dummy len
+    regexp {Tolerance MAX=([0-9\-+.eE]+)} [tolerance $e] dummy tol
+    puts "Error: edge $e (lenth=$len, tolerance=$tol) is too small"
+  }
+}
diff --git a/tests/bugs/modalg_6/bug28690_1 b/tests/bugs/modalg_6/bug28690_1
new file mode 100644 (file)
index 0000000..4d144eb
--- /dev/null
@@ -0,0 +1,25 @@
+puts "========"
+puts "OCC28690"
+puts "========"
+puts ""
+##########################################
+##  Section algorithm produces micro edge
+##########################################
+
+restore [locate_data_file bug28690_m8_faces_1.brep] a
+ttranslate a -20000 -2597.4029071873542 -8.9312813979176155
+plane f 0 0 0 1 0 0
+mkface f f
+bsection r a f
+checknbshapes r -edge 2 -vertex 3
+checkshape r
+checkprops r -l 3896.32
+
+# check that all edges have enough length
+foreach e [explode r] {
+  if {[validrange $e] == "edge has no valid range"} {
+    regexp {Mass : *([0-9\-+.eE]+)} [lprops $e] dummy len
+    regexp {Tolerance MAX=([0-9\-+.eE]+)} [tolerance $e] dummy tol
+    puts "Error: edge $e (lenth=$len, tolerance=$tol) is too small"
+  }
+}
diff --git a/tests/bugs/modalg_6/bug28690_2 b/tests/bugs/modalg_6/bug28690_2
new file mode 100644 (file)
index 0000000..dd524b4
--- /dev/null
@@ -0,0 +1,24 @@
+puts "========"
+puts "OCC28690"
+puts "========"
+puts ""
+##########################################
+##  Section algorithm produces micro edge
+##########################################
+
+restore [locate_data_file bug28690_m9_faces.brep] a
+plane f 0 0 0 0 1 0
+mkface f f
+bsection r a f
+checknbshapes r -edge 3 -vertex 4
+checkshape r
+checkprops r -l 7976.14
+
+# check that all edges have enough length
+foreach e [explode r] {
+  if {[validrange $e] == "edge has no valid range"} {
+    regexp {Mass : *([0-9\-+.eE]+)} [lprops $e] dummy len
+    regexp {Tolerance MAX=([0-9\-+.eE]+)} [tolerance $e] dummy tol
+    puts "Error: edge $e (lenth=$len, tolerance=$tol) is too small"
+  }
+}
diff --git a/tests/bugs/modalg_6/bug28690_3 b/tests/bugs/modalg_6/bug28690_3
new file mode 100644 (file)
index 0000000..a6ebb05
--- /dev/null
@@ -0,0 +1,27 @@
+puts "========"
+puts "OCC28690"
+puts "========"
+puts ""
+##########################################
+##  Section algorithm produces micro edge
+##########################################
+
+restore [locate_data_file bug28690_gdml_G1_tore_sphere.brep] c
+explode c
+bclearobjects
+bcleartools
+baddobjects c_1
+baddtools c_2
+bfillds
+bbuild result1
+
+checkshape result1
+checknbshapes result1 -wire 3 -face 3 -shell 5 -solid 3
+checkprops result1 -s 4420.05 -v 15877.8
+
+bbop result 2
+checkshape result
+checknbshapes result -wire 1 -face 1 -shell 1 -solid 1
+checkprops result -s 112.393 -v 89.7477
+
+checkview -display result -2d -path ${imagedir}/${test_image}.png
\ No newline at end of file
diff --git a/tests/bugs/modalg_6/bug28775 b/tests/bugs/modalg_6/bug28775
new file mode 100644 (file)
index 0000000..a056ea2
--- /dev/null
@@ -0,0 +1,22 @@
+puts "========"
+puts "OCC28775"
+puts "========"
+puts ""
+####################################################################
+# Code duplication removal across the BOPAlgo_PaveFiller algorithm
+####################################################################
+
+vertex v1 1 0 0
+polyline p1 0 0 0 2 0 0
+polyline p2 1 0 -1 1 0 1
+
+bnondestructive 1
+
+bclearobjects
+bcleartools
+baddobjects v1 p1 p2
+bfillds
+bbuild result
+
+checkshape result
+checknbshapes result -edge 4