NMTTools_PaveFiller_4.cxx

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