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