src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx

   1 // Created by: Peter KURNEV
   2 // Copyright (c) 2010-2014 OPEN CASCADE SAS
   3 // Copyright (c) 2007-2010 CEA/DEN, EDF R&D, OPEN CASCADE
   4 // Copyright (c) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, CEDRAT,
   5 //                         EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   6 //
   7 // This file is part of Open CASCADE Technology software library.
   8 //
   9 // This library is free software; you can redistribute it and/or modify it under
  10 // the terms of the GNU Lesser General Public License version 2.1 as published
  11 // by the Free Software Foundation, with special exception defined in the file
  12 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  13 // distribution for complete text of the license and disclaimer of any warranty.
  14 //
  15 // Alternatively, this file may be used under the terms of Open CASCADE
  16 // commercial license or contractual agreement.
  17
  18
  19 #include <Bnd_Box.hxx>
  20 #include <Bnd_Tools.hxx>
  21 #include <BOPAlgo_PaveFiller.hxx>
  22 #include <BOPAlgo_Alerts.hxx>
  23 #include <BOPAlgo_Tools.hxx>
  24 #include <BOPDS_CommonBlock.hxx>
  25 #include <BOPDS_CoupleOfPaveBlocks.hxx>
  26 #include <BOPDS_Curve.hxx>
  27 #include <BOPDS_DS.hxx>
  28 #include <BOPDS_Interf.hxx>
  29 #include <BOPDS_Iterator.hxx>
  30 #include <BOPDS_MapOfPaveBlock.hxx>
  31 #include <BOPDS_Pave.hxx>
  32 #include <BOPDS_PaveBlock.hxx>
  33 #include <BOPTools_AlgoTools.hxx>
  34 #include <BOPTools_AlgoTools2D.hxx>
  35 #include <BOPTools_Parallel.hxx>
  36 #include <BRep_Builder.hxx>
  37 #include <BRep_Tool.hxx>
  38 #include <BRepAdaptor_Curve.hxx>
  39 #include <GeomAPI_ProjectPointOnSurf.hxx>
  40 #include <gp_Pnt.hxx>
  41 #include <IntTools_CommonPrt.hxx>
  42 #include <IntTools_Context.hxx>
  43 #include <IntTools_EdgeFace.hxx>
  44 #include <IntTools_Range.hxx>
  45 #include <IntTools_SequenceOfCommonPrts.hxx>
  46 #include <IntTools_Tools.hxx>
  47 #include <NCollection_IncAllocator.hxx>
  48 #include <NCollection_Vector.hxx>
  49 #include <Precision.hxx>
  50 #include <TColStd_MapOfInteger.hxx>
  51 #include <TopoDS.hxx>
  52 #include <TopoDS_Edge.hxx>
  53 #include <TopoDS_Face.hxx>
  54 #include <TopoDS_Vertex.hxx>
  55
  56 //=======================================================================
  57 //class    : BOPAlgo_EdgeFace
  58 //purpose  :
  59 //=======================================================================
  60 class BOPAlgo_EdgeFace :
  61   public IntTools_EdgeFace,
  62   public BOPAlgo_Algo {
  63
  64  public:
  65   DEFINE_STANDARD_ALLOC
  66
  67   BOPAlgo_EdgeFace() :
  68     IntTools_EdgeFace(),
  69     BOPAlgo_Algo(),
  70     myIE(-1), myIF(-1) {
  71   };
  72   //
  73   virtual ~BOPAlgo_EdgeFace(){
  74   };
  75   //
  76   void SetIndices(const Standard_Integer nE,
  77                   const Standard_Integer nF) {
  78     myIE=nE;
  79     myIF=nF;
  80   }
  81   //
  82   void Indices(Standard_Integer& nE,
  83                Standard_Integer& nF) {
  84     nE=myIE;
  85     nF=myIF;
  86   }
  87   //
  88   void SetNewSR(const IntTools_Range& aR){
  89     myNewSR=aR;
  90   }
  91   //
  92   IntTools_Range& NewSR(){
  93     return myNewSR;
  94   }
  95   //
  96   void SetPaveBlock(const Handle(BOPDS_PaveBlock)& aPB) {
  97     myPB=aPB;
  98   }
  99   //
 100   Handle(BOPDS_PaveBlock)& PaveBlock() {
 101     return myPB;
 102   }
 103   //
 104   void SetFuzzyValue(const Standard_Real theFuzz) {
 105     IntTools_EdgeFace::SetFuzzyValue(theFuzz);
 106   }
 107   //
 108   void SetBoxes (const Bnd_Box& theBox1,
 109                  const Bnd_Box& theBox2)
 110   {
 111     myBox1 = theBox1;
 112     myBox2 = theBox2;
 113   }
 114   //
 115   virtual void Perform() {
 116     BOPAlgo_Algo::UserBreak();
 117     TopoDS_Face aFace = myFace;
 118     TopoDS_Edge anEdge = myEdge;
 119     Standard_Boolean hasTrsf = false;
 120     try
 121     {
 122       OCC_CATCH_SIGNALS
 123
 124       gp_Trsf aTrsf;
 125       if (BOPAlgo_Tools::TrsfToPoint (myBox1, myBox2, aTrsf))
 126       {
 127         // Shapes are located far from origin, move the shapes to the origin,
 128         // to increase the accuracy of intersection.
 129         TopLoc_Location aLoc (aTrsf);
 130         myEdge.Move (aLoc);
 131         myFace.Move (aLoc);
 132         hasTrsf = Standard_True;
 133       }
 134
 135       IntTools_EdgeFace::Perform();
 136     }
 137     catch (Standard_Failure const&)
 138     {
 139       AddError(new BOPAlgo_AlertIntersectionFailed);
 140     }
 141     myFace = aFace;
 142     myEdge = anEdge;
 143
 144     if (hasTrsf)
 145     {
 146       for (Standard_Integer i = 1; i <= mySeqOfCommonPrts.Length(); ++i)
 147       {
 148         IntTools_CommonPrt& aCPart = mySeqOfCommonPrts (i);
 149         aCPart.SetEdge1 (myEdge);
 150       }
 151     }
 152   }
 153   //
 154  protected:
 155   Standard_Integer myIE;
 156   Standard_Integer myIF;
 157   IntTools_Range myNewSR;
 158   Handle(BOPDS_PaveBlock) myPB;
 159   Bnd_Box myBox1;
 160   Bnd_Box myBox2;
 161 };
 162 //
 163 //=======================================================================
 164 typedef NCollection_Vector<BOPAlgo_EdgeFace> BOPAlgo_VectorOfEdgeFace;
 165
 166 //=======================================================================
 167 //function : PerformEF
 168 //purpose  :
 169 //=======================================================================
 170 void BOPAlgo_PaveFiller::PerformEF()
 171 {
 172   FillShrunkData(TopAbs_EDGE, TopAbs_FACE);
 173   //
 174   myIterator->Initialize(TopAbs_EDGE, TopAbs_FACE);
 175   Standard_Integer iSize = myIterator->ExpectedLength();
 176   if (!iSize) {
 177     return;
 178   }
 179   //
 180   Standard_Integer nE, nF;
 181   //
 182   if (myGlue == BOPAlgo_GlueFull) {
 183     // there is no need to intersect edges with faces in this mode
 184     // just initialize FaceInfo for faces
 185     for (; myIterator->More(); myIterator->Next()) {
 186       myIterator->Value(nE, nF);
 187       if (!myDS->ShapeInfo(nE).HasFlag()) {
 188         myDS->ChangeFaceInfo(nF);
 189       }
 190     }
 191     return;
 192   }
 193   //
 194   Standard_Boolean bV[2], bIsPBSplittable;
 195   Standard_Boolean bV1, bV2, bExpressCompute;
 196   Standard_Integer nV1, nV2;
 197   Standard_Integer i, aNbCPrts, iX, nV[2];
 198   Standard_Integer aNbEdgeFace, k;
 199   Standard_Real aTolE, aTolF, aTS1, aTS2, aT1, aT2;
 200   Handle(NCollection_BaseAllocator) aAllocator;
 201   TopAbs_ShapeEnum aType;
 202   BOPDS_ListIteratorOfListOfPaveBlock aIt;
 203   BOPAlgo_VectorOfEdgeFace aVEdgeFace;
 204   //-----------------------------------------------------scope f
 205   //
 206   aAllocator=NCollection_BaseAllocator::CommonBaseAllocator();
 207   //
 208   TColStd_MapOfInteger aMIEFC(100, aAllocator);
 209   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMVCPB(100, aAllocator);
 210   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(100, aAllocator);
 211   BOPAlgo_DataMapOfPaveBlockBndBox aDMPBBox(100, aAllocator);
 212   //
 213   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
 214   aEFs.SetIncrement(iSize);
 215   //
 216   for (; myIterator->More(); myIterator->Next()) {
 217     myIterator->Value(nE, nF);
 218     //
 219     const BOPDS_ShapeInfo& aSIE=myDS->ShapeInfo(nE);
 220     if (aSIE.HasFlag()){//degenerated
 221       continue;
 222     }
 223     //
 224     const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aSIE.Shape()));
 225     const TopoDS_Face& aF=(*(TopoDS_Face *)(&myDS->Shape(nF)));
 226     const Bnd_Box& aBBF=myDS->ShapeInfo(nF).Box();
 227     //
 228     BOPDS_FaceInfo& aFI=myDS->ChangeFaceInfo(nF);
 229     const BOPDS_IndexedMapOfPaveBlock& aMPBF=aFI.PaveBlocksOn();
 230     //
 231     const TColStd_MapOfInteger& aMVIn=aFI.VerticesIn();
 232     const TColStd_MapOfInteger& aMVOn=aFI.VerticesOn();
 233     //
 234     aTolE=BRep_Tool::Tolerance(aE);
 235     aTolF=BRep_Tool::Tolerance(aF);
 236     //
 237     BOPDS_ListOfPaveBlock& aLPB=myDS->ChangePaveBlocks(nE);
 238     aIt.Initialize(aLPB);
 239     for (; aIt.More(); aIt.Next()) {
 240       Handle(BOPDS_PaveBlock)& aPB=aIt.ChangeValue();
 241       //
 242       const Handle(BOPDS_PaveBlock) aPBR=myDS->RealPaveBlock(aPB);
 243       if (aMPBF.Contains(aPBR)) {
 244         continue;
 245       }
 246       //
 247       Bnd_Box aBBE;
 248       if (!GetPBBox(aE, aPB, aDMPBBox, aT1, aT2, aTS1, aTS2, aBBE)) {
 249         continue;
 250       }
 251       //
 252       if (aBBF.IsOut (aBBE)) {
 253         continue;
 254       }
 255       //
 256       aPBR->Indices(nV1, nV2);
 257       bV1=aMVIn.Contains(nV1) || aMVOn.Contains(nV1);
 258       bV2=aMVIn.Contains(nV2) || aMVOn.Contains(nV2);
 259       bExpressCompute=bV1 && bV2;
 260       //
 261       BOPAlgo_EdgeFace& aEdgeFace=aVEdgeFace.Appended();
 262       //
 263       aEdgeFace.SetIndices(nE, nF);
 264       aEdgeFace.SetPaveBlock(aPB);
 265       //
 266       aEdgeFace.SetEdge (aE);
 267       aEdgeFace.SetFace (aF);
 268       aEdgeFace.SetBoxes (myDS->ShapeInfo(nE).Box(), myDS->ShapeInfo (nF).Box());
 269       aEdgeFace.SetFuzzyValue(myFuzzyValue);
 270       aEdgeFace.UseQuickCoincidenceCheck(bExpressCompute);
 271       //
 272       IntTools_Range aSR(aTS1, aTS2);
 273       IntTools_Range anewSR=aSR;
 274       BOPTools_AlgoTools::CorrectRange(aE, aF, aSR, anewSR);
 275       aEdgeFace.SetNewSR(anewSR);
 276       //
 277       IntTools_Range aPBRange(aT1, aT2);
 278       aSR = aPBRange;
 279       BOPTools_AlgoTools::CorrectRange(aE, aF, aSR, aPBRange);
 280       aEdgeFace.SetRange (aPBRange);
 281       aEdgeFace.SetProgressIndicator(myProgressIndicator);
 282       // Save the pair to avoid their forced intersection
 283       BOPDS_MapOfPaveBlock* pMPB = myFPBDone.ChangeSeek(nF);
 284       if (!pMPB)
 285         pMPB = myFPBDone.Bound(nF, BOPDS_MapOfPaveBlock());
 286       pMPB->Add(aPB);
 287     }//for (; aIt.More(); aIt.Next()) {
 288   }//for (; myIterator->More(); myIterator->Next()) {
 289   //
 290   aNbEdgeFace=aVEdgeFace.Length();
 291   //=================================================================
 292   BOPTools_Parallel::Perform (myRunParallel, aVEdgeFace, myContext);
 293   //=================================================================
 294   //
 295   for (k=0; k < aNbEdgeFace; ++k) {
 296     BOPAlgo_EdgeFace& aEdgeFace=aVEdgeFace(k);
 297     if (!aEdgeFace.IsDone() || aEdgeFace.HasErrors()) {
 298       // Warn about failed intersection of sub-shapes
 299       AddIntersectionFailedWarning(aEdgeFace.Edge(), aEdgeFace.Face());
 300       continue;
 301     }
 302     //
 303     const IntTools_SequenceOfCommonPrts& aCPrts=aEdgeFace.CommonParts();
 304     aNbCPrts = aCPrts.Length();
 305     if (!aNbCPrts) {
 306       continue;
 307     }
 308     //
 309     aEdgeFace.Indices(nE, nF);
 310     //
 311     const TopoDS_Edge& aE=aEdgeFace.Edge();
 312     const TopoDS_Face& aF=aEdgeFace.Face();
 313     //
 314     aTolE=BRep_Tool::Tolerance(aE);
 315     aTolF=BRep_Tool::Tolerance(aF);
 316     const IntTools_Range& anewSR=aEdgeFace.NewSR();
 317     Handle(BOPDS_PaveBlock)& aPB=aEdgeFace.PaveBlock();
 318     //
 319     aPB->Range(aT1, aT2);
 320     aPB->Indices(nV[0], nV[1]);
 321     bIsPBSplittable = aPB->IsSplittable();
 322     //
 323     anewSR.Range(aTS1, aTS2);
 324     //
 325     if (aCPrts(1).Type() == TopAbs_VERTEX) {
 326       // for the intersection type VERTEX
 327       // extend vertices ranges using Edge/Edge intersections
 328       // between the edge aE and the edges of the face aF.
 329       // thereby the edge's intersection range is reduced
 330       ReduceIntersectionRange(nV[0], nV[1], nE, nF, aTS1, aTS2);
 331     }
 332     //
 333     IntTools_Range aR1(aT1, aTS1), aR2(aTS2, aT2);
 334     //
 335     BOPDS_FaceInfo& aFI=myDS->ChangeFaceInfo(nF);
 336     const TColStd_MapOfInteger& aMIFOn=aFI.VerticesOn();
 337     const TColStd_MapOfInteger& aMIFIn=aFI.VerticesIn();
 338     //
 339     Standard_Boolean bLinePlane = Standard_False;
 340     if (aNbCPrts) {
 341       BRepAdaptor_Curve aBAC(aE);
 342       bLinePlane = (aBAC.GetType() == GeomAbs_Line &&
 343                     myContext->SurfaceAdaptor(aF).GetType() == GeomAbs_Plane);
 344     }
 345     //
 346     for (i=1; i<=aNbCPrts; ++i) {
 347       const IntTools_CommonPrt& aCPart=aCPrts(i);
 348       aType=aCPart.Type();
 349       switch (aType) {
 350         case TopAbs_VERTEX: {
 351           Standard_Boolean bIsOnPave[2];
 352           Standard_Integer j;
 353           Standard_Real aT, aTolToDecide;
 354           TopoDS_Vertex aVnew;
 355           //
 356           IntTools_Tools::VertexParameter(aCPart, aT);
 357           BOPTools_AlgoTools::MakeNewVertex(aE, aT, aF, aVnew);
 358           //
 359           const IntTools_Range& aR=aCPart.Range1();
 360           aTolToDecide=5.e-8;
 361           //
 362           bIsOnPave[0]=IntTools_Tools::IsInRange(aR1, aR, aTolToDecide);
 363           bIsOnPave[1]=IntTools_Tools::IsInRange(aR2, aR, aTolToDecide);
 364           //
 365           if ((bIsOnPave[0] && bIsOnPave[1]) ||
 366               (bLinePlane && (bIsOnPave[0] || bIsOnPave[1]))) {
 367             bV[0]=CheckFacePaves(nV[0], aMIFOn, aMIFIn);
 368             bV[1]=CheckFacePaves(nV[1], aMIFOn, aMIFIn);
 369             if (bV[0] && bV[1]) {
 370               IntTools_CommonPrt aCP = aCPart;
 371               aCP.SetType(TopAbs_EDGE);
 372               BOPDS_InterfEF& aEF=aEFs.Appended();
 373               iX=aEFs.Length()-1;
 374               aEF.SetIndices(nE, nF);
 375               aEF.SetCommonPart(aCP);
 376               myDS->AddInterf(nE, nF);
 377               //
 378               aMIEFC.Add(nF);
 379               //
 380               BOPAlgo_Tools::FillMap(aPB, nF, aMPBLI, aAllocator);
 381               break;
 382             }
 383           }
 384           //
 385           if (!bIsPBSplittable) {
 386             continue;
 387           }
 388           //
 389           for (j = 0; j < 2; ++j)
 390           {
 391             if (bIsOnPave[j])
 392             {
 393               bV[j] = CheckFacePaves(nV[j], aMIFOn, aMIFIn);
 394               if (!bV[j])
 395                 bIsOnPave[j] = ForceInterfVF(nV[j], nF);
 396             }
 397           }
 398
 399           if (bIsOnPave[0] || bIsOnPave[1])
 400           {
 401             // The found intersection point is located closely to one of the pave block's
 402             // bounds. So, do not create the new vertex in this point.
 403             // Check if this point is a real intersection, or just a touching point.
 404             // If it is a touching point, do nothing.
 405             // If it is an intersection point, update the existing vertex to cover the
 406             // intersection point.
 407             GeomAPI_ProjectPointOnSurf& aProjPS = myContext->ProjPS(aF);
 408             const gp_Pnt aPnew = BRep_Tool::Pnt(aVnew);
 409             aProjPS.Perform(aPnew);
 410             Standard_Real aMinDistEF = (aProjPS.IsDone() && aProjPS.NbPoints()) ?
 411                                         aProjPS.LowerDistance() : Precision::Infinite();
 412             Standard_Boolean hasRealIntersection = aMinDistEF < Precision::Intersection();
 413
 414             if (!hasRealIntersection)
 415               // no intersection point
 416               continue;
 417
 418             // Real intersection is present.
 419             // Update the existing vertex to cover the intersection point.
 420             for (j = 0; j < 2; ++j)
 421             {
 422               if (bIsOnPave[j])
 423               {
 424                 const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV[j]));
 425                 const gp_Pnt aP = BRep_Tool::Pnt(aV);
 426                 Standard_Real aDistPP = aP.Distance(aPnew);
 427                 Standard_Real aTol = BRep_Tool::Tolerance(aV);
 428                 Standard_Real aMaxDist = 1.e4 * aTol;
 429                 if (aTol < .01)
 430                 {
 431                   aMaxDist = Min(aMaxDist, 0.1);
 432                 }
 433                 if (aDistPP < aMaxDist)
 434                 {
 435                   UpdateVertex(nV[j], aDistPP);
 436                   myVertsToAvoidExtension.Add(nV[j]);
 437                 }
 438               }
 439             }
 440             continue;
 441           }
 442
 443           if (CheckFacePaves(aVnew, aMIFOn)) {
 444             continue;
 445           }
 446           //
 447           Standard_Real aTolVnew = BRep_Tool::Tolerance(aVnew);
 448           aTolVnew = Max(aTolVnew, Max(aTolE, aTolF));
 449           BRep_Builder().UpdateVertex(aVnew, aTolVnew);
 450           if (bLinePlane) {
 451             // increase tolerance for Line/Plane intersection, but do not update
 452             // the vertex till its intersection with some other shape
 453             IntTools_Range aCR = aCPart.Range1();
 454             aTolVnew = Max(aTolVnew, (aCR.Last() - aCR.First()) / 2.);
 455           }
 456           //
 457           const gp_Pnt& aPnew = BRep_Tool::Pnt(aVnew);
 458           //
 459           if (!myContext->IsPointInFace(aPnew, aF, aTolVnew)) {
 460             continue;
 461           }
 462           //
 463           aMIEFC.Add(nF);
 464           // 1
 465           BOPDS_InterfEF& aEF = aEFs.Appended();
 466           iX = aEFs.Length() - 1;
 467           aEF.SetIndices(nE, nF);
 468           aEF.SetCommonPart(aCPart);
 469           // 2
 470           myDS->AddInterf(nE, nF);
 471           // 3
 472           BOPDS_CoupleOfPaveBlocks aCPB;
 473           //
 474           aCPB.SetPaveBlocks(aPB, aPB);
 475           aCPB.SetIndexInterf(iX);
 476           aCPB.SetTolerance(aTolVnew);
 477           aMVCPB.Add(aVnew, aCPB);
 478         }
 479           break;
 480         case TopAbs_EDGE:  {
 481           aMIEFC.Add(nF);
 482           //
 483           // 1
 484           BOPDS_InterfEF& aEF=aEFs.Appended();
 485           iX=aEFs.Length()-1;
 486           aEF.SetIndices(nE, nF);
 487           //
 488           bV[0]=CheckFacePaves(nV[0], aMIFOn, aMIFIn);
 489           bV[1]=CheckFacePaves(nV[1], aMIFOn, aMIFIn);
 490           if (!bV[0] || !bV[1]) {
 491             myDS->AddInterf(nE, nF);
 492             break;
 493           }
 494           aEF.SetCommonPart(aCPart);
 495           // 2
 496           myDS->AddInterf(nE, nF);
 497           // 3
 498           BOPAlgo_Tools::FillMap(aPB, nF, aMPBLI, aAllocator);
 499
 500         }
 501           break;
 502         default:
 503           break;
 504       }//switch (aType) {
 505     }//for (i=1; i<=aNbCPrts; ++i) {
 506   }// for (k=0; k < aNbEdgeEdge; ++k) {
 507   //
 508   //=========================================
 509   // post treatment
 510   //=========================================
 511   BOPAlgo_Tools::PerformCommonBlocks(aMPBLI, aAllocator, myDS, myContext);
 512   UpdateVerticesOfCB();
 513   PerformNewVertices(aMVCPB, aAllocator, Standard_False);
 514   //
 515   // Update FaceInfoIn for all faces having EF common parts
 516   myDS->UpdateFaceInfoIn (aMIEFC);
 517
 518   //-----------------------------------------------------scope t
 519   aMIEFC.Clear();
 520   aMVCPB.Clear();
 521   aMPBLI.Clear();
 522   ////aAllocator.Nullify();
 523 }
 524 //=======================================================================
 525 // function: CheckFacePaves
 526 // purpose:
 527 //=======================================================================
 528 Standard_Boolean BOPAlgo_PaveFiller::CheckFacePaves
 529   (const Standard_Integer nVx,
 530    const TColStd_MapOfInteger& aMIFOn,
 531    const TColStd_MapOfInteger& aMIFIn)
 532 {
 533   Standard_Boolean bRet;
 534   Standard_Integer nV;
 535   TColStd_MapIteratorOfMapOfInteger aIt;
 536   //
 537   bRet=Standard_False;
 538   //
 539   aIt.Initialize(aMIFOn);
 540   for (; aIt.More(); aIt.Next()) {
 541     nV=aIt.Value();
 542     if (nV==nVx) {
 543       bRet=!bRet;
 544       return bRet;
 545     }
 546   }
 547   aIt.Initialize(aMIFIn);
 548   for (; aIt.More(); aIt.Next()) {
 549     nV=aIt.Value();
 550     if (nV==nVx) {
 551       bRet=!bRet;
 552       return bRet;
 553     }
 554   }
 555   //
 556   return bRet;
 557 }
 558 //=======================================================================
 559 // function: CheckFacePaves
 560 // purpose:
 561 //=======================================================================
 562 Standard_Boolean BOPAlgo_PaveFiller::CheckFacePaves
 563   (const TopoDS_Vertex& aVnew,
 564    const TColStd_MapOfInteger& aMIF)
 565 {
 566   Standard_Boolean bRet;
 567   Standard_Integer nV, iFlag;
 568   TColStd_MapIteratorOfMapOfInteger aIt;
 569   //
 570   bRet=Standard_True;
 571   //
 572   aIt.Initialize(aMIF);
 573   for (; aIt.More(); aIt.Next()) {
 574     nV=aIt.Value();
 575     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&myDS->Shape(nV)));
 576     iFlag=BOPTools_AlgoTools::ComputeVV(aVnew, aV);
 577     if (!iFlag) {
 578       return bRet;
 579     }
 580   }
 581   //
 582   return !bRet;
 583 }
 584 //=======================================================================
 585 //function : ForceInterfVF
 586 //purpose  :
 587 //=======================================================================
 588 Standard_Boolean BOPAlgo_PaveFiller::ForceInterfVF
 589   (const Standard_Integer nV,
 590    const Standard_Integer nF)
 591 {
 592   Standard_Boolean bRet;
 593   Standard_Integer iFlag, nVx;
 594   Standard_Real U, V, aTolVNew;
 595   //
 596   bRet = Standard_False;
 597   const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV);
 598   const TopoDS_Face&   aF = *(TopoDS_Face*)  &myDS->Shape(nF);
 599   //
 600   iFlag = myContext->ComputeVF(aV, aF, U, V, aTolVNew, myFuzzyValue);
 601   if (iFlag == 0 || iFlag == -2) {
 602     bRet=!bRet;
 603   //
 604     BOPDS_VectorOfInterfVF& aVFs=myDS->InterfVF();
 605     aVFs.SetIncrement(10);
 606     // 1
 607     BOPDS_InterfVF& aVF=aVFs.Appended();
 608     //
 609     aVF.SetIndices(nV, nF);
 610     aVF.SetUV(U, V);
 611     // 2
 612     myDS->AddInterf(nV, nF);
 613     //
 614     // 3 update vertex V/F if necessary
 615     nVx=UpdateVertex(nV, aTolVNew);
 616     // 4
 617     if (myDS->IsNewShape(nVx)) {
 618       aVF.SetIndexNew(nVx);
 619     }
 620     //
 621     BOPDS_FaceInfo& aFI=myDS->ChangeFaceInfo(nF);
 622     TColStd_MapOfInteger& aMVIn=aFI.ChangeVerticesIn();
 623     aMVIn.Add(nVx);
 624     //
 625     // check for self-interference
 626     Standard_Integer iRV = myDS->Rank(nV);
 627     if (iRV >= 0 && iRV == myDS->Rank(nF)) {
 628       // add warning status
 629       TopoDS_Compound aWC;
 630       BRep_Builder().MakeCompound(aWC);
 631       BRep_Builder().Add(aWC, aV);
 632       BRep_Builder().Add(aWC, aF);
 633       AddWarning (new BOPAlgo_AlertSelfInterferingShape (aWC));
 634     }
 635
 636   }
 637   return bRet;
 638 }
 639 //=======================================================================
 640 //function : ReduceIntersectionRange
 641 //purpose  :
 642 //=======================================================================
 643 void BOPAlgo_PaveFiller::ReduceIntersectionRange(const Standard_Integer theV1,
 644                                                  const Standard_Integer theV2,
 645                                                  const Standard_Integer theE,
 646                                                  const Standard_Integer theF,
 647                                                  Standard_Real& theTS1,
 648                                                  Standard_Real& theTS2)
 649 {
 650   if (!myDS->IsNewShape(theV1) &&
 651       !myDS->IsNewShape(theV2)) {
 652     return;
 653   }
 654   //
 655   if (!myDS->HasInterfShapeSubShapes(theE, theF)) {
 656     return;
 657   }
 658   //
 659   BOPDS_VectorOfInterfEE& aEEs = myDS->InterfEE();
 660   Standard_Integer aNbEEs = aEEs.Length();
 661   if (!aNbEEs) {
 662     return;
 663   }
 664   //
 665   Standard_Integer i, nV, nE1, nE2;
 666   Standard_Real aTR1, aTR2;
 667   //
 668   // get face's edges to check that E/E contains the edge from the face
 669   TColStd_MapOfInteger aMFE;
 670   const TColStd_ListOfInteger& aLI = myDS->ShapeInfo(theF).SubShapes();
 671   TColStd_ListIteratorOfListOfInteger aItLI(aLI);
 672   for (; aItLI.More(); aItLI.Next()) {
 673     nE1 = aItLI.Value();
 674     if (myDS->ShapeInfo(nE1).ShapeType() == TopAbs_EDGE) {
 675       aMFE.Add(nE1);
 676     }
 677   }
 678   //
 679   for (i = 0; i < aNbEEs; ++i) {
 680     BOPDS_InterfEE& aEE = aEEs(i);
 681     if (!aEE.HasIndexNew()) {
 682       continue;
 683     }
 684     //
 685     // check the vertex
 686     nV = aEE.IndexNew();
 687     if (nV != theV1 && nV != theV2) {
 688       continue;
 689     }
 690     //
 691     // check that the intersection is between the edge
 692     // and one of the face's edge
 693     aEE.Indices(nE1, nE2);
 694     if (((theE != nE1) && (theE != nE2)) ||
 695         (!aMFE.Contains(nE1) && !aMFE.Contains(nE2))) {
 696       continue;
 697     }
 698     //
 699     // update the intersection range
 700     const IntTools_CommonPrt& aCPart = aEE.CommonPart();
 701     const IntTools_Range& aCRange =
 702       (theE == nE1) ? aCPart.Range1() : aCPart.Ranges2().First();
 703     aCRange.Range(aTR1, aTR2);
 704     //
 705     if (nV == theV1) {
 706       if (theTS1 < aTR2) {
 707         theTS1 = aTR2;
 708       }
 709     }
 710     else {
 711       if (theTS2 > aTR1) {
 712         theTS2 = aTR1;
 713       }
 714     }
 715   }
 716 }
 717
 718 //=======================================================================
 719 //function : ForceInterfEF
 720 //purpose  :
 721 //=======================================================================
 722 void BOPAlgo_PaveFiller::ForceInterfEF()
 723 {
 724   if (!myIsPrimary)
 725     return;
 726
 727   // Now that we have vertices increased and unified, try to find additional
 728   // edge/face common blocks among the pairs of edge/face.
 729   // Here, we are interested in common blocks only, as all real intersections
 730   // should have happened already. Thus, we need to check only those pairs
 731   // of edge/face which have the same vertices.
 732
 733   // Collect all pave blocks
 734   BOPDS_IndexedMapOfPaveBlock aMPB;
 735   const Standard_Integer aNbS = myDS->NbSourceShapes();
 736   for (Standard_Integer nE = 0; nE < aNbS; ++nE)
 737   {
 738     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nE);
 739     if (aSI.ShapeType() != TopAbs_EDGE)
 740       // Not an edge
 741       continue;
 742
 743     if (!aSI.HasReference())
 744       // Edge has no pave blocks
 745       continue;
 746
 747     if (aSI.HasFlag())
 748       // Degenerated edge
 749       continue;
 750
 751     const BOPDS_ListOfPaveBlock& aLPB = myDS->PaveBlocks(nE);
 752     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
 753     for (; aItLPB.More(); aItLPB.Next())
 754     {
 755       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
 756       const Handle(BOPDS_PaveBlock)& aPBR = myDS->RealPaveBlock(aPB);
 757       aMPB.Add(aPBR);
 758     }
 759   }
 760
 761   // Perform intersection of collected pave blocks with faces
 762   ForceInterfEF(aMPB, Standard_True);
 763 }
 764
 765 //=======================================================================
 766 //function : ForceInterfEF
 767 //purpose  :
 768 //=======================================================================
 769 void BOPAlgo_PaveFiller::ForceInterfEF(const BOPDS_IndexedMapOfPaveBlock& theMPB,
 770                                        const Standard_Boolean theAddInterf)
 771 {
 772   if (theMPB.IsEmpty())
 773     return;
 774
 775   // Fill the tree with bounding boxes of the pave blocks
 776   BOPTools_BoxTree aBBTree;
 777
 778   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
 779   BOPDS_IndexedMapOfPaveBlock aPBMap(1, anAlloc);
 780
 781   Standard_Integer aNbPB = theMPB.Extent();
 782   for (Standard_Integer iPB = 1; iPB <= aNbPB; ++iPB)
 783   {
 784     Handle(BOPDS_PaveBlock) aPB = theMPB(iPB);
 785     if (!aPB->HasShrunkData() || !myDS->IsValidShrunkData(aPB))
 786     {
 787       FillShrunkData(aPB);
 788       if (!aPB->HasShrunkData())
 789         continue;
 790     }
 791
 792     Standard_Real f, l;
 793     Bnd_Box aPBBox;
 794     Standard_Boolean isSplit;
 795     aPB->ShrunkData(f, l, aPBBox, isSplit);
 796
 797     aBBTree.Add(aPBMap.Add(aPB), Bnd_Tools::Bnd2BVH(aPBBox));
 798   }
 799
 800   // Shake the tree
 801   aBBTree.Build();
 802
 803   const Standard_Boolean bSICheckMode = (myArguments.Extent() == 1);
 804
 805   // Find pairs of Face/PaveBlock containing the same vertices
 806   // and prepare those pairs for intersection.
 807   BOPAlgo_VectorOfEdgeFace aVEdgeFace;
 808
 809   const Standard_Integer aNbS = myDS->NbSourceShapes();
 810   for (Standard_Integer nF = 0; nF < aNbS; ++nF)
 811   {
 812     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
 813     if (aSI.ShapeType() != TopAbs_FACE)
 814       // Not a face
 815       continue;
 816
 817     if (!aSI.HasReference())
 818       // Face has no face info
 819       continue;
 820
 821     const Bnd_Box& aBoxF = aSI.Box();
 822     BOPTools_BoxTreeSelector aSelector;
 823     aSelector.SetBox(Bnd_Tools::Bnd2BVH(aBoxF));
 824     aSelector.SetBVHSet (&aBBTree);
 825     if (!aSelector.Select())
 826       continue;
 827
 828     const TopoDS_Face& aF = TopoDS::Face(aSI.Shape());
 829     const BOPDS_FaceInfo& aFI = myDS->FaceInfo(nF);
 830     // Vertices of the face
 831     TColStd_MapOfInteger aMVF;
 832     const TColStd_MapOfInteger* pMVF[] = { &aFI.VerticesOn(),
 833                                            &aFI.VerticesIn(),
 834                                            &aFI.VerticesSc() };
 835     for (Standard_Integer iM = 0; iM < 3; ++iM)
 836     {
 837       TColStd_MapIteratorOfMapOfInteger itM(*pMVF[iM]);
 838       for (; itM.More(); itM.Next())
 839         aMVF.Add(itM.Value());
 840     }
 841
 842     // Pave Blocks of the face
 843     const BOPDS_IndexedMapOfPaveBlock* pMPBF[] = { &aFI.PaveBlocksOn(),
 844                                                    &aFI.PaveBlocksIn(),
 845                                                    &aFI.PaveBlocksSc() };
 846     for (Standard_Integer iM = 0; iM < 3; ++iM)
 847     {
 848       const Standard_Integer aNb = pMPBF[iM]->Extent();
 849       for (Standard_Integer iPB = 1; iPB <= aNb; ++iPB)
 850       {
 851         const Handle(BOPDS_PaveBlock)& aPB = pMPBF[iM]->FindKey(iPB);
 852         aMVF.Add(aPB->Pave1().Index());
 853         aMVF.Add(aPB->Pave2().Index());
 854       }
 855     }
 856
 857     // Projection tool
 858     GeomAPI_ProjectPointOnSurf& aProjPS = myContext->ProjPS(aF);
 859     BRepAdaptor_Surface& aSurfAdaptor = myContext->SurfaceAdaptor (aF);
 860
 861     // Iterate on pave blocks and combine pairs containing
 862     // the same vertices
 863     const TColStd_ListOfInteger& aLIPB = aSelector.Indices();
 864     TColStd_ListOfInteger::Iterator itLIPB(aLIPB);
 865     for (; itLIPB.More(); itLIPB.Next())
 866     {
 867       const Handle(BOPDS_PaveBlock)& aPB = aPBMap(itLIPB.Value());
 868       if (pMPBF[0]->Contains(aPB) ||
 869           pMPBF[1]->Contains(aPB) ||
 870           pMPBF[2]->Contains(aPB))
 871         continue;
 872
 873       // Check if the face contains both vertices of the pave block
 874       Standard_Integer nV1, nV2;
 875       aPB->Indices(nV1, nV2);
 876       if (!aMVF.Contains(nV1) || !aMVF.Contains(nV2))
 877         // Face does not contain the vertices
 878         continue;
 879
 880       // Get the edge
 881       Standard_Integer nE;
 882       if (!aPB->HasEdge(nE))
 883       {
 884         nE = aPB->OriginalEdge();
 885         if (nE < 0)
 886           continue;
 887
 888         // Make sure that the edge and face came from different arguments
 889         if (myDS->Rank(nF) == myDS->Rank(nE))
 890           continue;
 891       }
 892
 893       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
 894       BRepAdaptor_Curve aBAC(aE);
 895
 896       // Check directions coincidence at middle point on the edge
 897       // and projection of that point on the face.
 898       // If the angle between tangent vector to the curve and normal
 899       // of the face is not in the range of 65 - 115 degrees, do not use the additional
 900       // tolerance, as it may lead to undesired unification of edge with the face.
 901       Standard_Boolean bUseAddTol = Standard_True;
 902
 903       Standard_Real aTS[2];
 904       Bnd_Box aPBBox;
 905       Standard_Boolean isSplit;
 906       aPB->ShrunkData(aTS[0], aTS[1], aPBBox, isSplit);
 907
 908       // Middle point
 909       gp_Pnt aPOnE;
 910       // Tangent vector in the middle point
 911       gp_Vec aVETgt;
 912       aBAC.D1(BOPTools_AlgoTools2D::IntermediatePoint(aTS[0], aTS[1]), aPOnE, aVETgt);
 913       if (aVETgt.SquareMagnitude() < gp::Resolution())
 914         continue;
 915
 916       aProjPS.Perform(aPOnE);
 917       if (!aProjPS.NbPoints())
 918         continue;
 919
 920       // Check the distance in the middle point, using the max vertices
 921       // tolerance as the criteria.
 922       const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(nV1));
 923       const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(nV2));
 924
 925       // In the Self-Interference check mode we are interested in real
 926       // intersections only, so use only the real tolerance of edges,
 927       // no need to use the extended tolerance.
 928       Standard_Real aTolCheck = (bSICheckMode ? myFuzzyValue :
 929         2 * Max(BRep_Tool::Tolerance(aV1), BRep_Tool::Tolerance(aV2)));
 930
 931       if (aProjPS.LowerDistance() > aTolCheck + myFuzzyValue)
 932         continue;
 933
 934       Standard_Real U, V;
 935       aProjPS.LowerDistanceParameters(U, V);
 936       if (!myContext->IsPointInFace(aF, gp_Pnt2d(U, V)))
 937         continue;
 938
 939       if (aSurfAdaptor.GetType() != GeomAbs_Plane ||
 940           aBAC.GetType() != GeomAbs_Line)
 941       {
 942         gp_Pnt aPOnS = aProjPS.NearestPoint();
 943         gp_Vec aVFNorm(aPOnS, aPOnE);
 944         if (aVFNorm.SquareMagnitude() > gp::Resolution())
 945         {
 946           // Angle between vectors should be close to 90 degrees.
 947           // We allow deviation of 25 degrees.
 948           Standard_Real aCos = aVFNorm.Normalized().Dot (aVETgt.Normalized());
 949           if (Abs(aCos) > 0.4226)
 950             bUseAddTol = Standard_False;
 951         }
 952       }
 953
 954       // Compute an addition to Fuzzy value
 955       Standard_Real aTolAdd = 0.0;
 956       if (bUseAddTol)
 957       {
 958         // Compute the distance from the bounding points of the edge
 959         // to the face and use the maximal of these distances as a
 960         // fuzzy tolerance for the intersection.
 961         // Use the maximal tolerance of the pave block's vertices
 962         // as a max criteria for the computed distance.
 963
 964         for (Standard_Integer iP = 0; iP < 2; ++iP)
 965         {
 966           gp_Pnt aP = aBAC.Value(aTS[iP]);
 967           aProjPS.Perform(aP);
 968           if (aProjPS.NbPoints())
 969           {
 970             Standard_Real aDistEF = aProjPS.LowerDistance();
 971             if (aDistEF < aTolCheck && aDistEF > aTolAdd)
 972               aTolAdd = aDistEF;
 973           }
 974         }
 975         if (aTolAdd > 0.)
 976         {
 977           aTolAdd -= (BRep_Tool::Tolerance(aE) + BRep_Tool::Tolerance(aF));
 978           if (aTolAdd < 0.)
 979             aTolAdd = 0.;
 980         }
 981       }
 982
 983       Standard_Boolean bIntersect = aTolAdd > 0;
 984       if (!bIntersect)
 985       {
 986         const BOPDS_MapOfPaveBlock* pMPB = myFPBDone.Seek(nF);
 987         bIntersect = !pMPB || !(pMPB->Contains(aPB));
 988       }
 989
 990       if (bIntersect)
 991       {
 992         // Prepare pair for intersection
 993         BOPAlgo_EdgeFace& aEdgeFace = aVEdgeFace.Appended();
 994         aEdgeFace.SetIndices(nE, nF);
 995         aEdgeFace.SetPaveBlock(aPB);
 996         aEdgeFace.SetEdge(aE);
 997         aEdgeFace.SetFace(aF);
 998         aEdgeFace.SetBoxes (myDS->ShapeInfo(nE).Box(), myDS->ShapeInfo (nF).Box());
 999         aEdgeFace.SetFuzzyValue(myFuzzyValue + aTolAdd);
1000         aEdgeFace.UseQuickCoincidenceCheck(Standard_True);
1001         aEdgeFace.SetRange(IntTools_Range(aPB->Pave1().Parameter(), aPB->Pave2().Parameter()));
1002         aEdgeFace.SetProgressIndicator(myProgressIndicator);
1003       }
1004     }
1005   }
1006
1007   Standard_Integer aNbEFs = aVEdgeFace.Length();
1008   if (!aNbEFs)
1009     return;
1010
1011   aPBMap.Clear();
1012   anAlloc->Reset();
1013
1014   // Perform intersection of the found pairs
1015   BOPTools_Parallel::Perform (myRunParallel, aVEdgeFace, myContext);
1016
1017   BOPDS_VectorOfInterfEF& aEFs = myDS->InterfEF();
1018   if (theAddInterf && aEFs.IsEmpty())
1019     aEFs.SetIncrement(10);
1020
1021   // Analyze the results of intersection looking for TopAbs_EDGE
1022   // intersection type only.
1023
1024   // Collect all pairs for common block creation
1025   BOPDS_IndexedDataMapOfPaveBlockListOfInteger aMPBLI(1, anAlloc);
1026
1027   for (Standard_Integer i = 0; i < aNbEFs; ++i)
1028   {
1029     BOPAlgo_EdgeFace& anEdgeFace = aVEdgeFace(i);
1030     if (!anEdgeFace.IsDone() || anEdgeFace.HasErrors())
1031     {
1032       // Warn about failed intersection of sub-shapes
1033       AddIntersectionFailedWarning(anEdgeFace.Edge(), anEdgeFace.Face());
1034       continue;
1035     }
1036
1037     const IntTools_SequenceOfCommonPrts& aCParts = anEdgeFace.CommonParts();
1038     if (aCParts.Length() != 1)
1039       continue;
1040
1041     const IntTools_CommonPrt& aCP = aCParts(1);
1042     if (aCP.Type() != TopAbs_EDGE)
1043       continue;
1044
1045     Standard_Integer nE, nF;
1046     anEdgeFace.Indices(nE, nF);
1047     if (theAddInterf)
1048     {
1049       // Add interference
1050       BOPDS_InterfEF& aEF = aEFs.Appended();
1051       aEF.SetIndices(nE, nF);
1052       aEF.SetCommonPart(aCP);
1053       myDS->AddInterf(nE, nF);
1054     }
1055
1056     const Handle(BOPDS_PaveBlock)& aPB = anEdgeFace.PaveBlock();
1057     // Update face information with new IN pave block
1058     myDS->ChangeFaceInfo(nF).ChangePaveBlocksIn().Add(aPB);
1059     if (theAddInterf)
1060       // Fill map for common blocks creation
1061       BOPAlgo_Tools::FillMap(aPB, nF, aMPBLI, anAlloc);
1062   }
1063
1064   if (aMPBLI.Extent())
1065     // Create new common blocks for coinciding pairs
1066     BOPAlgo_Tools::PerformCommonBlocks(aMPBLI, anAlloc, myDS);
1067 }