src/NMTTools/NMTTools_PaveFiller_4.cxx

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