src/NMTTools/NMTTools_PaveFiller_4.cxx

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