src/NMTTools/NMTTools_PaveFiller_4.cxx

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