src/GEOMAlgo/GEOMAlgo_Builder_2.cxx

   1 // Copyright (C) 2005  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   2 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   3 //
   4 // This library is free software; you can redistribute it and/or
   5 // modify it under the terms of the GNU Lesser General Public
   6 // License as published by the Free Software Foundation; either
   7 // version 2.1 of the License.
   8 //
   9 // This library is distributed in the hope that it will be useful
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 // Lesser General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Lesser General Public
  15 // License along with this library; if not, write to the Free Software
  16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  17 //
  18 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  19 //
  20 // File:        GEOMAlgo_Builder_2.cxx
  21 // Created:
  22 // Author:      Peter KURNEV
  23
  24 #include <GEOMAlgo_Builder.hxx>
  25
  26 #include <TColStd_IndexedMapOfInteger.hxx>
  27 #include <TColStd_ListOfInteger.hxx>
  28
  29 #include <TopAbs_Orientation.hxx>
  30
  31 #include <TopoDS.hxx>
  32 #include <TopoDS_Face.hxx>
  33 #include <TopoDS_Edge.hxx>
  34 #include <TopoDS_Shape.hxx>
  35 #include <TopoDS_Compound.hxx>
  36
  37 #include <TopTools_IndexedMapOfShape.hxx>
  38 #include <TopTools_ListOfShape.hxx>
  39 #include <TopTools_MapOfShape.hxx>
  40 #include <TopTools_ListIteratorOfListOfShape.hxx>
  41
  42 #include <TopExp.hxx>
  43 #include <TopExp_Explorer.hxx>
  44
  45 #include <BRep_Tool.hxx>
  46 #include <BRep_Builder.hxx>
  47 #include <BRepAlgo_Image.hxx>
  48 #include <BRepTools.hxx>
  49
  50 #include <IntTools_Context.hxx>
  51 #include <IntTools_FClass2d.hxx>
  52
  53 #include <BooleanOperations_OnceExplorer.hxx>
  54 #include <BOPTColStd_IndexedDataMapOfIntegerIndexedMapOfInteger.hxx>
  55 #include <BOPTools_ListOfPaveBlock.hxx>
  56 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
  57 #include <BOPTools_CArray1OfSSInterference.hxx>
  58 #include <BOPTools_SSInterference.hxx>
  59 #include <BOPTools_SequenceOfCurves.hxx>
  60 #include <BOPTools_Curve.hxx>
  61 #include <BOPTools_ListOfPaveBlock.hxx>
  62 #include <BOPTools_PaveBlock.hxx>
  63 #include <BOPTools_Tools3D.hxx>
  64 #include <BOPTools_CArray1OfVSInterference.hxx>
  65 #include <BOPTools_VSInterference.hxx>
  66 #include <BOPTools_ESInterference.hxx>
  67 #include <BOPTools_CArray1OfESInterference.hxx>
  68
  69 #include <NMTDS_ShapesDataStructure.hxx>
  70 #include <NMTTools_PaveFiller.hxx>
  71 #include <NMTTools_ListOfCoupleOfShape.hxx>
  72 #include <NMTTools_Tools.hxx>
  73 #include <NMTTools_CoupleOfShape.hxx>
  74 #include <NMTTools_IndexedDataMapOfShapeIndexedMapOfShape.hxx>
  75 #include <NMTTools_Tools.hxx>
  76 #include <NMTTools_ListIteratorOfListOfCommonBlock.hxx>
  77 #include <NMTTools_ListOfCommonBlock.hxx>
  78 #include <NMTTools_CommonBlock.hxx>
  79 #include <NMTTools_IndexedDataMapOfIndexedMapOfInteger.hxx>
  80 //
  81 #include <GEOMAlgo_Tools3D.hxx>
  82 #include <GEOMAlgo_WireEdgeSet.hxx>
  83 #include <GEOMAlgo_BuilderFace.hxx>
  84 #include <NMTDS_InterfPool.hxx>
  85
  86 static
  87   void UpdateCandidates(const Standard_Integer ,
  88                         const Standard_Integer ,
  89                         NMTTools_IndexedDataMapOfIndexedMapOfInteger& );
  90
  91 //=======================================================================
  92 //function : FillImagesFaces
  93 //purpose  :
  94 //=======================================================================
  95   void GEOMAlgo_Builder::FillImagesFaces()
  96 {
  97   myErrorStatus=0;
  98   //
  99   FillIn2DParts();
 100   BuildSplitFaces();
 101   FillSameDomainFaces();
 102   FillImagesFaces1();
 103   FillInternalVertices();
 104 }
 105 //=======================================================================
 106 // function: FillIn2DParts
 107 // purpose:
 108 //=======================================================================
 109   void GEOMAlgo_Builder::FillIn2DParts()
 110 {
 111   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 112   NMTTools_PaveFiller* pPF=myPaveFiller;
 113   NMTDS_InterfPool* pIP=pPF->IP();
 114   BOPTools_CArray1OfSSInterference& aFFs=pIP->SSInterferences();
 115   NMTTools_CommonBlockPool& aCBP=pPF->ChangeCommonBlockPool();
 116   //
 117   Standard_Integer  j, nSpIn, nSpSc, aNbCurves;
 118   Standard_Integer aNbS, nF, aNbCBP, n1, n2, aNbFFs, aNbSpIn;
 119   TopTools_MapOfShape  aMFence;
 120   TopTools_ListOfShape aLSpIn;
 121   TopoDS_Face aF;
 122   NMTTools_ListIteratorOfListOfCommonBlock aItCB;
 123   BOPTools_ListIteratorOfListOfPaveBlock aItPB;
 124   //
 125   myInParts.Clear();
 126   //
 127   aNbFFs=aFFs.Extent();
 128   aNbCBP=aCBP.Extent();
 129   //
 130   aNbS=aDS.NumberOfShapesOfTheObject();
 131   for (nF=1; nF<=aNbS; ++nF) {
 132     if (aDS.GetShapeType(nF)!=TopAbs_FACE) {
 133       continue;
 134     }
 135     //
 136     aF=TopoDS::Face(aDS.Shape(nF));
 137     //
 138     aMFence.Clear();
 139     aLSpIn.Clear();
 140     //
 141     // 1. In Parts
 142     for (j=1; j<=aNbCBP; ++j) {
 143       NMTTools_ListOfCommonBlock& aLCB=aCBP(j);
 144       aItCB.Initialize(aLCB);
 145       for (; aItCB.More(); aItCB.Next()) {
 146         NMTTools_CommonBlock& aCB=aItCB.Value();
 147         if (aCB.IsPaveBlockOnFace(nF)) {
 148           const BOPTools_PaveBlock& aPB1=aCB.PaveBlock1();
 149           nSpIn=aPB1.Edge();
 150           const TopoDS_Shape& aSpIn=aDS.Shape(nSpIn);
 151           if (aMFence.Add(aSpIn)){
 152             aLSpIn.Append(aSpIn);
 153           }
 154         }
 155       }
 156     }
 157     //
 158     // 2. Section Parts
 159     for (j=1; j<=aNbFFs; ++j) {
 160       BOPTools_SSInterference& aFF=aFFs(j);
 161       aFF.Indices(n1, n2);
 162       if (!(n1==nF || n2==nF)) {
 163         continue;
 164       }
 165       BOPTools_SequenceOfCurves& aSC=aFF.Curves();
 166       aNbCurves=aSC.Length();
 167       if (!aNbCurves) {
 168         continue;
 169       }
 170       //
 171       const BOPTools_Curve& aBC=aSC(1);
 172       const BOPTools_ListOfPaveBlock& aLPB=aBC.NewPaveBlocks();
 173       aItPB.Initialize(aLPB);
 174       for (; aItPB.More(); aItPB.Next()) {
 175         const BOPTools_PaveBlock& aPBSc=aItPB.Value();
 176         nSpSc=aPBSc.Edge();
 177         const TopoDS_Shape& aSpSc=aDS.Shape(nSpSc);
 178         if (aMFence.Add(aSpSc)){
 179           aLSpIn.Append(aSpSc);
 180         }
 181       }
 182     }
 183     aNbSpIn=aLSpIn.Extent();
 184     if (aNbSpIn) {
 185       myInParts.Add(aF, aLSpIn);
 186     }
 187   }//for (nF=1; nF<=aNbS; ++nF) {
 188 }
 189 //=======================================================================
 190 // function: BuildSplitFaces
 191 // purpose:
 192 //=======================================================================
 193   void GEOMAlgo_Builder::BuildSplitFaces()
 194 {
 195   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 196   NMTTools_PaveFiller* pPF=myPaveFiller;
 197   NMTDS_InterfPool* pIP=pPF->IP();
 198   BOPTools_CArray1OfSSInterference& aFFs=pIP->SSInterferences();
 199   IntTools_Context& aCtx= pPF->ChangeContext();
 200   //
 201   Standard_Boolean bToReverse, bIsClosed, bIsDegenerated;
 202   Standard_Integer i, aNb, aNbF, nF;
 203   TopTools_MapOfShape aMFence;
 204   TColStd_IndexedMapOfInteger aMFP;
 205   TopExp_Explorer anExp;
 206   TopoDS_Face aFF;
 207   TopoDS_Edge aSp, aEE;
 208   TopTools_ListIteratorOfListOfShape aIt;
 209   TopAbs_Orientation anOriF, anOriE;
 210   //
 211   mySplitFaces.Clear();
 212   //
 213   // 1. Select Faces to process (MFP)
 214   aNb=aDS.NumberOfShapesOfTheObject();
 215   for (i=1; i<=aNb; ++i) {
 216     const TopoDS_Shape& aF=aDS.Shape(i);
 217     if (aF.ShapeType()!=TopAbs_FACE) {
 218       continue;
 219     }
 220     if (!aMFence.Add(aF)) {
 221       continue;
 222     }
 223     //
 224     if (myInParts.Contains(aF)) {
 225       aMFP.Add(i);
 226       continue;
 227     }
 228     //
 229     anExp.Init(aF, TopAbs_EDGE);
 230     for (; anExp.More(); anExp.Next()) {
 231       const TopoDS_Shape& aE=anExp.Current();
 232       if (myImages.HasImage(aE)) {
 233         aMFP.Add(i);
 234         break;
 235       }
 236     }
 237     //
 238     //===
 239     {
 240       Standard_Integer aNbFFs, aNbSE, j, n1, n2;
 241       //
 242       aNbFFs=aFFs.Extent();
 243       for (j=1; j<=aNbFFs; ++j) {
 244         BOPTools_SSInterference& aFFj=aFFs(j);
 245         aFFj.Indices(n1, n2);
 246         if (!(n1==i || n2==i)) {
 247           continue;
 248         }
 249         //
 250         const TColStd_ListOfInteger& aLSE=aFFj.SharedEdges();
 251         aNbSE=aLSE.Extent();
 252         if (aNbSE) {
 253           aMFP.Add(i);
 254         }
 255       }
 256     }
 257     //===
 258     //
 259   }// for (i=1; i<=aNb; ++i)
 260   //
 261   // 2. ProcessFaces
 262   aNbF=aMFP.Extent();
 263   for (i=1; i<=aNbF; ++i) {
 264     nF=aMFP(i);
 265     const TopoDS_Face& aF=TopoDS::Face(aDS.Shape(nF));
 266     anOriF=aF.Orientation();
 267     aFF=aF;
 268     aFF.Orientation(TopAbs_FORWARD);
 269     //
 270     aMFence.Clear();
 271     //
 272     // 2.1. Fill WES
 273     GEOMAlgo_WireEdgeSet aWES;
 274     aWES.SetFace(aFF);
 275     //
 276     //  2.1.1. Add Split parts
 277     anExp.Init(aFF, TopAbs_EDGE);
 278     for (; anExp.More(); anExp.Next()) {
 279       const TopoDS_Edge& aE=TopoDS::Edge(anExp.Current());
 280       anOriE=aE.Orientation();
 281       //
 282       if (!myImages.HasImage(aE)) {
 283         if (anOriE==TopAbs_INTERNAL) {
 284           aEE=aE;
 285           aEE.Orientation(TopAbs_FORWARD);
 286           aWES.AddStartElement(aEE);
 287           aEE.Orientation(TopAbs_REVERSED);
 288           aWES.AddStartElement(aEE);
 289         }
 290         else {
 291           aWES.AddStartElement(aE);
 292         }
 293         continue;
 294       }
 295       //
 296       bIsDegenerated=BRep_Tool::Degenerated(aE);
 297       bIsClosed=BRep_Tool::IsClosed(aE, aF);
 298       //
 299       const TopTools_ListOfShape& aLIE=myImages.Image(aE);
 300       aIt.Initialize(aLIE);
 301       for (; aIt.More(); aIt.Next()) {
 302         aSp=TopoDS::Edge(aIt.Value());
 303         //
 304         if (bIsDegenerated) {
 305           aSp.Orientation(anOriE);
 306           aWES.AddStartElement(aSp);
 307           continue;
 308         }
 309         //
 310         if (anOriE==TopAbs_INTERNAL) {
 311           aSp.Orientation(TopAbs_FORWARD);
 312           aWES.AddStartElement(aSp);
 313           aSp.Orientation(TopAbs_REVERSED);
 314           aWES.AddStartElement(aSp);
 315           continue;
 316         }
 317         //
 318         if (bIsClosed){
 319           if (aMFence.Add(aSp)) {
 320             //
 321             if (!BRep_Tool::IsClosed(aSp, aF)){
 322               BOPTools_Tools3D::DoSplitSEAMOnFace(aSp, aF);
 323             }
 324             //
 325             aSp.Orientation(TopAbs_FORWARD);
 326             aWES.AddStartElement(aSp);
 327             aSp.Orientation(TopAbs_REVERSED);
 328             aWES.AddStartElement(aSp);
 329           }
 330           continue;
 331         }// if (aMFence.Add(aSp))
 332         //
 333         aSp.Orientation(anOriE);
 334         bToReverse=BOPTools_Tools3D::IsSplitToReverse1(aSp, aE, aCtx);
 335         if (bToReverse) {
 336           aSp.Reverse();
 337         }
 338         aWES.AddStartElement(aSp);
 339       }// for (; aIt.More(); aIt.Next()) {
 340     }// for (; anExp.More(); anExp.Next()) {
 341     //
 342     // 2.1.2. Add In2D Parts
 343     if (myInParts.Contains(aF)) {
 344       const TopTools_ListOfShape& aLE=myInParts.FindFromKey(aF);
 345       aIt.Initialize(aLE);
 346       for (; aIt.More(); aIt.Next()) {
 347         aSp=TopoDS::Edge(aIt.Value());
 348         //
 349         aSp.Orientation(TopAbs_FORWARD);
 350         aWES.AddStartElement(aSp);
 351         //
 352         aSp.Orientation(TopAbs_REVERSED);
 353         aWES.AddStartElement(aSp);
 354       }
 355     }
 356     //
 357     // 2.2. Build images Faces
 358     GEOMAlgo_BuilderFace aBF;
 359     //
 360     aBF.SetFace(aFF);
 361     aBF.SetContext(aCtx);
 362     const TopTools_ListOfShape& aSE=aWES.StartElements();
 363     //
 364     //DEB f
 365     /*
 366     {
 367       TopoDS_Compound aCx;
 368       BRep_Builder aBBx;
 369       TopTools_ListIteratorOfListOfShape aItx;
 370       //
 371       aBBx.MakeCompound(aCx);
 372       aBBx.Add(aCx, aFF);
 373       aItx.Initialize(aSE);
 374       for (; aItx.More(); aItx.Next()) {
 375         TopoDS_Shape& aEx=aItx.Value();
 376         aBBx.Add(aCx, aEx);
 377       }
 378       int a=0;
 379     }
 380     */
 381     //DEB t
 382     //
 383     aBF.SetShapes(aSE);
 384     //
 385     aBF.Perform();
 386     //
 387     const TopTools_ListOfShape& aLF=aBF.Areas();
 388     //
 389     TopTools_ListOfShape aLFR;
 390     //
 391     aIt.Initialize(aLF);
 392     for (; aIt.More(); aIt.Next()) {
 393       TopoDS_Shape& aFR=aIt.Value();
 394       if (anOriF==TopAbs_REVERSED) {
 395         aFR.Orientation(TopAbs_REVERSED);
 396       }
 397       aLFR.Append(aFR);
 398     }
 399     //
 400     // 2.3. Collect draft images Faces
 401     mySplitFaces.Bind(aF, aLFR);
 402   }//for (i=1; i<=aNbF; ++i)
 403 }
 404 //=======================================================================
 405 // function: FillSameDomainFaces
 406 // purpose:
 407 //=======================================================================
 408   void GEOMAlgo_Builder::FillSameDomainFaces()
 409 {
 410   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 411   NMTTools_PaveFiller* pPF=myPaveFiller;
 412   NMTDS_InterfPool* pIP=pPF->IP();
 413   BOPTools_CArray1OfSSInterference& aFFs=pIP->SSInterferences();
 414   IntTools_Context& aCtx= pPF->ChangeContext();
 415   //
 416   Standard_Boolean bIsSDF;
 417   Standard_Integer i, j, aNbFF, nF1, nF2, aNbPBInOn, aNbC, aNbSE;
 418   TopTools_MapOfShape aMFence;
 419   TopTools_ListIteratorOfListOfShape aItF1, aItF2;
 420   NMTTools_ListOfCoupleOfShape aLCS;
 421   //
 422   //mySameDomainShapes.Clear();
 423   //
 424   // 1. For each FF find among images of faces
 425   //    all pairs of same domain faces (SDF) [=> aLCS]
 426   aNbFF=aFFs.Extent();
 427   for (i=1; i<=aNbFF; ++i) {
 428     BOPTools_SSInterference& aFF=aFFs(i);
 429     aFF.Indices(nF1, nF2);
 430     //
 431     const TopoDS_Face& aF1=TopoDS::Face(aDS.Shape(nF1));
 432     const TopoDS_Face& aF2=TopoDS::Face(aDS.Shape(nF2));
 433     //
 434     // if there are no in/on 2D split parts the faces nF1, nF2
 435     // can not be SDF
 436     const BOPTools_ListOfPaveBlock& aLPBInOn=aFF.PaveBlocks();
 437     aNbPBInOn=aLPBInOn.Extent();
 438     //
 439     //===
 440     const TColStd_ListOfInteger& aLSE=aFF.SharedEdges();
 441     aNbSE=aLSE.Extent();
 442     if (!aNbPBInOn && !aNbSE) {
 443       continue;
 444     }
 445     //===
 446     //
 447     // if there is at least one section edge between faces nF1, nF2
 448     // they can not be SDF
 449     BOPTools_SequenceOfCurves& aSC=aFF.Curves();
 450     aNbC=aSC.Length();
 451     if (aNbC) {
 452       continue;
 453     }
 454     //
 455     // the faces are suspected to be SDF.
 456     // Try to find SDF among images of nF1, nF2
 457     aMFence.Clear();
 458     const TopTools_ListOfShape& aLF1=mySplitFaces.Image(aF1);
 459     const TopTools_ListOfShape& aLF2=mySplitFaces.Image(aF2);
 460     //
 461     aItF1.Initialize(aLF1);
 462     for (; aItF1.More(); aItF1.Next()) {
 463       const TopoDS_Face& aF1x=TopoDS::Face(aItF1.Value());
 464       //
 465       aItF2.Initialize(aLF2);
 466       for (; aItF2.More(); aItF2.Next()) {
 467         const TopoDS_Face& aF2y=TopoDS::Face(aItF2.Value());
 468         bIsSDF=NMTTools_Tools::AreFacesSameDomain(aF1x, aF2y, aCtx);
 469         if (bIsSDF) {
 470           if (aMFence.Contains(aF1x) ||
 471               aMFence.Contains(aF2y)) {
 472             continue;
 473           }
 474           aMFence.Add(aF1x);
 475           aMFence.Add(aF2y);
 476           //
 477           NMTTools_CoupleOfShape aCS;
 478           //
 479           aCS.SetShape1(aF1x);
 480           aCS.SetShape2(aF2y);
 481           aLCS.Append(aCS);
 482           //
 483           if (aF1x==aF1) {
 484             if (!mySplitFaces.HasImage(aF1)) {
 485               mySplitFaces.Bind(aF1, aF1);
 486             }
 487           }
 488           if (aF2y==aF2) {
 489             if (!mySplitFaces.HasImage(aF2)) {
 490               mySplitFaces.Bind(aF2, aF2);
 491             }
 492           }
 493           //
 494
 495         }
 496       }
 497     }
 498   }//for (i=1; i<=aNbFF; ++i)
 499   //
 500   aNbC=aLCS.Extent();
 501   if (!aNbC) {
 502     return;
 503   }
 504   //
 505   // 2. Find Chains
 506   NMTTools_IndexedDataMapOfShapeIndexedMapOfShape aMC;
 507   //
 508   NMTTools_Tools::FindChains(aLCS, aMC);
 509   //
 510   // 3. Fill the map of SDF mySameDomainFaces
 511   aNbC=aMC.Extent();
 512   for (i=1; i<=aNbC; ++i) {
 513     const TopoDS_Shape& aF=aMC.FindKey(i);
 514     const TopTools_IndexedMapOfShape& aMSDF=aMC(i);
 515     //
 516     aNbFF=aMSDF.Extent();
 517     for (j=1; j<=aNbFF; ++j) {
 518       const TopoDS_Shape& aFSD=aMSDF(j);
 519       mySameDomainShapes.Add(aFSD, aF);
 520     }
 521   }
 522   //
 523 }
 524 //=======================================================================
 525 // function: FillImagesFaces1
 526 // purpose:
 527 //=======================================================================
 528   void GEOMAlgo_Builder::FillImagesFaces1()
 529 {
 530   Standard_Integer i, aNb, iSense;
 531   TopoDS_Face aF, aFSp, aFSD;
 532   TopTools_ListOfShape aLFx;
 533   TopTools_ListIteratorOfListOfShape aIt;
 534   //
 535   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 536   //
 537   aNb=aDS.NumberOfShapesOfTheObject();
 538   for (i=1; i<=aNb; ++i) {
 539     const TopoDS_Shape& aS=aDS.Shape(i);
 540     if (aS.ShapeType()!=TopAbs_FACE) {
 541       continue;
 542     }
 543     //
 544     if (!mySplitFaces.HasImage(aS)) {
 545       continue;
 546     }
 547     //
 548     aF=TopoDS::Face(aS);
 549     //
 550     aLFx.Clear();
 551     const TopTools_ListOfShape& aLF=mySplitFaces.Image(aF);
 552     aIt.Initialize(aLF);
 553     for (; aIt.More(); aIt.Next()) {
 554       aFSp=TopoDS::Face(aIt.Value());
 555       if (!mySameDomainShapes.Contains(aFSp)) {
 556         aLFx.Append(aFSp);
 557       }
 558       else {
 559         const TopoDS_Shape& aSx=mySameDomainShapes.FindFromKey(aFSp);
 560         aFSD=TopoDS::Face(aSx);
 561         iSense=GEOMAlgo_Tools3D::Sense(aFSp, aFSD);
 562         if (iSense<0) {
 563           aFSD.Reverse();
 564         }
 565         aLFx.Append(aFSD);
 566       }
 567     }
 568     if (!myImages.HasImage(aF)) {//XX
 569       myImages.Bind(aF, aLFx);
 570     }
 571   }
 572 }
 573 //=======================================================================
 574 // function: FillInternalVertices
 575 // purpose:
 576 //=======================================================================
 577   void GEOMAlgo_Builder::FillInternalVertices()
 578 {
 579   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 580   NMTTools_PaveFiller* pPF=myPaveFiller;
 581   NMTDS_InterfPool* pIP=pPF->IP();
 582   IntTools_Context& aCtx= pPF->ChangeContext();
 583   //
 584   BOPTools_CArray1OfSSInterference& aFFs=pIP->SSInterferences();
 585   BOPTools_CArray1OfVSInterference& aVFs=pIP->VSInterferences();
 586   BOPTools_CArray1OfESInterference& aEFs=pIP->ESInterferences();
 587   const NMTTools_IndexedDataMapOfIndexedMapOfInteger& aMAV=pPF->AloneVertices();
 588   //
 589   Standard_Boolean bHasImage;
 590   Standard_Integer i, j, nF, aNbS, nV, nVSD, n1, n2, iFlag;
 591   Standard_Integer aNbVFs, aNbAVF, aNbEFs, aNbVC, aNbE, aNbV;
 592   Standard_Real aU1, aU2, aTol;
 593   NMTTools_IndexedDataMapOfIndexedMapOfInteger aMFMV;
 594   TopTools_MapOfShape aMFence;
 595   TopTools_ListIteratorOfListOfShape aIt, aItV;
 596   BRep_Builder aBB;
 597   //
 598   // 1. Collect face-vertex candidates [aMFMV]
 599   //
 600   // 1.1. VFs
 601   aNbVFs=aVFs.Extent();
 602   for (i=1; i<=aNbVFs; ++i) {
 603     const BOPTools_VSInterference& aVS=aVFs(i);
 604     aVS.Indices(n1, n2);
 605     nF=n2;
 606     nV=n1;
 607     if (aDS.Shape(n1).ShapeType()==TopAbs_FACE) {
 608       nF=n1;
 609       nV=n2;
 610     }
 611     nVSD=pPF->FindSDVertex(nV);
 612     if (nVSD) {
 613       nV=nVSD;
 614     }
 615     //
 616     UpdateCandidates(nF, nV, aMFMV);
 617   }
 618   //
 619   // 1.2 EFs
 620   aNbEFs=aEFs.Extent();
 621   for (i=1; i<=aNbEFs; ++i) {
 622     const BOPTools_ESInterference& aEF=aEFs(i);
 623     aEF.Indices(n1, n2);
 624     nV=aEF.NewShape();
 625     if (!nV) {
 626       continue;
 627     }
 628     const TopoDS_Shape& aSnew=aDS.Shape(nV);
 629     if (aSnew.ShapeType()!=TopAbs_VERTEX) {
 630       continue;
 631     }
 632     //
 633     nF=(aDS.Shape(n1).ShapeType()==TopAbs_FACE) ? n1 : n2;
 634     nVSD=pPF->FindSDVertex(nV);
 635     if (nVSD) {
 636       nV=nVSD;
 637     }
 638     UpdateCandidates(nF, nV, aMFMV);
 639   }
 640   //
 641   aNbS=aDS.NumberOfShapesOfTheObject();
 642   for (nF=1; nF<=aNbS; ++nF) {
 643     const TopoDS_Shape& aF=aDS.Shape(nF);
 644     //
 645     if (aF.ShapeType()!=TopAbs_FACE) {
 646       continue;
 647     }
 648     if (!aMFence.Add(aF)) {
 649       continue;
 650     }
 651     //
 652     const TopoDS_Face& aFF=TopoDS::Face(aF);
 653     aTol=BRep_Tool::Tolerance(aFF);
 654     //
 655     // 1.3 FFs
 656     if (aMAV.Contains(nF)) {
 657       const TColStd_IndexedMapOfInteger& aMAVF=aMAV.FindFromKey(nF);
 658       aNbAVF=aMAVF.Extent();
 659       for (j=1; j<=aNbAVF; ++j) {
 660         nV=aMAVF(j);
 661         nVSD=pPF->FindSDVertex(nV);
 662         if (nVSD) {
 663           nV=nVSD;
 664         }
 665         //
 666         UpdateCandidates(nF, nV, aMFMV);
 667       }
 668     }
 669     //
 670     // 1.4 Internal vertices of the face nF
 671     BooleanOperations_OnceExplorer aExp(aDS);
 672     aExp.Init(nF, TopAbs_VERTEX);
 673     for (; aExp.More(); aExp.Next()) {
 674       nV=aExp.Current();
 675       const TopoDS_Shape& aV=aDS.Shape(nV);
 676       if (aV.Orientation()==TopAbs_INTERNAL) {
 677         nVSD=pPF->FindSDVertex(nV);
 678         if (nVSD) {
 679           nV=nVSD;
 680         }
 681         //
 682         UpdateCandidates(nF, nV, aMFMV);
 683       }
 684     }
 685     //
 686     // 2. Process face nF
 687     if (!aMFMV.Contains(nF)) {
 688       continue;
 689     }
 690     //
 691     const TColStd_IndexedMapOfInteger& aMVC=aMFMV.FindFromKey(nF);
 692     aNbVC=aMVC.Extent();
 693     if (!aNbVC) {
 694       continue;
 695     }
 696     //
 697     // 2.1 Refine candidates
 698     TopTools_IndexedDataMapOfShapeListOfShape aMVE;
 699     TopTools_ListOfShape aLV;
 700     //
 701     bHasImage=myImages.HasImage(aF);
 702     if (bHasImage) {
 703       const TopTools_ListOfShape& aLFx=myImages.Image(aF);
 704       aIt.Initialize(aLFx);
 705       for (; aIt.More(); aIt.Next()) {
 706         const TopoDS_Shape& aFx=aIt.Value();
 707         TopExp::MapShapesAndAncestors(aFx, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 708       }
 709     }
 710     else {
 711       Standard_Boolean bFaceToProcess;
 712       //
 713       TopExp::MapShapesAndAncestors(aF, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 714       bFaceToProcess=Standard_False;
 715       for (j=1; j<=aNbVC; ++j) {
 716         nV=aMVC(j);
 717         const TopoDS_Shape& aV=aDS.Shape(nV);
 718         if (!aMVE.Contains(aV)) {
 719           bFaceToProcess=!bFaceToProcess;
 720           break;
 721         }
 722       }
 723       if (!bFaceToProcess) {
 724         continue;
 725       }
 726     }// else
 727     //
 728     for (j=1; j<=aNbVC; ++j) {
 729       nV=aMVC(j);
 730       const TopoDS_Shape& aV=aDS.Shape(nV);
 731       if (aMVE.Contains(aV)) {
 732         const TopTools_ListOfShape& aLE=aMVE.FindFromKey(aV);
 733         aNbE=aLE.Extent();
 734         if (aNbE) {
 735           continue;
 736         }
 737       }
 738       aLV.Append(aV);
 739     }
 740     //
 741     aNbV=aLV.Extent();
 742     if (aNbV) {
 743       //  3. Try to put vertices into the face(s)
 744       aItV.Initialize(aLV);
 745       for (; aItV.More(); aItV.Next()) {
 746         TopoDS_Vertex aV=TopoDS::Vertex(aItV.Value());
 747         aV.Orientation(TopAbs_INTERNAL);
 748         //
 749         bHasImage=myImages.HasImage(aF);
 750         if (bHasImage) {
 751           const TopTools_ListOfShape& aLFx=myImages.Image(aF);
 752           aIt.Initialize(aLFx);
 753           for (; aIt.More(); aIt.Next()) {
 754             TopoDS_Face aFx=TopoDS::Face(aIt.Value());
 755             // update classifier
 756             IntTools_FClass2d& aClsf=aCtx.FClass2d(aFx);
 757             aClsf.Init(aFx, aTol);
 758             //
 759             iFlag=aCtx.ComputeVS (aV, aFx, aU1, aU2);
 760             if (!iFlag) {
 761               aBB.Add(aFx, aV);
 762               break;
 763             }
 764           }
 765         }
 766         else {
 767           const TopoDS_Face& aFx=TopoDS::Face(aF);
 768           // update classifier
 769           IntTools_FClass2d& aClsf=aCtx.FClass2d(aFx);
 770           aClsf.Init(aFx, aTol);
 771           //
 772           iFlag=aCtx.ComputeVS (aV, aFx, aU1, aU2);
 773           if (!iFlag) {
 774             TopoDS_Face aFz;
 775             //
 776             GEOMAlgo_Tools3D::CopyFace(aFx, aFz);
 777             aBB.Add(aFz, aV);
 778             myImages.Bind(aF, aFz);
 779           }
 780         }
 781       }// for (; aItV.More(); aItV.Next()) {
 782     }// if (aNbV) {
 783   }// for (nF=1; nF<=aNb; ++nF) {
 784 }
 785 //=======================================================================
 786 // function: UpdateCandidates
 787 // purpose:
 788 //=======================================================================
 789 void UpdateCandidates(const Standard_Integer theNF,
 790                       const Standard_Integer theNV,
 791                        NMTTools_IndexedDataMapOfIndexedMapOfInteger& theMFMV)
 792 {
 793   if (theMFMV.Contains(theNF)) {
 794     TColStd_IndexedMapOfInteger& aMV=theMFMV.ChangeFromKey(theNF);
 795     aMV.Add(theNV);
 796   }
 797   else {
 798     TColStd_IndexedMapOfInteger aMV;
 799     aMV.Add(theNV);
 800     theMFMV.Add(theNF, aMV);
 801   }
 802 }