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