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