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