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