src/BOPAlgo/BOPAlgo_Builder_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_Builder.hxx>
  20 #include <BOPAlgo_BuilderFace.hxx>
  21 #include <BOPAlgo_PaveFiller.hxx>
  22 #include <BOPAlgo_Tools.hxx>
  23 #include <BOPDS_DS.hxx>
  24 #include <BOPDS_FaceInfo.hxx>
  25 #include <BOPDS_Interf.hxx>
  26 #include <BOPDS_MapOfPaveBlock.hxx>
  27 #include <BOPDS_PaveBlock.hxx>
  28 #include <BOPDS_ShapeInfo.hxx>
  29 #include <BOPDS_VectorOfCurve.hxx>
  30 #include <BOPDS_VectorOfInterfFF.hxx>
  31 #include <BOPDS_VectorOfPoint.hxx>
  32 #include <BOPTools_AlgoTools.hxx>
  33 #include <BOPTools_AlgoTools2D.hxx>
  34 #include <BOPTools_AlgoTools3D.hxx>
  35 #include <BOPTools_CoupleOfShape.hxx>
  36 #include <BOPTools_ListOfCoupleOfShape.hxx>
  37 #include <BOPTools_MapOfSet.hxx>
  38 #include <BOPTools_Parallel.hxx>
  39 #include <BRep_Builder.hxx>
  40 #include <BRepLib.hxx>
  41 #include <BRep_Tool.hxx>
  42 #include <GeomAdaptor_Surface.hxx>
  43 #include <GeomLib.hxx>
  44 #include <NCollection_IncAllocator.hxx>
  45 #include <NCollection_Vector.hxx>
  46 #include <Precision.hxx>
  47 #include <IntTools_Context.hxx>
  48 #include <TColStd_ListOfInteger.hxx>
  49 #include <TColStd_MapOfInteger.hxx>
  50 #include <TopExp_Explorer.hxx>
  51 #include <TopoDS.hxx>
  52 #include <TopoDS_Compound.hxx>
  53 #include <TopoDS_Edge.hxx>
  54 #include <TopoDS_Face.hxx>
  55 #include <TopoDS_Shape.hxx>
  56 #include <TopoDS_Vertex.hxx>
  57 #include <TopTools_ListOfShape.hxx>
  58
  59 #include <algorithm>
  60 //
  61 static
  62   TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
  63                              const TopTools_DataMapOfShapeListOfShape& theImages,
  64                              Handle(IntTools_Context)& theCtx);
  65
  66 //=======================================================================
  67 //class    : BOPAlgo_PairOfShapeBoolean
  68 //purpose  :
  69 //=======================================================================
  70 class BOPAlgo_PairOfShapeBoolean : public BOPAlgo_Algo {
  71
  72  public:
  73   DEFINE_STANDARD_ALLOC
  74
  75   BOPAlgo_PairOfShapeBoolean() :
  76     BOPAlgo_Algo(),
  77     myFlag(Standard_False) {
  78   }
  79   //
  80   virtual ~BOPAlgo_PairOfShapeBoolean() {
  81   }
  82   //
  83   TopoDS_Shape& Shape1() {
  84     return myShape1;
  85   }
  86   //
  87   TopoDS_Shape& Shape2() {
  88     return myShape2;
  89   }
  90   //
  91   Standard_Boolean& Flag() {
  92     return myFlag;
  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   virtual void Perform() {
 104     BOPAlgo_Algo::UserBreak();
 105     //
 106     const TopoDS_Face& aFj=*((TopoDS_Face*)&myShape1);
 107     const TopoDS_Face& aFk=*((TopoDS_Face*)&myShape2);
 108     myFlag=BOPTools_AlgoTools::AreFacesSameDomain(aFj, aFk, myContext, myFuzzyValue);
 109   }
 110   //
 111  protected:
 112   Standard_Boolean myFlag;
 113   TopoDS_Shape myShape1;
 114   TopoDS_Shape myShape2;
 115   Handle(IntTools_Context) myContext;
 116 };
 117 //
 118 typedef NCollection_Vector<BOPAlgo_PairOfShapeBoolean> \
 119   BOPAlgo_VectorOfPairOfShapeBoolean;
 120 //
 121 typedef BOPTools_ContextFunctor
 122   <BOPAlgo_PairOfShapeBoolean,
 123   BOPAlgo_VectorOfPairOfShapeBoolean,
 124   Handle(IntTools_Context),
 125   IntTools_Context> BOPAlgo_BuilderSDFaceFunctor;
 126 //
 127 typedef BOPTools_ContextCnt
 128   <BOPAlgo_BuilderSDFaceFunctor,
 129   BOPAlgo_VectorOfPairOfShapeBoolean,
 130   Handle(IntTools_Context)> BOPAlgo_BuilderSDFaceCnt;
 131 //
 132 //=======================================================================
 133 // BuilderFace
 134 //
 135 typedef NCollection_Vector<BOPAlgo_BuilderFace> BOPAlgo_VectorOfBuilderFace;
 136 //
 137 typedef BOPTools_Functor
 138   <BOPAlgo_BuilderFace,
 139   BOPAlgo_VectorOfBuilderFace> BOPAlgo_BuilderFaceFunctor;
 140 //
 141 typedef BOPTools_Cnt
 142   <BOPAlgo_BuilderFaceFunctor,
 143   BOPAlgo_VectorOfBuilderFace> BOPAlgo_BuilderFaceCnt;
 144 //
 145 //=======================================================================
 146 //class    : BOPAlgo_VFI
 147 //purpose  :
 148 //=======================================================================
 149 class BOPAlgo_VFI : public BOPAlgo_Algo {
 150
 151  public:
 152   DEFINE_STANDARD_ALLOC
 153
 154   BOPAlgo_VFI() :
 155     BOPAlgo_Algo(),
 156     myIsInternal(Standard_False) {
 157   }
 158   //
 159   virtual ~BOPAlgo_VFI(){
 160   }
 161   //
 162   void SetVertex(const TopoDS_Vertex& aV) {
 163     myV=aV;
 164   }
 165   //
 166   TopoDS_Vertex& Vertex() {
 167     return myV;
 168   }
 169   //
 170   void SetFace(const TopoDS_Face& aF) {
 171     myF=aF;
 172   }
 173   //
 174   TopoDS_Face& Face() {
 175     return myF;
 176   }
 177   //
 178   Standard_Boolean IsInternal()const {
 179     return myIsInternal;
 180   }
 181   //
 182   void SetContext(const Handle(IntTools_Context)& aContext) {
 183     myContext=aContext;
 184   }
 185   //
 186   const Handle(IntTools_Context)& Context()const {
 187     return myContext;
 188   }
 189   //
 190   virtual void Perform() {
 191     Standard_Real aT1, aT2, dummy;
 192     //
 193     BOPAlgo_Algo::UserBreak();
 194     Standard_Integer iFlag =
 195       myContext->ComputeVF(myV, myF, aT1, aT2, dummy, myFuzzyValue);
 196     myIsInternal = (iFlag == 0);
 197   }
 198   //
 199  protected:
 200   Standard_Boolean myIsInternal;
 201   TopoDS_Vertex myV;
 202   TopoDS_Face myF;
 203   Handle(IntTools_Context) myContext;
 204 };
 205 //
 206 typedef NCollection_Vector<BOPAlgo_VFI> BOPAlgo_VectorOfVFI;
 207 //
 208 typedef BOPTools_ContextFunctor
 209   <BOPAlgo_VFI,
 210   BOPAlgo_VectorOfVFI,
 211   Handle(IntTools_Context),
 212   IntTools_Context> BOPAlgo_VFIFunctor;
 213 //
 214 typedef BOPTools_ContextCnt
 215   <BOPAlgo_VFIFunctor,
 216   BOPAlgo_VectorOfVFI,
 217   Handle(IntTools_Context)> BOPAlgo_VFICnt;
 218 //
 219 //=======================================================================
 220 //function : FillImagesFaces
 221 //purpose  :
 222 //=======================================================================
 223 void BOPAlgo_Builder::FillImagesFaces()
 224 {
 225   BuildSplitFaces();
 226   FillSameDomainFaces();
 227   FillInternalVertices();
 228 }
 229 //=======================================================================
 230 //function : BuildSplitFaces
 231 //purpose  :
 232 //=======================================================================
 233 void BOPAlgo_Builder::BuildSplitFaces()
 234 {
 235   Standard_Boolean bHasFaceInfo, bIsClosed, bIsDegenerated, bToReverse;
 236   Standard_Integer i, j, k, aNbS, aNbPBIn, aNbPBOn, aNbPBSc, aNbAV, nSp;
 237   TopoDS_Face aFF, aFSD;
 238   TopoDS_Edge aSp, aEE;
 239   TopAbs_Orientation anOriF, anOriE;
 240   TopExp_Explorer aExp;
 241   TopTools_ListIteratorOfListOfShape aIt;
 242   TColStd_ListOfInteger aLIAV;
 243   TopTools_MapOfShape aMFence;
 244   Handle(NCollection_BaseAllocator) aAllocator;
 245   BOPAlgo_VectorOfBuilderFace aVBF;
 246   //
 247   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope f
 248   aAllocator=
 249     NCollection_BaseAllocator::CommonBaseAllocator();
 250   //
 251   TopTools_ListOfShape aLE(aAllocator);
 252   TopTools_MapOfShape aMDE(100, aAllocator);
 253   //
 254   // Build temporary map of faces images to avoid rebuilding
 255   // of the faces without any IN or section edges
 256   NCollection_IndexedDataMap<Standard_Integer, TopTools_ListOfShape> aFacesIm;
 257   //
 258   aNbS=myDS->NbSourceShapes();
 259   //
 260   for (i=0; i<aNbS; ++i) {
 261     const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
 262     if (aSI.ShapeType()!=TopAbs_FACE) {
 263       continue;
 264     }
 265     //
 266     const TopoDS_Face& aF=(*(TopoDS_Face*)(&aSI.Shape()));
 267     Standard_Boolean isUClosed = Standard_False,
 268                      isVClosed = Standard_False,
 269                      isChecked = Standard_False;
 270     //
 271     bHasFaceInfo=myDS->HasFaceInfo(i);
 272     if(!bHasFaceInfo) {
 273       continue;
 274     }
 275     //
 276     const BOPDS_FaceInfo& aFI=myDS->FaceInfo(i);
 277     //
 278     const BOPDS_IndexedMapOfPaveBlock& aMPBIn=aFI.PaveBlocksIn();
 279     const BOPDS_IndexedMapOfPaveBlock& aMPBOn=aFI.PaveBlocksOn();
 280     const BOPDS_IndexedMapOfPaveBlock& aMPBSc=aFI.PaveBlocksSc();
 281     aLIAV.Clear();
 282     myDS->AloneVertices(i, aLIAV);
 283
 284     aNbPBIn=aMPBIn.Extent();
 285     aNbPBOn=aMPBOn.Extent();
 286     aNbPBSc=aMPBSc.Extent();
 287     aNbAV=aLIAV.Extent();
 288     if (!aNbPBIn && !aNbPBOn && !aNbPBSc && !aNbAV) { // not compete
 289       continue;
 290     }
 291
 292     if (!aNbPBIn && !aNbPBSc)
 293     {
 294       if (!aNbAV)
 295       {
 296         // Check if any wires of the face have been modified.
 297         // If not, there is no need to create the new face.
 298         TopoDS_Iterator aItW(aF);
 299         for (; aItW.More(); aItW.Next())
 300         {
 301           if (myImages.IsBound(aItW.Value()))
 302             break;
 303         }
 304         if (!aItW.More())
 305           continue;
 306       }
 307
 308       // No internal parts for the face, so just build the draft face
 309       // and keep it to pass directly into result.
 310       // If the original face has any internal edges or multi-connected vertices,
 311       // the draft face will be null, as such sub-shapes may split the face on parts
 312       // (as in the case "bugs modalg_5 bug25245_1").
 313       // The BuilderFace algorithm will be called in this case.
 314       TopoDS_Face aFD = BuildDraftFace(aF, myImages, myContext);
 315       if (!aFD.IsNull())
 316       {
 317         aFacesIm(aFacesIm.Add(i, TopTools_ListOfShape())).Append(aFD);
 318         continue;
 319       }
 320     }
 321
 322     aMFence.Clear();
 323     //
 324     anOriF=aF.Orientation();
 325     aFF=aF;
 326     aFF.Orientation(TopAbs_FORWARD);
 327     //
 328     // 1. Fill the edges set for the face aFF -> LE
 329     aLE.Clear();
 330
 331     // 1.1 Bounding edges
 332     aExp.Init(aFF, TopAbs_EDGE);
 333     for (; aExp.More(); aExp.Next()) {
 334       const TopoDS_Edge& aE=(*(TopoDS_Edge*)(&aExp.Current()));
 335       anOriE=aE.Orientation();
 336       //
 337       if (!myImages.IsBound(aE)) {
 338         if (anOriE==TopAbs_INTERNAL) {
 339           aEE=aE;
 340           aEE.Orientation(TopAbs_FORWARD);
 341           aLE.Append(aEE);
 342           aEE.Orientation(TopAbs_REVERSED);
 343           aLE.Append(aEE);
 344         }
 345         else {
 346           aLE.Append(aE);
 347         }
 348
 349         continue;
 350       }
 351
 352       if(!isChecked)
 353       {
 354         const Handle(Geom_Surface) aSurf = BRep_Tool::Surface(aF);
 355         GeomLib::IsClosed(aSurf, BRep_Tool::Tolerance(aE),
 356           isUClosed, isVClosed);
 357
 358         isChecked = Standard_True;
 359       }
 360
 361       bIsClosed = Standard_False;
 362
 363       if((isUClosed || isVClosed) && BRep_Tool::IsClosed(aE, aF))
 364       {
 365
 366         Standard_Boolean isUIso = Standard_False, isVIso = Standard_False;
 367         BOPTools_AlgoTools2D::IsEdgeIsoline(aE, aF, isUIso, isVIso);
 368
 369         bIsClosed = ((isUClosed && isUIso) || (isVClosed && isVIso));
 370       }
 371
 372       bIsDegenerated=BRep_Tool::Degenerated(aE);
 373
 374       const TopTools_ListOfShape& aLIE=myImages.Find(aE);
 375       aIt.Initialize(aLIE);
 376       for (; aIt.More(); aIt.Next()) {
 377         aSp=(*(TopoDS_Edge*)(&aIt.Value()));
 378         if (bIsDegenerated) {
 379           aSp.Orientation(anOriE);
 380           aLE.Append(aSp);
 381           continue;
 382         }
 383         //
 384         if (anOriE==TopAbs_INTERNAL) {
 385           aSp.Orientation(TopAbs_FORWARD);
 386           aLE.Append(aSp);
 387           aSp.Orientation(TopAbs_REVERSED);
 388           aLE.Append(aSp);
 389           continue;
 390         }
 391           //
 392         if (bIsClosed) {
 393           if (aMFence.Add(aSp)) {
 394             if (!BRep_Tool::IsClosed(aSp, aF)){
 395               BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, aF);
 396             }
 397             //
 398             aSp.Orientation(TopAbs_FORWARD);
 399             aLE.Append(aSp);
 400             aSp.Orientation(TopAbs_REVERSED);
 401             aLE.Append(aSp);
 402           }// if (aMFence.Add(aSp))
 403           continue;
 404         }// if (bIsClosed){
 405         //
 406         aSp.Orientation(anOriE);
 407         bToReverse=BOPTools_AlgoTools::IsSplitToReverse(aSp, aE, myContext);
 408         if (bToReverse) {
 409           aSp.Reverse();
 410         }
 411         aLE.Append(aSp);
 412       }// for (; aIt.More(); aIt.Next()) {
 413     }// for (; aExp.More(); aExp.Next()) {
 414     //
 415     //
 416     // 1.2 In edges
 417     for (j=1; j<=aNbPBIn; ++j) {
 418       const Handle(BOPDS_PaveBlock)& aPB=aMPBIn(j);
 419       nSp=aPB->Edge();
 420       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
 421       //
 422       aSp.Orientation(TopAbs_FORWARD);
 423       aLE.Append(aSp);
 424       aSp.Orientation(TopAbs_REVERSED);
 425       aLE.Append(aSp);
 426     }
 427     //
 428     //
 429     // 1.3 Section edges
 430     for (j=1; j<=aNbPBSc; ++j) {
 431       const Handle(BOPDS_PaveBlock)& aPB=aMPBSc(j);
 432       nSp=aPB->Edge();
 433       aSp=(*(TopoDS_Edge*)(&myDS->Shape(nSp)));
 434       //
 435       aSp.Orientation(TopAbs_FORWARD);
 436       aLE.Append(aSp);
 437       aSp.Orientation(TopAbs_REVERSED);
 438       aLE.Append(aSp);
 439     }
 440     //
 441     if (!myPaveFiller->NonDestructive()) {
 442       // speed up for planar faces
 443       BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
 444     }
 445     // 3 Build split faces
 446     BOPAlgo_BuilderFace& aBF=aVBF.Appended();
 447     aBF.SetFace(aF);
 448     aBF.SetShapes(aLE);
 449     aBF.SetRunParallel(myRunParallel);
 450     aBF.SetProgressIndicator(myProgressIndicator);
 451     //
 452   }// for (i=0; i<aNbS; ++i) {
 453   //
 454   //===================================================
 455   BOPAlgo_BuilderFaceCnt::Perform(myRunParallel, aVBF);
 456   //===================================================
 457   //
 458   Standard_Integer aNbBF = aVBF.Length();
 459   for (k = 0; k < aNbBF; ++k)
 460   {
 461     BOPAlgo_BuilderFace& aBF = aVBF(k);
 462     aFacesIm.Add(myDS->Index(aBF.Face()), aBF.Areas());
 463   }
 464
 465   aNbBF = aFacesIm.Extent();
 466   for (k = 1; k <= aNbBF; ++k)
 467   {
 468     const TopoDS_Face& aF = TopoDS::Face(myDS->Shape(aFacesIm.FindKey(k)));
 469     anOriF = aF.Orientation();
 470     const TopTools_ListOfShape& aLFR = aFacesIm(k);
 471     //
 472     TopTools_ListOfShape* pLFIm = myImages.Bound(aF, TopTools_ListOfShape());
 473     aIt.Initialize(aLFR);
 474     for (; aIt.More(); aIt.Next()) {
 475       TopoDS_Shape& aFR=aIt.ChangeValue();
 476       if (anOriF==TopAbs_REVERSED)
 477         aFR.Orientation(TopAbs_REVERSED);
 478       pLFIm->Append(aFR);
 479     }
 480   }
 481   //
 482   //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~scope t
 483 }
 484
 485 //=======================================================================
 486 //function : AddEdgeSet
 487 //purpose  :
 488 //=======================================================================
 489 typedef
 490   NCollection_IndexedDataMap<BOPTools_Set,
 491                              TopTools_ListOfShape,
 492                              BOPTools_SetMapHasher> BOPAlgo_IndexedDataMapOfSetListOfShape;
 493
 494 static void AddEdgeSet(const TopoDS_Shape& theS,
 495                        BOPAlgo_IndexedDataMapOfSetListOfShape& theMap,
 496                        const Handle(NCollection_BaseAllocator)& theAllocator)
 497 {
 498   // Make set
 499   BOPTools_Set aSE;
 500   aSE.Add(theS, TopAbs_EDGE);
 501   // Add set to the map, keeping connection to the shape
 502   TopTools_ListOfShape* pLF = theMap.ChangeSeek(aSE);
 503   if (!pLF)
 504     pLF = &theMap(theMap.Add(aSE, TopTools_ListOfShape(theAllocator)));
 505   pLF->Append(theS);
 506 }
 507
 508 //=======================================================================
 509 //function : FillSameDomainFaces
 510 //purpose  :
 511 //=======================================================================
 512 void BOPAlgo_Builder::FillSameDomainFaces()
 513 {
 514   // It is necessary to analyze all Face/Face intersections
 515   // and find all faces with equal sets of edges
 516   const BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
 517   Standard_Integer aNbFFs = aFFs.Length();
 518   if (!aNbFFs)
 519     return;
 520
 521   Handle(NCollection_BaseAllocator) aAllocator = new NCollection_IncAllocator;
 522
 523   // Vector to store the indices of faces for future sorting
 524   // for making the SD face for the group from the face with
 525   // smallest index in Data structure
 526   NCollection_Vector<Standard_Integer> aFIVec(256, aAllocator);
 527   // Fence map to avoid repeated checks of the same face.
 528   TColStd_MapOfInteger aMFence(1, aAllocator);
 529
 530   // Fill the vector with indices of faces
 531   for (Standard_Integer i = 0; i < aNbFFs; ++i)
 532   {
 533     const BOPDS_InterfFF& aFF = aFFs(i);
 534     // get indices
 535     Standard_Integer nF[2];
 536     aFF.Indices(nF[0], nF[1]);
 537     // store indices to the vector
 538     for (Standard_Integer j = 0; j < 2; ++j)
 539     {
 540       if (!myDS->HasFaceInfo(nF[j]))
 541         continue;
 542
 543       if (!aMFence.Add(nF[j]))
 544         continue;
 545
 546       aFIVec.Appended() = nF[j];
 547     }
 548   }
 549
 550   // Sort the indices
 551   std::sort(aFIVec.begin(), aFIVec.end());
 552
 553   // Data map of set of edges with all faces having this set
 554   NCollection_IndexedDataMap<BOPTools_Set,
 555                              TopTools_ListOfShape,
 556                              BOPTools_SetMapHasher> anESetFaces(1, aAllocator);
 557   // Map of planar bounded faces. If such faces have the same Edge set
 558   // they are considered Same domain, without additional check.
 559   TopTools_MapOfShape aMFPlanar(1, aAllocator);
 560
 561   Standard_Integer aNbF = aFIVec.Length();
 562   for (Standard_Integer i = 0; i < aNbF; ++i)
 563   {
 564     const Standard_Integer nF = aFIVec(i);
 565     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
 566     const TopoDS_Shape& aF = aSI.Shape();
 567
 568     Standard_Boolean bCheckPlanar = Standard_False;
 569     {
 570       // At this stage, context should contain adaptor for all intersected faces,
 571       // so getting a type of the underlying surface should be done at no cost.
 572       if (myContext->SurfaceAdaptor(TopoDS::Face(aF)).GetType() == GeomAbs_Plane)
 573       {
 574         // Check bounding box of the face - it should not be open in any side
 575         const Bnd_Box& aBox = aSI.Box();
 576         bCheckPlanar = !(aBox.IsOpenXmin() || aBox.IsOpenXmax() ||
 577                          aBox.IsOpenYmin() || aBox.IsOpenYmax() ||
 578                          aBox.IsOpenZmin() || aBox.IsOpenZmax());
 579       }
 580     }
 581
 582     const TopTools_ListOfShape* pLFSp = myImages.Seek(aF);
 583     if (pLFSp)
 584     {
 585       TopTools_ListIteratorOfListOfShape aItLF(*pLFSp);
 586       for (; aItLF.More(); aItLF.Next())
 587       {
 588         AddEdgeSet(aItLF.Value(), anESetFaces, aAllocator);
 589         if (bCheckPlanar)
 590           aMFPlanar.Add(aItLF.Value());
 591       }
 592     }
 593     else
 594     {
 595       AddEdgeSet(aF, anESetFaces, aAllocator);
 596       if (bCheckPlanar)
 597         aMFPlanar.Add(aF);
 598     }
 599   }
 600
 601   // Store pairs of faces with equal set of edges to check if they are really Same Domain
 602   BOPAlgo_VectorOfPairOfShapeBoolean aVPSB;
 603
 604   // Back and forth map of SD faces to make the blocks
 605   TopTools_IndexedDataMapOfShapeListOfShape aDMSLS(1, aAllocator);
 606
 607   Standard_Integer aNbSets = anESetFaces.Extent();
 608   for (Standard_Integer i = 1; i <= aNbSets; ++i)
 609   {
 610     const TopTools_ListOfShape& aLF = anESetFaces(i);
 611     if (aLF.Extent() < 2)
 612       continue;
 613
 614     // All possible pairs from <aLF> should be checked
 615     TopTools_ListIteratorOfListOfShape aIt1(aLF);
 616     for (; aIt1.More(); aIt1.Next())
 617     {
 618       const TopoDS_Shape& aF1 = aIt1.Value();
 619       Standard_Boolean bCheckPlanar = aMFPlanar.Contains(aF1);
 620
 621       TopTools_ListIteratorOfListOfShape aIt2 = aIt1;
 622       for (aIt2.Next(); aIt2.More(); aIt2.Next())
 623       {
 624         const TopoDS_Shape& aF2 = aIt2.Value();
 625         if (bCheckPlanar && aMFPlanar.Contains(aF2))
 626         {
 627           // Consider planar bounded faces as Same Domain without additional check
 628           BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>(aF1, aF2, aDMSLS, aAllocator);
 629           continue;
 630         }
 631         // Add pair for analysis
 632         BOPAlgo_PairOfShapeBoolean& aPSB = aVPSB.Appended();
 633         aPSB.Shape1() = aF1;
 634         aPSB.Shape2() = aF2;
 635         aPSB.SetFuzzyValue(myFuzzyValue);
 636         aPSB.SetProgressIndicator(myProgressIndicator);
 637       }
 638     }
 639   }
 640
 641   //================================================================
 642   // Perform analysis
 643   BOPAlgo_BuilderSDFaceCnt::Perform(myRunParallel, aVPSB, myContext);
 644   //================================================================
 645
 646   NCollection_List<TopTools_ListOfShape> aMBlocks(aAllocator);
 647   // Fill map with SD faces to make the blocks
 648   Standard_Integer aNbPairs = aVPSB.Length();
 649   for (Standard_Integer i = 0; i < aNbPairs; ++i)
 650   {
 651     BOPAlgo_PairOfShapeBoolean& aPSB = aVPSB(i);
 652     if (aPSB.Flag())
 653       BOPAlgo_Tools::FillMap<TopoDS_Shape, TopTools_ShapeMapHasher>
 654        (aPSB.Shape1(), aPSB.Shape2(), aDMSLS, aAllocator);
 655   }
 656   aVPSB.Clear();
 657
 658   // Make blocks of SD faces using the back and forth map
 659   BOPAlgo_Tools::MakeBlocks<TopoDS_Shape, TopTools_ShapeMapHasher>
 660     (aDMSLS, aMBlocks, aAllocator);
 661
 662   // Fill same domain faces map
 663   NCollection_List<TopTools_ListOfShape>::Iterator aItB(aMBlocks);
 664   for (; aItB.More(); aItB.Next())
 665   {
 666     const TopTools_ListOfShape& aLSD = aItB.Value();
 667     // If the group contains some original faces, the one with minimal
 668     // index in the DS will be chosen as the SD for the whole group.
 669     // If there are no original faces in the group, the first face from
 670     // the group will be used as the SD face.
 671     // Such SD face will be representative of the whole group in the result.
 672     TopoDS_Face* pFSD = NULL;
 673     Standard_Integer nFMin = ::IntegerLast();
 674     TopTools_ListIteratorOfListOfShape aItLF(aLSD);
 675     for (; aItLF.More(); aItLF.Next())
 676     {
 677       const TopoDS_Shape& aF = aItLF.Value();
 678       // Check the index of the face in DS
 679       const Standard_Integer nF = myDS->Index(aF);
 680       if (nF >= 0)
 681       {
 682         // The fact that the face is found in the DS, means that
 683         // the face has not been change, and thus it is original one.
 684         //
 685         // Such face does not have any splits, but have an SD face.
 686         // Consider it being split.
 687         myImages.Bound(aF, TopTools_ListOfShape())->Append(aF);
 688
 689         // For the SD face chose the one with minimal index
 690         if (nF < nFMin)
 691         {
 692           nFMin = nF;
 693           pFSD = (TopoDS_Face*)&aF;
 694         }
 695       }
 696     }
 697
 698     if (!pFSD)
 699     {
 700       // No original faces in the group, take the first one
 701       pFSD = (TopoDS_Face*)&aLSD.First();
 702     }
 703
 704     // Save all SD connections
 705     aItLF.Initialize(aLSD);
 706     for (; aItLF.More(); aItLF.Next())
 707     {
 708       const TopoDS_Shape& aF = aItLF.Value();
 709       myShapesSD.Bind(aF, *pFSD);
 710     }
 711   }
 712
 713   // Update the map of images with SD faces and
 714   // fill the map of origins.
 715   Standard_Integer aNbS = myDS->NbSourceShapes();
 716   for (Standard_Integer i = 0; i < aNbS; ++i)
 717   {
 718     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
 719     if (aSI.ShapeType() != TopAbs_FACE)
 720       continue;
 721
 722     const TopoDS_Shape& aF = aSI.Shape();
 723     TopTools_ListOfShape* pLFIm = myImages.ChangeSeek(aF);
 724     if (!pLFIm)
 725       continue;
 726
 727     TopTools_ListIteratorOfListOfShape aItLFIm(*pLFIm);
 728     for (; aItLFIm.More(); aItLFIm.Next())
 729     {
 730       TopoDS_Shape& aFIm = aItLFIm.ChangeValue();
 731       const TopoDS_Shape* pFSD = myShapesSD.Seek(aFIm);
 732       if (pFSD)
 733         // Update image with SD face
 734         aFIm = *pFSD;
 735
 736       // Fill the map of origins
 737       TopTools_ListOfShape* pLFOr = myOrigins.ChangeSeek(aFIm);
 738       if (!pLFOr)
 739         pLFOr = myOrigins.Bound(aFIm, TopTools_ListOfShape());
 740       pLFOr->Append(aF);
 741     }
 742   }
 743
 744   aMBlocks.Clear();
 745   aDMSLS.Clear();
 746 }
 747 //=======================================================================
 748 // function: FillImagesFaces1
 749 // purpose:
 750 //=======================================================================
 751 void BOPAlgo_Builder::FillInternalVertices()
 752 {
 753   // Vector of pairs of Vertex/Face for classification of the vertices
 754   // relatively faces, and adding them as internal into the faces
 755   BOPAlgo_VectorOfVFI aVVFI;
 756
 757   Standard_Integer aNbS = myDS->NbSourceShapes();
 758   for (Standard_Integer i = 0; i < aNbS; ++i)
 759   {
 760     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
 761     if (aSI.ShapeType() != TopAbs_FACE)
 762       continue;
 763
 764     const TopoDS_Shape& aF = aSI.Shape();
 765     const TopTools_ListOfShape* pLFIm = myImages.Seek(aF);
 766     if (!pLFIm)
 767       continue;
 768
 769     // Find vertices to add as internal into the splits
 770     TColStd_ListOfInteger aLIAV;
 771     myDS->AloneVertices(i, aLIAV);
 772
 773     // Add vertices and faces for classification
 774     TColStd_ListIteratorOfListOfInteger aItLV(aLIAV);
 775     for (; aItLV.More(); aItLV.Next())
 776     {
 777       TopoDS_Vertex aV = TopoDS::Vertex(myDS->Shape(aItLV.Value()));
 778       aV.Orientation(TopAbs_INTERNAL);
 779
 780       TopTools_ListIteratorOfListOfShape aItLFIm(*pLFIm);
 781       for (; aItLFIm.More(); aItLFIm.Next())
 782       {
 783         const TopoDS_Face& aFIm = TopoDS::Face(aItLFIm.Value());
 784         // Make the pair
 785         BOPAlgo_VFI& aVFI = aVVFI.Appended();
 786         aVFI.SetVertex(aV);
 787         aVFI.SetFace(aFIm);
 788         aVFI.SetFuzzyValue(myFuzzyValue);
 789         aVFI.SetProgressIndicator(myProgressIndicator);
 790       }
 791     }
 792   }
 793
 794   // Perform classification
 795   //================================================================
 796   BOPAlgo_VFICnt::Perform(myRunParallel, aVVFI, myContext);
 797   //================================================================
 798
 799   Standard_Integer aNbVFI = aVVFI.Length();
 800   for (Standard_Integer i = 0; i < aNbVFI; ++i)
 801   {
 802     BOPAlgo_VFI& aVFI = aVVFI(i);
 803     if (aVFI.IsInternal())
 804     {
 805       TopoDS_Vertex& aV = aVFI.Vertex();
 806       TopoDS_Face& aF = aVFI.Face();
 807       BRep_Builder().Add(aF, aV);
 808     }
 809   }
 810 }
 811 //=======================================================================
 812 //function : HasMultiConnected
 813 //purpose  : Checks if the edge has multi-connected vertices.
 814 //=======================================================================
 815 static Standard_Boolean HasMultiConnected(const TopoDS_Edge& theEdge,
 816                                           TopTools_DataMapOfShapeInteger& theMap)
 817 {
 818   TopoDS_Iterator itV(theEdge);
 819   for (; itV.More(); itV.Next())
 820   {
 821     const TopoDS_Shape& aV = itV.Value();
 822     Standard_Integer *pCounter = theMap.ChangeSeek(aV);
 823     if (!pCounter)
 824       pCounter = theMap.Bound(aV, 1);
 825     else
 826     {
 827       if (*pCounter == 2)
 828         return Standard_True;
 829
 830       ++(*pCounter);
 831     }
 832   }
 833   return Standard_False;
 834 }
 835 //=======================================================================
 836 //function : BuildDraftFace
 837 //purpose  : Build draft faces, updating the bounding edges,
 838 //           according to the information stored into the <theImages> map
 839 //=======================================================================
 840 TopoDS_Face BuildDraftFace(const TopoDS_Face& theFace,
 841                            const TopTools_DataMapOfShapeListOfShape& theImages,
 842                            Handle(IntTools_Context)& theCtx)
 843 {
 844   BRep_Builder aBB;
 845   // Take the information from the original face
 846   TopLoc_Location aLoc;
 847   const Handle(Geom_Surface)& aS = BRep_Tool::Surface(theFace, aLoc);
 848   const Standard_Real aTol = BRep_Tool::Tolerance(theFace);
 849   // Make the new face, without any wires
 850   TopoDS_Face aDraftFace;
 851   aBB.MakeFace(aDraftFace, aS, aLoc, aTol);
 852
 853   // Check if the thin face can be split by a vertex - in this case
 854   // this vertex will be contained in more than two edges. Thus, count
 855   // the vertices appearance, and if the multi-connexity is met return
 856   // the null face to use the BuilderFace algorithm for checking the
 857   // possibility of split.
 858   TopTools_DataMapOfShapeInteger aVerticesCounter;
 859
 860   // Update wires of the original face and add them to draft face
 861   TopoDS_Iterator aItW(theFace.Oriented(TopAbs_FORWARD));
 862   for (; aItW.More(); aItW.Next())
 863   {
 864     const TopoDS_Shape& aW = aItW.Value();
 865     if (aW.ShapeType() != TopAbs_WIRE)
 866       continue;
 867
 868     // Rebuild wire using images of edges
 869     TopoDS_Iterator aItE(aW.Oriented(TopAbs_FORWARD));
 870     if (!aItE.More())
 871       continue;
 872
 873     TopoDS_Wire aNewWire;
 874     aBB.MakeWire(aNewWire);
 875
 876     for (; aItE.More(); aItE.Next())
 877     {
 878       const TopoDS_Edge& aE = TopoDS::Edge(aItE.Value());
 879
 880       TopAbs_Orientation anOriE = aE.Orientation();
 881       if (anOriE == TopAbs_INTERNAL)
 882       {
 883         // The internal edges could split the original face on halves.
 884         // Thus, use the BuilderFace algorithm to build the new face.
 885         return TopoDS_Face();
 886       }
 887
 888       // Check for the splits of the edge
 889       const TopTools_ListOfShape* pLEIm = theImages.Seek(aE);
 890       if (!pLEIm)
 891       {
 892         // Check if the edge has multi-connected vertices
 893         if (HasMultiConnected(aE, aVerticesCounter))
 894           return TopoDS_Face();
 895
 896         aBB.Add(aNewWire, aE);
 897         continue;
 898       }
 899
 900       // Check if the original edge is degenerated
 901       Standard_Boolean bIsDegenerated = BRep_Tool::Degenerated(aE);
 902       // Check if the original edge is closed on the face
 903       Standard_Boolean bIsClosed = BRep_Tool::IsClosed(aE, theFace);
 904
 905       TopTools_ListIteratorOfListOfShape aItLEIm(*pLEIm);
 906       for (; aItLEIm.More(); aItLEIm.Next())
 907       {
 908         TopoDS_Edge& aSp = TopoDS::Edge(aItLEIm.Value());
 909
 910         // Check if the split has multi-connected vertices
 911         if (HasMultiConnected(aSp, aVerticesCounter))
 912           return TopoDS_Face();
 913
 914         aSp.Orientation(anOriE);
 915         if (bIsDegenerated)
 916         {
 917           aBB.Add(aNewWire, aSp);
 918           continue;
 919         }
 920
 921         // Check closeness of the split edge and if it is not
 922         // make the second PCurve
 923         if (bIsClosed && !BRep_Tool::IsClosed(aSp, theFace))
 924           BOPTools_AlgoTools3D::DoSplitSEAMOnFace(aSp, theFace);
 925
 926         // Check if the split should be reversed
 927         if (BOPTools_AlgoTools::IsSplitToReverse(aSp, aE, theCtx))
 928           aSp.Reverse();
 929
 930         aBB.Add(aNewWire, aSp);
 931       }
 932     }
 933
 934     aNewWire.Orientation(aW.Orientation());
 935     aNewWire.Closed(BRep_Tool::IsClosed(aNewWire));
 936     aBB.Add(aDraftFace, aNewWire);
 937   }
 938
 939   if (theFace.Orientation() == TopAbs_REVERSED)
 940     aDraftFace.Reverse();
 941
 942   return aDraftFace;
 943 }