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