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