src/NMTTools/NMTTools_PaveFiller_4.cxx

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