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