src/NMTTools/NMTTools_PaveFiller_4.cxx

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