src/BOPAlgo/BOPAlgo_PaveFiller_2.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
   3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
   4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
   5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   6 //
   7 // This file is part of Open CASCADE Technology software library.
   8 //
   9 // This library is free software; you can redistribute it and/or modify it under
  10 // the terms of the GNU Lesser General Public License version 2.1 as published
  11 // by the Free Software Foundation, with special exception defined in the file
  12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  13 // distribution for complete text of the license and disclaimer of any warranty.
  14 //
  15 // Alternatively, this file may be used under the terms of Open CASCADE
  16 // commercial license or contractual agreement.
  17
  18
  19 #include <BOPAlgo_PaveFiller.hxx>
  20 #include <BOPAlgo_Tools.hxx>
  21 #include <BOPCol_NCVector.hxx>
  22 #include <BOPCol_Parallel.hxx>
  23 #include <BOPDS_DS.hxx>
  24 #include <BOPDS_Interf.hxx>
  25 #include <BOPDS_Iterator.hxx>
  26 #include <BOPDS_Pair.hxx>
  27 #include <BOPDS_PaveBlock.hxx>
  28 #include <BOPDS_VectorOfInterfVE.hxx>
  29 #include <BOPTools_AlgoTools.hxx>
  30 #include <BRep_Tool.hxx>
  31 #include <gp_Pnt.hxx>
  32 #include <IntTools_Context.hxx>
  33 #include <Precision.hxx>
  34 #include <TopoDS.hxx>
  35 #include <TopoDS_Edge.hxx>
  36 #include <TopoDS_Vertex.hxx>
  37
  38 //=======================================================================
  39 //class    : BOPAlgo_VertexEdge
  40 //purpose  :
  41 //=======================================================================
  42 class BOPAlgo_VertexEdge : public BOPAlgo_Algo {
  43
  44  public:
  45   DEFINE_STANDARD_ALLOC
  46
  47   BOPAlgo_VertexEdge() :
  48     BOPAlgo_Algo(),
  49     myIV(-1), myIE(-1), myFlag(-1), myT(-1.), myTolVNew(-1.) {
  50   };
  51   //
  52   virtual ~BOPAlgo_VertexEdge(){
  53   };
  54   //
  55   void SetIndices(const Standard_Integer nV,
  56                   const Standard_Integer nE) {
  57     myIV=nV;
  58     myIE=nE;
  59   }
  60   //
  61   void Indices(Standard_Integer& nV,
  62                Standard_Integer& nE) const {
  63     nV=myIV;
  64     nE=myIE;
  65   }
  66   //
  67   void SetVertex(const TopoDS_Vertex& aV) {
  68     myV=aV;
  69   }
  70   //
  71   void SetEdge(const TopoDS_Edge& aE) {
  72     myE=aE;
  73   }
  74   //
  75   const TopoDS_Vertex& Vertex() const {
  76     return myV;
  77   }
  78   //
  79   const TopoDS_Edge& Edge() const {
  80     return myE;
  81   }
  82   //
  83   Standard_Integer Flag()const {
  84     return myFlag;
  85   }
  86   //
  87   Standard_Real Parameter()const {
  88     return myT;
  89   }
  90   //
  91   Standard_Real VertexNewTolerance()const {
  92     return myTolVNew;
  93   }
  94   //
  95   void SetContext(const Handle(IntTools_Context)& aContext) {
  96     myContext=aContext;
  97   }
  98   //
  99   const Handle(IntTools_Context)& Context()const {
 100     return myContext;
 101   }
 102   //
 103   void SetPaveBlock(const Handle(BOPDS_PaveBlock)& thePB) {
 104     myPB = thePB;
 105   }
 106   //
 107   const Handle(BOPDS_PaveBlock)& PaveBlock() const {
 108     return myPB;
 109   }
 110   //
 111   virtual void Perform() {
 112     BOPAlgo_Algo::UserBreak();
 113     myFlag=myContext->ComputeVE (myV, myE, myT, myTolVNew, myFuzzyValue);
 114   };
 115   //
 116  protected:
 117   Standard_Integer myIV;
 118   Standard_Integer myIE;
 119   Standard_Integer myFlag;
 120   Standard_Real myT;
 121   Standard_Real myTolVNew;
 122   TopoDS_Vertex myV;
 123   TopoDS_Edge myE;
 124   Handle(IntTools_Context) myContext;
 125   Handle(BOPDS_PaveBlock) myPB;
 126 };
 127 //=======================================================================
 128 typedef BOPCol_NCVector
 129   <BOPAlgo_VertexEdge> BOPAlgo_VectorOfVertexEdge;
 130 //
 131 typedef BOPCol_ContextFunctor
 132   <BOPAlgo_VertexEdge,
 133   BOPAlgo_VectorOfVertexEdge,
 134   Handle(IntTools_Context),
 135   IntTools_Context> BOPAlgo_VertexEdgeFunctor;
 136 //
 137 typedef BOPCol_ContextCnt
 138   <BOPAlgo_VertexEdgeFunctor,
 139   BOPAlgo_VectorOfVertexEdge,
 140   Handle(IntTools_Context)> BOPAlgo_VertexEdgeCnt;
 141 //
 142 //=======================================================================
 143 // function: PerformVE
 144 // purpose:
 145 //=======================================================================
 146 void BOPAlgo_PaveFiller::PerformVE()
 147 {
 148   FillShrunkData(TopAbs_VERTEX, TopAbs_EDGE);
 149   //
 150   myIterator->Initialize(TopAbs_VERTEX, TopAbs_EDGE);
 151   Standard_Integer iSize = myIterator->ExpectedLength();
 152   if (!iSize) {
 153     return;
 154   }
 155   //
 156   // Prepare pairs for intersection
 157   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMVEPairs;
 158   for (; myIterator->More(); myIterator->Next()) {
 159     Standard_Integer nV, nE;
 160     myIterator->Value(nV, nE);
 161     //
 162     const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
 163     if (aSIE.HasSubShape(nV)) {
 164       continue;
 165     }
 166     //
 167     if (aSIE.HasFlag()){
 168       continue;
 169     }
 170     //
 171     if (myDS->HasInterfShapeSubShapes(nV, nE)) {
 172       continue;
 173     }
 174     //
 175     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
 176     if (aLPB.IsEmpty()) {
 177       continue;
 178     }
 179     //
 180     const Handle(BOPDS_PaveBlock)& aPB = aLPB.First();
 181     if (!aPB->IsSplittable()) {
 182       // this is a micro edge, ignore it
 183       continue;
 184     }
 185     //
 186     BOPCol_ListOfInteger* pLV = aMVEPairs.ChangeSeek(aPB);
 187     if (!pLV)
 188       pLV = &aMVEPairs(aMVEPairs.Add(aPB, BOPCol_ListOfInteger()));
 189     pLV->Append(nV);
 190   }
 191   //
 192   IntersectVE(aMVEPairs);
 193 }
 194
 195 //=======================================================================
 196 // function: IntersectVE
 197 // purpose:
 198 //=======================================================================
 199 void BOPAlgo_PaveFiller::IntersectVE
 200   (const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& theVEPairs,
 201    const Standard_Boolean theAddInterfs)
 202 {
 203   Standard_Integer i, aNbVE = theVEPairs.Extent();
 204   if (!aNbVE) {
 205     return;
 206   }
 207   //
 208   BOPDS_VectorOfInterfVE& aVEs = myDS->InterfVE();
 209   if (theAddInterfs) {
 210     aVEs.SetIncrement(aNbVE);
 211   }
 212   //
 213   // Prepare for intersection.
 214   BOPAlgo_VectorOfVertexEdge aVVE;
 215   // Map to collect all SD connections to add interferences
 216   // for all vertices having the same SD vertex.
 217   // It will also be used as a Fence map to avoid repeated
 218   // intersection of the same SD vertex with edge
 219   NCollection_DataMap<BOPDS_Pair, BOPCol_ListOfInteger, BOPDS_PairMapHasher> aDMVSD;
 220   //
 221   for (i = 1; i <= aNbVE; ++i) {
 222     const Handle(BOPDS_PaveBlock)& aPB = theVEPairs.FindKey(i);
 223     Standard_Integer nE = aPB->OriginalEdge();
 224     //
 225     const BOPCol_ListOfInteger& aLV = theVEPairs(i);
 226     BOPCol_ListIteratorOfListOfInteger aItLV(aLV);
 227     for (; aItLV.More(); aItLV.Next()) {
 228       Standard_Integer nV = aItLV.Value();
 229       //
 230       Standard_Integer nVSD = nV;
 231       myDS->HasShapeSD(nV, nVSD);
 232       //
 233       BOPDS_Pair aPair(nVSD, nE);
 234       BOPCol_ListOfInteger* pLI = aDMVSD.ChangeSeek(aPair);
 235       if (pLI) {
 236         // Already added
 237         pLI->Append(nV);
 238         continue;
 239       }
 240       // New pair
 241       pLI = aDMVSD.Bound(aPair, BOPCol_ListOfInteger());
 242       pLI->Append(nV);
 243       //
 244       const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nVSD));
 245       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
 246       //
 247       BOPAlgo_VertexEdge& aVESolver = aVVE.Append1();
 248       aVESolver.SetIndices(nVSD, nE);
 249       aVESolver.SetVertex(aV);
 250       aVESolver.SetEdge(aE);
 251       aVESolver.SetPaveBlock(aPB);
 252       aVESolver.SetFuzzyValue(myFuzzyValue);
 253       aVESolver.SetProgressIndicator(myProgressIndicator);
 254     }
 255   }
 256   //
 257   // Perform intersection
 258   //=============================================================
 259   BOPAlgo_VertexEdgeCnt::Perform(myRunParallel, aVVE, myContext);
 260   //=============================================================
 261   //
 262   // Keep the modified edges for further update
 263   BOPCol_MapOfInteger aMEdges;
 264   //
 265   // Analyze intersections
 266   aNbVE = aVVE.Extent();
 267   for (i = 0; i < aNbVE; ++i) {
 268     const BOPAlgo_VertexEdge& aVESolver = aVVE(i);
 269     if (aVESolver.Flag() != 0) {
 270       continue;
 271     }
 272     //
 273     Standard_Integer nV, nE;
 274     aVESolver.Indices(nV, nE);
 275     // Parameter of vertex on edge
 276     Standard_Real aT = aVESolver.Parameter();
 277     // 1. Update vertex V/E if necessary
 278     Standard_Real aTolVNew = aVESolver.VertexNewTolerance();
 279     Standard_Integer nVx = UpdateVertex(nV, aTolVNew);
 280     // 2. Create new pave and add it as extra pave to pave block
 281     //    for further splitting of the edge
 282     const Handle(BOPDS_PaveBlock)& aPB = aVESolver.PaveBlock();
 283     BOPDS_Pave aPave;
 284     aPave.SetIndex(nVx);
 285     aPave.SetParameter(aT);
 286     aPB->AppendExtPave(aPave);
 287     aMEdges.Add(nE);
 288     //
 289     if (theAddInterfs) {
 290       // Add interferences into DS
 291       BOPDS_Pair aPair(nV, nE);
 292       const BOPCol_ListOfInteger& aLI = aDMVSD.Find(aPair);
 293       BOPCol_ListIteratorOfListOfInteger aItLI(aLI);
 294       for (; aItLI.More(); aItLI.Next()) {
 295         const Standard_Integer nVOld = aItLI.Value();
 296         // 3. Create interference V/E
 297         BOPDS_InterfVE& aVE = aVEs.Append1();
 298         aVE.SetIndices(nVOld, nE);
 299         aVE.SetParameter(aT);
 300         // 2. Add a pair in the whole table of interferences
 301         myDS->AddInterf(nVOld, nE);
 302         // 4. Set index of new vertex in the interference
 303         if (myDS->IsNewShape(nVx)) {
 304           aVE.SetIndexNew(nVx);
 305         }
 306       }
 307     }
 308   }
 309   //
 310   // Split pave blocks of the intersected edges with the extra paves.
 311   // At the same time compute shrunk data for the new pave blocks
 312   // and in case there is no valid range for the pave block,
 313   // the vertices of this pave block should be unified.
 314   SplitPaveBlocks(aMEdges, theAddInterfs);
 315 }
 316
 317 //=======================================================================
 318 // function: MakeNewCommonBlock
 319 // purpose: Make new Common Block from the given list of Pave Blocks
 320 //=======================================================================
 321 static
 322   void MakeNewCommonBlock(const BOPDS_ListOfPaveBlock& theLPB,
 323                           const BOPCol_ListOfInteger& theLFaces,
 324                           BOPDS_PDS& theDS)
 325 {
 326   // Make Common Block from the pave blocks in the list
 327   Handle(BOPDS_CommonBlock) aCBNew = new BOPDS_CommonBlock;
 328   aCBNew->SetPaveBlocks(theLPB);
 329   aCBNew->SetFaces(theLFaces);
 330   //
 331   BOPDS_ListIteratorOfListOfPaveBlock aItLPB(theLPB);
 332   for (; aItLPB.More(); aItLPB.Next()) {
 333     theDS->SetCommonBlock(aItLPB.ChangeValue(), aCBNew);
 334   }
 335 }
 336
 337 //=======================================================================
 338 // function: SplitPaveBlocks
 339 // purpose:
 340 //=======================================================================
 341 void BOPAlgo_PaveFiller::SplitPaveBlocks(const BOPCol_MapOfInteger& theMEdges,
 342                                          const Standard_Boolean theAddInterfs)
 343 {
 344   // Fence map to avoid unification of the same vertices twice
 345   BOPDS_MapOfPair aMPairs;
 346   // Map to treat the Common Blocks
 347   NCollection_IndexedDataMap<Handle(BOPDS_CommonBlock),
 348                              BOPDS_ListOfPaveBlock,
 349                              TColStd_MapTransientHasher> aMCBNewPB;
 350   //
 351   BOPCol_MapIteratorOfMapOfInteger aItM(theMEdges);
 352   for (; aItM.More(); aItM.Next()) {
 353     Standard_Integer nE = aItM.Value();
 354     BOPDS_ListOfPaveBlock& aLPB = myDS->ChangePaveBlocks(nE);
 355     //
 356     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
 357     for (; aItLPB.More();) {
 358       Handle(BOPDS_PaveBlock)& aPB = aItLPB.ChangeValue();
 359       //
 360       if (!aPB->IsToUpdate()) {
 361         aItLPB.Next();
 362         continue;
 363       }
 364       //
 365       const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
 366       //
 367       // Compute new pave blocks
 368       BOPDS_ListOfPaveBlock aLPBN;
 369       aPB->Update(aLPBN);
 370       //
 371       // Make sure that each new pave block has a valid range,
 372       // otherwise unify the vertices of the pave block
 373       BOPDS_ListIteratorOfListOfPaveBlock aItLPBN(aLPBN);
 374       for (; aItLPBN.More(); aItLPBN.Next()) {
 375         Handle(BOPDS_PaveBlock)& aPBN = aItLPBN.ChangeValue();
 376         myDS->UpdatePaveBlockWithSDVertices(aPBN);
 377         FillShrunkData(aPBN);
 378         //
 379         if (!aPBN->HasShrunkData()) {
 380           // No valid range, unify vertices
 381           Standard_Integer nV1, nV2;
 382           aPBN->Indices(nV1, nV2);
 383           if (nV1 != nV2) {
 384             BOPDS_Pair aPair;
 385             aPair.SetIndices(nV1, nV2);
 386             if (aMPairs.Add(aPair)) {
 387               BOPCol_ListOfInteger aLV;
 388               aLV.Append(nV1);
 389               aLV.Append(nV2);
 390               MakeSDVertices(aLV, theAddInterfs);
 391             }
 392           }
 393           continue;
 394         }
 395         //
 396         // Update the list with new pave block
 397         aLPB.Append(aPBN);
 398         // Treat the common block
 399         if (!aCB.IsNull()) {
 400           // Store the new pave block to make new common block
 401           BOPDS_ListOfPaveBlock* pLPBCB = aMCBNewPB.ChangeSeek(aCB);
 402           if (!pLPBCB) {
 403             pLPBCB = &aMCBNewPB(aMCBNewPB.Add(aCB, BOPDS_ListOfPaveBlock()));
 404           }
 405           pLPBCB->Append(aPBN);
 406         }
 407       }
 408       // Remove old pave block
 409       aLPB.Remove(aItLPB);
 410     }
 411   }
 412   //
 413   // Make Common Blocks
 414   Standard_Integer i, aNbCB = aMCBNewPB.Extent();
 415   for (i = 1; i <= aNbCB; ++i) {
 416     const Handle(BOPDS_CommonBlock)& aCB = aMCBNewPB.FindKey(i);
 417     const BOPDS_ListOfPaveBlock& aLPBN = aMCBNewPB(i);
 418     //
 419     // For each group of pave blocks with the same vertices make new common block
 420     NCollection_IndexedDataMap<BOPDS_Pair, BOPDS_ListOfPaveBlock, BOPDS_PairMapHasher> aMInds;
 421     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPBN);
 422     for (; aItLPB.More(); aItLPB.Next()) {
 423       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
 424       //
 425       BOPDS_Pair aPair;
 426       aPair.SetIndices(aPB->Pave1().Index(), aPB->Pave2().Index());
 427       //
 428       BOPDS_ListOfPaveBlock* pLPBx = aMInds.ChangeSeek(aPair);
 429       if (!pLPBx) {
 430         pLPBx = &aMInds(aMInds.Add(aPair, BOPDS_ListOfPaveBlock()));
 431       }
 432       pLPBx->Append(aPB);
 433     }
 434     //
 435     Standard_Integer nV1, nV2;
 436     aCB->PaveBlock1()->Indices(nV1, nV2);
 437     Standard_Boolean bIsClosed = (nV1 == nV2);
 438     //
 439     Standard_Integer j, aNbPairs = aMInds.Extent();
 440     for (j = 1; j <= aNbPairs; ++j) {
 441       BOPDS_ListOfPaveBlock& aLPB = aMInds(j);
 442       //
 443       if (!bIsClosed) {
 444         // Make Common Block from the pave blocks in the list
 445         MakeNewCommonBlock(aLPB, aCB->Faces(), myDS);
 446         continue;
 447       }
 448       //
 449       // Find coinciding pave blocks
 450       while (aLPB.Extent()) {
 451         // Pave blocks forming the common block
 452         BOPDS_ListOfPaveBlock aLPBCB;
 453         // Point in the middle of the first pave block in the common block
 454         gp_Pnt aPMFirst(0., 0., 0.);
 455         // Tolerance of the first edge in the common block
 456         Standard_Real aTolEFirst = 0.;
 457         //
 458         aItLPB.Initialize(aLPB);
 459         for (; aItLPB.More();) {
 460           const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
 461           if (aLPBCB.IsEmpty()) {
 462             aLPBCB.Append(aPB);
 463             const TopoDS_Edge& aEFirst = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
 464             aTolEFirst = BRep_Tool::MaxTolerance(aEFirst, TopAbs_VERTEX);
 465             //
 466             Standard_Real aTmFirst = (aPB->Pave1().Parameter() + aPB->Pave2().Parameter()) / 2.;
 467             BOPTools_AlgoTools::PointOnEdge(aEFirst, aTmFirst, aPMFirst);
 468             //
 469             aLPB.Remove(aItLPB);
 470             continue;
 471           }
 472           //
 473           // Check pave blocks for coincidence
 474           const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->OriginalEdge()));
 475           Standard_Real aTolE = BRep_Tool::MaxTolerance(aE, TopAbs_VERTEX);
 476           //
 477           Standard_Real aTOut, aDist;
 478           Standard_Integer iErr =
 479             myContext->ComputePE(aPMFirst, aTolEFirst + aTolE + myFuzzyValue, aE, aTOut, aDist);
 480           if (!iErr && ((aTOut > aPB->Pave1().Parameter()) && (aTOut < aPB->Pave2().Parameter()))) {
 481             aLPBCB.Append(aPB);
 482             aLPB.Remove(aItLPB);
 483             continue;
 484           }
 485           aItLPB.Next();
 486         }
 487         //
 488         // Make Common Block from the pave blocks in the list
 489         MakeNewCommonBlock(aLPBCB, aCB->Faces(), myDS);
 490       }
 491     }
 492   }
 493 }