0029301: Improve performance of Boolean Operations
[occt.git] / src / BOPAlgo / BOPAlgo_PaveFiller_6.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 #include <Bnd_Box.hxx>
19 #include <BOPAlgo_PaveFiller.hxx>
20 #include <BOPAlgo_SectionAttribute.hxx>
21 #include <BOPAlgo_Tools.hxx>
22 #include <BOPAlgo_Alerts.hxx>
23 #include <BOPCol_DataMapOfShapeInteger.hxx>
24 #include <BOPCol_ListOfInteger.hxx>
25 #include <BOPCol_ListOfShape.hxx>
26 #include <BOPCol_MapOfInteger.hxx>
27 #include <BOPCol_NCVector.hxx>
28 #include <BOPCol_Parallel.hxx>
29 #include <BOPDS_CommonBlock.hxx>
30 #include <BOPDS_CoupleOfPaveBlocks.hxx>
31 #include <BOPDS_Curve.hxx>
32 #include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
33 #include <BOPDS_DS.hxx>
34 #include <BOPDS_FaceInfo.hxx>
35 #include <BOPDS_Interf.hxx>
36 #include <BOPDS_Iterator.hxx>
37 #include <BOPDS_ListOfPave.hxx>
38 #include <BOPDS_ListOfPaveBlock.hxx>
39 #include <BOPDS_MapOfPaveBlock.hxx>
40 #include <BOPDS_PaveBlock.hxx>
41 #include <BOPDS_Point.hxx>
42 #include <BOPDS_ShapeInfo.hxx>
43 #include <BOPDS_VectorOfCurve.hxx>
44 #include <BOPDS_VectorOfPoint.hxx>
45 #include <BOPTools.hxx>
46 #include <BOPTools_AlgoTools.hxx>
47 #include <BOPTools_AlgoTools3D.hxx>
48 #include <BRep_Builder.hxx>
49 #include <BRep_Tool.hxx>
50 #include <BRep_TEdge.hxx>
51 #include <BRepLib.hxx>
52 #include <BRepAdaptor_Curve.hxx>
53 #include <BRepAdaptor_Surface.hxx>
54 #include <BRepBndLib.hxx>
55 #include <BRepBuilderAPI_MakeVertex.hxx>
56 #include <BRepTools.hxx>
57 #include <Geom2d_Curve.hxx>
58 #include <Geom_Curve.hxx>
59 #include <GeomAPI_ProjectPointOnCurve.hxx>
60 #include <GeomAPI_ProjectPointOnSurf.hxx>
61 #include <gp_Pnt.hxx>
62 #include <IntSurf_ListOfPntOn2S.hxx>
63 #include <IntSurf_PntOn2S.hxx>
64 #include <IntTools.hxx>
65 #include <IntTools_Context.hxx>
66 #include <IntTools_Curve.hxx>
67 #include <IntTools_EdgeFace.hxx>
68 #include <IntTools_FaceFace.hxx>
69 #include <IntTools_PntOn2Faces.hxx>
70 #include <IntTools_SequenceOfCurves.hxx>
71 #include <IntTools_SequenceOfPntOn2Faces.hxx>
72 #include <IntTools_ShrunkRange.hxx>
73 #include <IntTools_Tools.hxx>
74 #include <Precision.hxx>
75 #include <TopExp.hxx>
76 #include <TopExp_Explorer.hxx>
77 #include <TopoDS.hxx>
78 #include <TopoDS_Compound.hxx>
79 #include <TopoDS_Edge.hxx>
80 #include <TopoDS_Face.hxx>
81 #include <TopoDS_Vertex.hxx>
82
83 //
84 static Standard_Real ToleranceFF(const BRepAdaptor_Surface& aBAS1,
85                                  const BRepAdaptor_Surface& aBAS2);
86
87 /////////////////////////////////////////////////////////////////////////
88 //=======================================================================
89 //class    : BOPAlgo_FaceFace
90 //purpose  : 
91 //=======================================================================
92 class BOPAlgo_FaceFace : 
93   public IntTools_FaceFace,
94   public BOPAlgo_Algo {
95
96  public:
97   DEFINE_STANDARD_ALLOC
98
99   BOPAlgo_FaceFace() : 
100     IntTools_FaceFace(),  
101     BOPAlgo_Algo(),
102     myIF1(-1), myIF2(-1), myTolFF(1.e-7) {
103   }
104   //
105   virtual ~BOPAlgo_FaceFace() {
106   }
107   //
108   void SetIndices(const Standard_Integer nF1,
109                   const Standard_Integer nF2) {
110     myIF1=nF1;
111     myIF2=nF2;
112   }
113   //
114   void Indices(Standard_Integer& nF1,
115                Standard_Integer& nF2) const {
116     nF1=myIF1;
117     nF2=myIF2;
118   }
119   //
120   void SetFaces(const TopoDS_Face& aF1,
121                 const TopoDS_Face& aF2) {
122     myF1=aF1;
123     myF2=aF2;
124   }
125   //
126   const TopoDS_Face& Face1()const {
127     return myF1;
128   }
129   //
130   const TopoDS_Face& Face2()const {
131     return myF2;
132   }
133   //
134   void SetTolFF(const Standard_Real aTolFF) {
135     myTolFF=aTolFF;
136   }
137   //
138   Standard_Real TolFF() const{
139     return myTolFF;
140   }
141   //
142   void SetFuzzyValue(const Standard_Real theFuzz) {
143     IntTools_FaceFace::SetFuzzyValue(theFuzz);
144   }
145   //
146   virtual void Perform() {
147     BOPAlgo_Algo::UserBreak();
148     try
149     {
150       OCC_CATCH_SIGNALS
151
152       IntTools_FaceFace::Perform(myF1, myF2);
153     }
154     catch (Standard_Failure)
155     {
156       AddError(new BOPAlgo_AlertIntersectionFailed);
157     }
158   }
159   //
160  protected:
161   Standard_Integer myIF1;
162   Standard_Integer myIF2;
163   Standard_Real myTolFF;
164   TopoDS_Face myF1;
165   TopoDS_Face myF2;
166 };
167 //
168 //=======================================================================
169 typedef BOPCol_NCVector
170   <BOPAlgo_FaceFace> BOPAlgo_VectorOfFaceFace; 
171 //
172 typedef BOPCol_Functor 
173   <BOPAlgo_FaceFace,
174   BOPAlgo_VectorOfFaceFace> BOPAlgo_FaceFaceFunctor;
175 //
176 typedef BOPCol_Cnt 
177   <BOPAlgo_FaceFaceFunctor,
178   BOPAlgo_VectorOfFaceFace> BOPAlgo_FaceFaceCnt;
179 /////////////////////////////////////////////////////////////////////////
180 //=======================================================================
181 //function : PerformFF
182 //purpose  : 
183 //=======================================================================
184 void BOPAlgo_PaveFiller::PerformFF()
185 {
186   myIterator->Initialize(TopAbs_FACE, TopAbs_FACE);
187   Standard_Integer iSize = myIterator->ExpectedLength();
188   if (!iSize) {
189     return; 
190   }
191   //
192   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
193   aFFs.SetIncrement(iSize);
194   //
195   // Options for the intersection algorithm
196   Standard_Boolean bApprox   = mySectionAttribute.Approximation(),
197                    bCompC2D1 = mySectionAttribute.PCurveOnS1(),
198                    bCompC2D2 = mySectionAttribute.PCurveOnS2();
199   Standard_Real    anApproxTol = 1.e-7;
200   // Post-processing options
201   Standard_Boolean bSplitCurve = Standard_False;
202   //
203   // Fence map to store faces with updated FaceInfo structure
204   BOPCol_MapOfInteger aMIFence;
205   // Prepare the pairs of faces for intersection
206   BOPAlgo_VectorOfFaceFace aVFaceFace;
207   Standard_Integer nF1, nF2;
208   //
209   for (; myIterator->More(); myIterator->Next()) {
210     myIterator->Value(nF1, nF2);
211
212     // Update/Initialize FaceInfo structure for first face
213     if (myDS->HasFaceInfo(nF1))
214     {
215       if (aMIFence.Add(nF1))
216       {
217         myDS->UpdateFaceInfoOn(nF1);
218         myDS->UpdateFaceInfoIn(nF1);
219       }
220     }
221     else if (myDS->HasInterfShapeSubShapes(nF2, nF1))
222     {
223       myDS->ChangeFaceInfo(nF1);
224       aMIFence.Add(nF1);
225     }
226
227     // Update/Initialize FaceInfo structure for second face
228     if (myDS->HasFaceInfo(nF2))
229     {
230       if (aMIFence.Add(nF2))
231       {
232         myDS->UpdateFaceInfoOn(nF2);
233         myDS->UpdateFaceInfoIn(nF2);
234       }
235     }
236     else if (myDS->HasInterfShapeSubShapes(nF1, nF2))
237     {
238       myDS->ChangeFaceInfo(nF2);
239       aMIFence.Add(nF2);
240     }
241     //
242     if (myGlue == BOPAlgo_GlueOff)
243     {
244       const TopoDS_Face& aF1 = (*(TopoDS_Face *)(&myDS->Shape(nF1)));
245       const TopoDS_Face& aF2 = (*(TopoDS_Face *)(&myDS->Shape(nF2)));
246       //
247       const BRepAdaptor_Surface& aBAS1 = myContext->SurfaceAdaptor(aF1);
248       const BRepAdaptor_Surface& aBAS2 = myContext->SurfaceAdaptor(aF2);
249       if (aBAS1.GetType() == GeomAbs_Plane &&
250           aBAS2.GetType() == GeomAbs_Plane) {
251         // Check if the planes are really interfering
252         Standard_Boolean bToIntersect = CheckPlanes(nF1, nF2);
253         if (!bToIntersect) {
254           BOPDS_InterfFF& aFF = aFFs.Append1();
255           aFF.SetIndices(nF1, nF2);
256           aFF.Init(0, 0);
257           continue;
258         }
259       }
260       //
261       BOPAlgo_FaceFace& aFaceFace=aVFaceFace.Append1();
262       //
263       aFaceFace.SetIndices(nF1, nF2);
264       aFaceFace.SetFaces(aF1, aF2);
265       // compute minimal tolerance for the curves
266       Standard_Real aTolFF = ToleranceFF(aBAS1, aBAS2);
267       aFaceFace.SetTolFF(aTolFF);
268       //
269       IntSurf_ListOfPntOn2S aListOfPnts;
270       GetEFPnts(nF1, nF2, aListOfPnts);
271       Standard_Integer aNbLP = aListOfPnts.Extent();
272       if (aNbLP) {
273         aFaceFace.SetList(aListOfPnts);
274       }
275       //
276       aFaceFace.SetParameters(bApprox, bCompC2D1, bCompC2D2, anApproxTol);
277       aFaceFace.SetFuzzyValue(myFuzzyValue);
278       aFaceFace.SetProgressIndicator(myProgressIndicator);
279     }
280     else {
281       // for the Glue mode just add all interferences of that type
282       BOPDS_InterfFF& aFF = aFFs.Append1();
283       aFF.SetIndices(nF1, nF2);
284       aFF.SetTangentFaces(Standard_False);
285       aFF.Init(0, 0);
286     }
287   }//for (; myIterator->More(); myIterator->Next()) {
288   //
289   //======================================================
290   // Perform intersection
291   BOPAlgo_FaceFaceCnt::Perform(myRunParallel, aVFaceFace);
292   //======================================================
293   // Treatment of the results
294   Standard_Integer k, aNbFaceFace = aVFaceFace.Extent();
295   for (k = 0; k < aNbFaceFace; ++k) {
296     BOPAlgo_FaceFace& aFaceFace = aVFaceFace(k);
297     aFaceFace.Indices(nF1, nF2);
298     if (!aFaceFace.IsDone() || aFaceFace.HasErrors()) {
299       BOPDS_InterfFF& aFF = aFFs.Append1();
300       aFF.SetIndices(nF1, nF2);
301       aFF.Init(0, 0);
302       // Warn about failed intersection of faces
303       AddIntersectionFailedWarning(aFaceFace.Face1(), aFaceFace.Face2());
304       continue;
305     }
306     //
307     Standard_Boolean bTangentFaces = aFaceFace.TangentFaces();
308     Standard_Real aTolFF = aFaceFace.TolFF();
309     //
310     aFaceFace.PrepareLines3D(bSplitCurve);
311     //
312     const IntTools_SequenceOfCurves& aCvsX = aFaceFace.Lines();
313     const IntTools_SequenceOfPntOn2Faces& aPntsX = aFaceFace.Points();
314     //
315     Standard_Integer aNbCurves = aCvsX.Length();
316     Standard_Integer aNbPoints = aPntsX.Length();
317     //
318     if (aNbCurves || aNbPoints) {
319       myDS->AddInterf(nF1, nF2);
320     }
321     //
322     BOPDS_InterfFF& aFF = aFFs.Append1();
323     aFF.SetIndices(nF1, nF2);
324     aFF.SetTangentFaces(bTangentFaces);
325     aFF.Init(aNbCurves, aNbPoints);
326     //
327     // Curves
328     // Fix bounding box expanding coefficient.
329     Standard_Real aBoxExpandValue = aTolFF;
330     if (aNbCurves > 0)
331     {
332       // Modify geometric expanding coefficient by topology value,
333       // since this bounding box used in sharing (vertex or edge).
334       Standard_Real aMaxVertexTol = Max(BRep_Tool::MaxTolerance(aFaceFace.Face1(), TopAbs_VERTEX),
335         BRep_Tool::MaxTolerance(aFaceFace.Face2(), TopAbs_VERTEX));
336       aBoxExpandValue += aMaxVertexTol;
337     }
338     //
339     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
340     for (Standard_Integer i = 1; i <= aNbCurves; ++i) {
341       Bnd_Box aBox;
342       const IntTools_Curve& aIC = aCvsX(i);
343       Standard_Boolean bIsValid = IntTools_Tools::CheckCurve(aIC, aBox);
344       if (bIsValid) {
345         BOPDS_Curve& aNC = aVNC.Append1();
346         aNC.SetCurve(aIC);
347         // make sure that the bounding box has the maximal gap
348         aBox.Enlarge(aBoxExpandValue);
349         aNC.SetBox(aBox);
350         aNC.SetTolerance(Max(aIC.Tolerance(), aTolFF));
351       }
352     }
353     //
354     // Points
355     BOPDS_VectorOfPoint& aVNP = aFF.ChangePoints();
356     for (Standard_Integer i = 1; i <= aNbPoints; ++i) {
357       const IntTools_PntOn2Faces& aPi = aPntsX(i);
358       const gp_Pnt& aP = aPi.P1().Pnt();
359       //
360       BOPDS_Point& aNP = aVNP.Append1();
361       aNP.SetPnt(aP);
362     }
363   }
364 }
365 //=======================================================================
366 //function : MakeBlocks
367 //purpose  : 
368 //=======================================================================
369 void BOPAlgo_PaveFiller::MakeBlocks()
370 {
371   if (myGlue != BOPAlgo_GlueOff) {
372     return;
373   }
374   //
375   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
376   Standard_Integer aNbFF = aFFs.Extent();
377   if (!aNbFF) {
378     return;
379   }
380   //
381   Standard_Boolean bExist, bValid2D;
382   Standard_Integer i, nF1, nF2, aNbC, aNbP, j;
383   Standard_Integer nV1, nV2;
384   Standard_Real aT1, aT2;
385   Handle(NCollection_BaseAllocator) aAllocator;
386   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
387   TopoDS_Edge aES;
388   Handle(BOPDS_PaveBlock) aPBOut;
389   //
390   //-----------------------------------------------------scope f
391   aAllocator=
392     NCollection_BaseAllocator::CommonBaseAllocator();
393   //
394   BOPCol_ListOfInteger aLSE(aAllocator), aLBV(aAllocator);
395   BOPCol_MapOfInteger aMVOnIn(100, aAllocator),
396                       aMVStick(100,aAllocator), aMVEF(100, aAllocator),
397                       aMI(100, aAllocator), aMVBounds(100, aAllocator);
398   BOPDS_IndexedMapOfPaveBlock aMPBOnIn(100, aAllocator);
399   BOPDS_MapOfPaveBlock aMPBAdd(100, aAllocator), aMPBCommon;
400   BOPDS_ListOfPaveBlock aLPB(aAllocator);
401   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMSCPB(100, aAllocator); 
402   BOPCol_DataMapOfShapeInteger aMVI(100, aAllocator);
403   BOPDS_DataMapOfPaveBlockListOfPaveBlock aDMExEdges(100, aAllocator);
404   BOPCol_DataMapOfIntegerReal aMVTol(100, aAllocator);
405   BOPCol_DataMapOfIntegerInteger aDMNewSD(100, aAllocator);
406   BOPCol_DataMapOfIntegerListOfInteger aDMVLV;
407   BOPCol_DataMapOfIntegerListOfInteger aDMBV(100, aAllocator);
408   BOPCol_DataMapIteratorOfDataMapOfIntegerReal aItMV;
409   BOPCol_IndexedMapOfShape aMicroEdges(100, aAllocator);
410   BOPCol_IndexedMapOfShape aVertsOnRejectedPB;
411   //
412   for (i=0; i<aNbFF; ++i) {
413     //
414     UserBreak();
415     //
416     BOPDS_InterfFF& aFF=aFFs(i);
417     aFF.Indices(nF1, nF2);
418     //
419     BOPDS_VectorOfPoint& aVP=aFF.ChangePoints();
420     aNbP=aVP.Extent();
421     BOPDS_VectorOfCurve& aVC=aFF.ChangeCurves();
422     aNbC=aVC.Extent();
423     if (!aNbP && !aNbC) {
424       continue;
425     }
426     //
427     const TopoDS_Face& aF1=(*(TopoDS_Face *)(&myDS->Shape(nF1)));
428     const TopoDS_Face& aF2=(*(TopoDS_Face *)(&myDS->Shape(nF2)));
429     //
430     Standard_Real aTolFF = Max(BRep_Tool::Tolerance(aF1), BRep_Tool::Tolerance(aF2));
431     //
432     BOPDS_FaceInfo& aFI1 = myDS->ChangeFaceInfo(nF1);
433     BOPDS_FaceInfo& aFI2 = myDS->ChangeFaceInfo(nF2);
434     //
435     aMVOnIn.Clear();
436     aMPBOnIn.Clear();
437     aMPBCommon.Clear();
438     aDMBV.Clear();
439     aMVTol.Clear();
440     aLSE.Clear();
441     //
442     myDS->SubShapesOnIn(nF1, nF2, aMVOnIn, aMPBOnIn, aMPBCommon);
443     myDS->SharedEdges(nF1, nF2, aLSE, aAllocator);
444     //
445     Standard_Boolean bHasRealSectionEdge = Standard_False;
446     // 1. Treat Points
447     for (j=0; j<aNbP; ++j) {
448       TopoDS_Vertex aV;
449       BOPDS_CoupleOfPaveBlocks aCPB;
450       //
451       BOPDS_Point& aNP=aVP.ChangeValue(j);
452       const gp_Pnt& aP=aNP.Pnt();
453       //
454       bExist=IsExistingVertex(aP, aTolFF, aMVOnIn);
455       if (!bExist) {
456         BOPTools_AlgoTools::MakeNewVertex(aP, aTolFF, aV);
457         //
458         aCPB.SetIndexInterf(i);
459         aCPB.SetIndex(j);
460         aMSCPB.Add(aV, aCPB);
461       }
462     }
463     //
464     // 2. Treat Curves
465     aMVStick.Clear();
466     aMVEF.Clear();
467     GetStickVertices(nF1, nF2, aMVStick, aMVEF, aMI);
468     //
469     for (j = 0; j < aNbC; ++j) {
470       BOPDS_Curve& aNC = aVC.ChangeValue(j);
471       // DEBt
472       aNC.InitPaveBlock1();
473       //
474       PutPavesOnCurve(aMVOnIn, aNC, nF1, nF2, aMI, aMVEF, aMVTol, aDMVLV);
475     }
476
477     // if some E-F vertex was put on a curve due to large E-F intersection range,
478     // and it also was put on another curve correctly then remove this vertex from
479     // the first curve. Detect such case if the distance to curve exceeds aTolR3D.
480     FilterPavesOnCurves(aVC);
481
482     for (j = 0; j<aNbC; ++j) {
483       BOPDS_Curve& aNC=aVC.ChangeValue(j);
484       const IntTools_Curve& aIC=aNC.Curve();
485       //
486       PutStickPavesOnCurve(aF1, aF2, aMI, aNC, aMVStick, aMVTol, aDMVLV);
487       //904/F7
488       if (aNbC == 1) {
489         PutEFPavesOnCurve(aNC, aMI, aMVEF, aMVTol, aDMVLV);
490       }
491       //
492       if (aIC.HasBounds()) {
493         aLBV.Clear();
494         //
495         PutBoundPaveOnCurve(aF1, aF2, aNC, aLBV);
496         //
497         if (!aLBV.IsEmpty()) {
498           aDMBV.Bind(j, aLBV);
499           BOPCol_ListIteratorOfListOfInteger aItI(aLBV);
500           for (; aItI.More(); aItI.Next()) {
501             aMVBounds.Add(aItI.Value());
502           }
503         }
504       }
505     }//for (j=0; j<aNbC; ++j) {
506
507     // Put closing pave if needed
508     for (j=0; j<aNbC; ++j) {
509       BOPDS_Curve& aNC=aVC.ChangeValue(j);
510       PutClosingPaveOnCurve (aNC);
511     }
512     //
513     // 3. Make section edges
514     for (j=0; j<aNbC; ++j) {
515       BOPDS_Curve& aNC=aVC.ChangeValue(j);
516       const IntTools_Curve& aIC=aNC.Curve();
517       Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
518       //
519       BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
520       Handle(BOPDS_PaveBlock)& aPB1=aNC.ChangePaveBlock1();
521       //
522       aLPB.Clear();
523       aPB1->Update(aLPB, Standard_False);
524       //
525       aItLPB.Initialize(aLPB);
526       for (; aItLPB.More(); aItLPB.Next()) {
527         Handle(BOPDS_PaveBlock)& aPB=aItLPB.ChangeValue();
528         aPB->Indices(nV1, nV2);
529         aPB->Range  (aT1, aT2);
530         //
531         if (fabs(aT1 - aT2) < Precision::PConfusion()) {
532           continue;
533         }
534         //
535         bValid2D=myContext->IsValidBlockForFaces(aT1, aT2, aIC, 
536                                                  aF1, aF2, aTolR3D);
537         if (!bValid2D) {
538           continue;
539         }
540         //
541         bExist=IsExistingPaveBlock(aPB, aNC, aLSE);
542         if (bExist) {
543           continue;
544         }
545         //
546         const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
547         const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
548         //
549         // Make Edge
550         BOPTools_AlgoTools::MakeEdge (aIC, aV1, aT1, aV2, aT2, aTolR3D, aES);
551         //
552         // check for micro edge
553         if (BOPTools_AlgoTools::IsMicroEdge(aES, myContext, Standard_False)) {
554           // If the section edge is a micro edge, i.e. the whole edge is
555           // covered by the tolerance spheres of its vertices, it will be
556           // passed into post treatment process to fuse its vertices.
557           // The edge itself will not be kept.
558           if (!aMVBounds.Contains(nV1) && !aMVBounds.Contains(nV2)) {
559             aMicroEdges.Add(aES);
560             // keep vertices for post treatment
561             aMVI.Bind(aV1, nV1);
562             aMVI.Bind(aV2, nV2);
563           }
564           continue;
565         }
566         //
567         Standard_Real aTolNew;
568         bExist=IsExistingPaveBlock(aPB, aNC, aTolR3D, aMPBOnIn, aMPBCommon, aPBOut, aTolNew);
569         if (bExist) {
570           if (!aMPBAdd.Contains(aPBOut)) {
571             Standard_Boolean bInBothFaces = Standard_True;
572             if (!myDS->IsCommonBlock(aPBOut)) {
573               Standard_Integer nE;
574               Standard_Real aTolE;
575               //
576               nE = aPBOut->Edge();
577               const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(nE);
578               aTolE = BRep_Tool::Tolerance(aE);
579               if (aTolNew < aNC.Tolerance())
580                 aTolNew = aNC.Tolerance();  // use real tolerance of intersection
581               if (aTolNew > aTolE) {
582                 UpdateEdgeTolerance(nE, aTolNew);
583               }
584               bInBothFaces = Standard_False;
585             } 
586             else {
587               bInBothFaces = (aFI1.PaveBlocksOn().Contains(aPBOut) ||
588                               aFI1.PaveBlocksIn().Contains(aPBOut))&&
589                              (aFI2.PaveBlocksOn().Contains(aPBOut) ||
590                               aFI2.PaveBlocksIn().Contains(aPBOut));
591             }
592             if (!bInBothFaces) {
593               aMPBAdd.Add(aPBOut);
594               PreparePostTreatFF(i, j, aPBOut, aMSCPB, aMVI, aLPBC);
595               // Try fusing the vertices of the existing pave block
596               // with the vertices put on the real section curve (except
597               // for technological vertices, which will be removed)
598               Standard_Integer nVOut1, nVOut2;
599               aPBOut->Indices(nVOut1, nVOut2);
600               if (nV1 != nVOut1 && nV1 != nVOut2 && !aMVBounds.Contains(nV1))
601               {
602                 aVertsOnRejectedPB.Add(aV1);
603               }
604               if (nV2 != nVOut1 && nV2 != nVOut2 && !aMVBounds.Contains(nV2))
605               {
606                 aVertsOnRejectedPB.Add(aV2);
607               }
608             }
609           }
610           continue;
611         }
612         //
613         // Make p-curves
614         BOPTools_AlgoTools::MakePCurve(aES, aF1, aF2, aIC, 
615                                        mySectionAttribute.PCurveOnS1(),
616                                        mySectionAttribute.PCurveOnS2(),
617                                        myContext);
618         //
619         // Append the Pave Block to the Curve j
620         aLPBC.Append(aPB);
621         //
622         // Keep info for post treatment 
623         BOPDS_CoupleOfPaveBlocks aCPB;
624         aCPB.SetIndexInterf(i);
625         aCPB.SetIndex(j);
626         aCPB.SetPaveBlock1(aPB);
627         //
628         aMSCPB.Add(aES, aCPB);
629         aMVI.Bind(aV1, nV1);
630         aMVI.Bind(aV2, nV2);
631         //
632         aMVTol.UnBind(nV1);
633         aMVTol.UnBind(nV2);
634         //
635         bHasRealSectionEdge = Standard_True;
636       }
637       //
638       aLPBC.RemoveFirst();
639     }//for (j=0; j<aNbC; ++j) {
640     //
641     //back to previous tolerance values for unused vertices
642     //and forget about SD groups of such vertices
643     aItMV.Initialize(aMVTol);
644     for (; aItMV.More(); aItMV.Next()) {
645       nV1 = aItMV.Key();
646       Standard_Real aTol = aItMV.Value();
647       //
648       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV1);
649       const Handle(BRep_TVertex)& TV = 
650         *((Handle(BRep_TVertex)*)&aV.TShape());
651       TV->Tolerance(aTol);
652       // reset bnd box
653       BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV1);
654       Bnd_Box& aBoxDS=aSIDS.ChangeBox();
655       aBoxDS = Bnd_Box();
656       BRepBndLib::Add(aV, aBoxDS);
657       aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
658       //
659       if (aDMVLV.IsBound(nV1))
660         aDMVLV.UnBind(nV1);
661     }
662     //
663     ProcessExistingPaveBlocks(i, aMPBOnIn, aDMBV, aMSCPB, aMVI, aMPBAdd);
664     //
665     // If the pair of faces has produced any real section edges
666     // it is necessary to check if these edges do not intersect
667     // any common IN edges of the faces. For that, all such edges
668     // are added for Post Treatment along with sections edges.
669     if (bHasRealSectionEdge) {
670       const BOPDS_IndexedMapOfPaveBlock& aMPBIn1 = aFI1.PaveBlocksIn();
671       const BOPDS_IndexedMapOfPaveBlock& aMPBIn2 = aFI2.PaveBlocksIn();
672       //
673       // For simplicity add all IN edges into the first set of section curves.
674       // These existing edges will be removed from the set on the post treatment
675       // stage in the UpdateFaceInfo function.
676       BOPDS_ListOfPaveBlock& aLPBC = aVC.ChangeValue(0).ChangePaveBlocks();
677       //
678       Standard_Integer aNbIn1 = aMPBIn1.Extent();
679       for (j = 1; j <= aNbIn1; ++j) {
680         const Handle(BOPDS_PaveBlock)& aPB = aMPBIn1(j);
681         if (aMPBIn2.Contains(aPB) && aMPBAdd.Add(aPB)) {
682           PreparePostTreatFF(i, 0, aPB, aMSCPB, aMVI, aLPBC);
683         }
684       }
685     }
686   }//for (i=0; i<aNbFF; ++i) {
687   // 
688   // post treatment
689   MakeSDVerticesFF(aDMVLV, aDMNewSD);
690   PostTreatFF(aMSCPB, aDMExEdges, aDMNewSD, aMicroEdges, aVertsOnRejectedPB, aAllocator);
691   if (HasErrors()) {
692     return;
693   }
694   // reduce tolerances of section edges where it is appropriate
695   CorrectToleranceOfSE();
696   //
697   // update face info
698   UpdateFaceInfo(aDMExEdges, aDMNewSD);
699   //Update all pave blocks
700   UpdatePaveBlocks(aDMNewSD);
701   //
702   // Treat possible common zones by trying to put each section edge
703   // into all faces, not participated in creation of that edge, as IN edge
704   PutSEInOtherFaces();
705   //
706   //-----------------------------------------------------scope t
707   aMVStick.Clear();
708   aMPBOnIn.Clear();
709   aMVOnIn.Clear();
710   aDMExEdges.Clear();
711   aMI.Clear();
712   aDMNewSD.Clear();
713 }
714
715 //=======================================================================
716 //function : MakeSDVerticesFF
717 //purpose  : 
718 //=======================================================================
719 void BOPAlgo_PaveFiller::MakeSDVerticesFF
720   (const BOPCol_DataMapOfIntegerListOfInteger& theDMVLV,
721    BOPCol_DataMapOfIntegerInteger& theDMNewSD)
722 {
723   // Create a new SD vertex for each group of coinciding vertices
724   // and put new substitutions to theDMNewSD.
725   BOPCol_DataMapIteratorOfDataMapOfIntegerListOfInteger aItG(theDMVLV);
726   for (; aItG.More(); aItG.Next()) {
727     const BOPCol_ListOfInteger& aList = aItG.Value();
728     // make SD vertices w/o creation of interfs
729     Standard_Integer nSD = MakeSDVertices(aList, Standard_False);
730     // update theDMNewSD
731     BOPCol_ListIteratorOfListOfInteger aItL(aList);
732     for (; aItL.More(); aItL.Next()) {
733       Standard_Integer nV = aItL.Value();
734       theDMNewSD.Bind(nV, nSD);
735     }
736   }
737 }
738
739 //=======================================================================
740 //function : PostTreatFF
741 //purpose  : 
742 //=======================================================================
743 void BOPAlgo_PaveFiller::PostTreatFF
744     (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMSCPB,
745      BOPDS_DataMapOfPaveBlockListOfPaveBlock& aDMExEdges,
746      BOPCol_DataMapOfIntegerInteger& aDMNewSD,
747      const BOPCol_IndexedMapOfShape& theMicroEdges,
748      const BOPCol_IndexedMapOfShape& theVertsOnRejectedPB,
749      const Handle(NCollection_BaseAllocator)& theAllocator)
750 {
751   Standard_Integer aNbS = theMSCPB.Extent();
752   if (!aNbS) {
753     return;
754   }
755   //
756   Standard_Boolean bHasPaveBlocks, bOld;
757   Standard_Integer nSx, nVSD, iX, iP, iC, j, nV, iV = 0, iE, k;
758   Standard_Integer aNbLPBx;
759   TopAbs_ShapeEnum aType;
760   TopoDS_Shape aV, aE;
761   BOPCol_ListIteratorOfListOfShape aItLS;
762   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
763   BOPDS_PDS aPDS;
764   Handle(BOPDS_PaveBlock) aPB1;
765   BOPDS_Pave aPave[2];
766   BOPDS_ShapeInfo aSI;
767   //
768   BOPCol_ListOfShape aLS(theAllocator);
769   BOPAlgo_PaveFiller aPF(theAllocator);
770   aPF.SetIsPrimary(Standard_False);
771   aPF.SetNonDestructive(myNonDestructive);
772   //
773   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
774   //
775   Standard_Integer aNbME = theMicroEdges.Extent();
776   Standard_Integer aNbVOnRPB = theVertsOnRejectedPB.Extent();
777   // 0
778   if (aNbS==1 && (aNbME == 0) && (aNbVOnRPB == 0)) {
779     const TopoDS_Shape& aS=theMSCPB.FindKey(1);
780     const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromIndex(1);
781     //
782     aType=aS.ShapeType();
783     if (aType==TopAbs_VERTEX) {
784       aSI.SetShapeType(aType);
785       aSI.SetShape(aS);
786       iV=myDS->Append(aSI);
787       //
788       iX=aCPB.IndexInterf();
789       iP=aCPB.Index();
790       BOPDS_InterfFF& aFF=aFFs(iX); 
791       BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
792       BOPDS_Point& aNP=aVNP(iP);
793       aNP.SetIndex(iV);
794     }
795     else if (aType==TopAbs_EDGE) {
796       aPB1=aCPB.PaveBlock1();
797       //
798       if (aPB1->HasEdge()) {
799         BOPDS_ListOfPaveBlock aLPBx;
800         aLPBx.Append(aPB1);
801         aDMExEdges.Bind(aPB1, aLPBx);
802       } else {
803         aSI.SetShapeType(aType);
804         aSI.SetShape(aS);
805         iE=myDS->Append(aSI);
806         //
807         aPB1->SetEdge(iE);
808       }
809     }
810     return;
811   }
812   //
813   // 1 prepare arguments
814   BOPCol_MapOfShape anAddedSD;
815   for (k=1; k<=aNbS; ++k) {
816     const TopoDS_Shape& aS=theMSCPB.FindKey(k);
817     aLS.Append(aS);
818     // add vertices-candidates for SD from the map aDMNewSD,
819     // so that they took part in fuse operation.
820     TopoDS_Iterator itV(aS);
821     for (; itV.More(); itV.Next())
822     {
823       const TopoDS_Shape& aVer = itV.Value();
824       Standard_Integer iVer = myDS->Index(aVer);
825       const Standard_Integer* pSD = aDMNewSD.Seek(iVer);
826       if (pSD)
827       {
828         const TopoDS_Shape& aVSD = myDS->Shape(*pSD);
829         if (anAddedSD.Add(aVSD))
830           aLS.Append(aVSD);
831       }
832     }
833   }
834   //
835   // The section edges considered as a micro should be
836   // specially treated - their vertices should be united and
837   // the edge itself should be removed. Thus, we add only
838   // its vertices into operation.
839   //
840   BRep_Builder aBB;
841   for (k = 1; k <= aNbME; ++k) {
842     const TopoDS_Edge& aEM = TopoDS::Edge(theMicroEdges(k));
843     //
844     TopoDS_Vertex aVerts[2];
845     TopExp::Vertices(aEM, aVerts[0], aVerts[1]);
846     for (Standard_Integer i = 0; i < 2; ++i) {
847       nV = myDS->Index(aVerts[i]);
848       const Standard_Integer* pSD = aDMNewSD.Seek(nV);
849       if (pSD) {
850         aVerts[i] = TopoDS::Vertex(myDS->Shape(*pSD));
851       }
852       //
853       if (anAddedSD.Add(aVerts[i])) {
854         aLS.Append(aVerts[i]);
855       }
856     }
857     //
858     if (aVerts[0].IsSame(aVerts[1])) {
859       continue;
860     }
861     //
862     // make sure these vertices will be united
863     const gp_Pnt& aP1 = BRep_Tool::Pnt(aVerts[0]);
864     const gp_Pnt& aP2 = BRep_Tool::Pnt(aVerts[1]);
865     //
866     Standard_Real aDist = aP1.Distance(aP2);
867     Standard_Real aTolV1 = BRep_Tool::Tolerance(aVerts[0]);
868     Standard_Real aTolV2 = BRep_Tool::Tolerance(aVerts[1]);
869     //
870     aDist -= (aTolV1 + aTolV2);
871     if (aDist > 0.) {
872       aDist /= 2.;
873       aBB.UpdateVertex(aVerts[0], aTolV1 + aDist);
874       aBB.UpdateVertex(aVerts[1], aTolV2 + aDist);
875     }
876   }
877
878   // Add vertices put on the real section curves to unify them with the
879   // vertices of the edges, by which these sections curves have been rejected
880   for (Standard_Integer i = 1; i <= aNbVOnRPB; ++i)
881   {
882     TopoDS_Shape aVer = theVertsOnRejectedPB(i);
883     Standard_Integer iVer = myDS->Index(aVer);
884     const Standard_Integer* pSD = aDMNewSD.Seek(iVer);
885     if (pSD)
886       aVer = myDS->Shape(*pSD);
887
888     if (anAddedSD.Add(aVer))
889       aLS.Append(aVer);
890   }
891   //
892   // 2 Fuse shapes
893   aPF.SetProgressIndicator(myProgressIndicator);
894   aPF.SetRunParallel(myRunParallel);
895   aPF.SetArguments(aLS);
896   aPF.Perform();
897   if (aPF.HasErrors()) {
898     AddError (new BOPAlgo_AlertPostTreatFF);
899     return;
900   }
901   aPDS=aPF.PDS();
902   //
903   // Map to store the real tolerance of the common block
904   // and avoid repeated computation of it
905   NCollection_DataMap<Handle(BOPDS_CommonBlock),
906                       Standard_Real,
907                       TColStd_MapTransientHasher> aMCBTol;
908   // Map to avoid creation of different pave blocks for
909   // the same intersection edge
910   NCollection_DataMap<Standard_Integer, Handle(BOPDS_PaveBlock)> aMEPB;
911   //
912   aItLS.Initialize(aLS);
913   for (; aItLS.More(); aItLS.Next()) {
914     const TopoDS_Shape& aSx=aItLS.Value();
915     nSx=aPDS->Index(aSx);
916     const BOPDS_ShapeInfo& aSIx=aPDS->ShapeInfo(nSx);
917     //
918     aType=aSIx.ShapeType();
919     //
920     if (aType==TopAbs_VERTEX) {
921       Standard_Boolean bIntersectionPoint = theMSCPB.Contains(aSx);
922       //
923       if (aPDS->HasShapeSD(nSx, nVSD)) {
924         aV=aPDS->Shape(nVSD);
925       }
926       else {
927         aV=aSx;
928       }
929       // index of new vertex in theDS -> iV
930       iV = myDS->Index(aV);
931       if (iV < 0) {
932         aSI.SetShapeType(aType);
933         aSI.SetShape(aV);
934         iV=myDS->Append(aSI);
935       }
936       //
937       if (!bIntersectionPoint) {
938         // save SD connection
939         nSx = myDS->Index(aSx);
940         aDMNewSD.Bind(nSx, iV);
941         myDS->AddShapeSD(nSx, iV);
942       }
943       else {
944         // update FF interference
945         const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromKey(aSx);
946         iX=aCPB.IndexInterf();
947         iP=aCPB.Index();
948         BOPDS_InterfFF& aFF=aFFs(iX);
949         BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
950         BOPDS_Point& aNP=aVNP(iP);
951         aNP.SetIndex(iV);
952       }
953     }//if (aType==TopAbs_VERTEX) {
954     //
955     else if (aType==TopAbs_EDGE) {
956       bHasPaveBlocks=aPDS->HasPaveBlocks(nSx);
957       const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromKey(aSx);
958       iX=aCPB.IndexInterf();
959       iC=aCPB.Index();
960       aPB1=aCPB.PaveBlock1();
961       //
962       bOld = aPB1->HasEdge();
963       if (bOld) {
964         BOPDS_ListOfPaveBlock aLPBx;
965         aDMExEdges.Bind(aPB1, aLPBx);
966       }
967       //
968       if (!bHasPaveBlocks) {
969         if (bOld) {
970           aDMExEdges.ChangeFind(aPB1).Append(aPB1);
971         }
972         else {
973           aSI.SetShapeType(aType);
974           aSI.SetShape(aSx);
975           iE = myDS->Append(aSI);
976           //
977           aPB1->SetEdge(iE);
978         }
979       }
980       else {
981         BOPDS_InterfFF& aFF=aFFs(iX);
982         BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
983         BOPDS_Curve& aNC=aVNC(iC);
984         BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
985         //
986         // check if edge occured to be micro edge;
987         // note we check not the edge aSx itself, but its image in aPDS
988         const BOPDS_ListOfPaveBlock& aLPBx = aPDS->PaveBlocks(nSx);
989         aNbLPBx = aLPBx.Extent();
990         if (aPDS->HasPaveBlocks(nSx) &&
991             (aNbLPBx == 0 || (aNbLPBx == 1 && !aLPBx.First()->HasShrunkData()))) {
992           BOPDS_ListIteratorOfListOfPaveBlock it(aLPBC);
993           for (; it.More(); it.Next()) {
994             if (it.Value() == aPB1) {
995               aLPBC.Remove(it);
996               break;
997             }
998           }
999           continue;
1000         }
1001         //
1002         if (bOld && !aNbLPBx) {
1003           aDMExEdges.ChangeFind(aPB1).Append(aPB1);
1004           continue;
1005         }
1006         //
1007         if (!bOld) {
1008           aItLPB.Initialize(aLPBC);
1009           for (; aItLPB.More(); aItLPB.Next()) {
1010             const Handle(BOPDS_PaveBlock)& aPBC=aItLPB.Value();
1011             if (aPBC==aPB1) {
1012               aLPBC.Remove(aItLPB);
1013               break;
1014             }
1015           }
1016         }
1017         //
1018         if (aNbLPBx) {
1019           aItLPB.Initialize(aLPBx);
1020           for (; aItLPB.More(); aItLPB.Next()) {
1021             const Handle(BOPDS_PaveBlock)& aPBx=aItLPB.Value();
1022             const Handle(BOPDS_PaveBlock) aPBRx=aPDS->RealPaveBlock(aPBx);
1023             //
1024             // update vertices of paves
1025             aPave[0] = aPBx->Pave1();
1026             aPave[1] = aPBx->Pave2();
1027             for (j=0; j<2; ++j) {
1028               nV = aPave[j].Index();
1029               aV = aPDS->Shape(nV);
1030               // index of new vertex in myDS -> iV
1031               iV = myDS->Index(aV);
1032               if (iV < 0) {
1033                 aSI.SetShapeType(TopAbs_VERTEX);
1034                 aSI.SetShape(aV);
1035                 iV = myDS->Append(aSI);
1036               }
1037               const BOPDS_Pave& aP1 = !j ? aPB1->Pave1() : aPB1->Pave2();
1038               if (aP1.Index() != iV) {
1039                 if (aP1.Parameter() == aPave[j].Parameter()) {
1040                   aDMNewSD.Bind(aP1.Index(), iV);
1041                   myDS->AddShapeSD(aP1.Index(), iV);
1042                 }
1043                 else {
1044                   // check aPDS to have the SD connection between these vertices
1045                   const TopoDS_Shape& aVPave = myDS->Shape(aP1.Index());
1046                   Standard_Integer nVnewSD, nVnew = aPDS->Index(aVPave);
1047                   if (aPDS->HasShapeSD(nVnew, nVnewSD)) {
1048                     if (nVnewSD == nV) {
1049                       aDMNewSD.Bind(aP1.Index(), iV);
1050                       myDS->AddShapeSD(aP1.Index(), iV);
1051                     }
1052                   }
1053                 }
1054               }
1055               //
1056               aPave[j].SetIndex(iV);
1057             }
1058             //
1059             // add edge
1060             aE=aPDS->Shape(aPBRx->Edge());
1061             iE = myDS->Index(aE);
1062             if (iE < 0) {
1063               aSI.SetShapeType(aType);
1064               aSI.SetShape(aE);
1065               iE=myDS->Append(aSI);
1066             }
1067             //
1068             // update real edge tolerance according to distances in common block if any
1069             if (aPDS->IsCommonBlock(aPBRx)) {
1070               const Handle(BOPDS_CommonBlock)& aCB = aPDS->CommonBlock(aPBRx);
1071               Standard_Real *pTol = aMCBTol.ChangeSeek(aCB);
1072               if (!pTol) {
1073                 Standard_Real aTol = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, aPDS, aPF.Context());
1074                 pTol = aMCBTol.Bound(aCB, aTol);
1075               }
1076               //
1077               if (aNC.Tolerance() < *pTol) {
1078                 aNC.SetTolerance(*pTol);
1079               }
1080             }
1081             // append new PaveBlock to aLPBC
1082             Handle(BOPDS_PaveBlock) *pPBC = aMEPB.ChangeSeek(iE);
1083             if (!pPBC) {
1084               pPBC = aMEPB.Bound(iE, new BOPDS_PaveBlock());
1085               BOPDS_Pave aPaveR1, aPaveR2;
1086               aPaveR1 = aPBRx->Pave1();
1087               aPaveR2 = aPBRx->Pave2();
1088               aPaveR1.SetIndex(myDS->Index(aPDS->Shape(aPaveR1.Index())));
1089               aPaveR2.SetIndex(myDS->Index(aPDS->Shape(aPaveR2.Index())));
1090               //
1091               (*pPBC)->SetPave1(aPaveR1);
1092               (*pPBC)->SetPave2(aPaveR2);
1093               (*pPBC)->SetEdge(iE);
1094             }
1095             //
1096             if (bOld) {
1097               (*pPBC)->SetOriginalEdge(aPB1->OriginalEdge());
1098               aDMExEdges.ChangeFind(aPB1).Append(*pPBC);
1099             }
1100             else {
1101               aLPBC.Append(*pPBC);
1102             }
1103           }
1104         }
1105       }
1106     }//else if (aType==TopAbs_EDGE)
1107   }//for (; aItLS.More(); aItLS.Next()) {
1108
1109   // Update SD for vertices that did not participate in operation
1110   BOPCol_DataMapOfIntegerInteger::Iterator itDM(aDMNewSD);
1111   for (; itDM.More(); itDM.Next())
1112   {
1113     const Standard_Integer* pSD = aDMNewSD.Seek(itDM.Value());
1114     if (pSD)
1115     {
1116       itDM.ChangeValue() = *pSD;
1117       myDS->AddShapeSD(itDM.Key(), *pSD);
1118     }
1119   }
1120   return;
1121 }
1122
1123 //=======================================================================
1124 //function : UpdateFaceInfo
1125 //purpose  : 
1126 //=======================================================================
1127 void BOPAlgo_PaveFiller::UpdateFaceInfo
1128   (BOPDS_DataMapOfPaveBlockListOfPaveBlock& theDME,
1129    const BOPCol_DataMapOfIntegerInteger& theDMV)
1130 {
1131   Standard_Integer i, j, nV1, nF1, nF2, 
1132                    aNbFF, aNbC, aNbP;
1133   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
1134   BOPCol_MapOfInteger aMF;
1135   //
1136   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
1137   aNbFF=aFFs.Extent();
1138   //
1139   //1. Sections (curves, points);
1140   for (i=0; i<aNbFF; ++i) {
1141     BOPDS_InterfFF& aFF=aFFs(i);
1142     aFF.Indices(nF1, nF2);
1143     //
1144     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
1145     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
1146     //
1147     // 1.1. Section edges
1148     BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
1149     aNbC=aVNC.Extent();
1150     for (j=0; j<aNbC; ++j) {
1151       BOPDS_Curve& aNC=aVNC(j);
1152       BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
1153       //
1154       // Add section edges to face info
1155       aItLPB.Initialize(aLPBC);
1156       for (; aItLPB.More(); ) {
1157         const Handle(BOPDS_PaveBlock)& aPB=aItLPB.Value();
1158         //
1159         // Treat existing pave blocks
1160         if (theDME.IsBound(aPB)) {
1161           BOPDS_ListOfPaveBlock& aLPB=theDME.ChangeFind(aPB);
1162           UpdateExistingPaveBlocks(aPB, aLPB, nF1, nF2);
1163           aLPBC.Remove(aItLPB);
1164           continue;
1165         }
1166         //
1167         aFI1.ChangePaveBlocksSc().Add(aPB);
1168         aFI2.ChangePaveBlocksSc().Add(aPB);
1169         aItLPB.Next();
1170       }
1171     }
1172     //
1173     // 1.2. Section vertices
1174     const BOPDS_VectorOfPoint& aVNP=aFF.Points();
1175     aNbP=aVNP.Extent();
1176     for (j=0; j<aNbP; ++j) {
1177       const BOPDS_Point& aNP=aVNP(j);
1178       nV1=aNP.Index();
1179       if (nV1<0) {
1180         continue;
1181       }
1182       aFI1.ChangeVerticesSc().Add(nV1);
1183       aFI2.ChangeVerticesSc().Add(nV1);
1184     }
1185     //
1186     aMF.Add(nF1);
1187     aMF.Add(nF2);
1188   }
1189   //
1190   Standard_Boolean bVerts, bEdges;
1191   //
1192   bVerts = theDMV.Extent() > 0;
1193   bEdges = theDME.Extent() > 0;
1194   //
1195   if (!bVerts && !bEdges) {
1196     return;
1197   }
1198   //
1199   // 2. Update Face Info information with new vertices and new
1200   //    pave blocks created in PostTreatFF from existing ones
1201   Standard_Integer nV2, aNbPB;
1202   BOPCol_MapIteratorOfMapOfInteger aItMF;
1203   BOPCol_DataMapIteratorOfDataMapOfIntegerInteger aItMV;
1204   //
1205   aItMF.Initialize(aMF);
1206   for (; aItMF.More(); aItMF.Next()) {
1207     nF1 = aItMF.Value();
1208     //
1209     BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(nF1);
1210     //
1211     // 2.1. Update information about vertices
1212     if (bVerts) {
1213       BOPCol_MapOfInteger& aMVOn = aFI.ChangeVerticesOn();
1214       BOPCol_MapOfInteger& aMVIn = aFI.ChangeVerticesIn();
1215       //
1216       aItMV.Initialize(theDMV);
1217       for (; aItMV.More(); aItMV.Next()) {
1218         nV1 = aItMV.Key();
1219         nV2 = aItMV.Value();
1220         //
1221         if (aMVOn.Remove(nV1)) {
1222           aMVOn.Add(nV2);
1223         }
1224         //
1225         if (aMVIn.Remove(nV1)) {
1226           aMVIn.Add(nV2);
1227         }
1228       } // for (; aItMV.More(); aItMV.Next()) {
1229     } // if (bVerts) {
1230     //
1231     // 2.2. Update information about pave blocks
1232     if (bEdges) {
1233       BOPDS_IndexedMapOfPaveBlock& aMPBOn = aFI.ChangePaveBlocksOn();
1234       BOPDS_IndexedMapOfPaveBlock& aMPBIn = aFI.ChangePaveBlocksIn();
1235       //
1236       BOPDS_IndexedMapOfPaveBlock aMPBCopy;
1237       for (i = 0; i < 2; ++i) {
1238         BOPDS_IndexedMapOfPaveBlock& aMPBOnIn = !i ? aMPBOn : aMPBIn;
1239         aMPBCopy = aMPBOnIn;
1240         aMPBOnIn.Clear();
1241         //
1242         aNbPB = aMPBCopy.Extent();
1243         for (j = 1; j <= aNbPB; ++j) {
1244           const Handle(BOPDS_PaveBlock)& aPB = aMPBCopy(j);
1245           if (theDME.IsBound(aPB)) {
1246             const BOPDS_ListOfPaveBlock& aLPB = theDME.Find(aPB);
1247             if (aLPB.IsEmpty()) {
1248               aMPBOnIn.Add(aPB);
1249               continue;
1250             }
1251             //
1252             aItLPB.Initialize(aLPB);
1253             for (; aItLPB.More(); aItLPB.Next()) {
1254               const Handle(BOPDS_PaveBlock)& aPB1 = aItLPB.Value();
1255               aMPBOnIn.Add(aPB1);
1256             }
1257           }
1258           else {
1259             aMPBOnIn.Add(aPB);
1260           }
1261         } // for (j = 1; j <= aNbPB; ++j) {
1262       } // for (i = 0; i < 2; ++i) {
1263     } // if (bEdges) {
1264   }
1265 }
1266 //=======================================================================
1267 //function : IsExistingVertex
1268 //purpose  : 
1269 //=======================================================================
1270 Standard_Boolean BOPAlgo_PaveFiller::IsExistingVertex
1271   (const gp_Pnt& aP,
1272    const Standard_Real theTolR3D,
1273    const BOPCol_MapOfInteger& aMVOnIn)const
1274 {
1275   Standard_Boolean bRet;
1276   Standard_Integer nV, iFlag;
1277   Standard_Real aTolCheck;
1278   gp_Pnt aPV;
1279   Bnd_Box aBoxP;
1280   BOPCol_MapIteratorOfMapOfInteger aIt;
1281   //
1282   aTolCheck = theTolR3D + myFuzzyValue;
1283   bRet=Standard_True;
1284   //
1285   aBoxP.Add(aP);
1286   aBoxP.Enlarge(theTolR3D);
1287   //
1288   aIt.Initialize(aMVOnIn);
1289   for (; aIt.More(); aIt.Next()) {
1290     nV=aIt.Value();
1291     const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1292     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aSIV.Shape()));
1293     const Bnd_Box& aBoxV=aSIV.Box();
1294     //
1295     if (!aBoxP.IsOut(aBoxV)) {
1296       iFlag=BOPTools_AlgoTools::ComputeVV(aV, aP, aTolCheck);
1297       if (!iFlag) {
1298         return bRet;
1299       }
1300     }
1301   }
1302   return !bRet;
1303 }
1304 //=======================================================================
1305 //function : IsExistingPaveBlock
1306 //purpose  : 
1307 //=======================================================================
1308 Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
1309   (const Handle(BOPDS_PaveBlock)& thePB,
1310    const BOPDS_Curve& theNC,
1311    const BOPCol_ListOfInteger& theLSE)
1312 {
1313   Standard_Boolean bRet=Standard_True;
1314   //
1315   if (theLSE.IsEmpty()) {
1316     return !bRet;
1317   } 
1318   //
1319   Standard_Real aT1, aT2, aTm, aTx, aTolE, aTolCheck, aTol, aDist;
1320   Standard_Integer nE, iFlag, nV1, nV2;
1321   gp_Pnt aPm;
1322   Bnd_Box aBoxPm;
1323   BOPCol_ListIteratorOfListOfInteger aItLI;
1324   //
1325   thePB->Range(aT1, aT2);
1326   thePB->Indices(nV1, nV2);
1327   const TopoDS_Vertex &aV1 = TopoDS::Vertex(myDS->Shape(nV1)),
1328                       &aV2 = TopoDS::Vertex(myDS->Shape(nV2));
1329   const Standard_Real aTolV1 = BRep_Tool::Tolerance(aV1),
1330                       aTolV2 = BRep_Tool::Tolerance(aV2);
1331
1332   aTol = Max(aTolV1, aTolV2);
1333
1334   aTm=IntTools_Tools::IntermediatePoint (aT1, aT2);
1335   theNC.Curve().D0(aTm, aPm);
1336   aBoxPm.Add(aPm);
1337   aBoxPm.Enlarge(aTol);
1338   //
1339   aItLI.Initialize(theLSE);
1340   for (; aItLI.More(); aItLI.Next()) {
1341     nE=aItLI.Value();
1342     if (nE < 0)
1343       continue;
1344     const BOPDS_ShapeInfo& aSIE=myDS->ChangeShapeInfo(nE);
1345     const Bnd_Box& aBoxE=aSIE.Box();
1346     if (!aBoxE.IsOut(aBoxPm)) {
1347       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aSIE.Shape()));
1348       aTolE = BRep_Tool::Tolerance(aE);
1349       aTolCheck = Max(aTolE, aTol) + myFuzzyValue;
1350       iFlag = myContext->ComputePE(aPm, aTolCheck, aE, aTx, aDist);
1351       if (!iFlag) {
1352         if (aDist > aTolE)
1353           // Update tolerance of the edge
1354           UpdateEdgeTolerance(nE, aDist);
1355         return bRet;
1356       }
1357     }
1358   }
1359   return !bRet;
1360 }
1361
1362 //=======================================================================
1363 //function : IsExistingPaveBlock
1364 //purpose  : 
1365 //=======================================================================
1366 Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
1367     (const Handle(BOPDS_PaveBlock)& thePB,
1368      const BOPDS_Curve& theNC,
1369      const Standard_Real theTolR3D,
1370      const BOPDS_IndexedMapOfPaveBlock& theMPBOnIn,
1371      const BOPDS_MapOfPaveBlock& theMPBCommon,
1372      Handle(BOPDS_PaveBlock)& aPBOut,
1373      Standard_Real& theTolNew)
1374 {
1375   Standard_Boolean bRet;
1376   Standard_Real aT1, aT2, aTm, aTx, aTolCheck;
1377   Standard_Integer nSp, iFlag1, iFlag2, nV11, nV12, nV21, nV22, i, aNbPB;
1378   gp_Pnt aP1, aPm, aP2;
1379   Bnd_Box aBoxP1, aBoxPm, aBoxP2, aBoxTmp;
1380   //
1381   bRet=Standard_False;
1382   aTolCheck = theTolR3D + myFuzzyValue;
1383   const IntTools_Curve& aIC=theNC.Curve();
1384   //
1385   thePB->Range(aT1, aT2);
1386   thePB->Indices(nV11, nV12);
1387   const Standard_Real aTolV11 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV11)));
1388   const Standard_Real aTolV12 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV12)));
1389   const Standard_Real aTolV1 = Max(aTolV11, aTolV12) + myFuzzyValue;
1390
1391   //first point
1392   aIC.D0(aT1, aP1);
1393   aBoxP1.Add(aP1);
1394   aBoxP1.Enlarge(aTolV11);
1395   //intermediate point
1396   aTm=IntTools_Tools::IntermediatePoint (aT1, aT2);
1397   aIC.D0(aTm, aPm);
1398   aBoxPm.Add(aPm);
1399   //last point
1400   aIC.D0(aT2, aP2);
1401   aBoxP2.Add(aP2);
1402   aBoxP2.Enlarge(aTolV12);
1403   //
1404   theTolNew = 0.;
1405   aNbPB = theMPBOnIn.Extent();
1406   for (i = 1; i <= aNbPB; ++i) {
1407     const Handle(BOPDS_PaveBlock)& aPB = theMPBOnIn(i);
1408     aPB->Indices(nV21, nV22);
1409     const Standard_Real aTolV21 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV21)));
1410     const Standard_Real aTolV22 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV22)));
1411     const Standard_Real aTolV2 = Max(aTolV21, aTolV22) + myFuzzyValue;
1412     nSp=aPB->Edge();
1413     if (nSp < 0)
1414       continue;
1415     const BOPDS_ShapeInfo& aSISp=myDS->ChangeShapeInfo(nSp);
1416     const TopoDS_Edge& aSp=(*(TopoDS_Edge *)(&aSISp.Shape()));
1417     const Bnd_Box& aBoxSp=aSISp.Box();
1418     //
1419     iFlag1 = (nV11 == nV21 || nV11 == nV22) ? 2 : 
1420       (!aBoxSp.IsOut(aBoxP1) ? 1 : 0);
1421     iFlag2 = (nV12 == nV21 || nV12 == nV22) ? 2 : 
1422       (!aBoxSp.IsOut(aBoxP2) ? 1 : 0);
1423     if (iFlag1 && iFlag2) {
1424       Standard_Real aDist = 0.;
1425
1426       Standard_Real aRealTol = aTolCheck;
1427       if (myDS->IsCommonBlock(aPB))
1428       {
1429         aRealTol = Max(aRealTol, Max(aTolV1, aTolV2));
1430         if (theMPBCommon.Contains(aPB))
1431           // for an edge, which is a common block with a face,
1432           // increase the chance to coincide with section curve
1433           aRealTol *= 2.;
1434       }
1435       
1436       aBoxTmp = aBoxPm;
1437       aBoxTmp.Enlarge(aRealTol);
1438
1439       if (aBoxSp.IsOut(aBoxTmp) || myContext->ComputePE(aPm, 
1440                                                         aRealTol,
1441                                                         aSp, 
1442                                                         aTx, theTolNew)) {
1443         continue;
1444       }
1445       //
1446       if (iFlag1 == 1) {
1447         iFlag1 = !myContext->ComputePE(aP1, aRealTol, aSp, aTx, aDist);
1448         if (iFlag1 && theTolNew < aDist)
1449           theTolNew = aDist;
1450       }
1451       //
1452       if (iFlag2 == 1) {
1453         iFlag2 = !myContext->ComputePE(aP2, aRealTol, aSp, aTx, aDist);
1454         if (iFlag2 && theTolNew < aDist)
1455           theTolNew = aDist;
1456       }
1457       //
1458       if (iFlag1 && iFlag2) {
1459         aPBOut = aPB;
1460         bRet=Standard_True;
1461         break;
1462       }
1463     }
1464   }
1465   return bRet;
1466 }
1467 //=======================================================================
1468 //function : PutBoundPaveOnCurve
1469 //purpose  : 
1470 //=======================================================================
1471 void BOPAlgo_PaveFiller::PutBoundPaveOnCurve(const TopoDS_Face& aF1,
1472                                              const TopoDS_Face& aF2,
1473                                              BOPDS_Curve& aNC,
1474                                              BOPCol_ListOfInteger& aLVB)
1475 {
1476   Standard_Boolean bVF;
1477   Standard_Integer nV, iFlag, nVn, j, aNbEP;
1478   Standard_Real aT[2], aTmin, aTmax, aTV, aTol, aTolVnew;
1479   gp_Pnt aP[2];
1480   TopoDS_Vertex aVn;
1481   BOPDS_ListIteratorOfListOfPave aItLP;
1482   BOPDS_Pave aPn, aPMM[2];
1483   //
1484   aTolVnew = Precision::Confusion();
1485   //
1486   const IntTools_Curve& aIC=aNC.Curve();
1487   aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
1488   Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
1489   //
1490   Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
1491   const BOPDS_ListOfPave& aLP=aPB->ExtPaves();
1492   //
1493   aNbEP=aLP.Extent();
1494   if (aNbEP) {
1495     aTmin=1.e10;
1496     aTmax=-aTmin;
1497     //
1498     aItLP.Initialize(aLP);
1499     for (; aItLP.More(); aItLP.Next()) {
1500       const BOPDS_Pave& aPv=aItLP.Value();
1501       aPv.Contents(nV, aTV);
1502       if (aTV<aTmin) {
1503         aPMM[0]=aPv;
1504         aTmin=aTV;
1505       }
1506       if (aTV>aTmax) {
1507         aPMM[1]=aPv;
1508         aTmax=aTV;
1509       }
1510     }
1511   }
1512   //
1513   for (j=0; j<2; ++j) {
1514     //if curve is closed, process only one bound
1515     if (j && aP[1].IsEqual(aP[0], aTolVnew)) {
1516       continue;
1517     }
1518     //
1519     iFlag=1;
1520     //
1521     if (aNbEP) {
1522       Bnd_Box aBoxP;
1523       //
1524       aBoxP.Set(aP[j]);
1525       aTol = aTolR3D+Precision::Confusion();
1526       aBoxP.Enlarge(aTol);
1527       const BOPDS_Pave& aPV=aPMM[j];
1528       nV=aPV.Index();
1529       const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1530       const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aSIV.Shape()));
1531       const Bnd_Box& aBoxV=aSIV.Box();
1532       if (!aBoxP.IsOut(aBoxV)){
1533         iFlag=BOPTools_AlgoTools::ComputeVV(aV, aP[j], aTol);
1534       }
1535     }
1536     if (iFlag) {
1537       // 900/L5
1538       bVF=myContext->IsValidPointForFaces (aP[j], aF1, aF2, aTolR3D);
1539       if (!bVF) {
1540         continue;
1541       }
1542       //
1543       BOPDS_ShapeInfo aSIVn;
1544       //
1545       BOPTools_AlgoTools::MakeNewVertex(aP[j], aTolR3D, aVn);
1546       aSIVn.SetShapeType(TopAbs_VERTEX);
1547       aSIVn.SetShape(aVn);
1548       //
1549       nVn=myDS->Append(aSIVn);
1550       //
1551       aPn.SetIndex(nVn);
1552       aPn.SetParameter(aT[j]);
1553       aPB->AppendExtPave(aPn);
1554       //
1555       aVn=(*(TopoDS_Vertex *)(&myDS->Shape(nVn)));
1556       BOPTools_AlgoTools::UpdateVertex (aIC, aT[j], aVn);
1557       //
1558       aTolVnew = BRep_Tool::Tolerance(aVn);
1559       //
1560       BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nVn);
1561       Bnd_Box& aBoxDS=aSIDS.ChangeBox();
1562       BRepBndLib::Add(aVn, aBoxDS);
1563       aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
1564       //
1565       aLVB.Append(nVn);
1566     }
1567   }
1568 }
1569
1570 //=======================================================================
1571 //function : PutPavesOnCurve
1572 //purpose  : 
1573 //=======================================================================
1574 void BOPAlgo_PaveFiller::PutPavesOnCurve
1575   (const BOPCol_MapOfInteger& aMVOnIn,
1576    BOPDS_Curve& aNC,
1577    const Standard_Integer nF1,
1578    const Standard_Integer nF2,
1579    const BOPCol_MapOfInteger& aMI,
1580    const BOPCol_MapOfInteger& aMVEF,
1581    BOPCol_DataMapOfIntegerReal& aMVTol,
1582    BOPCol_DataMapOfIntegerListOfInteger& aDMVLV)
1583 {
1584   Standard_Boolean bInBothFaces;
1585   Standard_Integer nV;
1586   BOPCol_MapIteratorOfMapOfInteger aIt;
1587   //
1588   const Bnd_Box& aBoxC=aNC.Box();
1589   Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
1590   //
1591   //Put EF vertices first
1592   aIt.Initialize(aMVEF);
1593   for (; aIt.More(); aIt.Next()) {
1594     nV=aIt.Value();
1595     PutPaveOnCurve(nV, aTolR3D, aNC, aMI, aMVTol, aDMVLV, 2);
1596   }
1597   //Put all other vertices
1598   aIt.Initialize(aMVOnIn);
1599   for (; aIt.More(); aIt.Next()) {
1600     nV=aIt.Value();
1601     if (aMVEF.Contains(nV)) {
1602       continue;
1603     }
1604     //
1605     const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1606     const Bnd_Box& aBoxV=aSIV.Box();
1607     //
1608     if (aBoxC.IsOut(aBoxV)){
1609       continue;
1610     }
1611     if (!myDS->IsNewShape(nV)) {
1612       const BOPDS_FaceInfo& aFI1 = myDS->FaceInfo(nF1);
1613       const BOPDS_FaceInfo& aFI2 = myDS->FaceInfo(nF2);
1614       //
1615       bInBothFaces = (aFI1.VerticesOn().Contains(nV) ||
1616                       aFI1.VerticesIn().Contains(nV))&&
1617                      (aFI2.VerticesOn().Contains(nV) ||
1618                       aFI2.VerticesIn().Contains(nV));
1619       if (!bInBothFaces) {
1620         continue;
1621       }
1622     }
1623     //
1624     PutPaveOnCurve(nV, aTolR3D, aNC, aMI, aMVTol, aDMVLV, 1);
1625   }
1626 }
1627
1628 //=======================================================================
1629 //function : FilterPavesOnCurves
1630 //purpose  : 
1631 //=======================================================================
1632 namespace {
1633   struct PaveBlockDist {
1634     Handle(BOPDS_PaveBlock) PB;
1635     Standard_Real Dist; // square distance from vertex to the paveblock
1636     Standard_Real SinAngle; // sinus of angle between projection vector 
1637     // and tangent at projection point
1638     Standard_Real Tolerance; // tolerance of the section curve
1639   };
1640 }
1641 void BOPAlgo_PaveFiller::FilterPavesOnCurves(const BOPDS_VectorOfCurve& theVNC)
1642 {
1643   // For each vertex found in ExtPaves of pave blocks of section curves
1644   // collect list of pave blocks with distance to the curve
1645   NCollection_IndexedDataMap<Standard_Integer,NCollection_List<PaveBlockDist> > aIDMVertPBs;
1646   Standard_Integer i;
1647   const Standard_Real anEps = gp::Resolution();
1648   for (i = 0; i < theVNC.Extent(); ++i)
1649   {
1650     const BOPDS_Curve& aNC = theVNC(i);
1651     const IntTools_Curve& aIC = aNC.Curve();
1652     const Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
1653     GeomAdaptor_Curve aGAC(aIC.Curve());
1654     const Handle(BOPDS_PaveBlock)& aPB = aNC.PaveBlocks().First();
1655     const BOPDS_ListOfPave& aPaves = aPB->ExtPaves();
1656     BOPDS_ListOfPave::Iterator itPaves(aPaves);
1657     for (; itPaves.More(); itPaves.Next())
1658     {
1659       const BOPDS_Pave& aPave = itPaves.Value();
1660       Standard_Integer nV = aPave.Index();
1661       const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
1662       // compute distance from vertex to the point on curve with vertex parameter
1663       gp_Pnt aPV = BRep_Tool::Pnt(aV);
1664       Standard_Real aPar = aPave.Parameter();
1665       gp_Pnt aPonC;
1666       gp_Vec aD1;
1667       aGAC.D1(aPar, aPonC, aD1);
1668       gp_Vec aProjVec(aPV, aPonC);
1669       Standard_Real aSqDist = aProjVec.SquareMagnitude();
1670       Standard_Real aSqD1Mod = aD1.SquareMagnitude();
1671       Standard_Real aSin = aProjVec.CrossSquareMagnitude(aD1);
1672       if (aSqDist > anEps && aSqD1Mod > anEps)
1673         aSin = sqrt(aSin / aSqDist / aSqD1Mod);
1674       NCollection_List<PaveBlockDist>* pList = aIDMVertPBs.ChangeSeek(nV);
1675       if (!pList)
1676         pList = &aIDMVertPBs.ChangeFromIndex(aIDMVertPBs.Add(nV, NCollection_List<PaveBlockDist>()));
1677       PaveBlockDist aPBD = { aPB, aSqDist, aSin, aTolR3D };
1678       pList->Append(aPBD);
1679     }
1680   }
1681
1682   // Process each vertex
1683   const Standard_Real aSinAngleMin = 0.5; // angle below which projection is suspicious
1684   for (i = 1; i <= aIDMVertPBs.Extent(); i++)
1685   {
1686     Standard_Integer nV = aIDMVertPBs.FindKey(i);
1687     const NCollection_List<PaveBlockDist>& aList = aIDMVertPBs(i);
1688     // Find a pave with minimal distance
1689     Standard_Real aMinDist = RealLast();
1690     Handle(BOPDS_PaveBlock) aPBMinDist;
1691     NCollection_List<PaveBlockDist>::Iterator itL(aList);
1692     for (; itL.More(); itL.Next())
1693     {
1694       const PaveBlockDist& aPBD = itL.Value();
1695       if (aPBD.Dist < aMinDist)
1696       {
1697         aMinDist = aPBD.Dist;
1698         aPBMinDist = aPBD.PB;
1699       }
1700     }
1701     // Remove a vertex from a pave block if the distance is greater than the tolerance 
1702     // and there are other pave blocks for which the distance is less than the current.
1703     // Do not remove a vertex if it is projected on the curve with quite large angle
1704     // (see test bugs modalg_6 bug27761).
1705     for (itL.Init(aList); itL.More(); itL.Next())
1706     {
1707       const PaveBlockDist& aPBD = itL.Value();
1708       Standard_Real aCheckDist = 100. * Max(aPBD.Tolerance*aPBD.Tolerance, aMinDist);
1709       if (aPBD.Dist > aCheckDist && aPBD.SinAngle < aSinAngleMin)
1710       {
1711         aPBD.PB->RemoveExtPave(nV);
1712       }
1713     }
1714   }
1715 }
1716
1717 //=======================================================================
1718 //function : ExtendedTolerance
1719 //purpose  : 
1720 //=======================================================================
1721 Standard_Boolean BOPAlgo_PaveFiller::ExtendedTolerance
1722   (const Standard_Integer nV,
1723    const BOPCol_MapOfInteger& aMI,
1724    Standard_Real& aTolVExt,
1725    const Standard_Integer aType)
1726 {
1727   Standard_Boolean bFound = Standard_False;
1728   if (!(myDS->IsNewShape(nV))) {
1729     return bFound;
1730   }
1731   //
1732   Standard_Integer i, k, aNbLines, aNbInt;
1733   Standard_Real aT11, aT12, aD1, aD2, aD;
1734   TopoDS_Vertex aV;
1735   gp_Pnt aPV, aP11, aP12;
1736   //
1737   k = 0;
1738   aNbInt = 2;
1739   if (aType == 1) {
1740     aNbInt = 1;
1741   } else if (aType == 2) {
1742     k = 1;
1743   }
1744   //
1745   aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
1746   aPV=BRep_Tool::Pnt(aV);
1747   //
1748   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
1749   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
1750   //
1751   for (; k<aNbInt; ++k) {
1752     aNbLines = !k ? aEEs.Extent() : aEFs.Extent();
1753     for (i = 0; i < aNbLines; ++i) {
1754       BOPDS_Interf *aInt = !k ? (BOPDS_Interf*) (&aEEs(i)) :
1755         (BOPDS_Interf*) (&aEFs(i));
1756       if (aInt->IndexNew() == nV) {
1757         if (aMI.Contains(aInt->Index1()) && 
1758             aMI.Contains(aInt->Index2())) {
1759           const IntTools_CommonPrt& aComPrt = !k ? aEEs(i).CommonPart() :
1760             aEFs(i).CommonPart();
1761           //
1762           const TopoDS_Edge& aE1=aComPrt.Edge1();
1763           aComPrt.Range1(aT11, aT12);
1764           BOPTools_AlgoTools::PointOnEdge(aE1, aT11, aP11);
1765           BOPTools_AlgoTools::PointOnEdge(aE1, aT12, aP12);
1766           aD1=aPV.Distance(aP11);
1767           aD2=aPV.Distance(aP12);
1768           aD=(aD1>aD2)? aD1 : aD2;
1769           if (aD>aTolVExt) {
1770             aTolVExt=aD;
1771           }
1772           return !bFound;
1773         }//if (aMI.Contains(aEF.Index1()) && aMI.Contains(aEF.Index2())) {
1774       }//if (aInt->IndexNew() == nV) {
1775     }//for (i = 0; i < aNbLines; ++i) {
1776   }//for (k=0; k<2; ++k) {
1777   return bFound;
1778 }
1779
1780 //=======================================================================
1781 //function : GetEFPnts
1782 //purpose  : 
1783 //=======================================================================
1784 void BOPAlgo_PaveFiller::GetEFPnts
1785   (const Standard_Integer nF1,
1786    const Standard_Integer nF2,
1787    IntSurf_ListOfPntOn2S& aListOfPnts)
1788 {
1789   Standard_Integer nE, nF, nFOpposite, aNbEFs, i;
1790   Standard_Real U1, U2, V1, V2, f, l;
1791   BOPCol_MapOfInteger aMI;
1792   //
1793   //collect indexes of all shapes from nF1 and nF2.
1794   GetFullShapeMap(nF1, aMI);
1795   GetFullShapeMap(nF2, aMI);
1796   //
1797   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
1798   aNbEFs = aEFs.Extent();
1799   //
1800   for(i = 0; i < aNbEFs; ++i) {
1801     const BOPDS_InterfEF& aEF = aEFs(i);
1802     if (aEF.HasIndexNew()) {
1803       aEF.Indices(nE, nFOpposite);
1804       if(aMI.Contains(nE) && aMI.Contains(nFOpposite)) {
1805         const IntTools_CommonPrt& aCP = aEF.CommonPart();
1806         Standard_Real aPar = aCP.VertexParameter1();
1807         const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&myDS->Shape(nE)));
1808         const TopoDS_Face& aFOpposite = 
1809           (*(TopoDS_Face*)(&myDS->Shape(nFOpposite)));
1810         //
1811         const Handle(Geom_Curve)& aCurve = BRep_Tool::Curve(aE, f, l);
1812         //
1813         nF = (nFOpposite == nF1) ? nF2 : nF1;
1814         const TopoDS_Face& aF = (*(TopoDS_Face*)(&myDS->Shape(nF)));
1815         Handle(Geom2d_Curve) aPCurve = 
1816           BRep_Tool::CurveOnSurface(aE, aF, f, l);
1817         //
1818         GeomAPI_ProjectPointOnSurf& aProj=myContext->ProjPS(aFOpposite);
1819         //
1820         gp_Pnt aPoint;
1821         aCurve->D0(aPar, aPoint);
1822         IntSurf_PntOn2S aPnt;
1823         if(!aPCurve.IsNull()) {
1824           gp_Pnt2d aP2d = aPCurve->Value(aPar);
1825           aProj.Perform(aPoint);
1826           if(aProj.IsDone()) {
1827             aProj.LowerDistanceParameters(U1,V1);
1828             if (nF == nF1) {
1829               aPnt.SetValue(aP2d.X(),aP2d.Y(),U1,V1);
1830             } else {
1831               aPnt.SetValue(U1,V1,aP2d.X(),aP2d.Y());
1832             }
1833             aListOfPnts.Append(aPnt);
1834           }
1835         }
1836         else {
1837           GeomAPI_ProjectPointOnSurf& aProj1 = myContext->ProjPS(aF);
1838           aProj1.Perform(aPoint);
1839           aProj.Perform(aPoint);
1840           if(aProj1.IsDone() && aProj.IsDone()){
1841             aProj1.LowerDistanceParameters(U1,V1);
1842             aProj.LowerDistanceParameters(U2,V2);
1843             if (nF == nF1) {
1844               aPnt.SetValue(U1,V1,U2,V2);
1845             } else {
1846               aPnt.SetValue(U2,V2,U1,V1);
1847             }
1848             aListOfPnts.Append(aPnt);
1849           }
1850         }
1851       }
1852     }
1853   }
1854 }
1855
1856 //=======================================================================
1857 //function : PutEFPavesOnCurve
1858 //purpose  : 
1859 //=======================================================================
1860   void BOPAlgo_PaveFiller::PutEFPavesOnCurve
1861   (BOPDS_Curve& aNC,
1862    const BOPCol_MapOfInteger& aMI,
1863    const BOPCol_MapOfInteger& aMVEF,
1864    BOPCol_DataMapOfIntegerReal& aMVTol,
1865    BOPCol_DataMapOfIntegerListOfInteger& aDMVLV)
1866 {
1867   if (!aMVEF.Extent()) {
1868     return;
1869   }
1870   //
1871   const IntTools_Curve& aIC=aNC.Curve();
1872   GeomAbs_CurveType aTypeC;
1873   aTypeC=aIC.Type();
1874   if (!(aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve)) {
1875     return;
1876   }
1877   //
1878   Standard_Integer nV;
1879   BOPCol_MapOfInteger aMV;
1880   //
1881   aMV.Assign(aMVEF);
1882   RemoveUsedVertices(aNC, aMV);
1883   if (!aMV.Extent()) {
1884     return;
1885   }
1886   //
1887   Standard_Real aDist;
1888   BOPDS_Pave aPave;
1889   //
1890   const Handle(Geom_Curve)& aC3D=aIC.Curve();
1891   GeomAPI_ProjectPointOnCurve& aProjPT = myContext->ProjPT(aC3D);
1892   //
1893   BOPCol_MapIteratorOfMapOfInteger aItMI;
1894   aItMI.Initialize(aMV);
1895   for (; aItMI.More(); aItMI.Next()) {
1896     nV = aItMI.Value();
1897     const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
1898     gp_Pnt aPV = BRep_Tool::Pnt(aV);
1899     aProjPT.Perform(aPV);
1900     Standard_Integer aNbPoints = aProjPT.NbPoints();
1901     if (aNbPoints) {
1902       aDist = aProjPT.LowerDistance();
1903       PutPaveOnCurve(nV, aDist, aNC, aMI, aMVTol, aDMVLV);
1904     }
1905   }
1906 }
1907
1908 //=======================================================================
1909 //function : ProcessUnUsedVertices
1910 //purpose  : 
1911 //=======================================================================
1912   void BOPAlgo_PaveFiller::PutStickPavesOnCurve
1913   (const TopoDS_Face& aF1,
1914    const TopoDS_Face& aF2,
1915    const BOPCol_MapOfInteger& aMI,
1916    BOPDS_Curve& aNC,
1917    const BOPCol_MapOfInteger& aMVStick,
1918    BOPCol_DataMapOfIntegerReal& aMVTol,
1919    BOPCol_DataMapOfIntegerListOfInteger& aDMVLV)
1920 {
1921   BOPCol_MapOfInteger aMV;
1922   aMV.Assign(aMVStick);
1923   RemoveUsedVertices(aNC, aMV);
1924   //
1925   if (!aMV.Extent()) {
1926     return;
1927   }
1928   //
1929   Handle(Geom_Surface) aS1=BRep_Tool::Surface(aF1);
1930   Handle(Geom_Surface) aS2=BRep_Tool::Surface(aF2);
1931   //
1932   const IntTools_Curve& aIC=aNC.Curve();
1933   //if (aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve) {
1934   Handle(Geom2d_Curve) aC2D[2];
1935   //
1936   aC2D[0]=aIC.FirstCurve2d();
1937   aC2D[1]=aIC.SecondCurve2d();
1938   if (!aC2D[0].IsNull() && !aC2D[1].IsNull()) {
1939     Standard_Integer nV, m, n;
1940     Standard_Real aTC[2], aD, aD2, u, v, aDT2, aScPr, aDScPr;
1941     gp_Pnt aPC[2], aPV;
1942     gp_Dir aDN[2];
1943     gp_Pnt2d aP2D;
1944     BOPCol_MapIteratorOfMapOfInteger aItMI, aItMI1;
1945     //
1946     aDT2=2e-7;     // the rich criteria
1947     aDScPr=5.e-9;  // the creasing criteria
1948     aIC.Bounds(aTC[0], aTC[1], aPC[0], aPC[1]);
1949     //
1950     aItMI.Initialize(aMV);
1951     for (; aItMI.More(); aItMI.Next()) {
1952       nV = aItMI.Value();
1953       const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&myDS->Shape(nV));
1954       aPV=BRep_Tool::Pnt(aV);
1955       //
1956       for (m=0; m<2; ++m) {
1957         aD2=aPC[m].SquareDistance(aPV);
1958         if (aD2>aDT2) {// no rich
1959           continue; 
1960         }
1961         //
1962         for (n=0; n<2; ++n) {
1963           Handle(Geom_Surface)& aS=(!n)? aS1 : aS2;
1964           aC2D[n]->D0(aTC[m], aP2D);
1965           aP2D.Coord(u, v);
1966           BOPTools_AlgoTools3D::GetNormalToSurface(aS, u, v, aDN[n]);
1967         }
1968         // 
1969         aScPr=aDN[0]*aDN[1];
1970         if (aScPr<0.) {
1971           aScPr=-aScPr;
1972         }
1973         aScPr=1.-aScPr;
1974         //
1975         if (aScPr>aDScPr) {
1976           continue;
1977         }
1978         //
1979         // The intersection curve aIC is vanishing curve (the crease)
1980         aD=sqrt(aD2);
1981         //
1982         PutPaveOnCurve(nV, aD, aNC, aMI, aMVTol, aDMVLV);
1983       }
1984     }//for (jVU=1; jVU=aNbVU; ++jVU) {
1985   }
1986   //}//if (aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve) {
1987   //}//if(aType1==GeomAbs_Torus  || aType2==GeomAbs_Torus) {
1988 }
1989
1990 //=======================================================================
1991 //function : GetStickVertices
1992 //purpose  : 
1993 //=======================================================================
1994 void BOPAlgo_PaveFiller::GetStickVertices(const Standard_Integer nF1,
1995                                           const Standard_Integer nF2,
1996                                           BOPCol_MapOfInteger& aMVStick,
1997                                           BOPCol_MapOfInteger& aMVEF,
1998                                           BOPCol_MapOfInteger& aMI)
1999 {
2000   Standard_Integer nS1, nS2, nVNew, aTypeInt, i;
2001   //
2002   BOPDS_VectorOfInterfVV& aVVs=myDS->InterfVV();
2003   BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
2004   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
2005   BOPDS_VectorOfInterfVF& aVFs=myDS->InterfVF();
2006   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
2007   //
2008   Standard_Integer aNbLines[5] = {
2009     aVVs.Extent(), aVEs.Extent(), aEEs.Extent(),
2010     aVFs.Extent(), aEFs.Extent()
2011     };
2012   //collect indices of all shapes from nF1 and nF2.
2013   aMI.Clear();
2014   GetFullShapeMap(nF1, aMI);
2015   GetFullShapeMap(nF2, aMI);
2016   //
2017   //collect VV, VE, EE, VF interferences
2018   for (aTypeInt = 0; aTypeInt < 4; ++aTypeInt) {
2019     for (i = 0; i < aNbLines[aTypeInt]; ++i) {
2020       BOPDS_Interf* aInt = (aTypeInt==0) ? (BOPDS_Interf*)(&aVVs(i)) : 
2021         ((aTypeInt==1) ? (BOPDS_Interf*)(&aVEs(i)) :
2022          ((aTypeInt==2) ? (BOPDS_Interf*)(&aEEs(i)) : 
2023           (BOPDS_Interf*)(&aVFs(i))));
2024       if (aInt->HasIndexNew()) {
2025         aInt->Indices(nS1, nS2);
2026         if(aMI.Contains(nS1) && aMI.Contains(nS2)) {
2027           nVNew = aInt->IndexNew();
2028           aMVStick.Add(nVNew);
2029         }
2030       }
2031     }
2032   }
2033   //collect EF interferences
2034   for (i = 0; i < aNbLines[4]; ++i) {
2035     const BOPDS_InterfEF& aInt = aEFs(i);
2036     if (aInt.HasIndexNew()) {
2037       aInt.Indices(nS1, nS2);
2038       if(aMI.Contains(nS1) && aMI.Contains(nS2)) {
2039         nVNew = aInt.IndexNew();
2040         aMVStick.Add(nVNew);
2041         aMVEF.Add(nVNew);
2042       }
2043     }
2044   }
2045 }
2046
2047 //=======================================================================
2048 // function: GetFullShapeMap
2049 // purpose: 
2050 //=======================================================================
2051 void BOPAlgo_PaveFiller::GetFullShapeMap(const Standard_Integer nF,
2052                                          BOPCol_MapOfInteger& aMI)
2053 {
2054   BOPCol_ListIteratorOfListOfInteger aIt;
2055   Standard_Integer nS;
2056   //
2057   const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
2058   const BOPCol_ListOfInteger& aLI = aSI.SubShapes();
2059   //
2060   aMI.Add(nF);
2061   aIt.Initialize(aLI);
2062   for (; aIt.More(); aIt.Next()) {
2063     nS = aIt.Value();
2064     aMI.Add(nS);
2065   }
2066 }
2067
2068 //=======================================================================
2069 // function: RemoveUsedVertices
2070 // purpose: 
2071 //=======================================================================
2072 void BOPAlgo_PaveFiller::RemoveUsedVertices(BOPDS_Curve& aNC,
2073                                             BOPCol_MapOfInteger& aMV)
2074 {
2075   if (!aMV.Extent()) {
2076     return;
2077   }
2078   Standard_Integer nV;
2079   BOPDS_Pave aPave;
2080   BOPDS_ListIteratorOfListOfPave aItLP;
2081   //
2082   Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
2083   const BOPDS_ListOfPave& aLP = aPB->ExtPaves();
2084   aItLP.Initialize(aLP);
2085   for (;aItLP.More();aItLP.Next()) {
2086     aPave = aItLP.Value();
2087     nV = aPave.Index();
2088     aMV.Remove(nV);
2089   }
2090 }
2091
2092 //=======================================================================
2093 //function : PutPaveOnCurve
2094 //purpose  : 
2095 //=======================================================================
2096 void BOPAlgo_PaveFiller::PutPaveOnCurve
2097   (const Standard_Integer nV,
2098    const Standard_Real aTolR3D,
2099    const BOPDS_Curve& aNC,
2100    const BOPCol_MapOfInteger& aMI,
2101    BOPCol_DataMapOfIntegerReal& aMVTol,
2102    BOPCol_DataMapOfIntegerListOfInteger& aDMVLV,
2103    const Standard_Integer iCheckExtend)
2104 {
2105   Standard_Boolean bIsVertexOnLine;
2106   Standard_Real aT;
2107   //
2108   const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
2109   const Handle(BOPDS_PaveBlock)& aPB = aNC.PaveBlocks().First();
2110   const IntTools_Curve& aIC = aNC.Curve();
2111   //
2112   Standard_Real aTolV = (aMVTol.IsBound(nV) ? aMVTol(nV) : BRep_Tool::Tolerance(aV));
2113
2114   bIsVertexOnLine = myContext->IsVertexOnLine(aV, aTolV, aIC, aTolR3D + myFuzzyValue, aT);
2115   if (!bIsVertexOnLine && iCheckExtend) {
2116     ExtendedTolerance(nV, aMI, aTolV, iCheckExtend);
2117     bIsVertexOnLine = myContext->IsVertexOnLine(aV, aTolV, aIC, aTolR3D + myFuzzyValue, aT);
2118   }
2119   //
2120   if (bIsVertexOnLine) {
2121     // check if aPB contains the parameter aT
2122     Standard_Boolean bExist;
2123     Standard_Integer nVUsed;
2124     Standard_Real aPTol, aDTol;
2125     //
2126     aDTol = 1.e-12;
2127     //
2128     GeomAdaptor_Curve aGAC(aIC.Curve());
2129     aPTol = aGAC.Resolution(Max(aTolR3D, aTolV));
2130     //
2131     bExist = aPB->ContainsParameter(aT, aPTol, nVUsed);
2132     if (bExist) {
2133       // use existing pave
2134       BOPCol_ListOfInteger* pList = aDMVLV.ChangeSeek(nVUsed);
2135       if (!pList) {
2136         pList = aDMVLV.Bound(nVUsed, BOPCol_ListOfInteger());
2137         pList->Append(nVUsed);
2138         if (!aMVTol.IsBound(nVUsed)) {
2139           const TopoDS_Vertex& aVUsed = (*(TopoDS_Vertex *)(&myDS->Shape(nVUsed)));
2140           aTolV = BRep_Tool::Tolerance(aVUsed);
2141           aMVTol.Bind(nVUsed, aTolV);
2142         }
2143       }
2144       // avoid repeated elements in the list
2145       BOPCol_ListIteratorOfListOfInteger aItLI(*pList);
2146       for (; aItLI.More(); aItLI.Next()) {
2147         if (aItLI.Value() == nV) {
2148           break;
2149         }
2150       }
2151       if (!aItLI.More()) {
2152         pList->Append(nV);
2153       }
2154       // save initial tolerance for the vertex
2155       if (!aMVTol.IsBound(nV)) {
2156         aTolV = BRep_Tool::Tolerance(aV);
2157         aMVTol.Bind(nV, aTolV);
2158       }
2159     }
2160     else {
2161       // add new pave
2162       BOPDS_Pave aPave;
2163       aPave.SetIndex(nV);
2164       aPave.SetParameter(aT);
2165       aPB->AppendExtPave(aPave);
2166       //
2167       gp_Pnt aP1 = aGAC.Value(aT);
2168       aTolV = BRep_Tool::Tolerance(aV);
2169       gp_Pnt aP2 = BRep_Tool::Pnt(aV);
2170       Standard_Real aDist = aP1.Distance(aP2);
2171       if (aDist > aTolV) {
2172         BRep_Builder().UpdateVertex(aV, aDist + aDTol);
2173         //
2174         if (!aMVTol.IsBound(nV)) {
2175           aMVTol.Bind(nV, aTolV);
2176         }
2177         //
2178         BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nV);
2179         Bnd_Box& aBoxDS=aSIDS.ChangeBox();
2180         BRepBndLib::Add(aV, aBoxDS);
2181         aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
2182       }
2183     }
2184   }
2185 }
2186
2187 //=======================================================================
2188 //function : ProcessExistingPaveBlocks
2189 //purpose  : 
2190 //=======================================================================
2191 void BOPAlgo_PaveFiller::ProcessExistingPaveBlocks
2192     (const Standard_Integer theInt,
2193      const BOPDS_IndexedMapOfPaveBlock& aMPBOnIn,
2194      const BOPCol_DataMapOfIntegerListOfInteger& aDMBV,
2195      BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& aMSCPB,
2196      BOPCol_DataMapOfShapeInteger& aMVI,
2197      BOPDS_MapOfPaveBlock& aMPB)
2198 {
2199   if (aDMBV.IsEmpty()) {
2200     return;
2201   }
2202   //
2203   Standard_Real aT, dummy;
2204   Standard_Integer i, nV, nE, iC, aNbPB, iFlag;
2205   BOPCol_ListIteratorOfListOfInteger aItLI;
2206   BOPCol_DataMapIteratorOfDataMapOfIntegerListOfInteger aItBV;
2207   //
2208   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2209   BOPDS_InterfFF& aFF = aFFs(theInt);
2210   BOPDS_VectorOfCurve& aVC = aFF.ChangeCurves();
2211   //
2212   aNbPB = aMPBOnIn.Extent();
2213   //
2214   aItBV.Initialize(aDMBV);
2215   for (; aItBV.More(); aItBV.Next()) {
2216     iC = aItBV.Key();
2217     const BOPCol_ListOfInteger& aLBV = aItBV.Value();
2218     //
2219     BOPDS_Curve& aNC = aVC.ChangeValue(iC);
2220     BOPDS_ListOfPaveBlock& aLPBC = aNC.ChangePaveBlocks();
2221     //
2222     aItLI.Initialize(aLBV);
2223     for (; aItLI.More(); aItLI.Next()) {
2224       nV = aItLI.Value();
2225       const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
2226       const Bnd_Box& aBoxV=aSIV.Box();
2227       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&aSIV.Shape();
2228       if (!aMVI.IsBound(aV)) {
2229         continue;
2230       }
2231       //
2232       for (i = 1; i <= aNbPB; ++i) {
2233         const Handle(BOPDS_PaveBlock)& aPB = aMPBOnIn(i);
2234         if (aPB->Pave1().Index() == nV || aPB->Pave2().Index() == nV) {
2235           continue;
2236         }
2237         //
2238         if (aMPB.Contains(aPB)) {
2239           continue;
2240         }
2241         if (myDS->ShapeInfo(aPB->OriginalEdge()).HasFlag()) { // skip degenerated edges
2242           continue;
2243         }
2244         //
2245         nE = aPB->Edge();
2246         const BOPDS_ShapeInfo& aSIE = myDS->ShapeInfo(nE);
2247         const Bnd_Box& aBoxE = aSIE.Box();
2248         //
2249         if (aBoxV.IsOut(aBoxE)) {
2250           continue;
2251         }
2252         //
2253         const TopoDS_Edge& aE = *(TopoDS_Edge*)&aSIE.Shape();
2254         //
2255         iFlag = myContext->ComputeVE(aV, aE, aT, dummy, myFuzzyValue);
2256         if (!iFlag) {
2257           aMPB.Add(aPB);
2258           PreparePostTreatFF(theInt, iC, aPB, aMSCPB, aMVI, aLPBC);
2259         }
2260       }
2261     }
2262   }
2263 }
2264 //=======================================================================
2265 //function : UpdateExistingPaveBlocks
2266 //purpose  : 
2267 //=======================================================================
2268 void BOPAlgo_PaveFiller::UpdateExistingPaveBlocks
2269   (const Handle(BOPDS_PaveBlock)& aPBf,
2270    BOPDS_ListOfPaveBlock& aLPB,
2271    const Standard_Integer nF1,
2272    const Standard_Integer nF2) 
2273 {
2274   if (!aLPB.Extent()) {
2275     return;
2276   }
2277   //
2278   Standard_Integer nE;
2279   Standard_Boolean bCB;
2280   Handle(BOPDS_PaveBlock) aPB, aPB1, aPB2, aPB2n;
2281   Handle(BOPDS_CommonBlock) aCB;
2282   BOPDS_ListIteratorOfListOfPaveBlock aIt, aIt1, aIt2;
2283   //
2284   BOPDS_FaceInfo& aFI1 = myDS->ChangeFaceInfo(nF1);
2285   BOPDS_FaceInfo& aFI2 = myDS->ChangeFaceInfo(nF2);
2286   //
2287   BOPDS_IndexedMapOfPaveBlock& aMPBOn1 = aFI1.ChangePaveBlocksOn();
2288   BOPDS_IndexedMapOfPaveBlock& aMPBIn1 = aFI1.ChangePaveBlocksIn();
2289   BOPDS_IndexedMapOfPaveBlock& aMPBOn2 = aFI2.ChangePaveBlocksOn();
2290   BOPDS_IndexedMapOfPaveBlock& aMPBIn2 = aFI2.ChangePaveBlocksIn();
2291   //
2292   // 1. Remove old pave blocks
2293   const Handle(BOPDS_CommonBlock)& aCB1 = myDS->CommonBlock(aPBf);
2294   bCB = !aCB1.IsNull();
2295   BOPDS_ListOfPaveBlock aLPB1;
2296   //
2297   if (bCB) {
2298     aLPB1.Assign(aCB1->PaveBlocks());
2299   } else {
2300     aLPB1.Append(aPBf);
2301   }
2302   aIt1.Initialize(aLPB1);
2303   for (; aIt1.More(); aIt1.Next()) {
2304     aPB1 = aIt1.Value();
2305     nE = aPB1->OriginalEdge();
2306     //
2307     BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE);
2308     aIt2.Initialize(aLPB2);
2309     for (; aIt2.More(); aIt2.Next()) {
2310       aPB2 = aIt2.Value();
2311       if (aPB1 == aPB2) {
2312         aLPB2.Remove(aIt2);
2313         break;
2314       }
2315     }
2316   }
2317   //
2318   // 2. Update pave blocks
2319   if (bCB) {
2320     // Create new common blocks
2321     BOPDS_ListOfPaveBlock aLPBNew;
2322     const BOPCol_ListOfInteger& aFaces = aCB1->Faces();
2323     aIt.Initialize(aLPB);
2324     for (; aIt.More(); aIt.Next()) {
2325       const Handle(BOPDS_PaveBlock)& aPBValue = aIt.Value();
2326       BOPDS_Pave aPBValuePaves[2] = {aPBValue->Pave1(), aPBValue->Pave2()};
2327       //
2328       aCB = new BOPDS_CommonBlock;
2329       aIt1.Initialize(aLPB1);
2330       for (; aIt1.More(); aIt1.Next()) {
2331         aPB2 = aIt1.Value();
2332         nE = aPB2->OriginalEdge();
2333         //
2334         // Create new pave block
2335         aPB2n = new BOPDS_PaveBlock;
2336         if (aPBValue->OriginalEdge() == nE) {
2337           aPB2n->SetPave1(aPBValuePaves[0]);
2338           aPB2n->SetPave2(aPBValuePaves[1]);
2339         }
2340         else {
2341           // For the different original edge compute the parameters of paves
2342           BOPDS_Pave aPave[2];
2343           for (Standard_Integer i = 0; i < 2; ++i) {
2344             Standard_Integer nV = aPBValuePaves[i].Index();
2345             aPave[i].SetIndex(nV);
2346             if (nV == aPB2->Pave1().Index()) {
2347               aPave[i].SetParameter(aPB2->Pave1().Parameter());
2348             }
2349             else if (nV == aPB2->Pave2().Index()) {
2350               aPave[i].SetParameter(aPB2->Pave2().Parameter());
2351             }
2352             else {
2353               // Compute the parameter by projecting the point
2354               const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
2355               const TopoDS_Edge& aEOr = TopoDS::Edge(myDS->Shape(nE));
2356               Standard_Real aTOut, aDist;
2357               Standard_Integer iErr = myContext->ComputeVE(aV, aEOr, aTOut, aDist, myFuzzyValue);
2358               if (!iErr) {
2359                 aPave[i].SetParameter(aTOut);
2360               }
2361               else {
2362                 // Unable to project - set the parameter of the closest boundary
2363                 const TopoDS_Vertex& aV1 = TopoDS::Vertex(myDS->Shape(aPB2->Pave1().Index()));
2364                 const TopoDS_Vertex& aV2 = TopoDS::Vertex(myDS->Shape(aPB2->Pave2().Index()));
2365                 //
2366                 gp_Pnt aP = BRep_Tool::Pnt(aV);
2367                 gp_Pnt aP1 = BRep_Tool::Pnt(aV1);
2368                 gp_Pnt aP2 = BRep_Tool::Pnt(aV2);
2369                 //
2370                 Standard_Real aDist1 = aP.SquareDistance(aP1);
2371                 Standard_Real aDist2 = aP.SquareDistance(aP2);
2372                 //
2373                 aPave[i].SetParameter(aDist1 < aDist2 ? aPB2->Pave1().Parameter() : aPB2->Pave2().Parameter());
2374               }
2375             }
2376           }
2377           //
2378           if (aPave[1].Parameter() < aPave[0].Parameter()) {
2379             BOPDS_Pave aPaveTmp = aPave[0];
2380             aPave[0] = aPave[1];
2381             aPave[1] = aPaveTmp;
2382           }
2383           //
2384           aPB2n->SetPave1(aPave[0]);
2385           aPB2n->SetPave2(aPave[1]);
2386         }
2387         //
2388         aPB2n->SetEdge(aPBValue->Edge());
2389         aPB2n->SetOriginalEdge(nE);
2390         aCB->AddPaveBlock(aPB2n);
2391         myDS->SetCommonBlock(aPB2n, aCB);
2392         myDS->ChangePaveBlocks(nE).Append(aPB2n);
2393       }
2394       aCB->SetFaces(aFaces);
2395       //
2396       const Handle(BOPDS_PaveBlock)& aPBNew = aCB->PaveBlocks().First();
2397       aLPBNew.Append(aPBNew);
2398     }
2399     //
2400     aLPB = aLPBNew;
2401   } 
2402   else {
2403     nE = aPBf->OriginalEdge();
2404     BOPDS_ListOfPaveBlock& aLPBE = myDS->ChangePaveBlocks(nE);
2405     aIt.Initialize(aLPB);
2406     for (; aIt.More(); aIt.Next()) {
2407       aPB = aIt.Value();
2408       aLPBE.Append(aPB);
2409     }
2410   }
2411   //
2412   Standard_Boolean bIn1, bIn2;
2413   //
2414   bIn1 = aMPBOn1.Contains(aPBf) || aMPBIn1.Contains(aPBf);
2415   bIn2 = aMPBOn2.Contains(aPBf) || aMPBIn2.Contains(aPBf);
2416   //
2417   if (bIn1 && bIn2) {
2418     return;
2419   }
2420   //
2421   // 3. Check new pave blocks for coincidence 
2422   //    with the opposite face.
2423   //    In case of coincidence create common blocks
2424   Standard_Integer nF;
2425   //
2426   nF = bIn1 ? nF2 : nF1;
2427   const TopoDS_Face& aF = *(TopoDS_Face*)&myDS->Shape(nF);
2428   BOPDS_IndexedMapOfPaveBlock& aMPBIn = bIn1 ? aMPBIn2 : aMPBIn1;
2429   //
2430   aIt.Initialize(aLPB);
2431   for (; aIt.More(); aIt.Next()) {
2432     Handle(BOPDS_PaveBlock)& aPBChangeValue = aIt.ChangeValue();
2433     const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPBChangeValue->Edge());
2434     //
2435     IntTools_EdgeFace anEF;
2436     anEF.SetEdge(aE);
2437     anEF.SetFace(aF);
2438     anEF.SetFuzzyValue(myFuzzyValue);
2439     anEF.SetRange(aPBChangeValue->Pave1().Parameter(), aPBChangeValue->Pave2().Parameter());
2440     anEF.SetContext(myContext);
2441     anEF.Perform();
2442     //
2443     const IntTools_SequenceOfCommonPrts& aCPrts=anEF.CommonParts();
2444     if (aCPrts.Length() == 1) {
2445       Standard_Boolean bCoinc = (aCPrts(1).Type() == TopAbs_EDGE);
2446       if (bCoinc) {
2447         if (bCB) {
2448           aCB = myDS->CommonBlock(aPBChangeValue);
2449         } else {
2450           aCB = new BOPDS_CommonBlock;
2451           aCB->AddPaveBlock(aPBChangeValue);
2452           myDS->SetCommonBlock(aPBChangeValue, aCB);
2453         }
2454         aCB->AddFace(nF);
2455         //
2456         aMPBIn.Add(aPBChangeValue);
2457       }
2458     }
2459   }
2460 }
2461 //=======================================================================
2462 // function: PutClosingPaveOnCurve
2463 // purpose:
2464 //=======================================================================
2465 void BOPAlgo_PaveFiller::PutClosingPaveOnCurve(BOPDS_Curve& aNC)
2466 {
2467   const IntTools_Curve& aIC = aNC.Curve();
2468   const Handle(Geom_Curve)& aC3D = aIC.Curve();
2469   // check 3d curve
2470   if (aC3D.IsNull())
2471     return;
2472
2473   // check bounds
2474   if (!aIC.HasBounds())
2475     return;
2476
2477   // check closeness
2478   Standard_Real aT[2];
2479   gp_Pnt aP[2];
2480   aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
2481
2482   // Find the pave which has been put at one of the ends
2483   Standard_Integer nV = -1;
2484   // Keep the opposite parameter
2485   Standard_Real aTOp = 0.;
2486
2487   Standard_Boolean bFound = Standard_False;
2488
2489   Handle(BOPDS_PaveBlock)& aPB = aNC.ChangePaveBlock1();
2490   BOPDS_ListOfPave& aLP = aPB->ChangeExtPaves();
2491   BOPDS_ListIteratorOfListOfPave aItLP(aLP);
2492   for (; aItLP.More() && !bFound; aItLP.Next())
2493   {
2494     const BOPDS_Pave& aPC = aItLP.Value();
2495     Standard_Real aTC = aPC.Parameter();
2496     for (Standard_Integer j = 0; j < 2; ++j)
2497     {
2498       if (Abs(aTC - aT[j]) < Precision::PConfusion())
2499       {
2500         nV = aPC.Index();
2501         aTOp = (!j) ? aT[1] : aT[0];
2502         bFound = Standard_True;
2503         break;
2504       }
2505     }
2506   }
2507
2508   if (!bFound)
2509     return;
2510
2511   // Check if the curve is closed using the tolerance
2512   // of found vertex
2513   const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
2514   const Standard_Real aTolV = BRep_Tool::Tolerance(aV);
2515
2516   Standard_Real aDist = aP[0].Distance(aP[1]);
2517   if (aDist > aTolV)
2518     return;
2519
2520   // Check if there will be valid range on the curve
2521   Standard_Real aFirst, aLast;
2522   if (!BRepLib::FindValidRange(GeomAdaptor_Curve(aIC.Curve()), aIC.Tolerance(),
2523                                aT[0], aP[0], aTolV,
2524                                aT[1], aP[1], aTolV,
2525                                aFirst, aLast))
2526   {
2527     return;
2528   }
2529
2530   // Add closing pave to the curve
2531   BOPDS_Pave aPave;
2532   aPave.SetIndex(nV);
2533   aPave.SetParameter(aTOp);
2534   aLP.Append(aPave);
2535 }
2536 //=======================================================================
2537 //function : PreparePostTreatFF
2538 //purpose  : 
2539 //=======================================================================
2540 void BOPAlgo_PaveFiller::PreparePostTreatFF
2541     (const Standard_Integer aInt,
2542      const Standard_Integer aCur,
2543      const Handle(BOPDS_PaveBlock)& aPB,
2544      BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& aMSCPB,
2545      BOPCol_DataMapOfShapeInteger& aMVI,
2546      BOPDS_ListOfPaveBlock& aLPBC)
2547 {
2548   Standard_Integer nV1, nV2;
2549   //
2550   aLPBC.Append(aPB);
2551   //
2552   aPB->Indices(nV1, nV2);
2553   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
2554   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
2555   const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPB->Edge());
2556   // Keep info for post treatment 
2557   BOPDS_CoupleOfPaveBlocks aCPB;
2558   aCPB.SetIndexInterf(aInt);
2559   aCPB.SetIndex(aCur);
2560   aCPB.SetPaveBlock1(aPB);
2561   //
2562   aMSCPB.Add(aE, aCPB);
2563   aMVI.Bind(aV1, nV1);
2564   aMVI.Bind(aV2, nV2);
2565 }
2566
2567 //=======================================================================
2568 //function : CheckPlanes
2569 //purpose  : 
2570 //=======================================================================
2571 Standard_Boolean BOPAlgo_PaveFiller::CheckPlanes
2572   (const Standard_Integer nF1,
2573    const Standard_Integer nF2)const
2574 {
2575   Standard_Boolean bToIntersect;
2576   Standard_Integer i, nV2, iCnt;
2577   BOPCol_MapIteratorOfMapOfInteger aIt;
2578   //
2579   bToIntersect=Standard_False;
2580   //
2581   const BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
2582   const BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
2583   //
2584   const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
2585   const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
2586   //
2587   iCnt=0;
2588   for (i=0; (i<2 && !bToIntersect); ++i) {
2589     const BOPCol_MapOfInteger& aMV2=(!i) ? aFI2.VerticesIn() 
2590       : aFI2.VerticesOn();
2591     //
2592     aIt.Initialize(aMV2);
2593     for (; aIt.More(); aIt.Next()) {
2594       nV2=aIt.Value();
2595       if (aMVIn1.Contains(nV2) || aMVOn1.Contains(nV2)) {
2596         ++iCnt;
2597         if (iCnt>1) {
2598           bToIntersect=!bToIntersect;
2599           break;
2600         }
2601       }
2602     }
2603   }
2604   //
2605   return bToIntersect;
2606 }
2607 //=======================================================================
2608 //function : UpdatePaveBlocks
2609 //purpose  : 
2610 //=======================================================================
2611 void BOPAlgo_PaveFiller::UpdatePaveBlocks
2612 (const BOPCol_DataMapOfIntegerInteger& aDMNewSD)
2613 {
2614   if (aDMNewSD.IsEmpty()) {
2615     return;
2616   }
2617   //
2618   Standard_Integer nSp, aNbPBP, nV[2], i, j;
2619   Standard_Real aT[2];
2620   Standard_Boolean bCB, bRebuild;
2621   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
2622   BOPDS_MapOfPaveBlock aMPB;
2623   BOPCol_MapOfInteger aMicroEdges;
2624   //
2625   BOPDS_ListOfPaveBlock anAllPBs;
2626
2627   // Get pave blocks of section edges
2628   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2629   Standard_Integer aNbFF = aFFs.Extent();
2630   for (i = 0; i < aNbFF; ++i)
2631   {
2632     const BOPDS_InterfFF& aFF = aFFs(i);
2633     const BOPDS_VectorOfCurve& aVNC = aFF.Curves();
2634     Standard_Integer aNbC = aVNC.Extent();
2635     for (j = 0; j < aNbC; ++j)
2636     {
2637       const BOPDS_Curve& aNC = aVNC(j);
2638       const BOPDS_ListOfPaveBlock& aLPBC = aNC.PaveBlocks();
2639       aItPB.Initialize(aLPBC);
2640       for (; aItPB.More(); aItPB.Next())
2641         anAllPBs.Append(aItPB.Value());
2642     }
2643   }
2644
2645   // Get pave blocks from the pool
2646   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
2647   aNbPBP = aPBP.Extent();
2648   for (i = 0; i < aNbPBP; ++i) {
2649     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2650     aItPB.Initialize(aLPB);
2651     for (; aItPB.More(); aItPB.Next())
2652       anAllPBs.Append(aItPB.Value());
2653   }
2654
2655   // Process all pave blocks
2656   aItPB.Initialize(anAllPBs);
2657   for (; aItPB.More(); aItPB.Next())
2658   {
2659     Handle(BOPDS_PaveBlock) aPB = aItPB.Value();
2660     const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
2661     bCB = !aCB.IsNull();
2662     if (bCB) {
2663       aPB = aCB->PaveBlock1();
2664     }
2665     //
2666     if (aMPB.Add(aPB)) {
2667       bRebuild = Standard_False;
2668       aPB->Indices(nV[0], nV[1]);
2669       aPB->Range(aT[0], aT[1]);
2670       // remember the fact if the edge had different vertices before substitution
2671       Standard_Boolean wasRegularEdge = (nV[0] != nV[1]);
2672       //
2673       for (j = 0; j < 2; ++j) {
2674         if (aDMNewSD.IsBound(nV[j])) {
2675           BOPDS_Pave aPave;
2676           //
2677           nV[j] = aDMNewSD.Find(nV[j]);
2678           aPave.SetIndex(nV[j]);
2679           aPave.SetParameter(aT[j]);
2680           //
2681           bRebuild = Standard_True;
2682           if (!j) {
2683             aPB->SetPave1(aPave);
2684           }
2685           else {
2686             aPB->SetPave2(aPave);
2687           }
2688         }
2689       }
2690       //
2691       if (bRebuild) {
2692         Standard_Integer nE = aPB->Edge();
2693         // Check if the Pave Block has the edge set
2694         if (nE < 0) {
2695           // untouched edge
2696           nE = aPB->OriginalEdge();
2697         }
2698         Standard_Boolean isDegEdge = myDS->ShapeInfo(nE).HasFlag();
2699         if (wasRegularEdge && !isDegEdge && nV[0] == nV[1]) {
2700           // now edge has the same vertex on both ends;
2701           // check if it is not a regular closed curve.
2702           const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
2703           const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV[0]));
2704           Standard_Real aLength = IntTools::Length(aE);
2705           Standard_Real aTolV = BRep_Tool::Tolerance(aV);
2706           if (aLength <= aTolV * 2.) {
2707             // micro edge, so mark it for removal
2708             aMicroEdges.Add(nE);
2709             continue;
2710           }
2711         }
2712         nSp = SplitEdge(nE, nV[0], aT[0], nV[1], aT[1]);
2713         if (bCB)
2714           aCB->SetEdge(nSp);
2715         else
2716           aPB->SetEdge(nSp);
2717       }// if (bRebuild) {
2718     }// if (aMPB.Add(aPB)) {
2719   }// for (; aItPB.More(); aItPB.Next()) {
2720   aMPB.Clear();
2721
2722   if (aMicroEdges.Extent())
2723     RemovePaveBlocks(aMicroEdges);
2724 }
2725 //=======================================================================
2726 //function : RemovePaveBlocks
2727 //purpose  : 
2728 //=======================================================================
2729 void BOPAlgo_PaveFiller::RemovePaveBlocks(const BOPCol_MapOfInteger theEdges)
2730 {
2731   // Remove all pave blocks referring to input edges:
2732   //
2733   // 1. from the Pave Blocks Pool
2734   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
2735   Standard_Integer aNbPBP = aPBP.Extent(), i;
2736   for (i = 0; i < aNbPBP; ++i) {
2737     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2738     //
2739     BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
2740     while (aItPB.More()) {
2741       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
2742       if (theEdges.Contains(aPB->Edge()))
2743         aLPB.Remove(aItPB);
2744       else
2745         aItPB.Next();
2746     }
2747   }
2748
2749   // 2. from Face Info and section curves
2750   BOPCol_MapOfInteger aMPassed;
2751   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2752   Standard_Integer aNbFF = aFFs.Extent(), j;
2753   for (i = 0; i < aNbFF; ++i) {
2754     BOPDS_InterfFF& aFF = aFFs(i);
2755     Standard_Integer nF1, nF2;
2756     aFF.Indices(nF1, nF2);
2757     //
2758     // rebuild pave block maps of face info
2759     for (j = 0; j < 2; j++) {
2760       Standard_Integer nF = (j == 0 ? nF1 : nF2);
2761       if (!aMPassed.Add(nF))
2762         continue;
2763       BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(nF);
2764       BOPDS_IndexedMapOfPaveBlock* aIMPB[] = { &aFI.ChangePaveBlocksIn(),
2765         &aFI.ChangePaveBlocksOn(), &aFI.ChangePaveBlocksSc() };
2766       for (Standard_Integer k = 0; k < 3; k++) {
2767         Standard_Integer aNbPB = aIMPB[k]->Extent(), m;
2768         for (m = 1; m <= aNbPB; ++m) {
2769           const Handle(BOPDS_PaveBlock)& aPB = aIMPB[k]->FindKey(m);
2770           if (theEdges.Contains(aPB->Edge()))
2771             break;
2772         }
2773         if (m <= aNbPB) {
2774           BOPDS_IndexedMapOfPaveBlock aMPBCopy = *aIMPB[k];
2775           aIMPB[k]->Clear();
2776           for (m = 1; m <= aNbPB; ++m) {
2777             const Handle(BOPDS_PaveBlock)& aPB = aMPBCopy(m);
2778             if (!theEdges.Contains(aPB->Edge()))
2779               aIMPB[k]->Add(aPB);
2780           }
2781         }
2782       }
2783     }
2784     // remove from Section pave blocks
2785     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
2786     Standard_Integer aNbC = aVNC.Extent();
2787     for (j = 0; j < aNbC; ++j) {
2788       BOPDS_Curve& aNC = aVNC(j);
2789       BOPDS_ListOfPaveBlock& aLPB = aNC.ChangePaveBlocks();
2790       BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
2791       while (aItPB.More()) {
2792         const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
2793         if (theEdges.Contains(aPB->Edge()))
2794           aLPB.Remove(aItPB);
2795         else
2796           aItPB.Next();
2797       }
2798     }
2799   }
2800 }
2801 //=======================================================================
2802 //function : ToleranceFF
2803 //purpose  : Computes the TolFF according to the tolerance value and 
2804 //           types of the faces.
2805 //=======================================================================
2806 Standard_Real ToleranceFF(const BRepAdaptor_Surface& aBAS1,
2807                           const BRepAdaptor_Surface& aBAS2)
2808 {
2809   Standard_Real aTol1 = aBAS1.Tolerance();
2810   Standard_Real aTol2 = aBAS2.Tolerance();
2811   Standard_Real aTolFF = Max(aTol1, aTol2);
2812   //
2813   Standard_Boolean isAna1, isAna2;
2814   isAna1 = (aBAS1.GetType() == GeomAbs_Plane ||
2815             aBAS1.GetType() == GeomAbs_Cylinder ||
2816             aBAS1.GetType() == GeomAbs_Cone ||
2817             aBAS1.GetType() == GeomAbs_Sphere ||
2818             aBAS1.GetType() == GeomAbs_Torus);
2819   //
2820   isAna2 = (aBAS2.GetType() == GeomAbs_Plane ||
2821             aBAS2.GetType() == GeomAbs_Cylinder ||
2822             aBAS2.GetType() == GeomAbs_Cone ||
2823             aBAS2.GetType() == GeomAbs_Sphere ||
2824             aBAS2.GetType() == GeomAbs_Torus);
2825   //
2826   if (!isAna1 || !isAna2) {
2827     aTolFF =  Max(aTolFF, 5.e-6);
2828   }
2829   return aTolFF;
2830 }
2831 //=======================================================================
2832 //function : UpdateBlocksWithSharedVertices
2833 //purpose  : 
2834 //=======================================================================
2835 void BOPAlgo_PaveFiller::UpdateBlocksWithSharedVertices()
2836 {
2837   if (!myNonDestructive) {
2838     return;
2839   }
2840   //
2841   Standard_Integer aNbFF;
2842   //
2843   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
2844   aNbFF=aFFs.Extent();
2845   if (!aNbFF) {
2846     return;
2847   }
2848   //
2849   Standard_Boolean bOnCurve, bHasShapeSD;
2850   Standard_Integer i, nF1, nF2, aNbC, j, nV, nVSD;
2851   Standard_Real aTolV;
2852   BOPCol_MapOfInteger aMF;
2853   //
2854   for (i=0; i<aNbFF; ++i) {
2855     BOPDS_InterfFF& aFF=aFFs(i);
2856     //
2857     BOPDS_VectorOfCurve& aVC=aFF.ChangeCurves();
2858     aNbC=aVC.Extent();
2859     if (!aNbC) {
2860       continue;
2861     }
2862     //
2863     aFF.Indices(nF1, nF2);
2864     //
2865     if (aMF.Add(nF1)) {
2866       myDS->UpdateFaceInfoOn(nF1);
2867     }
2868     if (aMF.Add(nF2)) {
2869       myDS->UpdateFaceInfoOn(nF2);
2870     }
2871     //
2872     // Collect old vertices that are shared for nF1, nF2 ->aMI;
2873     BOPCol_MapOfInteger aMI;
2874     BOPCol_MapIteratorOfMapOfInteger aItMI;
2875     //
2876     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
2877     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
2878     //
2879     const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
2880     const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
2881     const BOPCol_MapOfInteger& aMVOn2=aFI2.VerticesOn();
2882     const BOPCol_MapOfInteger& aMVIn2=aFI2.VerticesIn();
2883     //
2884     for (j=0; j<2; ++j) {
2885       const BOPCol_MapOfInteger& aMV1=(!j) ? aMVOn1 : aMVIn1;
2886       aItMI.Initialize(aMV1);
2887       for (; aItMI.More(); aItMI.Next()) {
2888         nV=aItMI.Value();
2889         if (myDS->IsNewShape(nV)) {
2890           continue;
2891         }
2892         if (aMVOn2.Contains(nV) || aMVIn2.Contains(nV)) {
2893           aMI.Add(nV);
2894         }
2895       }
2896     }
2897     //
2898     // Try to put vertices aMI on curves
2899     for (j=0; j<aNbC; ++j) {
2900       BOPDS_Curve& aNC=aVC.ChangeValue(j);
2901       Standard_Real aTolR3D = Max(aNC.Tolerance(), aNC.TangentialTolerance());
2902       //
2903       aItMI.Initialize(aMI);
2904       for (; aItMI.More(); aItMI.Next()) {
2905         nV=aItMI.Value();
2906         //
2907         bHasShapeSD=myDS->HasShapeSD(nV, nVSD);
2908         if (bHasShapeSD) {
2909           continue;
2910         }
2911         //
2912         bOnCurve=EstimatePaveOnCurve(nV, aNC, aTolR3D);
2913         if (!bOnCurve) {
2914           continue;
2915         }
2916         //
2917         const TopoDS_Vertex& aV=*((TopoDS_Vertex *)&myDS->Shape(nV));
2918         aTolV=BRep_Tool::Tolerance(aV);
2919         //
2920         UpdateVertex(nV, aTolV);
2921       }
2922     }//for (j=0; j<aNbC; ++j) {
2923   }//for (i=0; i<aNbFF; ++i) {
2924   //
2925   UpdateCommonBlocksWithSDVertices();
2926 }
2927 //=======================================================================
2928 //function : EstimatePaveOnCurve
2929 //purpose  : 
2930 //=======================================================================
2931 Standard_Boolean BOPAlgo_PaveFiller::EstimatePaveOnCurve
2932   (const Standard_Integer nV,
2933    const BOPDS_Curve& aNC,
2934    const Standard_Real aTolR3D)
2935 {
2936   Standard_Boolean bIsVertexOnLine;
2937   Standard_Real aT;
2938   //
2939   const TopoDS_Vertex& aV=*((TopoDS_Vertex *)&myDS->Shape(nV));
2940   const IntTools_Curve& aIC=aNC.Curve();
2941   //
2942   bIsVertexOnLine=myContext->IsVertexOnLine(aV, aIC, aTolR3D, aT);
2943   return bIsVertexOnLine;
2944 }
2945
2946 //=======================================================================
2947 //function : CorrectToleranceOfSE
2948 //purpose  : 
2949 //=======================================================================
2950 void BOPAlgo_PaveFiller::CorrectToleranceOfSE()
2951 {
2952   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2953   NCollection_IndexedDataMap<Standard_Integer,BOPDS_ListOfPaveBlock> aMVIPBs;
2954   BOPCol_MapOfInteger aMVIToReduce;
2955   // Fence map to avoid repeated checking of the same edge
2956   BOPDS_MapOfPaveBlock aMPB;
2957   //
2958   // 1. iterate on all sections F-F
2959   Standard_Integer aNb = aFFs.Extent(), i;
2960   for (i = 0; i < aNb; ++i) {
2961     BOPDS_InterfFF& aFF = aFFs(i);
2962     //
2963     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
2964     Standard_Integer aNbC = aVNC.Extent(), k;
2965     for (k = 0; k < aNbC; ++k) {
2966       BOPDS_Curve& aNC = aVNC(k);
2967       BOPDS_ListOfPaveBlock& aLPB = aNC.ChangePaveBlocks();
2968       BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
2969       for (; aItLPB.More(); ) {
2970         const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
2971         Standard_Integer nE;
2972         if (!aPB->HasEdge(nE)) {
2973           aLPB.Remove(aItLPB);
2974           continue;
2975         }
2976         //
2977         if (!aMPB.Add(aPB)) {
2978           aItLPB.Next();
2979           continue;
2980         }
2981         //
2982         Standard_Boolean bIsReduced = Standard_False;
2983         if (aPB->OriginalEdge() < 0) {
2984           // It is possible that due to small angle between faces the
2985           // common zone between faces can be large and the tangential
2986           // tolerance of the curve will be large as well.
2987           // Here we're trying to reduce the tolerance of the section
2988           // edge using the valid tolerance of the edge.
2989           // Note, that if the pave block has created common block with
2990           // other edges its valid tolerance could have been changed to
2991           // cover all edges in common block (see PostTreatFF() method).
2992           Standard_Real aTolC = aNC.Tolerance();
2993           Standard_Real aTolTang = aNC.TangentialTolerance();
2994           if (aTolC < aTolTang) {
2995             const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
2996             Standard_Real aTolE = BRep_Tool::Tolerance(aE);
2997             if (aTolC < aTolE) {
2998               // reduce edge tolerance
2999               reinterpret_cast<BRep_TEdge*>(aE.TShape().operator->())->Tolerance(aTolC);
3000               bIsReduced = Standard_True;
3001             }
3002           }
3003         }
3004         //
3005         // fill in the map vertex index - pave blocks
3006         for (Standard_Integer j=0; j < 2; j++) {
3007           Standard_Integer nV = (j == 0 ? aPB->Pave1().Index() : aPB->Pave2().Index());
3008           myDS->HasShapeSD(nV, nV);
3009           BOPDS_ListOfPaveBlock *pPBList = aMVIPBs.ChangeSeek(nV);
3010           if (!pPBList) {
3011             pPBList = &aMVIPBs.ChangeFromIndex(aMVIPBs.Add(nV, BOPDS_ListOfPaveBlock()));
3012           }
3013           pPBList->Append(aPB);
3014           if (bIsReduced) {
3015             aMVIToReduce.Add(nV);
3016           }
3017         }
3018         aItLPB.Next();
3019       }
3020     }
3021   }
3022   //
3023   if (aMVIToReduce.IsEmpty()) {
3024     return;
3025   }
3026   //
3027   // 2. try to reduce tolerances of connected vertices
3028   // 2.1 find all other edges containing these connected vertices to avoid
3029   //     reducing the tolerance to the value less than the tolerances of edges,
3030   //     i.e. minimal tolerance for the vertex is the max tolerance of the
3031   //     edges containing this vertex
3032   BOPCol_DataMapOfIntegerReal aMVITol;
3033   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
3034   aNb = aPBP.Extent();
3035   for (i = 0; i < aNb; ++i) {
3036     const BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
3037     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3038     for (; aItLPB.More(); aItLPB.Next()) {
3039       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3040       Standard_Integer nE;
3041       if (!aPB->HasEdge(nE)) {
3042         continue;
3043       }
3044       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
3045       Standard_Real aTolE = BRep_Tool::Tolerance(aE);
3046       //
3047       Standard_Integer nV[2];
3048       aPB->Indices(nV[0], nV[1]);
3049       //
3050       for (Standard_Integer j = 0; j < 2; j++) {
3051         if (aMVIToReduce.Contains(nV[j])) {
3052           Standard_Real *aMaxTol = aMVITol.ChangeSeek(nV[j]);
3053           if (!aMaxTol) {
3054             aMVITol.Bind(nV[j], aTolE);
3055           }
3056           else if (aTolE > *aMaxTol) {
3057             *aMaxTol = aTolE;
3058           }
3059         }
3060       }
3061     }
3062   }
3063   //
3064   // 2.2 reduce tolerances if possible
3065   aNb = aMVIPBs.Extent();
3066   for (i = 1; i <= aNb; ++i) {
3067     Standard_Integer nV = aMVIPBs.FindKey(i);
3068     if (!aMVIToReduce.Contains(nV)) {
3069       continue;
3070     }
3071     //
3072     const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
3073     Standard_Real aTolV = BRep_Tool::Tolerance(aV);
3074     Standard_Real aMaxTol = aMVITol.IsBound(nV) ? aMVITol.Find(nV) : 0.;
3075     // it makes no sense to compute the real tolerance if it is
3076     // impossible to reduce the tolerance at least 0.1% of the current value
3077     if (aTolV - aMaxTol < 0.001 * aTolV) {
3078       continue;
3079     }
3080     //
3081     // compute the maximal distance from the vertex to the adjacent edges
3082     gp_Pnt aP = BRep_Tool::Pnt(aV);
3083     //
3084     // Avoid repeated checks
3085     BOPDS_MapOfPaveBlock aMPBFence;
3086     //
3087     const BOPDS_ListOfPaveBlock& aLPB = aMVIPBs.FindFromIndex(i);
3088     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
3089     for (; aItLPB.More(); aItLPB.Next()) {
3090       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
3091       if (!aMPBFence.Add(aPB)) {
3092         continue;
3093       }
3094       Standard_Integer nE = aPB->Edge();
3095       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
3096       BRepAdaptor_Curve aC(aE);
3097       for (Standard_Integer iPave = 0; iPave < 2; ++iPave) {
3098         const BOPDS_Pave& aPave = !iPave ? aPB->Pave1() : aPB->Pave2();
3099         Standard_Integer nVSD = aPave.Index();
3100         myDS->HasShapeSD(nVSD, nVSD);
3101         if (nVSD != nV) {
3102           continue;
3103         }
3104         //
3105         gp_Pnt aPonE = aC.Value(aPave.Parameter());
3106         Standard_Real aDist = aP.Distance(aPonE);
3107         aDist += BRep_Tool::Tolerance(aE);
3108         if (aDist > aMaxTol) {
3109           aMaxTol = aDist;
3110         }
3111       }
3112     }
3113     //
3114     if (aMaxTol < aTolV) {
3115       reinterpret_cast<BRep_TVertex*>(aV.TShape().operator->())->Tolerance(aMaxTol);
3116     }
3117   }
3118 }
3119
3120 //=======================================================================
3121 //function : PutSEInOtherFaces
3122 //purpose  : 
3123 //=======================================================================
3124 void BOPAlgo_PaveFiller::PutSEInOtherFaces()
3125 {
3126   // Try to intersect each section edge with the faces
3127   // not participated in its creation
3128   //
3129   // 1. Get all section edges
3130   BOPDS_IndexedMapOfPaveBlock aMPBScAll;
3131   //
3132   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
3133   Standard_Integer i, j, aNbFF = aFFs.Extent();
3134   //
3135   for (i = 0; i < aNbFF; ++i) {
3136     const BOPDS_VectorOfCurve& aVNC = aFFs(i).Curves();
3137     Standard_Integer aNbC = aVNC.Extent();
3138     for (j = 0; j < aNbC; ++j) {
3139       const BOPDS_ListOfPaveBlock& aLPBC = aVNC(j).PaveBlocks();
3140       BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPBC);
3141       for (; aItPB.More(); aItPB.Next()) {
3142         aMPBScAll.Add(aItPB.Value());
3143       }
3144     }
3145   }
3146   //
3147   Standard_Integer aNbPBSc = aMPBScAll.Extent();
3148   //
3149   // 2. Loop for all faces and check each section curve
3150   Standard_Integer aNbS = myDS->NbSourceShapes();
3151   for (i = 0; i < aNbS; ++i) {
3152     const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
3153     if (aSI.ShapeType() != TopAbs_FACE) {
3154       continue;
3155     }
3156     //
3157     const TopoDS_Face& aF = (*(TopoDS_Face*)(&aSI.Shape()));
3158     BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(i);
3159     //
3160     // IN edges to add new ones
3161     BOPDS_IndexedMapOfPaveBlock& aMFPBIn = aFI.ChangePaveBlocksIn();
3162     // Section edges to check the participation of the face
3163     const BOPDS_IndexedMapOfPaveBlock& aMFPBSc = aFI.PaveBlocksSc();
3164     //
3165     // Get vertices of the face to check that vertices of the
3166     // processed section edge belong to the face
3167     BOPCol_MapOfInteger aMFVerts;
3168     // Get vertices from ON, IN and Sc pave blocks of the face
3169     for (j = 0; j < 3; ++j) {
3170       const BOPDS_IndexedMapOfPaveBlock& aMPB =
3171         !j ? aFI.PaveBlocksOn() : (j == 1 ? aMFPBIn : aMFPBSc);
3172       Standard_Integer aNbPB = aMPB.Extent();
3173       for (Standard_Integer k = 1; k <= aNbPB; ++k) {
3174         const Handle(BOPDS_PaveBlock)& aPB = aMPB(k);
3175         aMFVerts.Add(aPB->Pave1().Index());
3176         aMFVerts.Add(aPB->Pave2().Index());
3177       }
3178     }
3179     // Add ON, IN and Sc vertices of the face
3180     for (j = 0; j < 3; ++j) {
3181       const BOPCol_MapOfInteger& aMFV = !j ? aFI.VerticesOn() :
3182         (j == 1 ? aFI.VerticesIn() : aFI.VerticesSc());
3183       BOPCol_MapIteratorOfMapOfInteger aItMI(aMFV);
3184       for (; aItMI.More(); aItMI.Next()) {
3185         aMFVerts.Add(aItMI.Value());
3186       }
3187     }
3188     //
3189     // Check each section edge for possible belonging to the face
3190     for (j = 1; j <= aNbPBSc; ++j) {
3191       const Handle(BOPDS_PaveBlock)& aPB = aMPBScAll(j);
3192       if (aMFPBSc.Contains(aPB)) {
3193         continue;
3194       }
3195       //
3196       // Both vertices of the section edge should belong to the face
3197       if (!aMFVerts.Contains(aPB->Pave1().Index()) ||
3198         !aMFVerts.Contains(aPB->Pave2().Index())) {
3199         continue;
3200       }
3201       //
3202       // Perform intersection
3203       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->Edge()));
3204       //
3205       IntTools_EdgeFace anEFInt;
3206       anEFInt.SetEdge(aE);
3207       anEFInt.SetFace(aF);
3208       anEFInt.SetFuzzyValue(myFuzzyValue);
3209       anEFInt.SetRange(aPB->Pave1().Parameter(), aPB->Pave2().Parameter());
3210       anEFInt.SetContext(myContext);
3211       anEFInt.UseQuickCoincidenceCheck(Standard_True);
3212       anEFInt.Perform();
3213       //
3214       const IntTools_SequenceOfCommonPrts& aCPrts = anEFInt.CommonParts();
3215       if ((aCPrts.Length() == 1) && (aCPrts(1).Type() == TopAbs_EDGE)) {
3216         Handle(BOPDS_CommonBlock) aCB;
3217         if (myDS->IsCommonBlock(aPB)) {
3218           aCB = myDS->CommonBlock(aPB);
3219         }
3220         else {
3221           aCB = new BOPDS_CommonBlock;
3222           aCB->AddPaveBlock(aPB);
3223         }
3224         //
3225         aCB->AddFace(i);
3226         //
3227         aMFPBIn.Add(aPB);
3228       }
3229     }
3230   }
3231 }