src/NMTTools/NMTTools_PaveFiller_4.cxx

   1 // Copyright (C) 2005  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   2 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   3 //
   4 // This library is free software; you can redistribute it and/or
   5 // modify it under the terms of the GNU Lesser General Public
   6 // License as published by the Free Software Foundation; either
   7 // version 2.1 of the License.
   8 //
   9 // This library is distributed in the hope that it will be useful
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 // Lesser General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Lesser General Public
  15 // License along with this library; if not, write to the Free Software
  16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  17 //
  18 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  19 //
  20 // File:        NMTTools_PaveFiller_4.cxx
  21 // Created:     Mon Dec  8 17:08:58 2003
  22 // Author:      Peter KURNEV
  23 //              <pkv@irinox>
  24
  25
  26 #include <NMTTools_PaveFiller.ixx>
  27 //
  28 #include <stdio.h>
  29 #include <Precision.hxx>
  30
  31 #include <TColStd_MapOfInteger.hxx>
  32 #include <TColStd_IndexedMapOfInteger.hxx>
  33
  34 #include <TopoDS.hxx>
  35 #include <TopoDS_Edge.hxx>
  36 #include <TopoDS_Vertex.hxx>
  37 #include <TopoDS_Compound.hxx>
  38
  39 #include <TopTools_IndexedMapOfShape.hxx>
  40
  41 #include <BRep_Tool.hxx>
  42 #include <BRep_Builder.hxx>
  43
  44 #include <Bnd_Box.hxx>
  45
  46 #include <IntTools_ShrunkRange.hxx>
  47 #include <IntTools_Range.hxx>
  48 #include <IntTools_CommonPrt.hxx>
  49 #include <IntTools_SequenceOfRanges.hxx>
  50 #include <IntTools_EdgeEdge.hxx>
  51 #include <IntTools_SequenceOfCommonPrts.hxx>
  52
  53 #include <BOPTools_Pave.hxx>
  54 #include <BOPTools_PaveSet.hxx>
  55 #include <BOPTools_PaveBlockIterator.hxx>
  56 #include <BOPTools_PaveBlock.hxx>
  57 #include <BOPTools_CArray1OfEEInterference.hxx>
  58 #include <BOPTools_EEInterference.hxx>
  59 #include <BOPTools_ListOfPaveBlock.hxx>
  60 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
  61 #include <BOPTools_CArray1OfVVInterference.hxx>
  62 #include <BOPTools_VVInterference.hxx>
  63 #include <BOPTools_CArray1OfEEInterference.hxx>
  64 #include <BOPTools_Tools.hxx>
  65 #include <BOPTools_IDMapOfPaveBlockIMapOfPaveBlock.hxx>
  66 #include <BOPTools_IMapOfPaveBlock.hxx>
  67 #include <BOPTools_ListIteratorOfListOfPave.hxx>
  68 #include <BOPTools_SequenceOfPaveBlock.hxx>
  69
  70 #include <BOPTColStd_Dump.hxx>
  71 #include <BOPTColStd_Failure.hxx>
  72
  73 #include <BooleanOperations_AncestorsSeqAndSuccessorsSeq.hxx>
  74 #include <BooleanOperations_IndexedDataMapOfShapeInteger.hxx>
  75 #include <BooleanOperations_KindOfInterference.hxx>
  76
  77 #include <NMTDS_ShapesDataStructure.hxx>
  78
  79 #include <NMTTools_IndexedDataMapOfIndexedMapOfInteger.hxx>
  80 #include <NMTTools_ListOfCommonBlock.hxx>
  81 #include <NMTTools_CommonBlock.hxx>
  82 #include <NMTTools_ListIteratorOfListOfCommonBlock.hxx>
  83
  84 //
  85 static
  86   void VertexParameters(const IntTools_CommonPrt& aCPart,
  87                         Standard_Real& aT1,
  88                         Standard_Real& aT2);
  89 static
  90   Standard_Boolean IsOnPave(const Standard_Real& aT1,
  91                             const IntTools_Range& aRange,
  92                             const Standard_Real& aTolerance);
  93 static
  94   void ProcessBlock(const BOPTools_PaveBlock& aPB,
  95                     const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
  96                     BOPTools_IMapOfPaveBlock& aProcessedBlocks,
  97                     BOPTools_IMapOfPaveBlock& aChain);
  98 static
  99   void FindChains(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
 100                   NMTTools_ListOfCommonBlock& aLCB);
 101
 102 //=======================================================================
 103 // function: PerformEE
 104 // purpose:
 105 //=======================================================================
 106   void NMTTools_PaveFiller::PerformEE()
 107 {
 108   myIsDone=Standard_False;
 109   //
 110   Standard_Boolean bJustAdd;
 111   Standard_Integer n1, n2, anIndexIn, nE1, nE2, aNbVEs, aBlockLength;
 112   Standard_Integer aTmp, aWhat, aWith, i, aNbCPrts, aDiscretize=30;
 113   Standard_Real aTolE1, aTolE2, aDeflection=0.01;
 114   BOPTools_ListIteratorOfListOfPaveBlock anIt1, anIt2;
 115   TopoDS_Edge aEWhat, aEWith;
 116   TopoDS_Vertex aNewVertex;
 117   BooleanOperations_IndexedDataMapOfShapeInteger aMapVI;
 118   BOPTools_IDMapOfPaveBlockIMapOfPaveBlock aMapCB;
 119   //
 120   BOPTools_CArray1OfEEInterference& aEEs=myIntrPool->EEInterferences();
 121   //
 122   // BlockLength correction
 123   aNbVEs=ExpectedPoolLength();
 124   aBlockLength=aEEs.BlockLength();
 125   if (aNbVEs > aBlockLength) {
 126     aEEs.SetBlockLength(aNbVEs);
 127   }
 128   //
 129   myDSIt.Initialize(TopAbs_EDGE, TopAbs_EDGE);
 130   //
 131   for (; myDSIt.More(); myDSIt.Next()) {
 132     myDSIt.Current(n1, n2, bJustAdd);
 133     anIndexIn = 0;
 134     //
 135     if (myIntrPool->IsComputed(n1, n2)) {
 136       continue;
 137     }
 138     //
 139     nE1=n1;
 140     nE2=n2;
 141     SortTypes(nE1, nE2);
 142     //
 143     if(bJustAdd) {
 144       myIntrPool->AddInterference (nE1, nE2, BooleanOperations_EdgeEdge, anIndexIn);
 145       continue;
 146     }
 147     //
 148     const TopoDS_Edge& aE1=TopoDS::Edge(myDS->Shape(nE1));
 149     const TopoDS_Edge& aE2=TopoDS::Edge(myDS->Shape(nE2));
 150     //
 151     if (BRep_Tool::Degenerated(aE1) || BRep_Tool::Degenerated(aE2)){
 152       continue;
 153     }
 154     //
 155     aTolE1=BRep_Tool::Tolerance(aE1);
 156     aTolE2=BRep_Tool::Tolerance(aE2);
 157     //
 158     BOPTools_ListOfPaveBlock& aLPB1=mySplitShapesPool(myDS->RefEdge(nE1));
 159     //
 160     for (anIt1.Initialize(aLPB1); anIt1.More(); anIt1.Next()) {
 161       BOPTools_PaveBlock& aPB1=anIt1.Value();
 162       const IntTools_ShrunkRange& aShrunkRange1=aPB1.ShrunkRange();
 163       //
 164       const IntTools_Range& aSR1=aShrunkRange1.ShrunkRange();
 165       const Bnd_Box&        aBB1=aShrunkRange1.BndBox();
 166       //
 167       BOPTools_ListOfPaveBlock& aLPB2=mySplitShapesPool(myDS->RefEdge(nE2));
 168       //
 169       for (anIt2.Initialize(aLPB2); anIt2.More(); anIt2.Next()) {
 170         BOPTools_PaveBlock& aPB2=anIt2.Value();
 171         const IntTools_ShrunkRange& aShrunkRange2=aPB2.ShrunkRange();
 172
 173         const IntTools_Range& aSR2=aShrunkRange2.ShrunkRange();
 174         const Bnd_Box&        aBB2=aShrunkRange2.BndBox();
 175         //
 176         if (aBB1.IsOut (aBB2)) {
 177           continue;
 178         }
 179         //
 180         // EE
 181         IntTools_EdgeEdge aEE;
 182         aEE.SetEdge1 (aE1);
 183         aEE.SetEdge2 (aE2);
 184         aEE.SetTolerance1 (aTolE1);
 185         aEE.SetTolerance2 (aTolE2);
 186         aEE.SetDiscretize (aDiscretize);
 187         aEE.SetDeflection (aDeflection);
 188         //
 189         IntTools_Range anewSR1 = aSR1;
 190         IntTools_Range anewSR2 = aSR2;
 191         //
 192         BOPTools_Tools::CorrectRange (aE1, aE2, aSR1, anewSR1);
 193         BOPTools_Tools::CorrectRange (aE2, aE1, aSR2, anewSR2);
 194         //
 195         aEE.SetRange1(anewSR1);
 196         aEE.SetRange2(anewSR2);
 197
 198         aEE.Perform();
 199         //
 200         anIndexIn=0;
 201         //
 202         if (aEE.IsDone()) {
 203           // reverse order if it is necessary
 204           aEWhat=aE1;
 205           aEWith=aE2;
 206           aWhat=nE1;
 207           aWith=nE2;
 208           if (aEE.Order()) {
 209             aTmp=aWhat;
 210             aWhat=aWith;
 211             aWith=aTmp;
 212             aEWhat=aE2;
 213             aEWith=aE1;
 214           }
 215           //
 216           const IntTools_SequenceOfCommonPrts& aCPrts=aEE.CommonParts();
 217           aNbCPrts=aCPrts.Length();
 218           for (i=1; i<=aNbCPrts; i++) {
 219             const IntTools_CommonPrt& aCPart=aCPrts(i);
 220             const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
 221             //
 222             anIndexIn=0;
 223             //
 224             TopAbs_ShapeEnum aType=aCPart.Type();
 225             switch (aType) {
 226               case TopAbs_VERTEX:  {
 227                 Standard_Real aT1, aT2, aTol=Precision::PConfusion();
 228                 Standard_Boolean bIsOnPave1, bIsOnPave2;
 229                 IntTools_Range aR1, aR2;
 230                 //
 231                 VertexParameters(aCPart, aT1, aT2);
 232                 //
 233                 //decide to keep the pave or not
 234                 aR1 = (aEE.Order()) ? anewSR2 : anewSR1;
 235                 aR2 = (aEE.Order()) ? anewSR1 : anewSR2;
 236                 //
 237                 bIsOnPave1=IsOnPave(aT1, aR1, aTol);
 238                 bIsOnPave2=IsOnPave(aT2, aR2, aTol);
 239                 //
 240                 if(bIsOnPave1 || bIsOnPave2) {
 241                   myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
 242                   continue;
 243                 }
 244                 //
 245                 BOPTools_Tools::MakeNewVertex(aEWhat, aT1, aEWith, aT2, aNewVertex);
 246                 //
 247                 // Add Interference to the Pool
 248                 BOPTools_EEInterference anInterf (aWhat, aWith, aCPart);
 249                 //
 250                 anIndexIn=aEEs.Append(anInterf);
 251                 myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
 252                 //
 253                 // Collect
 254                 aMapVI.Add(aNewVertex, anIndexIn);
 255               }
 256                 break;
 257
 258               case TopAbs_EDGE: {
 259                 Standard_Integer aNbComPrt2;
 260                 Standard_Boolean aCoinsideFlag;
 261                 //
 262                 aNbComPrt2=aRanges2.Length();
 263                 aCoinsideFlag=IsBlocksCoinside(aPB1, aPB2);
 264                 //
 265                 if (aNbComPrt2>1 || !aCoinsideFlag) {
 266                   myIntrPool->AddInterference (aWhat, aWith, BooleanOperations_EdgeEdge, anIndexIn);
 267                   break;
 268                 }
 269                 //
 270                 // Fill aMapCB
 271                 if (aMapCB.Contains(aPB1)) {
 272                   BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.ChangeFromKey(aPB1);
 273                   aMapPB.Add(aPB1);
 274                   aMapPB.Add(aPB2);
 275                 }
 276                 else {
 277                   BOPTools_IMapOfPaveBlock aMapPB;
 278                   aMapPB.Add(aPB1);
 279                   aMapPB.Add(aPB2);
 280                   aMapCB.Add(aPB1, aMapPB);
 281                 }
 282                 //
 283                 if (aMapCB.Contains(aPB2)) {
 284                   BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.ChangeFromKey(aPB2);
 285                   aMapPB.Add(aPB1);
 286                   aMapPB.Add(aPB2);
 287                 }
 288                 else {
 289                   BOPTools_IMapOfPaveBlock aMapPB;
 290                   aMapPB.Add(aPB1);
 291                   aMapPB.Add(aPB2);
 292                   aMapCB.Add(aPB2, aMapPB);
 293                 }
 294               }
 295                 break;
 296             default:
 297               break;
 298             } // switch (aType)
 299           } // for (i=1; i<=aNbCPrts; i++)
 300         }// if (aEE.IsDone())
 301       } // for (; anIt2.More(); anIt2.Next())
 302     } // for (; anIt1.More(); anIt1.Next())
 303   }// for (; myDSIt.More(); myDSIt.Next())
 304   //
 305   EENewVertices (aMapVI);
 306   EECommonBlocks(aMapCB);
 307   //
 308   myIsDone=Standard_True;
 309 }
 310 //=======================================================================
 311 // function:EECommonBlocks
 312 // purpose:
 313 //=======================================================================
 314   void NMTTools_PaveFiller::EECommonBlocks(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB)
 315 {
 316   NMTTools_ListOfCommonBlock aLCB;
 317   //
 318   FindChains(aMapCB, aLCB);
 319   ReplaceCommonBlocks(aLCB);
 320 }
 321 //=======================================================================
 322 // function:EENewVertices
 323 // purpose:
 324 //=======================================================================
 325   void NMTTools_PaveFiller::EENewVertices (const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI)
 326 {
 327   Standard_Integer aNb, i, j, aNewShape, aNbEdges, aNbIEE, aNbVV, aNbSimple;
 328   Standard_Integer aWhat, aWith, i1, i2, nE1, nE2, nE, nV, aFlag;
 329   Standard_Real aT;
 330   TopoDS_Compound aCompound;
 331   BRep_Builder aBB;
 332   NMTTools_IndexedDataMapOfIndexedMapOfInteger aMNVE, aMNVIEE;
 333   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
 334   BOPTools_Pave aPave;
 335   TopoDS_Vertex aNewVertex;
 336   TopTools_IndexedMapOfShape aMNVComplex, aMNVSimple;
 337   //
 338   BOPTools_CArray1OfEEInterference& aEEs=myIntrPool->EEInterferences();
 339   //
 340   aNb=aMapVI.Extent();
 341   //
 342   if (!aNb) { // no new vertices, no new problems
 343     return;
 344   }
 345   //
 346   // 0.
 347   if (aNb==1) {
 348     aNewVertex=TopoDS::Vertex(aMapVI.FindKey(1));
 349     EENewVertices(aNewVertex, aMapVI);
 350     return;
 351   }
 352   //
 353   // 1. Make compound from new vertices
 354   aBB.MakeCompound(aCompound);
 355   for (i=1; i<=aNb; ++i) {
 356     const TopoDS_Shape& aV=aMapVI.FindKey(i);
 357     aBB.Add(aCompound, aV);
 358   }
 359   //
 360   // 2. VV intersection between these vertices
 361   //       using the auxiliary Filler
 362   NMTDS_ShapesDataStructure tDS;
 363   //
 364   tDS.SetCompositeShape(aCompound);
 365   tDS.Init();
 366   //
 367   BOPTools_InterferencePool tInterfPool(tDS);
 368   NMTTools_PaveFiller tPaveFiller(tInterfPool);
 369   //
 370   tPaveFiller.Init();
 371   //
 372   tPaveFiller.PerformVV();
 373   tPaveFiller.PerformNewVertices();
 374   //
 375   const BOPTools_CArray1OfVVInterference& aVVInterfs=tInterfPool.VVInterfs();
 376   //
 377   // 3. Separate Comlex and Simple new vertices
 378   aNbVV=aVVInterfs.Extent();
 379   for (i=1; i<=aNbVV; ++i) {
 380     const BOPTools_VVInterference& aVV=aVVInterfs(i);
 381     aVV.Indices(aWhat, aWith);
 382     const TopoDS_Shape& aV1=tDS.Shape(aWhat);
 383     const TopoDS_Shape& aV2=tDS.Shape(aWith);
 384     aMNVComplex.Add(aV1);
 385     aMNVComplex.Add(aV2);
 386   }
 387   //
 388   for (i=1; i<=aNb; ++i) {
 389     const TopoDS_Shape& aV=aMapVI.FindKey(i);
 390     if (!aMNVComplex.Contains(aV)) {
 391       aMNVSimple.Add(aV);
 392     }
 393   }
 394   //
 395   // 4. Treat Simple new Vertices
 396   aNbSimple=aMNVSimple.Extent();
 397   for (i=1; i<=aNbSimple; ++i) {
 398     const TopoDS_Vertex& aV=TopoDS::Vertex(aMNVSimple(i));
 399     EENewVertices(aV, aMapVI);
 400   }
 401   //
 402   // 3. Fill Maps : NewVertex-edges (aMNVE)
 403   //                NewVertex-interferences (aMNVIEE)
 404   for (i=1; i<=aNbVV; ++i) {
 405     const BOPTools_VVInterference& aVV=aVVInterfs(i);
 406     aNewShape=aVV.NewShape();
 407     if (!aNewShape) {
 408       continue;
 409     }
 410     //
 411     if (!aMNVE.Contains(aNewShape)) {
 412       TColStd_IndexedMapOfInteger aMx;
 413       aMNVE.Add(aNewShape, aMx);
 414     }
 415     if (!aMNVIEE.Contains(aNewShape)) {
 416       TColStd_IndexedMapOfInteger aMx;
 417       aMNVIEE.Add(aNewShape, aMx);
 418     }
 419     //
 420     TColStd_IndexedMapOfInteger& aME=aMNVE.ChangeFromKey(aNewShape);
 421     TColStd_IndexedMapOfInteger& aMIEE=aMNVIEE.ChangeFromKey(aNewShape);
 422     //
 423     aVV.Indices(aWhat, aWith);
 424     //aWhat
 425     const TopoDS_Shape& aV1=tDS.Shape(aWhat);
 426     i1=aMapVI.FindFromKey(aV1);
 427     const BOPTools_EEInterference& aEE1=aEEs(i1);
 428     aEE1.Indices(nE1, nE2);
 429     aME.Add(nE1);
 430     aME.Add(nE2);
 431     aMIEE.Add(i1);
 432     //aWith
 433     const TopoDS_Shape& aV2=tDS.Shape(aWith);
 434     i2=aMapVI.FindFromKey(aV2);
 435     const BOPTools_EEInterference& aEE2=aEEs(i2);
 436     aEE2.Indices(nE1, nE2);
 437     aME.Add(nE1);
 438     aME.Add(nE2);
 439     aMIEE.Add(i2);
 440     //
 441     //printf(" VV: (%d, %d) -> %d\n", aWhat, aWith, aNewShape);
 442   }
 443   //
 444   // 4. Process new vertices
 445   aNb=aMNVE.Extent();
 446   for (i=1; i<=aNb; ++i) { // xx
 447     //
 448     //  new Vertex
 449     nV=aMNVE.FindKey(i);
 450     aNewVertex=TopoDS::Vertex(tDS.Shape(nV));
 451     //
 452     // Insert New Vertex in DS;
 453     myDS->InsertShapeAndAncestorsSuccessors(aNewVertex, anASSeq);
 454     aNewShape=myDS->NumberOfInsertedShapes();
 455     myDS->SetState (aNewShape, BooleanOperations_ON);
 456     //
 457     // Update index of NewShape in EE interferences
 458     const TColStd_IndexedMapOfInteger& aMIEE=aMNVIEE.FindFromKey(nV);//(i);
 459     aNbIEE=aMIEE.Extent();
 460     for (j=1; j<=aNbIEE; ++j) {
 461       i1=aMIEE(j);
 462       BOPTools_EEInterference& aEE1=aEEs(i1);
 463       aEE1.SetNewShape(aNewShape);
 464     }
 465     //
 466     // Update Paves on edges
 467     const TColStd_IndexedMapOfInteger& aME=aMNVE(i);
 468     aNbEdges=aME.Extent();
 469     for (j=1; j<=aNbEdges; ++j) {
 470       nE=aME(j);
 471       const TopoDS_Edge& aE=TopoDS::Edge(myDS->Shape(nE));
 472       //
 473       aFlag=myContext.ComputeVE (aNewVertex, aE, aT);
 474       //
 475       if (!aFlag) {
 476         aPave.SetInterference(-1);
 477         aPave.SetType (BooleanOperations_EdgeEdge);
 478         aPave.SetIndex(aNewShape);
 479         aPave.SetParam(aT);
 480         //
 481         BOPTools_PaveSet& aPaveSet=myPavePoolNew(myDS->RefEdge(nE));
 482         aPaveSet.Append(aPave);
 483       }
 484     }
 485   }// for (i=1; i<=aNb; ++i) {// xx
 486 }
 487 //=======================================================================
 488 // function:EENewVertices
 489 // purpose:
 490 //=======================================================================
 491   void NMTTools_PaveFiller::EENewVertices (const TopoDS_Vertex& aNewVertex,
 492                                            const BooleanOperations_IndexedDataMapOfShapeInteger& aMapVI)
 493 {
 494   Standard_Integer  i, aNewShape, nE1, nE2;
 495   Standard_Real  aT1, aT2;
 496   BooleanOperations_AncestorsSeqAndSuccessorsSeq anASSeq;
 497   BOPTools_Pave aPave;
 498   //
 499   BOPTools_CArray1OfEEInterference& aEEs=myIntrPool->EEInterferences();
 500   //
 501   // one new vertex case is treated in usual way
 502   //
 503   // Insert New Vertex in DS;
 504   myDS->InsertShapeAndAncestorsSuccessors(aNewVertex, anASSeq);
 505   aNewShape=myDS->NumberOfInsertedShapes();
 506   myDS->SetState (aNewShape, BooleanOperations_ON);
 507   // Insert New Vertex in EE Interference
 508   i=aMapVI.FindFromKey(aNewVertex);
 509   BOPTools_EEInterference& aEEInterf= aEEs(i);
 510   aEEInterf.SetNewShape(aNewShape);
 511   // Extact interference info
 512   aEEInterf.Indices(nE1, nE2);
 513   const IntTools_CommonPrt& aCPart=aEEInterf.CommonPrt();
 514   VertexParameters(aCPart, aT1, aT2);
 515   //
 516   // Add Paves to the myPavePoolNew
 517   aPave.SetInterference(i);
 518   aPave.SetType (BooleanOperations_EdgeEdge);
 519   aPave.SetIndex(aNewShape);
 520   // Pave for edge nE1
 521   aPave.SetParam(aT1);
 522   BOPTools_PaveSet& aPaveSet1=myPavePoolNew(myDS->RefEdge(nE1));
 523   aPaveSet1.Append(aPave);
 524   // Pave for edge nE2
 525   aPave.SetParam(aT2);
 526   BOPTools_PaveSet& aPaveSet2=myPavePoolNew(myDS->RefEdge(nE2));
 527   aPaveSet2.Append(aPave);
 528 }
 529 //=======================================================================
 530 // function: RefinePavePool
 531 // purpose:
 532 //=======================================================================
 533   void NMTTools_PaveFiller::RefinePavePool()
 534 {
 535   Standard_Integer  i, aNbNew;
 536
 537   for (i=1; i<=myNbSources; i++) {
 538
 539     if ((myDS->GetShape(i)).ShapeType()==TopAbs_EDGE) {
 540       BOPTools_PaveSet& aPS= myPavePool(myDS->RefEdge(i));
 541       //
 542       BOPTools_PaveSet& aNewPS= myPavePoolNew(myDS->RefEdge(i));
 543       BOPTools_ListOfPave& aNewLP=aNewPS.ChangeSet();
 544       //
 545       aNbNew=aNewLP.Extent();
 546       if (aNbNew) {
 547         BOPTools_ListIteratorOfListOfPave anIt(aNewLP);
 548         for (; anIt.More(); anIt.Next()) {
 549           const BOPTools_Pave& aPave=anIt.Value();
 550           aPS.Append(aPave);
 551         }
 552         // Clear the ListOfPaveBlock
 553         BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(i));
 554         aLPB.Clear();
 555         // Prepare the paveBlocks for that egde again
 556         PreparePaveBlocks(i);
 557       }
 558       aNewLP.Clear();
 559     }
 560   }
 561 }
 562 //=======================================================================
 563 // function: PreparePaveBlocks
 564 // purpose:
 565 //=======================================================================
 566   void NMTTools_PaveFiller::PreparePaveBlocks(const TopAbs_ShapeEnum aType1,
 567                                               const TopAbs_ShapeEnum aType2)
 568 {
 569   myIsDone=Standard_False;
 570   //
 571   Standard_Boolean Ok1, Ok2, Ok3;
 572   Ok1= (aType1==TopAbs_VERTEX) &&  (aType2==TopAbs_EDGE) ;
 573   Ok2= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_EDGE) ;
 574   Ok3= (aType1==TopAbs_EDGE)   &&  (aType2==TopAbs_FACE) ;
 575   if (!Ok1 && !Ok2 && !Ok3) {
 576     // error: Type mismatch
 577     return;
 578   }
 579   //
 580   Standard_Boolean aFlag = Standard_False;
 581   Standard_Integer n1, n2, nE1, nE2, aNbSplits;
 582   TColStd_MapOfInteger aMap;
 583   //
 584   myDSIt.Initialize(aType1, aType2);
 585   //
 586   for (; myDSIt.More(); myDSIt.Next()) {
 587     myDSIt.Current(n1, n2, aFlag);
 588     nE1=n1;
 589     nE2=n2;
 590     SortTypes(nE1, nE2);
 591     //
 592     if (aType1==TopAbs_EDGE) {
 593       BOPTools_ListOfPaveBlock& aLPB1=mySplitShapesPool(myDS->RefEdge(nE1));
 594       aNbSplits=aLPB1.Extent();
 595       if (!aNbSplits) {
 596         if (!aMap.Contains(nE1)) {
 597           aMap.Add(nE1);
 598           PreparePaveBlocks(nE1);
 599           //
 600           if (!myIsDone) {
 601             return;
 602           }
 603         }
 604       }
 605     }
 606     //
 607     if (aType2==TopAbs_EDGE) {
 608       BOPTools_ListOfPaveBlock& aLPB2=mySplitShapesPool(myDS->RefEdge(nE2));
 609       aNbSplits=aLPB2.Extent();
 610       if (!aNbSplits) {
 611         if (!aMap.Contains(nE2)) {
 612           aMap.Add(nE2);
 613           PreparePaveBlocks(nE2);
 614           //
 615           if (!myIsDone) {
 616             return;
 617           }
 618         }
 619       }
 620     }// if (aType2==TopAbs_EDGE)
 621   }// for (; myDSIt.More(); myDSIt.Next())
 622
 623   myIsDone=Standard_True;
 624 }
 625 //=======================================================================
 626 // function: PreparePaveBlocks
 627 // purpose:
 628 //=======================================================================
 629   void NMTTools_PaveFiller::PreparePaveBlocks(const Standard_Integer nE)
 630 {
 631   myIsDone=Standard_False;
 632
 633   Standard_Integer nV1, nV2;
 634
 635   TopoDS_Edge aE;
 636   TopoDS_Vertex aV1, aV2;
 637
 638   // SplitShapesPool
 639   BOPTools_ListOfPaveBlock& aLPB=mySplitShapesPool(myDS->RefEdge(nE));
 640   // Edge
 641   aE=TopoDS::Edge(myDS->Shape(nE));
 642   //
 643   if (!BRep_Tool::Degenerated(aE)){
 644     //
 645     BOPTools_PaveSet& aPS=myPavePool(myDS->RefEdge(nE));
 646
 647     BOPTools_PaveBlockIterator aPBIt(nE, aPS);
 648     for (; aPBIt.More(); aPBIt.Next()) {
 649       BOPTools_PaveBlock& aPB=aPBIt.Value();
 650
 651       const IntTools_Range& aRange=aPB.Range();
 652
 653       const BOPTools_Pave& aPave1=aPB.Pave1();
 654       nV1=aPave1.Index();
 655       aV1=TopoDS::Vertex(myDS->GetShape(nV1));
 656
 657       const BOPTools_Pave& aPave2=aPB.Pave2();
 658       nV2=aPave2.Index();
 659       aV2=TopoDS::Vertex(myDS->GetShape(nV2));
 660       //
 661       // ShrunkRange
 662       IntTools_ShrunkRange aSR (aE, aV1, aV2, aRange, myContext);
 663       //
 664       Standard_Integer anErrorStatus;
 665       anErrorStatus=aSR.ErrorStatus();
 666
 667       char buf[512];
 668       if (!aSR.IsDone()) {
 669         sprintf (buf, "Can not obtain ShrunkRange for Edge %d\n", nE);
 670         BOPTColStd_Dump::PrintMessage(buf);
 671         sprintf (buf, "Can not obtain ShrunkRange for Edge %d", nE);
 672         throw
 673           BOPTColStd_Failure(buf) ;
 674       }
 675       //
 676       if (anErrorStatus==6) {
 677         sprintf(buf,
 678                 "Warning: [PreparePaveBlocks()] Max.Dummy Shrunk Range for Edge %d\n", nE);
 679         BOPTColStd_Dump::PrintMessage(buf);
 680       }
 681       else {
 682         // Check left paves and correct ShrunkRange if it is necessary
 683         CorrectShrunkRanges (0, aPave1, aSR);
 684         CorrectShrunkRanges (1, aPave2, aSR);
 685       }
 686       //
 687       aPB.SetShrunkRange(aSR);
 688       aLPB.Append(aPB);
 689     } //for (; aPBIt1.More(); aPBIt1.Next())
 690   }
 691   myIsDone=Standard_True;
 692 }
 693 //=======================================================================
 694 // function: CorrectShrunkRanges
 695 // purpose:
 696 //=======================================================================
 697   void NMTTools_PaveFiller::CorrectShrunkRanges(const Standard_Integer aSide,
 698                                                 const BOPTools_Pave& aPave,
 699                                                 IntTools_ShrunkRange& aShrunkRange)
 700 {
 701   BooleanOperations_KindOfInterference aType;
 702   Standard_Integer anIndexInterf ;
 703   //
 704   aType=aPave.Type();
 705   if (aType!=BooleanOperations_EdgeEdge) {
 706     return;
 707   }
 708   //
 709   anIndexInterf=aPave.Interference();
 710   if (anIndexInterf<0) {
 711     // it can be EE interf between E and (e1,e2,..en) -> vertex
 712     // so we can't decide which aEE.CommonPrt() we should take.
 713     return;
 714   }
 715
 716   BOPTools_CArray1OfEEInterference& aEEs=myIntrPool->EEInterferences();
 717   const BOPTools_EEInterference& aEE=aEEs(anIndexInterf);
 718   const IntTools_CommonPrt& aCP=aEE.CommonPrt();
 719   const TopoDS_Edge& aE1=aCP.Edge1();
 720   const TopoDS_Edge& aE2=aCP.Edge2();
 721
 722   const IntTools_Range& aSR=aShrunkRange.ShrunkRange();
 723   const TopoDS_Edge& aE=aShrunkRange.Edge();
 724
 725   IntTools_Range aNewRange;
 726   IntTools_Range aCPRange;
 727
 728   if (aE1.IsSame(aE)) {
 729     const IntTools_Range& aR1=aCP.Range1();
 730     aCPRange=aR1;
 731   }
 732   if (aE2.IsSame(aE)) {
 733     const IntTools_SequenceOfRanges& aSeqR=aCP.Ranges2();
 734     const IntTools_Range& aR2=aSeqR(1);
 735      aCPRange=aR2;
 736   }
 737   //
 738   Standard_Real aCoeff=1.05, tV, tNV;
 739   tV=aPave.Param();
 740   if (aSide==0) { // Left
 741     if (aCPRange.Last() > aSR.First()) {
 742       tNV=aCPRange.Last();
 743       tNV=tV+aCoeff*(tNV-tV);
 744       aNewRange.SetFirst(tNV);
 745       aNewRange.SetLast (aSR.Last());
 746
 747       if(aNewRange.First() > aNewRange.Last()) {
 748         aShrunkRange.SetShrunkRange(aNewRange);
 749       }
 750     }
 751   }
 752   else { // Right
 753     if (aCPRange.First() < aSR.Last()) {
 754       tNV=aCPRange.First();
 755       tNV=tV-aCoeff*(tV-tNV);
 756       aNewRange.SetFirst(aSR.First());
 757       aNewRange.SetLast (tNV);
 758
 759       if(aNewRange.First() < aNewRange.Last()) {
 760         aShrunkRange.SetShrunkRange(aNewRange);
 761       }
 762     }
 763   }
 764 }
 765 //=======================================================================
 766 // function:  IsBlocksCoinside
 767 // purpose:
 768 //=======================================================================
 769   Standard_Boolean
 770     NMTTools_PaveFiller::IsBlocksCoinside(const BOPTools_PaveBlock& aPB1,
 771                                           const BOPTools_PaveBlock& aPB2) const
 772 {
 773   Standard_Boolean bRetFlag=Standard_True;
 774   Standard_Real aTolV11, aTolV12, aTolV21, aTolV22;
 775   Standard_Real d1121, d1122, d1222, d1221, aTolSum, aCoeff=1.05;
 776   gp_Pnt aP11, aP12, aP21, aP22;
 777
 778   const TopoDS_Vertex& aV11=TopoDS::Vertex(myDS->Shape(aPB1.Pave1().Index()));
 779   const TopoDS_Vertex& aV12=TopoDS::Vertex(myDS->Shape(aPB1.Pave2().Index()));
 780   const TopoDS_Vertex& aV21=TopoDS::Vertex(myDS->Shape(aPB2.Pave1().Index()));
 781   const TopoDS_Vertex& aV22=TopoDS::Vertex(myDS->Shape(aPB2.Pave2().Index()));
 782
 783   aTolV11=BRep_Tool::Tolerance(aV11);
 784   aTolV12=BRep_Tool::Tolerance(aV12);
 785   aTolV21=BRep_Tool::Tolerance(aV21);
 786   aTolV22=BRep_Tool::Tolerance(aV22);
 787
 788   aP11=BRep_Tool::Pnt(aV11);
 789   aP12=BRep_Tool::Pnt(aV12);
 790   aP21=BRep_Tool::Pnt(aV21);
 791   aP22=BRep_Tool::Pnt(aV22);
 792
 793   d1121=aP11.Distance(aP21);
 794   aTolSum=aCoeff*(aTolV11+aTolV21);
 795   if (d1121<aTolSum) {
 796     d1222=aP12.Distance(aP22);
 797     aTolSum=aCoeff*(aTolV12+aTolV22);
 798     if (d1222<aTolSum) {
 799       return bRetFlag;
 800     }
 801   }
 802   //
 803   d1122=aP11.Distance(aP22);
 804   aTolSum=aCoeff*(aTolV11+aTolV22);
 805   if (d1122<aTolSum) {
 806     d1221=aP12.Distance(aP21);
 807     aTolSum=aCoeff*(aTolV12+aTolV21);
 808     if (d1221<aTolSum) {
 809       return bRetFlag;
 810     }
 811   }
 812   return !bRetFlag;
 813 }
 814 //=======================================================================
 815 // function: ReplaceCommonBlocks
 816 // purpose:
 817 //=======================================================================
 818   void NMTTools_PaveFiller::ReplaceCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
 819 {
 820   RemoveCommonBlocks(aLCB);
 821   SplitCommonBlocks(aLCB);
 822 }
 823 //=======================================================================
 824 // function: SplitCommonBlocks
 825 // purpose:
 826 //=======================================================================
 827   void NMTTools_PaveFiller::SplitCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
 828 {
 829   Standard_Integer nE;
 830   NMTTools_ListOfCommonBlock aLCBx;
 831   NMTTools_ListIteratorOfListOfCommonBlock anIt, anItCBx;
 832   BOPTools_ListIteratorOfListOfPaveBlock anItLPE;
 833   //
 834   anIt.Initialize(aLCB);
 835   for (; anIt.More(); anIt.Next()) {
 836     const NMTTools_CommonBlock& aCB=anIt.Value();
 837     //
 838     //XXX
 839     aLCBx.Clear();
 840     //XXX
 841     SplitCommonBlock(aCB, aLCBx);
 842     //
 843     anItCBx.Initialize(aLCBx);
 844     for (; anItCBx.More(); anItCBx.Next()) {
 845       const NMTTools_CommonBlock& aCBx=anItCBx.Value();
 846       const BOPTools_ListOfPaveBlock& aLPBx=aCBx.PaveBlocks();
 847       //
 848       anItLPE.Initialize(aLPBx);
 849       for (; anItLPE.More(); anItLPE.Next()) {
 850         const BOPTools_PaveBlock& aPBx=anItLPE.Value();
 851         nE=aPBx.OriginalEdge();
 852         NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
 853         aLCBE.Append(aCBx);
 854       }
 855     }
 856   }
 857 }
 858 //=======================================================================
 859 // function: RemoveCommonBlocks
 860 // purpose:
 861 //=======================================================================
 862   void NMTTools_PaveFiller::RemoveCommonBlocks(const NMTTools_ListOfCommonBlock& aLCB)
 863 {
 864   Standard_Integer nE;
 865   NMTTools_ListOfCommonBlock aLCBx;
 866   NMTTools_ListIteratorOfListOfCommonBlock anItCB, anItCBE;
 867   BOPTools_ListIteratorOfListOfPaveBlock anItLPB;
 868   //
 869   anItCB.Initialize(aLCB);
 870   for (; anItCB.More(); anItCB.Next()) {
 871     const NMTTools_CommonBlock& aCB=anItCB.Value();
 872     const BOPTools_ListOfPaveBlock& aLPB=aCB.PaveBlocks();
 873     //
 874     // Remove aCB from each edge
 875     anItLPB.Initialize(aLPB);
 876     for (; anItLPB.More(); anItLPB.Next()) {
 877       const BOPTools_PaveBlock& aPB=anItLPB.Value();
 878       nE=aPB.OriginalEdge();
 879       //
 880       NMTTools_ListOfCommonBlock& aLCBE=myCommonBlockPool(myDS->RefEdge(nE));
 881       anItCBE.Initialize(aLCBE);
 882       for (; anItCBE.More(); anItCBE.Next()) {
 883         const NMTTools_CommonBlock& aCBE=anItCBE.Value();
 884         if (aCBE.IsEqual(aCB)) {
 885           aLCBE.Remove(anItCBE);
 886           break;
 887         }
 888       }
 889     }
 890   }
 891 }
 892 //=======================================================================
 893 // function: SplitCommonBlock
 894 // purpose:
 895 //=======================================================================
 896   void NMTTools_PaveFiller::SplitCommonBlock(const NMTTools_CommonBlock& aCB,
 897                                              NMTTools_ListOfCommonBlock& aLCBx)
 898 {
 899   Standard_Integer i, j, k, nE, aNbE, aNbSPBx, aNbPB;
 900   BOPTools_SequenceOfPaveBlock aSPBx;
 901   BOPTools_ListIteratorOfListOfPaveBlock anItLPB;
 902   BOPTools_ListIteratorOfListOfPave anIt;
 903
 904   BOPTools_PaveBlockIterator anPBIt;
 905   //
 906   const BOPTools_ListOfPaveBlock& aLPB=aCB.PaveBlocks();
 907   aNbE=aLPB.Extent();
 908   //
 909   // 1. Whether we realy need to split the common block ?
 910   anItLPB.Initialize(aLPB);
 911   for (; anItLPB.More(); anItLPB.Next()) {
 912     const BOPTools_PaveBlock& aPB=anItLPB.Value();
 913     nE=aPB.OriginalEdge();
 914     BOPTools_PaveSet& aPSE=myPavePoolNew(myDS->RefEdge(nE));
 915     aPSE.SortSet();
 916     //
 917     BOPTools_PaveSet aPSx;
 918     //
 919     const BOPTools_ListOfPave& aLPE=aPSE.Set();
 920     anIt.Initialize(aLPE);
 921     for (; anIt.More(); anIt.Next()) {
 922       const BOPTools_Pave& aPx=anIt.Value();
 923       if (aPB.IsInBlock(aPx)) {
 924         aPSx.Append(aPx);
 925       }
 926     }
 927     aNbPB=aPSx.Set().Extent();
 928     break;
 929   }
 930   //
 931   if (!aNbPB) {
 932     // we need not split it
 933     aLCBx.Append(aCB);
 934     return;
 935   }
 936   //
 937   // 2. Get sequence of pave Blocks containing all new pave blocks
 938   // for each edges's source pave Block
 939   anItLPB.Initialize(aLPB);
 940   for (; anItLPB.More(); anItLPB.Next()) {
 941     const BOPTools_PaveBlock& aPB=anItLPB.Value();
 942     const BOPTools_Pave& aPave1=aPB.Pave1();
 943     const BOPTools_Pave& aPave2=aPB.Pave2();
 944     nE=aPB.OriginalEdge();
 945     //
 946     BOPTools_PaveSet aPSx;
 947     //
 948     // the set aPsx will contain bounadry paves aPave1, aPave2 and
 949     // all paves of the edge nE that are inside block aPB
 950     aPSx.Append(aPave1);
 951     aPSx.Append(aPave2);
 952     //
 953     BOPTools_PaveSet& aPSE=myPavePoolNew(myDS->RefEdge(nE));
 954     aPSE.SortSet();
 955     //
 956     const BOPTools_ListOfPave& aLPE=aPSE.Set();
 957     anIt.Initialize(aLPE);
 958     for (; anIt.More(); anIt.Next()) {
 959       const BOPTools_Pave& aPx=anIt.Value();
 960       if (aPB.IsInBlock(aPx)) {
 961         aPSx.Append(aPx);
 962       }
 963     }
 964     //
 965     // Form pave blocks from aPSx and collect them in aSPBx
 966     anPBIt.Initialize(nE, aPSx);
 967     for (; anPBIt.More(); anPBIt.Next()) {
 968       const BOPTools_PaveBlock& aPBx=anPBIt.Value();
 969       aSPBx.Append(aPBx);
 970     }
 971   }
 972   //
 973   // 3. Do new common blocks
 974   //
 975   const TColStd_ListOfInteger& aLF=aCB.Faces();
 976   aNbSPBx=aSPBx.Length();
 977   aNbPB=aNbSPBx/aNbE;
 978   //
 979   for (i=1; i<=aNbPB; ++i) {
 980     NMTTools_CommonBlock aCBx;
 981     //
 982     aCBx.AddFaces(aLF);
 983     //
 984     for (j=1; j<=aNbE; ++j) {
 985       k=i+(j-1)*aNbPB;
 986       const BOPTools_PaveBlock& aPB=aSPBx(k);
 987       aCBx.AddPaveBlock(aPB);
 988     }
 989     aLCBx.Append(aCBx);
 990   }
 991 }
 992
 993 //=======================================================================
 994 // function: VertexParameters
 995 // purpose:
 996 //=======================================================================
 997 void VertexParameters(const IntTools_CommonPrt& aCPart,
 998                       Standard_Real& aT1,
 999                       Standard_Real& aT2)
1000 {
1001   const IntTools_Range& aR1=aCPart.Range1();
1002   aT1=0.5*(aR1.First()+aR1.Last());
1003   //
1004   if((aCPart.VertexParameter1() >= aR1.First()) &&
1005      (aCPart.VertexParameter1() <= aR1.Last())) {
1006     aT1 = aCPart.VertexParameter1();
1007   }
1008   //
1009   const IntTools_SequenceOfRanges& aRanges2=aCPart.Ranges2();
1010   const IntTools_Range& aR2=aRanges2(1);
1011   aT2=0.5*(aR2.First()+aR2.Last());
1012   //
1013   if((aCPart.VertexParameter2() >= aR2.First()) &&
1014      (aCPart.VertexParameter2() <= aR2.Last())) {
1015     aT2 = aCPart.VertexParameter2();
1016   }
1017 }
1018 //=======================================================================
1019 // function: KeepPave
1020 // purpose:
1021 //=======================================================================
1022 Standard_Boolean IsOnPave(const Standard_Real& aT1,
1023                           const IntTools_Range& aRange,
1024                           const Standard_Real& aTolerance)
1025 {
1026   Standard_Boolean firstisonpave1, firstisonpave2, bIsOnPave;
1027   //
1028   firstisonpave1  = (Abs(aRange.First() - aT1) < aTolerance);
1029   firstisonpave2  = (Abs(aRange.Last()  - aT1) < aTolerance);
1030   bIsOnPave=(firstisonpave1 || firstisonpave2);
1031   return bIsOnPave;
1032 }
1033
1034 //=======================================================================
1035 // function:FindChains
1036 // purpose:
1037 //=======================================================================
1038 void FindChains(const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
1039                 NMTTools_ListOfCommonBlock& aLCB)
1040 {
1041   Standard_Integer  i, j, aNbCB, aNbPB;
1042   BOPTools_IMapOfPaveBlock aProcessedBlocks, aChain;
1043   //
1044   aNbCB=aMapCB.Extent();
1045   for (i=1; i<=aNbCB; ++i) {
1046     const BOPTools_PaveBlock& aPB=aMapCB.FindKey(i);
1047     if (aProcessedBlocks.Contains(aPB)) {
1048       continue;
1049     }
1050     //
1051     aProcessedBlocks.Add(aPB);
1052     aChain.Add(aPB);
1053     //
1054     const BOPTools_IMapOfPaveBlock& aMapPB=aMapCB(i);
1055     aNbPB=aMapPB.Extent();
1056     for (j=1; j<=aNbPB; ++j) {
1057       const BOPTools_PaveBlock& aPBx=aMapPB(j);
1058       ProcessBlock(aPBx, aMapCB, aProcessedBlocks, aChain);
1059     }
1060     //
1061     NMTTools_CommonBlock aCB;
1062     //
1063     aNbPB=aChain.Extent();
1064     for (j=1; j<=aNbPB; ++j) {
1065       const BOPTools_PaveBlock& aPBx=aChain(j);
1066       aCB.AddPaveBlock(aPBx);
1067     }
1068     aLCB.Append(aCB);
1069     aChain.Clear();
1070   }
1071 }
1072 //=======================================================================
1073 // function:ProcessBlock
1074 // purpose:
1075 //=======================================================================
1076 void ProcessBlock(const BOPTools_PaveBlock& aPB,
1077                   const BOPTools_IDMapOfPaveBlockIMapOfPaveBlock& aMapCB,
1078                   BOPTools_IMapOfPaveBlock& aProcessedBlocks,
1079                   BOPTools_IMapOfPaveBlock& aChain)
1080 {
1081   Standard_Integer j, aNbPB;
1082   //
1083   if (aProcessedBlocks.Contains(aPB)) {
1084     return;
1085   }
1086   aProcessedBlocks.Add(aPB);
1087   aChain.Add(aPB);
1088   //
1089   const BOPTools_IMapOfPaveBlock& aMapPB=aMapCB.FindFromKey(aPB);
1090   aNbPB=aMapPB.Extent();
1091   for (j=1; j<=aNbPB; ++j) {
1092     const BOPTools_PaveBlock& aPBx=aMapPB(j);
1093     ProcessBlock(aPBx, aMapCB, aProcessedBlocks, aChain);
1094   }
1095 }