src/NMTTools/NMTTools_PaveFiller_4.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:        NMTTools_PaveFiller_4.cxx
  21 // Created:     Mon Dec  8 17:08:58 2003
  22 // Author:      Peter KURNEV
  23 //              <pkv@irinox>
  24
  25
  26 #include <NMTTools_PaveFiller.ixx>
  27 //
  28 #include <stdio.h>
  29 #include <Precision.hxx>
  30
  31 #include <gp_XYZ.hxx>
  32 #include <gp_Pnt.hxx>
  33 #include <Bnd_Box.hxx>
  34
  35 #include <TColStd_MapOfInteger.hxx>
  36 #include <TColStd_IndexedMapOfInteger.hxx>
  37 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  38 #include <TColStd_MapIteratorOfMapOfInteger.hxx>
  39
  40 #include <TopoDS.hxx>
  41 #include <TopoDS_Edge.hxx>
  42 #include <TopoDS_Vertex.hxx>
  43 #include <TopoDS_Compound.hxx>
  44
  45 #include <TopTools_IndexedMapOfShape.hxx>
  46 #include <TopTools_ListIteratorOfListOfShape.hxx>
  47 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
  48 #include <TopTools_DataMapOfShapeListOfShape.hxx>
  49 #include <TopTools_ListOfShape.hxx>
  50 #include <TopTools_DataMapOfShapeShape.hxx>
  51
  52 #include <BRep_Tool.hxx>
  53 #include <BRep_Builder.hxx>
  54 #include <BRepBndLib.hxx>
  55
  56 #include <BOPTColStd_Dump.hxx>
  57 #include <BOPTColStd_Failure.hxx>
  58
  59 #include <IntTools_ShrunkRange.hxx>
  60 #include <IntTools_Range.hxx>
  61 #include <IntTools_CommonPrt.hxx>
  62 #include <IntTools_SequenceOfRanges.hxx>
  63 #include <IntTools_EdgeEdge.hxx>
  64 #include <IntTools_SequenceOfCommonPrts.hxx>
  65
  66 #include <BOPTools_Pave.hxx>
  67 #include <BOPTools_PaveSet.hxx>
  68 #include <BOPTools_PaveBlockIterator.hxx>
  69 #include <BOPTools_PaveBlock.hxx>
  70 #include <BOPTools_CArray1OfEEInterference.hxx>
  71 #include <BOPTools_EEInterference.hxx>
  72 #include <BOPTools_ListOfPaveBlock.hxx>
  73 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
  74 #include <BOPTools_CArray1OfVVInterference.hxx>
  75 #include <BOPTools_VVInterference.hxx>
  76 #include <BOPTools_CArray1OfEEInterference.hxx>
  77 #include <BOPTools_Tools.hxx>
  78 #include <BOPTools_IDMapOfPaveBlockIMapOfPaveBlock.hxx>
  79 #include <BOPTools_IMapOfPaveBlock.hxx>
  80 #include <BOPTools_ListIteratorOfListOfPave.hxx>
  81 #include <BOPTools_SequenceOfPaveBlock.hxx>
  82
  83 #include <BooleanOperations_AncestorsSeqAndSuccessorsSeq.hxx>
  84 #include <BooleanOperations_IndexedDataMapOfShapeInteger.hxx>
  85 #include <BooleanOperations_KindOfInterference.hxx>
  86
  87 #include <NMTDS_Iterator.hxx>
  88 #include <NMTDS_ShapesDataStructure.hxx>
  89 #include <NMTDS_IndexedDataMapOfIntegerShape.hxx>
  90 #include <NMTDS_IndexedDataMapOfShapeBox.hxx>
  91 #include <NMTDS_BoxBndTree.hxx>
  92 #include <NCollection_UBTreeFiller.hxx>
  93 #include <NMTDS_InterfPool.hxx>
  94
  95 #include <NMTTools_IndexedDataMapOfIndexedMapOfInteger.hxx>
  96 #include <NMTTools_ListOfCommonBlock.hxx>
  97 #include <NMTTools_CommonBlock.hxx>
  98 #include <NMTTools_ListIteratorOfListOfCommonBlock.hxx>
  99
 100 // Modified  Thu Sep 14 14:35:18 2006
 101 // Contribution of Samtech www.samcef.com BEGIN
 102 #include <TColStd_ListOfInteger.hxx>
 103 #include <TColStd_ListIteratorOfListOfInteger.hxx>
 104 #include <BRepBndLib.hxx>
 105 #include <BOPTools_CArray1OfVSInterference.hxx>
 106 #include <BOPTools_VSInterference.hxx>
 107 // Contribution of Samtech www.samcef.com END
 108 //
 109 //
 110
 111
 112 static
 113   void TreatNewVertices(const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI,
 114                         TopTools_DataMapOfShapeListOfShape& myImages,
 115                         TopTools_DataMapOfShapeShape& myOrigins);
 116
 117 static
 118   void MakeNewVertex(const TopTools_ListOfShape& aLV,
 119                      TopoDS_Vertex& aNewVertex);
 120
 121
 122 static
 123   void VertexParameters(const IntTools_CommonPrt& aCPart,
 124                         Standard_Real& aT1,
 125                         Standard_Real& aT2);
 126 static
 127   Standard_Boolean IsOnPave(const Standard_Real& aT1,
 128                             const IntTools_Range& aRange,
 129                             const Standard_Real& aTolerance);
 130 static
 131   void EECommonBlocks(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB);
 132
 133 static
 134   void ProcessBlock(const BOPTools_PaveBlock& aPB,
 135                     const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
 136                     BOPTools_IMapOfPaveBlock& aProcessedBlocks,
 137                     BOPTools_IMapOfPaveBlock& aChain);
 138 static
 139   void FindChains(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
 140                   NMTTools_ListOfCommonBlock& aLCB);
 141
 142 //=======================================================================
 143 // function: PerformEE
 144 // purpose:
 145 //=======================================================================
 146   void NMTTools_PaveFiller::PerformEE()
 147 {
 148   myIsDone=Standard_False;
 149   //
 150   Standard_Boolean bJustAdd;
 151   Standard_Integer n1, n2, anIndexIn, nE1, nE2, aNbVEs, aBlockLength;
 152   Standard_Integer aTmp, aWhat, aWith, i, aNbCPrts, aDiscretize=30;
 153   Standard_Integer aNbLPB1, aNbLPB2;
 154   Standard_Real aTolE1, aTolE2, aDeflection=0.01;
 155   BOPTools_ListIteratorOfListOfPaveBlock anIt1, anIt2;
 156   TopoDS_Edge aEWhat, aEWith;
 157   TopoDS_Vertex aNewVertex;
 158   BooleanOperations_IndexedDataMapOfShapeInteger aMapVI;
 159   BOPTools_IDMapOfPaveBlockIMapOfPaveBlock aMapCB;
 160   //
 161   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
 162   //
 163   myDSIt->Initialize(TopAbs_EDGE, TopAbs_EDGE);
 164   //
 165   // BlockLength correction
 166   aNbVEs=myDSIt->BlockLength();
 167   aBlockLength=aEEs.BlockLength();
 168   if (aNbVEs > aBlockLength) {
 169     aEEs.SetBlockLength(aNbVEs);
 170   }
 171   //
 172   for (; myDSIt->More(); myDSIt->Next()) {
 173     myDSIt->Current(n1, n2, bJustAdd);
 174     anIndexIn = 0;
 175     //
 176     //if (myIntrPool->IsComputed(n1, n2)) {
 177     //  continue;
 178     //}
 179     //
 180     nE1=n1;
 181     nE2=n2;
 182     //
 183     if(bJustAdd) {
 184       //myIntrPool->AddInterference (nE1, nE2, BooleanOperations_EdgeEdge, anIndexIn);
 185       continue;
 186     }
 187     //
 188     const TopoDS_Edge aE1=TopoDS::Edge(myDS->Shape(nE1));//mpv
 189     const TopoDS_Edge aE2=TopoDS::Edge(myDS->Shape(nE2));//mpv
 190
 191     //
 192     if (BRep_Tool::Degenerated(aE1) || BRep_Tool::Degenerated(aE2)){
 193       continue;
 194     }
 195     //
 196     aTolE1=BRep_Tool::Tolerance(aE1);
 197     aTolE2=BRep_Tool::Tolerance(aE2);
 198     //
 199     BOPTools_ListOfPaveBlock& aLPB1=mySplitShapesPool(myDS->RefEdge(nE1));
 200     BOPTools_ListOfPaveBlock& aLPB2=mySplitShapesPool(myDS->RefEdge(nE2));
 201     //
 202     // Modified  Thu Sep 14 14:35:18 2006
 203     // Contribution of Samtech www.samcef.com BEGIN
 204     aNbLPB1=aLPB1.Extent();
 205     aNbLPB2=aLPB2.Extent();
 206
 207     //if (aE1.IsSame(aE2) && aNbLPB1==1 && aNbLPB2==1) {
 208     //  continue;
 209     //}
 210     // Contribution of Samtech www.samcef.com END
 211     //
 212     for (anIt1.Initialize(aLPB1); anIt1.More(); anIt1.Next()) {
 213       BOPTools_PaveBlock& aPB1=anIt1.Value();
 214       const IntTools_ShrunkRange& aShrunkRange1=aPB1.ShrunkRange();
 215       //
 216       const IntTools_Range& aSR1=aShrunkRange1.ShrunkRange();
 217       const Bnd_Box&        aBB1=aShrunkRange1.BndBox();
 218       //
 219       for (anIt2.Initialize(aLPB2); anIt2.More(); anIt2.Next()) {
 220         BOPTools_PaveBlock& aPB2=anIt2.Value();
 221         const IntTools_ShrunkRange& aShrunkRange2=aPB2.ShrunkRange();
 222
 223         const IntTools_Range& aSR2=aShrunkRange2.ShrunkRange();
 224         const Bnd_Box&        aBB2=aShrunkRange2.BndBox();
 225         //
 226         if (aBB1.IsOut (aBB2)) {
 227           continue;
 228         }
 229         //
 230         // EE
 231         IntTools_EdgeEdge aEE;
 232         aEE.SetEdge1 (aE1);
 233         aEE.SetEdge2 (aE2);
 234         aEE.SetTolerance1 (aTolE1);
 235         aEE.SetTolerance2 (aTolE2);
 236         aEE.SetDiscretize (aDiscretize);
 237         aEE.SetDeflection (aDeflection);
 238         //
 239         IntTools_Range anewSR1 = aSR1;
 240         IntTools_Range anewSR2 = aSR2;
 241         //
 242         BOPTools_Tools::CorrectRange (aE1, aE2, aSR1, anewSR1);
 243         BOPTools_Tools::CorrectRange (aE2, aE1, aSR2, anewSR2);
 244         //
 245         aEE.SetRange1(anewSR1);
 246         aEE.SetRange2(anewSR2);
 247
 248         aEE.Perform();
 249         //
 250         anIndexIn=0;
 251         //
 252         if (aEE.IsDone()) {
 253           // reverse order if it is necessary
 254           aEWhat=aE1;
 255           aEWith=aE2;
 256           aWhat=nE1;
 257           aWith=nE2;
 258           if (aEE.Order()) {
 259             aTmp=aWhat;
 260             aWhat=aWith;
 261             aWith=aTmp;
 262             aEWhat=aE2;
 263             aEWith=aE1;
 264           }
 265           //
 266           const IntTools_SequenceOfCommonPrts& aCPrts=aEE.CommonParts();
 267           aNbCPrts=aCPrts.Length();
 268           for (i=1; i<=aNbCPrts; i++) {
 269             const IntTools_CommonPrt& aCPart=aCPrts(i);
 270             const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
 271             //
 272             anIndexIn=0;
 273             //
 274             TopAbs_ShapeEnum aType=aCPart.Type();
 275             switch (aType) {
 276               case TopAbs_VERTEX:  {
 277                 Standard_Real aT1, aT2, aTol=Precision::PConfusion();
 278                 Standard_Boolean bIsOnPave1, bIsOnPave2;
 279                 IntTools_Range aR1, aR2;
 280                 //
 281                 VertexParameters(aCPart, aT1, aT2);
 282                 //
 283                 //decide to keep the pave or not
 284                 aR1 = (aEE.Order()) ? anewSR2 : anewSR1;
 285                 aR2 = (aEE.Order()) ? anewSR1 : anewSR2;
 286                 //
 287                 bIsOnPave1=IsOnPave(aT1, aR1, aTol);
 288                 bIsOnPave2=IsOnPave(aT2, aR2, aTol);
 289                 //
 290                 if(bIsOnPave1 || bIsOnPave2) {
 291                    continue;
 292                 }
 293                 //
 294                 BOPTools_Tools::MakeNewVertex(aEWhat, aT1, aEWith, aT2, aNewVertex);
 295                 //
 296                 //modified by NIZNHY-PKV Mon Jun 19 11:40:09 2007f
 297                 {
 298                   Standard_Integer nV11, nV12, nV21, nV22, nVS[2], k, j, iFound;
 299                   Standard_Real aTolVx, aTolVnew, aD2, aDT2;
 300                   TColStd_MapOfInteger aMV;
 301                   gp_Pnt aPnew, aPx;
 302                   //
 303                   iFound=0;
 304                   j=-1;
 305                   nV11=aPB1.Pave1().Index();
 306                   nV12=aPB1.Pave2().Index();
 307                   nV21=aPB2.Pave1().Index();
 308                   nV22=aPB2.Pave2().Index();
 309                   aMV.Add(nV11);
 310                   aMV.Add(nV12);
 311                   //
 312                   if (aMV.Contains(nV21)) {
 313                     ++j;
 314                     nVS[j]=nV21;
 315                   }
 316                   if (aMV.Contains(nV22)) {
 317                     ++j;
 318                     nVS[j]=nV22;
 319                   }
 320                   //
 321                   aTolVnew=BRep_Tool::Tolerance(aNewVertex);
 322                   aPnew=BRep_Tool::Pnt(aNewVertex);
 323                   //
 324                   for (k=0; k<=j; ++k) {
 325                     const TopoDS_Vertex& aVx=TopoDS::Vertex(myDS->Shape(nVS[k]));
 326                     aTolVx=BRep_Tool::Tolerance(aVx);
 327                     aPx=BRep_Tool::Pnt(aVx);
 328                     aD2=aPnew.SquareDistance(aPx);
 329                     //
 330                     aDT2=100.*(aTolVnew+aTolVx)*(aTolVnew+aTolVx);
 331                     //
 332                     if (aD2<aDT2) {
 333                       iFound=1;
 334                       break;
 335                     }
 336                   }
 337                   //
 338                   if (iFound) {
 339                     continue;
 340                   }
 341                 }
 342                 //modified by NIZNHY-PKV Mon Jun 19 11:40:16 2007t
 343                 //
 344                 // Add Interference to the Pool
 345                 BOPTools_EEInterference anInterf (aWhat, aWith, aCPart);
 346                 //
 347                 anIndexIn=aEEs.Append(anInterf);
 348                 // qqf
 349                 {
 350                   myIP->Add(aWhat, aWith, Standard_True, NMTDS_TI_EE);
 351                 }
 352                 // qqt
 353                 //
 354                 // Collect
 355                 aMapVI.Add(aNewVertex, anIndexIn);
 356               }
 357                 break;
 358
 359               case TopAbs_EDGE: {
 360                 Standard_Integer aNbComPrt2;
 361                 Standard_Boolean aCoinsideFlag;
 362                 //
 363                 aNbComPrt2=aRanges2.Length();
 364                 aCoinsideFlag=IsBlocksCoinside(aPB1, aPB2);
 365                 //
 366                 if (aNbComPrt2>1 || !aCoinsideFlag) {
 367                   //myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
 368                   break;
 369                 }
 370                 //
 371                 // Fill aMapCB
 372                 if (aMapCB.Contains(aPB1)) {
 373                   BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.ChangeFromKey(aPB1);
 374                   aMapPB.Add(aPB1);
 375                   aMapPB.Add(aPB2);
 376                 }
 377                 else {
 378                   BOPTools_IMapOfPaveBlock aMapPB;
 379                   aMapPB.Add(aPB1);
 380                   aMapPB.Add(aPB2);
 381                   aMapCB.Add(aPB1, aMapPB);
 382                 }
 383                 //
 384                 if (aMapCB.Contains(aPB2)) {
 385                   BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.ChangeFromKey(aPB2);
 386                   aMapPB.Add(aPB1);
 387                   aMapPB.Add(aPB2);
 388                 }
 389                 else {
 390                   BOPTools_IMapOfPaveBlock aMapPB;
 391                   aMapPB.Add(aPB1);
 392                   aMapPB.Add(aPB2);
 393                   aMapCB.Add(aPB2, aMapPB);
 394                 }
 395                 // qqf
 396                 {
 397                   myIP->Add(aWhat, aWith, Standard_True, NMTDS_TI_EE);
 398                 }
 399                 // qqt
 400               }
 401                 break;
 402             default:
 403               break;
 404             } // switch (aType)
 405           } // for (i=1; i<=aNbCPrts; i++)
 406         }// if (aEE.IsDone())
 407       } // for (; anIt2.More(); anIt2.Next())
 408     } // for (; anIt1.More(); anIt1.Next())
 409   }// for (; myDSIt.More(); myDSIt.Next())
 410   //
 411   EENewVertices (aMapVI);
 412   EECommonBlocks(aMapCB);
 413   // Modified to invoke new nethod Thu Sep 14 14:35:18 2006
 414   // Contribution of Samtech www.samcef.com BEGIN
 415   PerformVF1();
 416   // Contribution of Samtech www.samcef.com BEGIN
 417   myIsDone=Standard_True;
 418 }
 419 //=======================================================================
 420 // function:EECommonBlocks
 421 // purpose:
 422 //=======================================================================
 423   void NMTTools_PaveFiller::EECommonBlocks(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB)
 424 {
 425   NMTTools_ListOfCommonBlock aLCB;
 426   //
 427   FindChains(aMapCB, aLCB);
 428   ReplaceCommonBlocks(aLCB);
 429 }
 430 //=======================================================================
 431 // function:EENewVertices
 432 // purpose:
 433 //=======================================================================
 434   void NMTTools_PaveFiller::EENewVertices (const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI)
 435 {
 436   Standard_Integer aNb, aNbVSD, nVnew, nIEE, nE[2], j, iFlag;
 437   Standard_Real aT;
 438   TopoDS_Edge aE;
 439   TopTools_DataMapOfShapeListOfShape myImages;
 440   TopTools_DataMapOfShapeShape myOrigins;
 441   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape aItIm;
 442   TopTools_ListIteratorOfListOfShape aIt;
 443   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
 444   TColStd_MapOfInteger aMFence;
 445   BOPTools_Pave aPave;
 446   //
 447   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
 448   //
 449   aNb=aMapVI.Extent();
 450   if (!aNb) { // no new vertices, no new problems
 451     return;
 452   }
 453   //
 454   // 0.
 455   if (aNb==1) {
 456     TopoDS_Vertex aV1=TopoDS::Vertex(aMapVI.FindKey(1));
 457     EENewVertices(aV1, aMapVI);
 458     return;
 459   }
 460   //
 461   // 1.
 462   TreatNewVertices(aMapVI, myImages, myOrigins);
 463   //
 464   aItIm.Initialize(myImages);
 465   for (; aItIm.More(); aItIm.Next()) {
 466     const TopoDS_Vertex& aVnew=TopoDS::Vertex(aItIm.Key());
 467     const TopTools_ListOfShape& aLVSD=aItIm.Value();
 468     //
 469     aNbVSD=aLVSD.Extent();
 470     if (aNbVSD==1) {// simple case aVnew=aVold
 471       EENewVertices(aVnew, aMapVI);
 472       continue;
 473     }
 474     //
 475     // aNbVSD>1
 476     myDS->InsertShapeAndAncestorsSuccessors(aVnew, anASSeq);
 477     nVnew=myDS->NumberOfInsertedShapes();
 478     myDS->SetState(nVnew, BooleanOperations_ON);
 479     //
 480     aMFence.Clear();
 481     aIt.Initialize(aLVSD);
 482     for (; aIt.More(); aIt.Next()) {
 483       const TopoDS_Vertex& aVold=TopoDS::Vertex(aIt.Value());
 484       nIEE=aMapVI.FindFromKey(aVold);
 485       BOPTools_EEInterference& aEE=aEEs(nIEE);
 486       aEE.Indices(nE[0], nE[1]);
 487       aEE.SetNewShape(nVnew);
 488       //
 489       for (j=0; j<2; ++j) {
 490         if (aMFence.Add(nE[j])) {
 491           aE=TopoDS::Edge(myDS->Shape(nE[j]));
 492           iFlag=myContext.ComputeVE (aVnew, aE, aT);
 493           if (!iFlag) {
 494             aPave.SetInterference(-1);
 495             aPave.SetType (BooleanOperations_EdgeEdge);
 496             aPave.SetIndex(nVnew);
 497             aPave.SetParam(aT);
 498             //
 499             BOPTools_PaveSet& aPaveSet=myPavePoolNew(myDS->RefEdge(nE[j]));
 500             aPaveSet.Append(aPave);
 501           }
 502         }// if (aMFence.Add(nE[j])) {
 503       }// for (j=0; j<2; ++j) {
 504     }//for (; aIt.More(); aIt.Next()) {
 505   }// for (; aItIm.More(); aItIm.Next())
 506 }
 507 //
 508 // case: use_02
 509 // completely rewritten
 510 //=======================================================================
 511 //function : TreatNewVertices
 512 //purpose  :
 513 //=======================================================================
 514 void TreatNewVertices(const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI,
 515                    TopTools_DataMapOfShapeListOfShape& myImages,
 516                    TopTools_DataMapOfShapeShape& myOrigins)
 517 {
 518   Standard_Integer j, i, aNbV, aNbVSD;
 519   Standard_Real aTol;
 520   TColStd_ListIteratorOfListOfInteger aIt;
 521   TopoDS_Shape aSTmp, aVF;
 522   TopoDS_Vertex aVnew;
 523   TopTools_IndexedMapOfShape aMV, aMVProcessed;
 524   TopTools_ListIteratorOfListOfShape aItS;
 525   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape aItIm;
 526   TopTools_DataMapOfShapeListOfShape aMVV;
 527   NMTDS_IndexedDataMapOfIntegerShape aMIS;
 528   NMTDS_IndexedDataMapOfShapeBox aMSB;
 529   //
 530   NMTDS_BoxBndTreeSelector aSelector;
 531   NMTDS_BoxBndTree aBBTree;
 532   NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
 533   //
 534   myImages.Clear();
 535   myOrigins.Clear();
 536   //
 537   aNbV=aMapVI.Extent();
 538   for (i=1; i<=aNbV; ++i) {
 539     const TopoDS_Shape& aV=aMapVI.FindKey(i);
 540     aMV.Add(aV);
 541   }
 542   //
 543   for (i=1; i<=aNbV; ++i) {
 544     const TopoDS_Shape& aV=aMV(i);
 545     Bnd_Box aBox;
 546     //
 547     aTol=BRep_Tool::Tolerance(TopoDS::Vertex(aV));
 548     aBox.SetGap(aTol);
 549     BRepBndLib::Add(aV, aBox);
 550     //
 551     aTreeFiller.Add(i, aBox);
 552     //
 553     aMIS.Add(i, aV);
 554     aMSB.Add(aV, aBox);
 555   }
 556   //
 557   aTreeFiller.Fill();
 558   //
 559   // Chains
 560   for (i=1; i<=aNbV; ++i) {
 561     const TopoDS_Shape& aV=aMV(i);
 562     //
 563     if (aMVProcessed.Contains(aV)) {
 564       continue;
 565     }
 566     //
 567     Standard_Integer aNbIP, aIP, aNbIP1, aIP1;
 568     TopTools_ListOfShape aLVSD;
 569     TColStd_MapOfInteger aMIP, aMIP1, aMIPC;
 570     TColStd_MapIteratorOfMapOfInteger aIt1;
 571     //
 572     aMIP.Add(i);
 573     while(1) {
 574       aNbIP=aMIP.Extent();
 575       aIt1.Initialize(aMIP);
 576       for(; aIt1.More(); aIt1.Next()) {
 577         aIP=aIt1.Key();
 578         if (aMIPC.Contains(aIP)) {
 579           continue;
 580         }
 581         //
 582         const TopoDS_Shape& aVP=aMIS.FindFromKey(aIP);
 583         const Bnd_Box& aBoxVP=aMSB.FindFromKey(aVP);
 584         //
 585         aSelector.Clear();
 586         aSelector.SetBox(aBoxVP);
 587         //
 588         aNbVSD=aBBTree.Select(aSelector);
 589         if (!aNbVSD) {
 590           continue;  // it must not be
 591         }
 592         //
 593         const TColStd_ListOfInteger& aLI=aSelector.Indices();
 594         aIt.Initialize(aLI);
 595         for (; aIt.More(); aIt.Next()) {
 596           aIP1=aIt.Value();
 597           if (aMIP.Contains(aIP1)) {
 598             continue;
 599           }
 600           aMIP1.Add(aIP1);
 601         } //for (; aIt.More(); aIt.Next()) {
 602       }//for(; aIt1.More(); aIt1.Next()) {
 603       //
 604       aNbIP1=aMIP1.Extent();
 605       if (!aNbIP1) {
 606         break; // from while(1)
 607       }
 608       //
 609       aIt1.Initialize(aMIP);
 610       for(; aIt1.More(); aIt1.Next()) {
 611         aIP=aIt1.Key();
 612         aMIPC.Add(aIP);
 613       }
 614       //
 615       aMIP.Clear();
 616       aIt1.Initialize(aMIP1);
 617       for(; aIt1.More(); aIt1.Next()) {
 618         aIP=aIt1.Key();
 619         aMIP.Add(aIP);
 620       }
 621       aMIP1.Clear();
 622     }// while(1)
 623     //...
 624     aNbIP=aMIPC.Extent();
 625     if (!aNbIP) {
 626       aMIPC.Add(i);
 627     }
 628     //
 629     aIt1.Initialize(aMIPC);
 630     for(j=0; aIt1.More(); aIt1.Next(), ++j) {
 631       aIP=aIt1.Key();
 632       const TopoDS_Shape& aVP=aMIS.FindFromKey(aIP);
 633       if (!j) {
 634         aVF=aVP;
 635       }
 636       aLVSD.Append(aVP);
 637       aMVProcessed.Add(aVP);
 638     }
 639     myImages.Bind(aVF, aLVSD);
 640   }// for (i=1; i<=aNbV; ++i) {
 641   //------------------------------
 642   //
 643   // Make new vertices
 644   aMV.Clear();
 645   aItIm.Initialize(myImages);
 646   for (; aItIm.More(); aItIm.Next()) {
 647     const TopoDS_Shape& aV=aItIm.Key();
 648     const TopTools_ListOfShape& aLVSD=aItIm.Value();
 649     aNbVSD=aLVSD.Extent();
 650     if (aNbVSD>1) {
 651       aMV.Add(aV);
 652       MakeNewVertex(aLVSD, aVnew);
 653       aMVV.Bind(aVnew, aLVSD);
 654     }
 655   }
 656   //
 657   // UnBind old vertices
 658   aNbV=aMV.Extent();
 659   for (i=1; i<=aNbV; ++i) {
 660     const TopoDS_Shape& aV=aMV(i);
 661     myImages.UnBind(aV);
 662   }
 663   //
 664   // Bind new vertices
 665   aItIm.Initialize(aMVV);
 666   for (; aItIm.More(); aItIm.Next()) {
 667     const TopoDS_Shape& aV=aItIm.Key();
 668     const TopTools_ListOfShape& aLVSD=aItIm.Value();
 669     myImages.Bind(aV, aLVSD);
 670   }
 671   //
 672   // Origins
 673   aItIm.Initialize(myImages);
 674   for (; aItIm.More(); aItIm.Next()) {
 675     const TopoDS_Shape& aV=aItIm.Key();
 676     const TopTools_ListOfShape& aLVSD=aItIm.Value();
 677     //
 678     aItS.Initialize(aLVSD);
 679     for (; aItS.More(); aItS.Next()) {
 680       const TopoDS_Shape& aVSD=aItS.Value();
 681       if (!myOrigins.IsBound(aVSD)) {
 682         myOrigins.Bind(aVSD, aV);
 683       }
 684     }
 685   }
 686 }
 687 //
 688 //=======================================================================
 689 //function : MakeNewVertex
 690 //purpose  :
 691 //=======================================================================
 692 void MakeNewVertex(const TopTools_ListOfShape& aLV,
 693                    TopoDS_Vertex& aNewVertex)
 694 {
 695   Standard_Integer aNbV;
 696   Standard_Real aTolV, aD, aDmax;
 697   gp_XYZ aGC;
 698   gp_Pnt aP3D, aPGC;
 699   TopoDS_Vertex aVx;
 700   BRep_Builder aBB;
 701   TopTools_ListIteratorOfListOfShape aIt;
 702   //
 703   aNbV=aLV.Extent();
 704   if (!aNbV) {
 705     return;
 706   }
 707   //
 708   // center of gravity
 709   aGC.SetCoord(0.,0.,0.);
 710   aIt.Initialize(aLV);
 711   for (; aIt.More(); aIt.Next()) {
 712     aVx=TopoDS::Vertex(aIt.Value());
 713     aP3D=BRep_Tool::Pnt(aVx);
 714     aGC+=aP3D.XYZ();
 715   }
 716   aGC/=(Standard_Real)aNbV;
 717   aPGC.SetXYZ(aGC);
 718   //
 719   // tolerance value
 720   aDmax=-1.;
 721   aIt.Initialize(aLV);
 722   for (; aIt.More(); aIt.Next()) {
 723     aVx=TopoDS::Vertex(aIt.Value());
 724     aP3D=BRep_Tool::Pnt(aVx);
 725     aTolV=BRep_Tool::Tolerance(aVx);
 726     aD=aPGC.Distance(aP3D)+aTolV;
 727     if (aD>aDmax) {
 728       aDmax=aD;
 729     }
 730   }
 731   //
 732   aBB.MakeVertex (aNewVertex, aPGC, aDmax);
 733 }
 734 //=======================================================================
 735 // function:EENewVertices
 736 // purpose:
 737 //=======================================================================
 738   void NMTTools_PaveFiller::EENewVertices (const TopoDS_Vertex& aNewVertex,
 739                                            const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI)
 740 {
 741   Standard_Integer  i, aNewShape, nE1, nE2;
 742   Standard_Real  aT1, aT2;
 743   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
 744   BOPTools_Pave aPave;
 745   //
 746   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
 747   //
 748   // one new vertex case is treated in usual way
 749   //
 750   // Insert New Vertex in DS;
 751   myDS->InsertShapeAndAncestorsSuccessors(aNewVertex, anASSeq);
 752   aNewShape=myDS->NumberOfInsertedShapes();
 753   myDS->SetState (aNewShape, BooleanOperations_ON);
 754   // Insert New Vertex in EE Interference
 755   i=aMapVI.FindFromKey(aNewVertex);
 756   BOPTools_EEInterference& aEEInterf= aEEs(i);
 757   aEEInterf.SetNewShape(aNewShape);
 758   // Extact interference info
 759   aEEInterf.Indices(nE1, nE2);
 760   const IntTools_CommonPrt& aCPart=aEEInterf.CommonPrt();
 761   VertexParameters(aCPart, aT1, aT2);
 762   //
 763   // Add Paves to the myPavePoolNew
 764   aPave.SetInterference(i);
 765   aPave.SetType (BooleanOperations_EdgeEdge);
 766   aPave.SetIndex(aNewShape);
 767   // Pave for edge nE1
 768   aPave.SetParam(aT1);
 769   BOPTools_PaveSet& aPaveSet1=myPavePoolNew(myDS->RefEdge(nE1));
 770   aPaveSet1.Append(aPave);
 771   // Pave for edge nE2
 772   aPave.SetParam(aT2);
 773   BOPTools_PaveSet& aPaveSet2=myPavePoolNew(myDS->RefEdge(nE2));
 774   aPaveSet2.Append(aPave);
 775 }
 776 //=======================================================================
 777 // function: RefinePavePool
 778 // purpose:
 779 //=======================================================================
 780   void NMTTools_PaveFiller::RefinePavePool()
 781 {
 782   Standard_Integer  i, aNbNew;
 783
 784   for (i=1; i<=myNbSources; i++) {
 785
 786     if ((myDS->GetShape(i)).ShapeType()==TopAbs_EDGE) {
 787       BOPTools_PaveSet& aPS= myPavePool(myDS->RefEdge(i));
 788       //
 789       BOPTools_PaveSet& aNewPS= myPavePoolNew(myDS->RefEdge(i));
 790       BOPTools_ListOfPave& aNewLP=aNewPS.ChangeSet();
 791       //
 792       aNbNew=aNewLP.Extent();
 793       if (aNbNew) {
 794         BOPTools_ListIteratorOfListOfPave anIt(aNewLP);
 795         for (; anIt.More(); anIt.Next()) {
 796           const BOPTools_Pave& aPave=anIt.Value();
 797           aPS.Append(aPave);
 798         }
 799         // Clear the ListOfPaveBlock
 800         BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(i));
 801         aLPB.Clear();
 802         // Prepare the paveBlocks for that egde again
 803         PreparePaveBlocks(i);
 804       }
 805       aNewLP.Clear();
 806     }
 807   }
 808 }
 809 //=======================================================================
 810 // function: PreparePaveBlocks
 811 // purpose:
 812 //=======================================================================
 813   void NMTTools_PaveFiller::PreparePaveBlocks(const TopAbs_ShapeEnum aType1,
 814                                               const TopAbs_ShapeEnum aType2)
 815 {
 816   myIsDone=Standard_False;
 817   //
 818   Standard_Boolean bOk1, bOk2, bOk3, bFlag;
 819   Standard_Integer i, aNb, nE[2], n1, n2, aNbSplits;
 820   TColStd_MapOfInteger aMap;
 821
 822   bOk1= (aType1==TopAbs_VERTEX) &&  (aType2==TopAbs_EDGE) ;
 823   bOk2= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_EDGE) ;
 824   bOk3= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_FACE) ;
 825   if (!bOk1 && !bOk2 && !bOk3) {// error: Type mismatch
 826     return;
 827   }
 828   //
 829   aNb=bOk2 ? 2 : 1;
 830   //
 831   myDSIt->Initialize(aType1, aType2);
 832   for (; myDSIt->More(); myDSIt->Next()) {
 833     myDSIt->Current(n1, n2, bFlag);
 834     //
 835     nE[0]=n1;
 836     nE[1]=n2;
 837     if (myDS->GetShapeType(n1)!=TopAbs_EDGE) {
 838       nE[0]=n2;
 839       nE[1]=n1;
 840     }
 841     //
 842     for (i=0; i<aNb; ++i) {
 843       BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(nE[i]));
 844       aNbSplits=aLPB.Extent();
 845       if (!aNbSplits) {
 846         if (aMap.Add(nE[i])) {
 847           PreparePaveBlocks(nE[i]);
 848           if (!myIsDone) {
 849             return;
 850           }
 851         }
 852       }
 853     }
 854   }// for (; myDSIt.More(); myDSIt.Next())
 855   myIsDone=Standard_True;
 856 }
 857 //=======================================================================
 858 // function: PreparePaveBlocks
 859 // purpose:
 860 //=======================================================================
 861   void NMTTools_PaveFiller::PreparePaveBlocks(const Standard_Integer nE)
 862 {
 863   myIsDone=Standard_False;
 864   //
 865   char buf[512];
 866   Standard_Integer nV1, nV2, iErr;
 867   TopoDS_Edge aE;
 868   TopoDS_Vertex aV1, aV2;
 869   //
 870   BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(nE));
 871   // Edge
 872   aE=TopoDS::Edge(myDS->Shape(nE));
 873   if (BRep_Tool::Degenerated(aE)) {
 874     myIsDone=Standard_True;
 875     return;
 876   }
 877   //
 878   BOPTools_PaveSet& aPS=myPavePool(myDS->RefEdge(nE));
 879
 880   BOPTools_PaveBlockIterator aPBIt(nE, aPS);
 881   for (; aPBIt.More(); aPBIt.Next()) {
 882     BOPTools_PaveBlock& aPB=aPBIt.Value();
 883     const IntTools_Range& aRange=aPB.Range();
 884     //
 885     const BOPTools_Pave& aPave1=aPB.Pave1();
 886     nV1=aPave1.Index();
 887     aV1=TopoDS::Vertex(myDS->GetShape(nV1));
 888     //
 889     const BOPTools_Pave& aPave2=aPB.Pave2();
 890     nV2=aPave2.Index();
 891     aV2=TopoDS::Vertex(myDS->GetShape(nV2));
 892     //
 893     // ShrunkRange
 894     IntTools_ShrunkRange aSR (aE, aV1, aV2, aRange, myContext);
 895     iErr=aSR.ErrorStatus();
 896     if (!aSR.IsDone()) {
 897       sprintf (buf, "Can not obtain ShrunkRange for Edge %d\n", nE);
 898       BOPTColStd_Dump::PrintMessage(buf);
 899       sprintf (buf, "Can not obtain ShrunkRange for Edge %d", nE);
 900       throw
 901         BOPTColStd_Failure(buf) ;
 902     }
 903     //
 904     if (iErr==6) {
 905       sprintf(buf,
 906               "Warning: [PreparePaveBlocks()] Max.Dummy Shrunk Range for Edge %d\n", nE);
 907       BOPTColStd_Dump::PrintMessage(buf);
 908     }
 909     else {
 910       // Check left paves and correct ShrunkRange if it is necessary
 911       CorrectShrunkRanges (0, aPave1, aSR);
 912       CorrectShrunkRanges (1, aPave2, aSR);
 913     }
 914     //
 915     aPB.SetShrunkRange(aSR);
 916     aLPB.Append(aPB);
 917   } //for (; aPBIt.More(); aPBIt.Next())
 918   myIsDone=Standard_True;
 919 }
 920 //=======================================================================
 921 // function: CorrectShrunkRanges
 922 // purpose:
 923 //=======================================================================
 924   void NMTTools_PaveFiller::CorrectShrunkRanges(const Standard_Integer aSide,
 925                                                 const BOPTools_Pave& aPave,
 926                                                 IntTools_ShrunkRange& aShrunkRange)
 927 {
 928   BooleanOperations_KindOfInterference aType;
 929   Standard_Integer anIndexInterf ;
 930   //
 931   aType=aPave.Type();
 932   if (aType!=BooleanOperations_EdgeEdge) {
 933     return;
 934   }
 935   //
 936   anIndexInterf=aPave.Interference();
 937   if (anIndexInterf<0) {
 938     // it can be EE interf between E and (e1,e2,..en) -> vertex
 939     // so we can't decide which aEE.CommonPrt() we should take.
 940     return;
 941   }
 942
 943   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
 944   const BOPTools_EEInterference& aEE=aEEs(anIndexInterf);
 945   const IntTools_CommonPrt& aCP=aEE.CommonPrt();
 946   const TopoDS_Edge& aE1=aCP.Edge1();
 947   const TopoDS_Edge& aE2=aCP.Edge2();
 948
 949   const IntTools_Range& aSR=aShrunkRange.ShrunkRange();
 950   const TopoDS_Edge& aE=aShrunkRange.Edge();
 951
 952   IntTools_Range aNewRange;
 953   IntTools_Range aCPRange;
 954
 955   if (aE1.IsSame(aE)) {
 956     const IntTools_Range& aR1=aCP.Range1();
 957     aCPRange=aR1;
 958   }
 959   if (aE2.IsSame(aE)) {
 960     const IntTools_SequenceOfRanges& aSeqR=aCP.Ranges2();
 961     const IntTools_Range& aR2=aSeqR(1);
 962      aCPRange=aR2;
 963   }
 964   //
 965   Standard_Real aCoeff=1.05, tV, tNV;
 966   tV=aPave.Param();
 967   if (aSide==0) { // Left
 968     if (aCPRange.Last() > aSR.First()) {
 969       tNV=aCPRange.Last();
 970       tNV=tV+aCoeff*(tNV-tV);
 971       aNewRange.SetFirst(tNV);
 972       aNewRange.SetLast (aSR.Last());
 973       //modified by NIZNHY-PKV Tue Jan 23 14:07:55 2007f
 974       //if(aNewRange.First() > aNewRange.Last()) {
 975       if(aNewRange.First() < aNewRange.Last()) {
 976       //modified by NIZNHY-PKV Tue Jan 23 14:08:02 2007t
 977         aShrunkRange.SetShrunkRange(aNewRange);
 978       }
 979     }
 980   }
 981   else { // Right
 982     if (aCPRange.First() < aSR.Last()) {
 983       tNV=aCPRange.First();
 984       tNV=tV-aCoeff*(tV-tNV);
 985       aNewRange.SetFirst(aSR.First());
 986       aNewRange.SetLast (tNV);
 987
 988       if(aNewRange.First() < aNewRange.Last()) {
 989         aShrunkRange.SetShrunkRange(aNewRange);
 990       }
 991     }
 992   }
 993 }
 994 //=======================================================================
 995 // function:  IsBlocksCoinside
 996 // purpose:
 997 //=======================================================================
 998   Standard_Boolean
 999     NMTTools_PaveFiller::IsBlocksCoinside(const BOPTools_PaveBlock& aPB1,
1000                                           const BOPTools_PaveBlock& aPB2) const
1001 {
1002   Standard_Boolean bRetFlag=Standard_True;
1003   Standard_Real aTolV11, aTolV12, aTolV21, aTolV22;
1004   Standard_Real d1121, d1122, d1222, d1221, aTolSum, aCoeff=1.05;
1005   gp_Pnt aP11, aP12, aP21, aP22;
1006
1007   const TopoDS_Vertex aV11=TopoDS::Vertex(myDS->Shape(aPB1.Pave1().Index()));//mpv
1008   const TopoDS_Vertex aV12=TopoDS::Vertex(myDS->Shape(aPB1.Pave2().Index()));//mpv
1009   const TopoDS_Vertex aV21=TopoDS::Vertex(myDS->Shape(aPB2.Pave1().Index()));//mpv
1010   const TopoDS_Vertex aV22=TopoDS::Vertex(myDS->Shape(aPB2.Pave2().Index()));//mpv
1011
1012   aTolV11=BRep_Tool::Tolerance(aV11);
1013   aTolV12=BRep_Tool::Tolerance(aV12);
1014   aTolV21=BRep_Tool::Tolerance(aV21);
1015   aTolV22=BRep_Tool::Tolerance(aV22);
1016
1017   aP11=BRep_Tool::Pnt(aV11);
1018   aP12=BRep_Tool::Pnt(aV12);
1019   aP21=BRep_Tool::Pnt(aV21);
1020   aP22=BRep_Tool::Pnt(aV22);
1021
1022   d1121=aP11.Distance(aP21);
1023   aTolSum=aCoeff*(aTolV11+aTolV21);
1024   if (d1121<aTolSum) {
1025     d1222=aP12.Distance(aP22);
1026     aTolSum=aCoeff*(aTolV12+aTolV22);
1027     if (d1222<aTolSum) {
1028       return bRetFlag;
1029     }
1030   }
1031   //
1032   d1122=aP11.Distance(aP22);
1033   aTolSum=aCoeff*(aTolV11+aTolV22);
1034   if (d1122<aTolSum) {
1035     d1221=aP12.Distance(aP21);
1036     aTolSum=aCoeff*(aTolV12+aTolV21);
1037     if (d1221<aTolSum) {
1038       return bRetFlag;
1039     }
1040   }
1041   return !bRetFlag;
1042 }
1043 //=======================================================================
1044 // function: ReplaceCommonBlocks
1045 // purpose:
1046 //=======================================================================
1047   void NMTTools_PaveFiller::ReplaceCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
1048 {
1049   RemoveCommonBlocks(aLCB);
1050   SplitCommonBlocks(aLCB);
1051 }
1052 //=======================================================================
1053 // function: SplitCommonBlocks
1054 // purpose:
1055 //=======================================================================
1056   void NMTTools_PaveFiller::SplitCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
1057 {
1058   Standard_Integer nE;
1059   NMTTools_ListOfCommonBlock aLCBx;
1060   NMTTools_ListIteratorOfListOfCommonBlock anIt, anItCBx;
1061   BOPTools_ListIteratorOfListOfPaveBlock anItLPE;
1062   //
1063   anIt.Initialize(aLCB);
1064   for (; anIt.More(); anIt.Next()) {
1065     const NMTTools_CommonBlock& aCB=anIt.Value();
1066     //
1067     //XXX
1068     aLCBx.Clear();
1069     //XXX
1070     SplitCommonBlock(aCB, aLCBx);
1071     //
1072     anItCBx.Initialize(aLCBx);
1073     for (; anItCBx.More(); anItCBx.Next()) {
1074       const NMTTools_CommonBlock& aCBx=anItCBx.Value();
1075       const BOPTools_ListOfPaveBlock& aLPBx=aCBx.PaveBlocks();
1076       //
1077       anItLPE.Initialize(aLPBx);
1078       for (; anItLPE.More(); anItLPE.Next()) {
1079         const BOPTools_PaveBlock& aPBx=anItLPE.Value();
1080         nE=aPBx.OriginalEdge();
1081         NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
1082         aLCBE.Append(aCBx);
1083       }
1084     }
1085   }
1086   // Modified to provide the order of edges
1087   // in common block where the edge with max
1088   // tolerance value will be the first
1089   //  Thu Sep 14 14:35:18 2006
1090   // Contribution of Samtech www.samcef.com BEGIN
1091   Standard_Integer i, iMax, aNb, aNbCB, nSp;
1092   Standard_Real aTolSp, aTolMax;
1093   BOPTools_ListOfPaveBlock *pLPBE;
1094   //
1095   aNb=myDS->NumberOfShapesOfTheObject();
1096   for (nE=1; nE<=aNb; ++nE) {
1097     const TopoDS_Shape& aE=myDS->Shape(nE);
1098     if (aE.ShapeType()!=TopAbs_EDGE) {
1099       continue;
1100     }
1101     //
1102     NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
1103     aNbCB=aLCBE.Extent();
1104     if (!aNbCB) {
1105       continue;
1106     }
1107     //
1108     anIt.Initialize(aLCBE);
1109     for (; anIt.More(); anIt.Next()) {
1110       NMTTools_CommonBlock& aCBE=anIt.Value();
1111       const BOPTools_ListOfPaveBlock& aLPBE=aCBE.PaveBlocks();
1112       //
1113       aTolMax=-1.;
1114       anItLPE.Initialize(aLPBE);
1115       for (i=0; anItLPE.More(); anItLPE.Next(), ++i) {
1116         const BOPTools_PaveBlock& aPB=anItLPE.Value();
1117         nSp=aPB.OriginalEdge();
1118         const TopoDS_Edge& aSp=TopoDS::Edge(myDS->Shape(nSp));
1119         aTolSp=BRep_Tool::Tolerance(aSp);
1120         if (aTolSp>aTolMax) {
1121           iMax=i;
1122           aTolSp=aTolMax;
1123         }
1124       }
1125       //
1126       BOPTools_ListOfPaveBlock aLPBx;
1127       //
1128       anItLPE.Initialize(aLPBE);
1129       for (i=0; anItLPE.More(); anItLPE.Next(), ++i) {
1130         const BOPTools_PaveBlock& aPB=anItLPE.Value();
1131         if (i==iMax) {
1132           aLPBx.Prepend(aPB);
1133         }
1134         else {
1135           aLPBx.Append(aPB);
1136         }
1137       }
1138       //
1139       pLPBE=(BOPTools_ListOfPaveBlock *)&aLPBE;
1140       pLPBE->Clear();
1141       pLPBE->Append(aLPBx);
1142     }//for (; anIt.More(); anIt.Next()) {
1143   }//for (nE=1; nE<=aNb; ++nE) {
1144   // Contribution of Samtech www.samcef.com END
1145 }
1146 //=======================================================================
1147 // function: RemoveCommonBlocks
1148 // purpose:
1149 //=======================================================================
1150   void NMTTools_PaveFiller::RemoveCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
1151 {
1152   Standard_Integer nE;
1153   NMTTools_ListOfCommonBlock aLCBx;
1154   NMTTools_ListIteratorOfListOfCommonBlock anItCB, anItCBE;
1155   BOPTools_ListIteratorOfListOfPaveBlock anItLPB;
1156   //
1157   anItCB.Initialize(aLCB);
1158   for (; anItCB.More(); anItCB.Next()) {
1159     const NMTTools_CommonBlock& aCB=anItCB.Value();
1160     const BOPTools_ListOfPaveBlock& aLPB=aCB.PaveBlocks();
1161     //
1162     // Remove aCB from each edge
1163     anItLPB.Initialize(aLPB);
1164     for (; anItLPB.More(); anItLPB.Next()) {
1165       const BOPTools_PaveBlock& aPB=anItLPB.Value();
1166       nE=aPB.OriginalEdge();
1167       //
1168       NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
1169       anItCBE.Initialize(aLCBE);
1170       for (; anItCBE.More(); anItCBE.Next()) {
1171         const NMTTools_CommonBlock& aCBE=anItCBE.Value();
1172         if (aCBE.IsEqual(aCB)) {
1173           aLCBE.Remove(anItCBE);
1174           break;
1175         }
1176       }
1177     }
1178   }
1179 }
1180 //=======================================================================
1181 // function: SplitCommonBlock
1182 // purpose:
1183 //=======================================================================
1184   void NMTTools_PaveFiller::SplitCommonBlock(const NMTTools_CommonBlock& aCB,
1185                                              NMTTools_ListOfCommonBlock& aLCBx)
1186 {
1187   Standard_Integer i, j, k, nE, aNbE, aNbSPBx, aNbPB;
1188   BOPTools_SequenceOfPaveBlock aSPBx;
1189   BOPTools_ListIteratorOfListOfPaveBlock anItLPB;
1190   BOPTools_ListIteratorOfListOfPave anIt;
1191
1192   BOPTools_PaveBlockIterator anPBIt;
1193   //
1194   const BOPTools_ListOfPaveBlock& aLPB=aCB.PaveBlocks();
1195   aNbE=aLPB.Extent();
1196   //
1197   // 1. Whether we realy need to split the common block ?
1198   anItLPB.Initialize(aLPB);
1199   for (; anItLPB.More(); anItLPB.Next()) {
1200     const BOPTools_PaveBlock& aPB=anItLPB.Value();
1201     nE=aPB.OriginalEdge();
1202     BOPTools_PaveSet& aPSE=myPavePoolNew(myDS->RefEdge(nE));
1203     aPSE.SortSet();
1204     //
1205     BOPTools_PaveSet aPSx;
1206     //
1207     const BOPTools_ListOfPave& aLPE=aPSE.Set();
1208     anIt.Initialize(aLPE);
1209     for (; anIt.More(); anIt.Next()) {
1210       const BOPTools_Pave& aPx=anIt.Value();
1211       if (aPB.IsInBlock(aPx)) {
1212         aPSx.Append(aPx);
1213       }
1214     }
1215     aNbPB=aPSx.Set().Extent();
1216     break;
1217   }
1218   //
1219   if (!aNbPB) {
1220     // we need not split it
1221     aLCBx.Append(aCB);
1222     return;
1223   }
1224   //
1225   // 2. Get sequence of pave Blocks containing all new pave blocks
1226   // for each edges's source pave Block
1227   anItLPB.Initialize(aLPB);
1228   for (; anItLPB.More(); anItLPB.Next()) {
1229     const BOPTools_PaveBlock& aPB=anItLPB.Value();
1230     const BOPTools_Pave& aPave1=aPB.Pave1();
1231     const BOPTools_Pave& aPave2=aPB.Pave2();
1232     nE=aPB.OriginalEdge();
1233     //
1234     BOPTools_PaveSet aPSx;
1235     //
1236     // the set aPsx will contain bounadry paves aPave1, aPave2 and
1237     // all paves of the edge nE that are inside block aPB
1238     aPSx.Append(aPave1);
1239     aPSx.Append(aPave2);
1240     //
1241     BOPTools_PaveSet& aPSE=myPavePoolNew(myDS->RefEdge(nE));
1242     aPSE.SortSet();
1243     //
1244     const BOPTools_ListOfPave& aLPE=aPSE.Set();
1245     anIt.Initialize(aLPE);
1246     for (; anIt.More(); anIt.Next()) {
1247       const BOPTools_Pave& aPx=anIt.Value();
1248       if (aPB.IsInBlock(aPx)) {
1249         aPSx.Append(aPx);
1250       }
1251     }
1252     //
1253     // Form pave blocks from aPSx and collect them in aSPBx
1254     anPBIt.Initialize(nE, aPSx);
1255     for (; anPBIt.More(); anPBIt.Next()) {
1256       const BOPTools_PaveBlock& aPBx=anPBIt.Value();
1257       aSPBx.Append(aPBx);
1258     }
1259   }
1260   //
1261   // 3. Do new common blocks
1262   //
1263   const TColStd_ListOfInteger& aLF=aCB.Faces();
1264   aNbSPBx=aSPBx.Length();
1265   aNbPB=aNbSPBx/aNbE;
1266   //
1267   for (i=1; i<=aNbPB; ++i) {
1268     NMTTools_CommonBlock aCBx;
1269     //
1270     aCBx.AddFaces(aLF);
1271     //
1272     for (j=1; j<=aNbE; ++j) {
1273       k=i+(j-1)*aNbPB;
1274       const BOPTools_PaveBlock& aPB=aSPBx(k);
1275       aCBx.AddPaveBlock(aPB);
1276     }
1277     aLCBx.Append(aCBx);
1278   }
1279 }
1280
1281 //=======================================================================
1282 // function: VertexParameters
1283 // purpose:
1284 //=======================================================================
1285 void VertexParameters(const IntTools_CommonPrt& aCPart,
1286                       Standard_Real& aT1,
1287                       Standard_Real& aT2)
1288 {
1289   const IntTools_Range& aR1=aCPart.Range1();
1290   aT1=0.5*(aR1.First()+aR1.Last());
1291   //
1292   if((aCPart.VertexParameter1() >= aR1.First()) &&
1293      (aCPart.VertexParameter1() <= aR1.Last())) {
1294     aT1 = aCPart.VertexParameter1();
1295   }
1296   //
1297   const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
1298   const IntTools_Range& aR2=aRanges2(1);
1299   aT2=0.5*(aR2.First()+aR2.Last());
1300   //
1301   if((aCPart.VertexParameter2() >= aR2.First()) &&
1302      (aCPart.VertexParameter2() <= aR2.Last())) {
1303     aT2 = aCPart.VertexParameter2();
1304   }
1305 }
1306 //=======================================================================
1307 // function: KeepPave
1308 // purpose:
1309 //=======================================================================
1310 Standard_Boolean IsOnPave(const Standard_Real& aT1,
1311                           const IntTools_Range& aRange,
1312                           const Standard_Real& aTolerance)
1313 {
1314   Standard_Boolean firstisonpave1, firstisonpave2, bIsOnPave;
1315   //
1316   firstisonpave1  = (Abs(aRange.First() - aT1) < aTolerance);
1317   firstisonpave2  = (Abs(aRange.Last()  - aT1) < aTolerance);
1318   bIsOnPave=(firstisonpave1 || firstisonpave2);
1319   return bIsOnPave;
1320 }
1321
1322 //=======================================================================
1323 // function:FindChains
1324 // purpose:
1325 //=======================================================================
1326 void FindChains(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
1327                 NMTTools_ListOfCommonBlock& aLCB)
1328 {
1329   Standard_Integer  i, j, aNbCB, aNbPB;
1330   BOPTools_IMapOfPaveBlock aProcessedBlocks, aChain;
1331   //
1332   aNbCB=aMapCB.Extent();
1333   for (i=1; i<=aNbCB; ++i) {
1334     const BOPTools_PaveBlock& aPB=aMapCB.FindKey(i);
1335     if (aProcessedBlocks.Contains(aPB)) {
1336       continue;
1337     }
1338     //
1339     aProcessedBlocks.Add(aPB);
1340     aChain.Add(aPB);
1341     //
1342     const BOPTools_IMapOfPaveBlock& aMapPB=aMapCB(i);
1343     aNbPB=aMapPB.Extent();
1344     for (j=1; j<=aNbPB; ++j) {
1345       const BOPTools_PaveBlock& aPBx=aMapPB(j);
1346       ProcessBlock(aPBx, aMapCB, aProcessedBlocks, aChain);
1347     }
1348     //
1349     NMTTools_CommonBlock aCB;
1350     //
1351     aNbPB=aChain.Extent();
1352     for (j=1; j<=aNbPB; ++j) {
1353       const BOPTools_PaveBlock& aPBx=aChain(j);
1354       aCB.AddPaveBlock(aPBx);
1355     }
1356     aLCB.Append(aCB);
1357     aChain.Clear();
1358   }
1359 }
1360 //=======================================================================
1361 // function:ProcessBlock
1362 // purpose:
1363 //=======================================================================
1364 void ProcessBlock(const BOPTools_PaveBlock& aPB,
1365                   const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
1366                   BOPTools_IMapOfPaveBlock& aProcessedBlocks,
1367                   BOPTools_IMapOfPaveBlock& aChain)
1368 {
1369   Standard_Integer j, aNbPB;
1370   //
1371   if (aProcessedBlocks.Contains(aPB)) {
1372     return;
1373   }
1374   aProcessedBlocks.Add(aPB);
1375   aChain.Add(aPB);
1376   //
1377   const BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.FindFromKey(aPB);
1378   aNbPB=aMapPB.Extent();
1379   for (j=1; j<=aNbPB; ++j) {
1380     const BOPTools_PaveBlock& aPBx=aMapPB(j);
1381     ProcessBlock(aPBx, aMapCB, aProcessedBlocks, aChain);
1382   }
1383 }
1384 // Modified  to provide VS interference between
1385 // vertex as result of EE and a Face of argument
1386 // Thu Sep 14 14:35:18 2006
1387 // Contribution of Samtech www.samcef.com BEGIN
1388 //=======================================================================
1389 // function: PerformVF1
1390 // purpose:
1391 //=======================================================================
1392   void NMTTools_PaveFiller::PerformVF1()
1393 {
1394   Standard_Integer i, aNbEE, n1, n2, nNewShape, aNbS, nF;
1395   Standard_Integer anIndexIn, aFlag;
1396   Standard_Real aU, aV;
1397   TColStd_ListOfInteger aLFI;
1398   TColStd_ListIteratorOfListOfInteger aItLFI;
1399   //
1400   BOPTools_CArray1OfVSInterference& aVSs=myIP->VSInterferences();
1401   BOPTools_CArray1OfEEInterference& aEEs=myIP->EEInterferences();
1402   //
1403   aNbS=myDS->NumberOfShapesOfTheObject();
1404   for (i=1; i<=aNbS; ++i) {
1405     const TopoDS_Shape& aF=myDS->Shape(i);
1406     if (aF.ShapeType()==TopAbs_FACE) {
1407       aLFI.Append(i);
1408     }
1409   }
1410   if (!aLFI.Extent()) {
1411     return;
1412   }
1413   //
1414   aNbEE=aEEs.Extent();
1415   for (i=1; i<=aNbEE; ++i) {
1416     BOPTools_EEInterference& aEE=aEEs(i);
1417     aEE.Indices(n1, n2);
1418     nNewShape=aEE.NewShape();
1419     if (!nNewShape) {
1420       continue;
1421     }
1422     //
1423     const TopoDS_Shape& aSnew=myDS->Shape(nNewShape);
1424     if (aSnew.ShapeType()!=TopAbs_VERTEX) {
1425       continue;
1426     }
1427     //
1428     const TopoDS_Vertex& aVnew=TopoDS::Vertex(aSnew);
1429     //
1430     Bnd_Box aBV;
1431     //
1432     BRepBndLib::Add(aVnew, aBV);
1433     //
1434     aItLFI.Initialize(aLFI);
1435     for (; aItLFI.More(); aItLFI.Next()) {
1436       nF=aItLFI.Value();
1437       //
1438       const TopoDS_Face& aF=TopoDS::Face(myDS->Shape(nF));
1439       const Bnd_Box& aBF=myDS->GetBoundingBox(nF);
1440       if (aBF.IsOut(aBV)) {
1441         continue;
1442       }
1443       //
1444       anIndexIn=0;
1445       aFlag=myContext.ComputeVS (aVnew, aF, aU, aV);
1446       if (!aFlag) {
1447         BOPTools_VSInterference anInterf (nNewShape, nF, aU, aV);
1448         //
1449         anIndexIn=aVSs.Append(anInterf);
1450         BOPTools_VSInterference& aVS=aVSs(anIndexIn);
1451         aVS.SetNewShape(nNewShape);//->
1452       }
1453     }
1454   }
1455 }
1456 // Contribution of Samtech www.samcef.com END