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     aBF.SetShapes(aSE);
 364     //
 365     aBF.Perform();
 366     //
 367     const TopTools_ListOfShape& aLF=aBF.Areas();
 368     //
 369     TopTools_ListOfShape aLFR;
 370     //
 371     aIt.Initialize(aLF);
 372     for (; aIt.More(); aIt.Next()) {
 373       TopoDS_Shape& aFR=aIt.Value();
 374       if (anOriF==TopAbs_REVERSED) {
 375         aFR.Orientation(TopAbs_REVERSED);
 376       }
 377       aLFR.Append(aFR);
 378     }
 379     //
 380     // 2.3. Collect draft images Faces
 381     mySplitFaces.Bind(aF, aLFR);
 382   }//for (i=1; i<=aNbF; ++i)
 383 }
 384 //=======================================================================
 385 // function: FillSameDomainFaces
 386 // purpose:
 387 //=======================================================================
 388   void GEOMAlgo_Builder::FillSameDomainFaces()
 389 {
 390   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 391   NMTTools_PaveFiller* pPF=myPaveFiller;
 392   NMTDS_InterfPool* pIP=pPF->IP();
 393   BOPTools_CArray1OfSSInterference& aFFs=pIP->SSInterferences();
 394   IntTools_Context& aCtx= pPF->ChangeContext();
 395   //
 396   Standard_Boolean bIsSDF;
 397   Standard_Integer i, j, aNbFF, nF1, nF2, aNbPBInOn, aNbC, aNbSE;
 398   TopTools_MapOfShape aMFence;
 399   TopTools_ListIteratorOfListOfShape aItF1, aItF2;
 400   NMTTools_ListOfCoupleOfShape aLCS;
 401   //
 402   //mySameDomainShapes.Clear();
 403   //
 404   // 1. For each FF find among images of faces
 405   //    all pairs of same domain faces (SDF) [=> aLCS]
 406   aNbFF=aFFs.Extent();
 407   for (i=1; i<=aNbFF; ++i) {
 408     BOPTools_SSInterference& aFF=aFFs(i);
 409     aFF.Indices(nF1, nF2);
 410     //
 411     const TopoDS_Face& aF1=TopoDS::Face(aDS.Shape(nF1));
 412     const TopoDS_Face& aF2=TopoDS::Face(aDS.Shape(nF2));
 413     //
 414     // if there are no in/on 2D split parts the faces nF1, nF2
 415     // can not be SDF
 416     const BOPTools_ListOfPaveBlock& aLPBInOn=aFF.PaveBlocks();
 417     aNbPBInOn=aLPBInOn.Extent();
 418     //
 419     //===
 420     const TColStd_ListOfInteger& aLSE=aFF.SharedEdges();
 421     aNbSE=aLSE.Extent();
 422     if (!aNbPBInOn && !aNbSE) {
 423       continue;
 424     }
 425     //===
 426     //
 427     // if there is at least one section edge between faces nF1, nF2
 428     // they can not be SDF
 429     BOPTools_SequenceOfCurves& aSC=aFF.Curves();
 430     aNbC=aSC.Length();
 431     if (aNbC) {
 432       continue;
 433     }
 434     //
 435     // the faces are suspected to be SDF.
 436     // Try to find SDF among images of nF1, nF2
 437     aMFence.Clear();
 438     const TopTools_ListOfShape& aLF1=mySplitFaces.Image(aF1);
 439     const TopTools_ListOfShape& aLF2=mySplitFaces.Image(aF2);
 440     //
 441     aItF1.Initialize(aLF1);
 442     for (; aItF1.More(); aItF1.Next()) {
 443       const TopoDS_Face& aF1x=TopoDS::Face(aItF1.Value());
 444       //
 445       aItF2.Initialize(aLF2);
 446       for (; aItF2.More(); aItF2.Next()) {
 447         const TopoDS_Face& aF2y=TopoDS::Face(aItF2.Value());
 448         bIsSDF=NMTTools_Tools::AreFacesSameDomain(aF1x, aF2y, aCtx);
 449         if (bIsSDF) {
 450           if (aMFence.Contains(aF1x) ||
 451               aMFence.Contains(aF2y)) {
 452             continue;
 453           }
 454           aMFence.Add(aF1x);
 455           aMFence.Add(aF2y);
 456           //
 457           NMTTools_CoupleOfShape aCS;
 458           //
 459           aCS.SetShape1(aF1x);
 460           aCS.SetShape2(aF2y);
 461           aLCS.Append(aCS);
 462           //
 463           if (aF1x==aF1) {
 464             if (!mySplitFaces.HasImage(aF1)) {
 465               mySplitFaces.Bind(aF1, aF1);
 466             }
 467           }
 468           if (aF2y==aF2) {
 469             if (!mySplitFaces.HasImage(aF2)) {
 470               mySplitFaces.Bind(aF2, aF2);
 471             }
 472           }
 473           //
 474
 475         }
 476       }
 477     }
 478   }//for (i=1; i<=aNbFF; ++i)
 479   //
 480   aNbC=aLCS.Extent();
 481   if (!aNbC) {
 482     return;
 483   }
 484   //
 485   // 2. Find Chains
 486   NMTTools_IndexedDataMapOfShapeIndexedMapOfShape aMC;
 487   //
 488   NMTTools_Tools::FindChains(aLCS, aMC);
 489   //
 490   // 3. Fill the map of SDF mySameDomainFaces
 491   aNbC=aMC.Extent();
 492   for (i=1; i<=aNbC; ++i) {
 493     const TopoDS_Shape& aF=aMC.FindKey(i);
 494     const TopTools_IndexedMapOfShape& aMSDF=aMC(i);
 495     //
 496     aNbFF=aMSDF.Extent();
 497     for (j=1; j<=aNbFF; ++j) {
 498       const TopoDS_Shape& aFSD=aMSDF(j);
 499       mySameDomainShapes.Add(aFSD, aF);
 500     }
 501   }
 502   //
 503 }
 504 //=======================================================================
 505 // function: FillImagesFaces1
 506 // purpose:
 507 //=======================================================================
 508   void GEOMAlgo_Builder::FillImagesFaces1()
 509 {
 510   Standard_Integer i, aNb, iSense;
 511   TopoDS_Face aF, aFSp, aFSD;
 512   TopTools_ListOfShape aLFx;
 513   TopTools_ListIteratorOfListOfShape aIt;
 514   //
 515   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 516   //
 517   aNb=aDS.NumberOfShapesOfTheObject();
 518   for (i=1; i<=aNb; ++i) {
 519     const TopoDS_Shape& aS=aDS.Shape(i);
 520     if (aS.ShapeType()!=TopAbs_FACE) {
 521       continue;
 522     }
 523     //
 524     if (!mySplitFaces.HasImage(aS)) {
 525       continue;
 526     }
 527     //
 528     aF=TopoDS::Face(aS);
 529     //
 530     aLFx.Clear();
 531     const TopTools_ListOfShape& aLF=mySplitFaces.Image(aF);
 532     aIt.Initialize(aLF);
 533     for (; aIt.More(); aIt.Next()) {
 534       aFSp=TopoDS::Face(aIt.Value());
 535       if (!mySameDomainShapes.Contains(aFSp)) {
 536         aLFx.Append(aFSp);
 537       }
 538       else {
 539         const TopoDS_Shape& aSx=mySameDomainShapes.FindFromKey(aFSp);
 540         aFSD=TopoDS::Face(aSx);
 541         iSense=GEOMAlgo_Tools3D::Sense(aFSp, aFSD);
 542         if (iSense<0) {
 543           aFSD.Reverse();
 544         }
 545         aLFx.Append(aFSD);
 546       }
 547     }
 548     if (!myImages.HasImage(aF)) {//XX
 549       myImages.Bind(aF, aLFx);
 550     }
 551   }
 552 }
 553 //=======================================================================
 554 // function: FillInternalVertices
 555 // purpose:
 556 //=======================================================================
 557   void GEOMAlgo_Builder::FillInternalVertices()
 558 {
 559   const NMTDS_ShapesDataStructure& aDS=*myPaveFiller->DS();
 560   NMTTools_PaveFiller* pPF=myPaveFiller;
 561   NMTDS_InterfPool* pIP=pPF->IP();
 562   IntTools_Context& aCtx= pPF->ChangeContext();
 563   //
 564   BOPTools_CArray1OfSSInterference& aFFs=pIP->SSInterferences();
 565   BOPTools_CArray1OfVSInterference& aVFs=pIP->VSInterferences();
 566   BOPTools_CArray1OfESInterference& aEFs=pIP->ESInterferences();
 567   const NMTTools_IndexedDataMapOfIndexedMapOfInteger& aMAV=pPF->AloneVertices();
 568   //
 569   Standard_Boolean bHasImage;
 570   Standard_Integer i, j, nF, aNbS, nV, nVSD, n1, n2, iFlag;
 571   Standard_Integer aNbVFs, aNbAVF, aNbEFs, aNbVC, aNbE, aNbV;
 572   Standard_Real aU1, aU2, aTol;
 573   NMTTools_IndexedDataMapOfIndexedMapOfInteger aMFMV;
 574   TopTools_MapOfShape aMFence;
 575   TopTools_ListIteratorOfListOfShape aIt, aItV;
 576   BRep_Builder aBB;
 577   //
 578   // 1. Collect face-vertex candidates [aMFMV]
 579   //
 580   // 1.1. VFs
 581   aNbVFs=aVFs.Extent();
 582   for (i=1; i<=aNbVFs; ++i) {
 583     const BOPTools_VSInterference& aVS=aVFs(i);
 584     aVS.Indices(n1, n2);
 585     nF=n2;
 586     nV=n1;
 587     if (aDS.Shape(n1).ShapeType()==TopAbs_FACE) {
 588       nF=n1;
 589       nV=n2;
 590     }
 591     nVSD=pPF->FindSDVertex(nV);
 592     if (nVSD) {
 593       nV=nVSD;
 594     }
 595     //
 596     UpdateCandidates(nF, nV, aMFMV);
 597   }
 598   //
 599   // 1.2 EFs
 600   aNbEFs=aEFs.Extent();
 601   for (i=1; i<=aNbEFs; ++i) {
 602     const BOPTools_ESInterference& aEF=aEFs(i);
 603     aEF.Indices(n1, n2);
 604     nV=aEF.NewShape();
 605     if (!nV) {
 606       continue;
 607     }
 608     const TopoDS_Shape& aSnew=aDS.Shape(nV);
 609     if (aSnew.ShapeType()!=TopAbs_VERTEX) {
 610       continue;
 611     }
 612     //
 613     nF=(aDS.Shape(n1).ShapeType()==TopAbs_FACE) ? n1 : n2;
 614     nVSD=pPF->FindSDVertex(nV);
 615     if (nVSD) {
 616       nV=nVSD;
 617     }
 618     UpdateCandidates(nF, nV, aMFMV);
 619   }
 620   //
 621   aNbS=aDS.NumberOfShapesOfTheObject();
 622   for (nF=1; nF<=aNbS; ++nF) {
 623     const TopoDS_Shape& aF=aDS.Shape(nF);
 624     //
 625     if (aF.ShapeType()!=TopAbs_FACE) {
 626       continue;
 627     }
 628     if (!aMFence.Add(aF)) {
 629       continue;
 630     }
 631     //
 632     const TopoDS_Face& aFF=TopoDS::Face(aF);
 633     aTol=BRep_Tool::Tolerance(aFF);
 634     //
 635     // 1.3 FFs
 636     if (aMAV.Contains(nF)) {
 637       const TColStd_IndexedMapOfInteger& aMAVF=aMAV.FindFromKey(nF);
 638       aNbAVF=aMAVF.Extent();
 639       for (j=1; j<=aNbAVF; ++j) {
 640         nV=aMAVF(j);
 641         nVSD=pPF->FindSDVertex(nV);
 642         if (nVSD) {
 643           nV=nVSD;
 644         }
 645         //
 646         UpdateCandidates(nF, nV, aMFMV);
 647       }
 648     }
 649     //
 650     // 1.4 Internal vertices of the face nF
 651     BooleanOperations_OnceExplorer aExp(aDS);
 652     aExp.Init(nF, TopAbs_VERTEX);
 653     for (; aExp.More(); aExp.Next()) {
 654       nV=aExp.Current();
 655       const TopoDS_Shape& aV=aDS.Shape(nV);
 656       if (aV.Orientation()==TopAbs_INTERNAL) {
 657         nVSD=pPF->FindSDVertex(nV);
 658         if (nVSD) {
 659           nV=nVSD;
 660         }
 661         //
 662         UpdateCandidates(nF, nV, aMFMV);
 663       }
 664     }
 665     //
 666     // 2. Process face nF
 667     if (!aMFMV.Contains(nF)) {
 668       continue;
 669     }
 670     //
 671     const TColStd_IndexedMapOfInteger& aMVC=aMFMV.FindFromKey(nF);
 672     aNbVC=aMVC.Extent();
 673     if (!aNbVC) {
 674       continue;
 675     }
 676     //
 677     // 2.1 Refine candidates
 678     TopTools_IndexedDataMapOfShapeListOfShape aMVE;
 679     TopTools_ListOfShape aLV;
 680     //
 681     bHasImage=myImages.HasImage(aF);
 682     if (bHasImage) {
 683       const TopTools_ListOfShape& aLFx=myImages.Image(aF);
 684       aIt.Initialize(aLFx);
 685       for (; aIt.More(); aIt.Next()) {
 686         const TopoDS_Shape& aFx=aIt.Value();
 687         TopExp::MapShapesAndAncestors(aFx, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 688       }
 689     }
 690     else {
 691       Standard_Boolean bFaceToProcess;
 692       //
 693       TopExp::MapShapesAndAncestors(aF, TopAbs_VERTEX, TopAbs_EDGE, aMVE);
 694       bFaceToProcess=Standard_False;
 695       for (j=1; j<=aNbVC; ++j) {
 696         nV=aMVC(j);
 697         const TopoDS_Shape& aV=aDS.Shape(nV);
 698         if (!aMVE.Contains(aV)) {
 699           bFaceToProcess=!bFaceToProcess;
 700           break;
 701         }
 702       }
 703       if (!bFaceToProcess) {
 704         continue;
 705       }
 706     }// else
 707     //
 708     for (j=1; j<=aNbVC; ++j) {
 709       nV=aMVC(j);
 710       const TopoDS_Shape& aV=aDS.Shape(nV);
 711       if (aMVE.Contains(aV)) {
 712         const TopTools_ListOfShape& aLE=aMVE.FindFromKey(aV);
 713         aNbE=aLE.Extent();
 714         if (aNbE) {
 715           continue;
 716         }
 717       }
 718       aLV.Append(aV);
 719     }
 720     //
 721     aNbV=aLV.Extent();
 722     if (aNbV) {
 723       //  3. Try to put vertices into the face(s)
 724       aItV.Initialize(aLV);
 725       for (; aItV.More(); aItV.Next()) {
 726         TopoDS_Vertex aV=TopoDS::Vertex(aItV.Value());
 727         aV.Orientation(TopAbs_INTERNAL);
 728         //
 729         bHasImage=myImages.HasImage(aF);
 730         if (bHasImage) {
 731           const TopTools_ListOfShape& aLFx=myImages.Image(aF);
 732           aIt.Initialize(aLFx);
 733           for (; aIt.More(); aIt.Next()) {
 734             TopoDS_Face aFx=TopoDS::Face(aIt.Value());
 735             // update classifier
 736             IntTools_FClass2d& aClsf=aCtx.FClass2d(aFx);
 737             aClsf.Init(aFx, aTol);
 738             //
 739             iFlag=aCtx.ComputeVS (aV, aFx, aU1, aU2);
 740             if (!iFlag) {
 741               aBB.Add(aFx, aV);
 742               break;
 743             }
 744           }
 745         }
 746         else {
 747           const TopoDS_Face& aFx=TopoDS::Face(aF);
 748           // update classifier
 749           IntTools_FClass2d& aClsf=aCtx.FClass2d(aFx);
 750           aClsf.Init(aFx, aTol);
 751           //
 752           iFlag=aCtx.ComputeVS (aV, aFx, aU1, aU2);
 753           if (!iFlag) {
 754             TopoDS_Face aFz;
 755             //
 756             GEOMAlgo_Tools3D::CopyFace(aFx, aFz);
 757             aBB.Add(aFz, aV);
 758             myImages.Bind(aF, aFz);
 759           }
 760         }
 761       }// for (; aItV.More(); aItV.Next()) {
 762     }// if (aNbV) {
 763   }// for (nF=1; nF<=aNb; ++nF) {
 764 }
 765 //=======================================================================
 766 // function: UpdateCandidates
 767 // purpose:
 768 //=======================================================================
 769 void UpdateCandidates(const Standard_Integer theNF,
 770                       const Standard_Integer theNV,
 771                        NMTTools_IndexedDataMapOfIndexedMapOfInteger& theMFMV)
 772 {
 773   if (theMFMV.Contains(theNF)) {
 774     TColStd_IndexedMapOfInteger& aMV=theMFMV.ChangeFromKey(theNF);
 775     aMV.Add(theNV);
 776   }
 777   else {
 778     TColStd_IndexedMapOfInteger aMV;
 779     aMV.Add(theNV);
 780     theMFMV.Add(theNF, aMV);
 781   }
 782 }