src/NMTTools/NMTTools_PaveFiller_4.cxx

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