0025748: Parallel version of progress indicator
[occt.git] / 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(*myProgressScope);
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(*myProgressScope);
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 }