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