0027179: The algorithm of sharing edges in Boolean operation should be improved
[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 <BOPCol_DataMapOfIntegerReal.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 void ToleranceFF(const BRepAdaptor_Surface& aBAS1,
84                         const BRepAdaptor_Surface& aBAS2,
85                         Standard_Real& aTolFF);
86
87 /////////////////////////////////////////////////////////////////////////
88 //=======================================================================
89 //class    : BOPAlgo_FaceFace
90 //purpose  : 
91 //=======================================================================
92 class BOPAlgo_FaceFace : 
93   public IntTools_FaceFace,
94   public BOPAlgo_Algo {
95
96  public:
97   DEFINE_STANDARD_ALLOC
98
99   BOPAlgo_FaceFace() : 
100     IntTools_FaceFace(),  
101     BOPAlgo_Algo(),
102     myIF1(-1), myIF2(-1), myTolFF(1.e-7) {
103   }
104   //
105   virtual ~BOPAlgo_FaceFace() {
106   }
107   //
108   void SetIndices(const Standard_Integer nF1,
109                   const Standard_Integer nF2) {
110     myIF1=nF1;
111     myIF2=nF2;
112   }
113   //
114   void Indices(Standard_Integer& nF1,
115                Standard_Integer& nF2) const {
116     nF1=myIF1;
117     nF2=myIF2;
118   }
119   //
120   void SetFaces(const TopoDS_Face& aF1,
121                 const TopoDS_Face& aF2) {
122     myF1=aF1;
123     myF2=aF2;
124   }
125   //
126   const TopoDS_Face& Face1()const {
127     return myF1;
128   }
129   //
130   const TopoDS_Face& Face2()const {
131     return myF2;
132   }
133   //
134   void SetTolFF(const Standard_Real aTolFF) {
135     myTolFF=aTolFF;
136   }
137   //
138   Standard_Real TolFF() const{
139     return myTolFF;
140   }
141   //
142   virtual void Perform() {
143     BOPAlgo_Algo::UserBreak();
144     IntTools_FaceFace::Perform(myF1, myF2);
145   }
146   //
147  protected:
148   Standard_Integer myIF1;
149   Standard_Integer myIF2;
150   Standard_Real myTolFF;
151   TopoDS_Face myF1;
152   TopoDS_Face myF2;
153 };
154 //
155 //=======================================================================
156 typedef BOPCol_NCVector
157   <BOPAlgo_FaceFace> BOPAlgo_VectorOfFaceFace; 
158 //
159 typedef BOPCol_Functor 
160   <BOPAlgo_FaceFace,
161   BOPAlgo_VectorOfFaceFace> BOPAlgo_FaceFaceFunctor;
162 //
163 typedef BOPCol_Cnt 
164   <BOPAlgo_FaceFaceFunctor,
165   BOPAlgo_VectorOfFaceFace> BOPAlgo_FaceFaceCnt;
166 /////////////////////////////////////////////////////////////////////////
167 //=======================================================================
168 //function : PerformFF
169 //purpose  : 
170 //=======================================================================
171 void BOPAlgo_PaveFiller::PerformFF()
172 {
173   Standard_Integer iSize;
174   Standard_Boolean bValid;
175   //
176   myErrorStatus=0;
177   //
178   myIterator->Initialize(TopAbs_FACE, TopAbs_FACE);
179   iSize=myIterator->ExpectedLength();
180   if (!iSize) {
181     return; 
182   }
183   //
184   Standard_Boolean bJustAdd, bApp, bCompC2D1, bCompC2D2, bIsDone;
185   Standard_Boolean bToSplit, bTangentFaces;
186   Standard_Integer nF1, nF2, aNbCurves, aNbPoints, i, aNbLP;
187   Standard_Integer aNbFaceFace, k;
188   Standard_Real aApproxTol, aTolR3D, aTolR2D, aTolFF, aTolReal;
189   BRepAdaptor_Surface aBAS1, aBAS2;
190   BOPCol_MapOfInteger aMI;
191   BOPAlgo_VectorOfFaceFace aVFaceFace;
192   //
193   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
194   aFFs.SetIncrement(iSize);
195   //
196   bApp=mySectionAttribute.Approximation();
197   bCompC2D1=mySectionAttribute.PCurveOnS1();
198   bCompC2D2=mySectionAttribute.PCurveOnS2();
199   aApproxTol=1.e-7;
200   bToSplit = Standard_False;
201   //
202   for (; myIterator->More(); myIterator->Next()) {
203     myIterator->Value(nF1, nF2, bJustAdd);
204     if(bJustAdd) {
205       continue;
206     }
207     //
208     const TopoDS_Face& aF1=(*(TopoDS_Face *)(&myDS->Shape(nF1)));
209     const TopoDS_Face& aF2=(*(TopoDS_Face *)(&myDS->Shape(nF2)));
210     //
211     if (aMI.Add(nF1)) {
212       myDS->UpdateFaceInfoOn(nF1);
213       myDS->UpdateFaceInfoIn(nF1);
214     }
215     if (aMI.Add(nF2)) {
216       myDS->UpdateFaceInfoOn(nF2);
217       myDS->UpdateFaceInfoIn(nF2);
218     }
219     //
220     aBAS1.Initialize(aF1, Standard_False);
221     aBAS2.Initialize(aF2, Standard_False);
222     if (aBAS1.GetType() == GeomAbs_Plane && 
223         aBAS2.GetType() == GeomAbs_Plane) {
224       Standard_Boolean bToIntersect;
225       //
226       bToIntersect = CheckPlanes(nF1, nF2);
227       if (!bToIntersect) {
228         myDS->AddInterf(nF1, nF2);
229         BOPDS_InterfFF& aFF=aFFs.Append1();
230         aFF.SetIndices(nF1, nF2);
231         aFF.Init(0, 0);
232         continue;
233       }
234     }
235     //
236     ToleranceFF(aBAS1, aBAS2, aTolFF); 
237     //
238     BOPAlgo_FaceFace& aFaceFace=aVFaceFace.Append1();
239     //
240     aFaceFace.SetIndices(nF1, nF2);
241     aFaceFace.SetFaces(aF1, aF2);
242     aFaceFace.SetTolFF(aTolFF);
243     //
244     IntSurf_ListOfPntOn2S aListOfPnts;
245     GetEFPnts(nF1, nF2, aListOfPnts);
246     aNbLP = aListOfPnts.Extent();
247     if (aNbLP) {
248       aFaceFace.SetList(aListOfPnts);
249     }
250     //
251     aFaceFace.SetParameters(bApp, bCompC2D1, bCompC2D2, aApproxTol);
252     aFaceFace.SetProgressIndicator(myProgressIndicator);
253   }//for (; myIterator->More(); myIterator->Next()) {
254   //
255   aNbFaceFace=aVFaceFace.Extent();
256   //======================================================
257   BOPAlgo_FaceFaceCnt::Perform(myRunParallel, aVFaceFace);
258   //======================================================
259   //
260   for (k=0; k < aNbFaceFace; ++k) {
261     BOPAlgo_FaceFace& aFaceFace=aVFaceFace(k);
262     //
263     aFaceFace.Indices(nF1, nF2);
264     aTolFF=aFaceFace.TolFF();
265     //
266     bIsDone=aFaceFace.IsDone();
267     if (bIsDone) {
268       aTolR3D=aFaceFace.TolReached3d();
269       aTolR2D=aFaceFace.TolReached2d();
270       aTolReal = aFaceFace.TolReal();
271       bTangentFaces=aFaceFace.TangentFaces();
272       //
273       if (aTolR3D < aTolFF){
274         aTolR3D=aTolFF;
275       }
276       if (aTolReal < aTolFF) {
277         aTolReal = aTolFF;
278       }
279       if (aTolR2D < 1.e-7){
280         aTolR2D=1.e-7;
281       }
282       //
283       aFaceFace.PrepareLines3D(bToSplit);
284       //
285       const IntTools_SequenceOfCurves& aCvsX=aFaceFace.Lines();
286       const IntTools_SequenceOfPntOn2Faces& aPntsX=aFaceFace.Points();
287       //
288       aNbCurves=aCvsX.Length();
289       aNbPoints=aPntsX.Length();
290       //
291       if (aNbCurves || aNbPoints) {
292         myDS->AddInterf(nF1, nF2);
293       } 
294       //
295       BOPDS_InterfFF& aFF=aFFs.Append1();
296       aFF.SetIndices(nF1, nF2);
297       //
298       aFF.SetTolR3D(aTolR3D);
299       aFF.SetTolR2D(aTolR2D);
300       aFF.SetTolReal(aTolReal);
301       aFF.SetTangentFaces(bTangentFaces);
302       //
303       // Curves, Points 
304       aFF.Init(aNbCurves, aNbPoints);
305       //
306       // Curves
307
308       // Fix bounding box expanding coefficient.
309       Standard_Real aBoxExpandValue = aTolR3D;
310       if (aNbCurves > 0)
311       {
312         // Modify geometric expanding coefficient by topology value,
313         // since this bounging box used in sharing (vertex or edge).
314         Standard_Real aMaxVertexTol = Max (BRep_Tool::MaxTolerance(aFaceFace.Face1(), TopAbs_VERTEX),
315                                            BRep_Tool::MaxTolerance(aFaceFace.Face2(), TopAbs_VERTEX));
316         aBoxExpandValue += aMaxVertexTol;
317       }
318
319       BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
320       for (i=1; i<=aNbCurves; ++i) {
321         Bnd_Box aBox;
322         //
323         const IntTools_Curve& aIC=aCvsX(i);
324         const Handle(Geom_Curve)& aC3D= aIC.Curve();
325         bValid=IntTools_Tools::CheckCurve(aC3D, aBoxExpandValue, aBox);
326         if (bValid) {
327           BOPDS_Curve& aNC=aVNC.Append1();
328           aNC.SetCurve(aIC);
329           aNC.SetBox(aBox);
330         }
331       }
332       //
333       // Points
334       BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
335       for (i=1; i<=aNbPoints; ++i) {
336         const IntTools_PntOn2Faces& aPi=aPntsX(i);
337         const gp_Pnt& aP=aPi.P1().Pnt();
338         //
339         BOPDS_Point& aNP=aVNP.Append1();
340         aNP.SetPnt(aP);
341       }
342     //}// if (aNbCs || aNbPs)
343     }// if (bIsDone) {
344     else {// 904/L1
345       BOPDS_InterfFF& aFF=aFFs.Append1();
346       aFF.SetIndices(nF1, nF2);
347       aNbCurves=0;
348       aNbPoints=0;
349       aFF.Init(aNbCurves, aNbPoints);
350     }
351   }// for (k=0; k < aNbFaceFace; ++k) {
352 }
353 //=======================================================================
354 //function : MakeBlocks
355 //purpose  : 
356 //=======================================================================
357 void BOPAlgo_PaveFiller::MakeBlocks()
358 {
359   Standard_Integer aNbFF;
360   //
361   myErrorStatus=0;
362   //
363   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
364   aNbFF=aFFs.Extent();
365   if (!aNbFF) {
366     return;
367   }
368   //
369   Standard_Boolean bExist, bValid2D;
370   Standard_Integer i, nF1, nF2, aNbC, aNbP, j;
371   Standard_Integer nV1, nV2;
372   Standard_Real aTolR3D, aT1, aT2, aTol;
373   Handle(NCollection_BaseAllocator) aAllocator;
374   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
375   TopoDS_Edge aES;
376   Handle(BOPDS_PaveBlock) aPBOut;
377   //
378   //-----------------------------------------------------scope f
379   aAllocator=
380     NCollection_BaseAllocator::CommonBaseAllocator();
381   //
382   BOPCol_ListOfInteger aLSE(aAllocator), aLBV(aAllocator);
383   BOPCol_MapOfInteger aMVOnIn(100, aAllocator), aMF(100, aAllocator),
384                       aMVStick(100,aAllocator), aMVEF(100, aAllocator),
385                       aMI(100, aAllocator);
386   BOPDS_IndexedMapOfPaveBlock aMPBOnIn(100, aAllocator);
387   BOPDS_MapOfPaveBlock aMPBAdd(100, aAllocator);
388   BOPDS_ListOfPaveBlock aLPB(aAllocator);
389   BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks aMSCPB(100, aAllocator); 
390   BOPCol_DataMapOfShapeInteger aMVI(100, aAllocator);
391   BOPDS_DataMapOfPaveBlockListOfPaveBlock aDMExEdges(100, aAllocator);
392   BOPCol_DataMapOfIntegerReal aMVTol(100, aAllocator);
393   BOPCol_DataMapOfIntegerInteger aDMI(100, aAllocator);
394   BOPCol_DataMapOfIntegerListOfInteger aDMBV(100, aAllocator);
395   BOPCol_DataMapIteratorOfDataMapOfIntegerReal aItMV;
396   //
397   for (i=0; i<aNbFF; ++i) {
398     //
399     UserBreak();
400     //
401     BOPDS_InterfFF& aFF=aFFs(i);
402     aFF.Indices(nF1, nF2);
403     //
404     BOPDS_VectorOfPoint& aVP=aFF.ChangePoints();
405     aNbP=aVP.Extent();
406     BOPDS_VectorOfCurve& aVC=aFF.ChangeCurves();
407     aNbC=aVC.Extent();
408     if (!aNbP && !aNbC) {
409       continue;
410     }
411     //
412     const TopoDS_Face& aF1=(*(TopoDS_Face *)(&myDS->Shape(nF1)));
413     const TopoDS_Face& aF2=(*(TopoDS_Face *)(&myDS->Shape(nF2)));
414     //
415     aTolR3D=aFF.TolR3D();
416     //
417     // Update face info
418     if (aMF.Add(nF1)) {
419       myDS->UpdateFaceInfoOn(nF1);
420       myDS->UpdateFaceInfoIn(nF1);
421     }
422     if (aMF.Add(nF2)) {
423       myDS->UpdateFaceInfoOn(nF2);
424       myDS->UpdateFaceInfoIn(nF2);
425     }
426     //
427     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
428     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
429     //
430     aMVOnIn.Clear();
431     aMPBOnIn.Clear();
432     aDMBV.Clear();
433     aMVTol.Clear();
434     //
435     myDS->VerticesOnIn(nF1, nF2, aMVOnIn, aMPBOnIn);
436     myDS->SharedEdges(nF1, nF2, aLSE, aAllocator);
437     
438     // 1. Treat Points
439     for (j=0; j<aNbP; ++j) {
440       TopoDS_Vertex aV;
441       BOPDS_CoupleOfPaveBlocks aCPB;
442       //
443       BOPDS_Point& aNP=aVP.ChangeValue(j);
444       const gp_Pnt& aP=aNP.Pnt();
445       //
446       bExist=IsExistingVertex(aP, aTolR3D, aMVOnIn);
447       if (!bExist) {
448         BOPTools_AlgoTools::MakeNewVertex(aP, aTolR3D, aV);
449         //
450         aCPB.SetIndexInterf(i);
451         aCPB.SetIndex(j);
452         aMSCPB.Add(aV, aCPB);
453       }
454     }
455     //
456     // 2. Treat Curves
457     aMVStick.Clear();
458     aMVEF.Clear();
459     GetStickVertices(nF1, nF2, aMVStick, aMVEF, aMI);
460     //
461     for (j=0; j<aNbC; ++j) {
462       BOPDS_Curve& aNC=aVC.ChangeValue(j);
463       const IntTools_Curve& aIC=aNC.Curve();
464       // DEBt
465       aNC.InitPaveBlock1();
466       //
467       PutPavesOnCurve(aMVOnIn, aTolR3D, aNC, nF1, nF2, aMI, aMVEF, aMVTol);
468       //
469       PutStickPavesOnCurve(aF1, aF2, aMI, aNC, aMVStick, aMVTol);
470       //904/F7
471       if (aNbC == 1) {
472         PutEFPavesOnCurve(aNC, aMI, aMVEF, aMVTol);
473       }
474       //
475       if (aIC.HasBounds()) {
476         aLBV.Clear();
477         //
478         PutBoundPaveOnCurve(aF1, aF2, aTolR3D, aNC, aLBV);
479         //
480         if (!aLBV.IsEmpty()) {
481           aDMBV.Bind(j, aLBV);
482         }
483       }
484     }//for (j=0; j<aNbC; ++j) {
485     //
486     // Put closing pave if needed
487     for (j=0; j<aNbC; ++j) {
488       BOPDS_Curve& aNC=aVC.ChangeValue(j);
489       PutClosingPaveOnCurve (aNC);
490     }
491     //
492     // 3. Make section edges
493     for (j=0; j<aNbC; ++j) {
494       BOPDS_Curve& aNC=aVC.ChangeValue(j);
495       const IntTools_Curve& aIC=aNC.Curve();
496       //
497       BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
498       Handle(BOPDS_PaveBlock)& aPB1=aNC.ChangePaveBlock1();
499       //
500       aLPB.Clear();
501       aPB1->Update(aLPB, Standard_False);
502       //
503       aItLPB.Initialize(aLPB);
504       for (; aItLPB.More(); aItLPB.Next()) {
505         Handle(BOPDS_PaveBlock)& aPB=aItLPB.ChangeValue();
506         aPB->Indices(nV1, nV2);
507         aPB->Range  (aT1, aT2);
508         //
509         if (fabs(aT1 - aT2) < Precision::PConfusion()) {
510           continue;
511         }
512         //
513         bValid2D=myContext->IsValidBlockForFaces(aT1, aT2, aIC, 
514                                                  aF1, aF2, aTolR3D);
515         if (!bValid2D) {
516           continue;
517         }
518         //
519         bExist=IsExistingPaveBlock(aPB, aNC, aLSE);
520         if (bExist) {
521           continue;
522         }
523         //
524         Standard_Real aTolNew;
525         bExist=IsExistingPaveBlock(aPB, aNC, aTolR3D, aMPBOnIn, aPBOut, aTolNew);
526         if (bExist) {
527           if (aMPBAdd.Add(aPBOut)) {
528             Standard_Boolean bInBothFaces = Standard_True;
529             if (!myDS->IsCommonBlock(aPBOut)) {
530               Standard_Integer nE;
531               Standard_Real aTolE;
532               //
533               nE = aPBOut->Edge();
534               const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(nE);
535               aTolE = BRep_Tool::Tolerance(aE);
536               if (aTolNew < aFF.TolReal())
537                 aTolNew = aFF.TolReal();  // use real tolerance of intersection
538               if (aTolNew > aTolE) {
539                 UpdateEdgeTolerance(nE, aTolNew);
540               }
541               bInBothFaces = Standard_False;
542             } 
543             else {
544               bInBothFaces = (aFI1.PaveBlocksOn().Contains(aPBOut) ||
545                               aFI1.PaveBlocksIn().Contains(aPBOut))&&
546                              (aFI2.PaveBlocksOn().Contains(aPBOut) ||
547                               aFI2.PaveBlocksIn().Contains(aPBOut));
548             }
549             if (!bInBothFaces) {
550               PreparePostTreatFF(i, j, aPBOut, aMSCPB, aMVI, aLPBC);
551             }
552           }
553           continue;
554         }
555         //
556         // Make Edge
557         const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
558         const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
559         //
560         BOPTools_AlgoTools::MakeEdge (aIC, aV1, aT1, 
561                                       aV2, aT2, aTolR3D, aES);
562         BOPTools_AlgoTools::MakePCurve(aES, aF1, aF2, aIC, 
563                                        mySectionAttribute.PCurveOnS1(),
564                                        mySectionAttribute.PCurveOnS2());
565         //
566         if (BOPTools_AlgoTools::IsMicroEdge(aES, myContext)) {
567           continue;
568         }
569         //
570         // Append the Pave Block to the Curve j
571         aLPBC.Append(aPB);
572         //
573         // Keep info for post treatment 
574         BOPDS_CoupleOfPaveBlocks aCPB;
575         aCPB.SetIndexInterf(i);
576         aCPB.SetIndex(j);
577         aCPB.SetPaveBlock1(aPB);
578         //
579         aMSCPB.Add(aES, aCPB);
580         aMVI.Bind(aV1, nV1);
581         aMVI.Bind(aV2, nV2);
582         //
583         aMVTol.UnBind(nV1);
584         aMVTol.UnBind(nV2);
585       }
586       //
587       aLPBC.RemoveFirst();
588     }//for (j=0; j<aNbC; ++j) {
589     //back to previous tolerance values for unused vertices
590     aItMV.Initialize(aMVTol);
591     for (; aItMV.More(); aItMV.Next()) {
592       nV1 = aItMV.Key();
593       aTol = aItMV.Value();
594       //
595       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&myDS->Shape(nV1);
596       const Handle(BRep_TVertex)& TV = 
597         *((Handle(BRep_TVertex)*)&aV.TShape());
598       TV->Tolerance(aTol);
599     }
600     //
601     ProcessExistingPaveBlocks(i, aMPBOnIn, aDMBV, aMSCPB, aMVI, aMPBAdd);
602   }//for (i=0; i<aNbFF; ++i) {
603   // 
604   // post treatment
605   myErrorStatus=PostTreatFF(aMSCPB, aMVI, aDMExEdges, aDMI, aAllocator);
606   if (myErrorStatus) {
607     return;
608   }
609   // reduce tolerances of section edges where it is appropriate
610   CorrectToleranceOfSE();
611   //
612   // update face info
613   UpdateFaceInfo(aDMExEdges, aDMI);
614   //Update all pave blocks
615   UpdatePaveBlocks(aDMI);
616   //-----------------------------------------------------scope t
617   aMF.Clear();
618   aMVStick.Clear();
619   aMPBOnIn.Clear();
620   aMVOnIn.Clear();
621   aDMExEdges.Clear();
622   aMI.Clear();
623   aDMI.Clear();
624 }
625
626 //=======================================================================
627 //function : PostTreatFF
628 //purpose  : 
629 //=======================================================================
630 Standard_Integer BOPAlgo_PaveFiller::PostTreatFF
631     (BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& theMSCPB,
632      BOPCol_DataMapOfShapeInteger& aMVI,
633      BOPDS_DataMapOfPaveBlockListOfPaveBlock& aDMExEdges,
634      BOPCol_DataMapOfIntegerInteger& aDMI,
635      const Handle(NCollection_BaseAllocator)& theAllocator)
636 {
637   Standard_Integer iRet, aNbS;
638   //
639   iRet=0;
640   aNbS=theMSCPB.Extent();
641   if (!aNbS) {
642     return iRet;
643   }
644   //
645   Standard_Boolean bHasPaveBlocks, bOld;
646   Standard_Integer iErr, nSx, nVSD, iX, iP, iC, j, nV, iV = 0, iE, k;
647   Standard_Integer aNbLPBx;
648   TopAbs_ShapeEnum aType;
649   TopoDS_Shape aV, aE;
650   BOPCol_ListIteratorOfListOfShape aItLS;
651   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
652   BOPDS_PDS aPDS;
653   Handle(BOPDS_PaveBlock) aPB1;
654   BOPDS_Pave aPave[2];
655   BOPDS_ShapeInfo aSI;
656   //
657   BOPCol_ListOfShape aLS(theAllocator);
658   BOPAlgo_PaveFiller aPF(theAllocator);
659   aPF.SetIsPrimary(Standard_False);
660   aPF.SetNonDestructive(myNonDestructive);
661   //
662   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
663   //
664   // 0
665   if (aNbS==1) {
666     const TopoDS_Shape& aS=theMSCPB.FindKey(1);
667     const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromIndex(1);
668     
669     //
670     aType=aS.ShapeType();
671     if (aType==TopAbs_VERTEX) {
672       aSI.SetShapeType(aType);
673       aSI.SetShape(aS);
674       iV=myDS->Append(aSI);
675       //
676       iX=aCPB.IndexInterf();
677       iP=aCPB.Index();
678       BOPDS_InterfFF& aFF=aFFs(iX); 
679       BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
680       BOPDS_Point& aNP=aVNP(iP);
681       aNP.SetIndex(iV);
682     }
683     else if (aType==TopAbs_EDGE) {
684       aPB1=aCPB.PaveBlock1();
685       //
686       if (aPB1->HasEdge()) {
687         BOPDS_ListOfPaveBlock aLPBx;
688         aLPBx.Append(aPB1);
689         aDMExEdges.Bind(aPB1, aLPBx);
690       } else {
691         aSI.SetShapeType(aType);
692         aSI.SetShape(aS);
693         iE=myDS->Append(aSI);
694         //
695         aPB1->SetEdge(iE);
696       }
697     }
698     return iRet;
699   }
700   //
701   // 1 prepare arguments
702   for (k=1; k<=aNbS; ++k) {
703     const TopoDS_Shape& aS=theMSCPB.FindKey(k);
704     aLS.Append(aS);
705   }
706   //
707   // 2 Fuse shapes
708   aPF.SetProgressIndicator(myProgressIndicator);
709   aPF.SetRunParallel(myRunParallel);
710   aPF.SetArguments(aLS);
711   aPF.Perform();
712   iErr=aPF.ErrorStatus();
713   if (iErr) {
714     return iRet;
715   }
716   aPDS=aPF.PDS();
717   //
718   aItLS.Initialize(aLS);
719   for (; aItLS.More(); aItLS.Next()) {
720     const TopoDS_Shape& aSx=aItLS.Value();
721     nSx=aPDS->Index(aSx);
722     const BOPDS_ShapeInfo& aSIx=aPDS->ShapeInfo(nSx);
723     //
724     aType=aSIx.ShapeType();
725     //
726     if (aType==TopAbs_VERTEX) {
727       if (aPDS->HasShapeSD(nSx, nVSD)) {
728         aV=aPDS->Shape(nVSD);
729       }
730       else {
731         aV=aSx;
732       }
733       // index of new vertex in theDS -> iV
734       if (!aMVI.IsBound(aV)) {
735         aSI.SetShapeType(aType);
736         aSI.SetShape(aV);
737         iV=myDS->Append(aSI);
738         //
739         aMVI.Bind(aV, iV);
740       }
741       else {
742         iV=aMVI.Find(aV);
743       }
744       // update FF interference
745       const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromKey(aSx);
746       iX=aCPB.IndexInterf();
747       iP=aCPB.Index();
748       BOPDS_InterfFF& aFF=aFFs(iX);
749       BOPDS_VectorOfPoint& aVNP=aFF.ChangePoints();
750       BOPDS_Point& aNP=aVNP(iP);
751       aNP.SetIndex(iV);
752     }//if (aType==TopAbs_VERTEX) {
753     //
754     else if (aType==TopAbs_EDGE) {
755       bHasPaveBlocks=aPDS->HasPaveBlocks(nSx);
756       const BOPDS_CoupleOfPaveBlocks &aCPB=theMSCPB.FindFromKey(aSx);
757       iX=aCPB.IndexInterf();
758       iC=aCPB.Index();
759       aPB1=aCPB.PaveBlock1();
760       //
761       bOld = aPB1->HasEdge();
762       if (bOld) {
763         BOPDS_ListOfPaveBlock aLPBx;
764         aDMExEdges.Bind(aPB1, aLPBx);
765       }
766       //
767       if (!bHasPaveBlocks) {
768         if (bOld) {
769           aDMExEdges.ChangeFind(aPB1).Append(aPB1);
770         }
771         else {
772           aSI.SetShapeType(aType);
773           aSI.SetShape(aSx);
774           iE = myDS->Append(aSI);
775           //
776           aPB1->SetEdge(iE);
777         }
778       }
779       else {
780         BOPDS_InterfFF& aFF=aFFs(iX);
781         BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
782         BOPDS_Curve& aNC=aVNC(iC);
783         BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
784         //
785         // check if edge occured to be micro edge;
786         // note we check not the edge aSx itself, but its image in aPDS
787         const BOPDS_ListOfPaveBlock& aLPBx = aPDS->PaveBlocks(nSx);
788         aNbLPBx = aLPBx.Extent();
789         if (aPDS->HasPaveBlocks(nSx) &&
790             (aNbLPBx == 0 || (aNbLPBx == 1 && !aLPBx.First()->HasShrunkData()))) {
791           BOPDS_ListIteratorOfListOfPaveBlock it(aLPBC);
792           for (; it.More(); it.Next()) {
793             if (it.Value() == aPB1) {
794               aLPBC.Remove(it);
795               break;
796             }
797           }
798           continue;
799         }
800         //
801         if (bOld && !aNbLPBx) {
802           aDMExEdges.ChangeFind(aPB1).Append(aPB1);
803           continue;
804         }
805         //
806         if (!bOld) {
807           aItLPB.Initialize(aLPBC);
808           for (; aItLPB.More(); aItLPB.Next()) {
809             const Handle(BOPDS_PaveBlock)& aPBC=aItLPB.Value();
810             if (aPBC==aPB1) {
811               aLPBC.Remove(aItLPB);
812               break;
813             }
814           } 
815         }
816         //
817         if (!aNbLPBx) {
818           aE=aSx;
819           //
820           if (!aMVI.IsBound(aE)) {
821             aSI.SetShapeType(aType);
822             aSI.SetShape(aE);
823             iE=myDS->Append(aSI);
824             aMVI.Bind(aE, iE);
825           }
826           else {
827             iE=aMVI.Find(aE);
828           }
829           // append new PaveBlock to aLPBC
830           aPB1->SetEdge(iE);
831           aLPBC.Append(aPB1);
832         } // if (!aNbLPBx) {
833         //
834         else {
835           aItLPB.Initialize(aLPBx);
836           for (; aItLPB.More(); aItLPB.Next()) {
837             const Handle(BOPDS_PaveBlock)& aPBx=aItLPB.Value();
838             const Handle(BOPDS_PaveBlock) aPBRx=aPDS->RealPaveBlock(aPBx);
839             //
840             // update vertices of paves
841             aPave[0]=aPBx->Pave1();
842             aPave[1]=aPBx->Pave2();
843             for (j=0; j<2; ++j) {
844               nV = aPave[j].Index();
845               aV = aPDS->Shape(nV);
846               //
847               if (!aMVI.IsBound(aV)) {
848                 // index of new vertex in theDS -> iV
849                 aSI.SetShapeType(TopAbs_VERTEX);
850                 aSI.SetShape(aV);
851                 iV = myDS->Append(aSI);
852                 aMVI.Bind(aV, iV);
853               }
854               else {
855                 iV = aMVI.Find(aV);
856               }
857               const BOPDS_Pave& aP1 = !j ? aPB1->Pave1() : aPB1->Pave2();
858               if (aP1.Parameter() == aPave[j].Parameter() && 
859                   aP1.Index() != iV) {
860                 aDMI.Bind(aP1.Index(), iV);
861                 myDS->AddShapeSD(aP1.Index(), iV);
862               }
863               //
864               aPave[j].SetIndex(iV);
865             }
866             //
867             // add edge
868             aE=aPDS->Shape(aPBRx->Edge());
869             //
870             if (!aMVI.IsBound(aE)) {
871               aSI.SetShapeType(aType);
872               aSI.SetShape(aE);
873               iE=myDS->Append(aSI);
874               aMVI.Bind(aE, iE);
875               // update real edge tolerance according to distances in common block if any
876               if (aPDS->IsCommonBlock(aPBx)) {
877                 const Handle(BOPDS_CommonBlock)& aCB = aPDS->CommonBlock(aPBx);
878                 Standard_Real aTol = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, aPDS, aPF.Context());
879                 if (aFF.TolReal() < aTol) {
880                   aFF.SetTolReal(aTol);
881                 }
882               }
883             }
884             else {
885               iE=aMVI.Find(aE);
886             }
887             // append new PaveBlock to aLPBC
888             Handle(BOPDS_PaveBlock) aPBC=new BOPDS_PaveBlock();
889             //
890             aPBC->SetPave1(aPave[0]);
891             aPBC->SetPave2(aPave[1]);
892             aPBC->SetEdge(iE);
893             if (bOld) {
894               aPBC->SetOriginalEdge(aPB1->OriginalEdge());
895               aDMExEdges.ChangeFind(aPB1).Append(aPBC);
896             }
897             else {
898               aLPBC.Append(aPBC);
899             }
900           }
901         }
902       }
903     }//else if (aType==TopAbs_EDGE)
904   }//for (; aItLS.More(); aItLS.Next()) {
905   return iRet;
906 }
907
908 //=======================================================================
909 //function : UpdateFaceInfo
910 //purpose  : 
911 //=======================================================================
912 void BOPAlgo_PaveFiller::UpdateFaceInfo
913   (BOPDS_DataMapOfPaveBlockListOfPaveBlock& theDME,
914    const BOPCol_DataMapOfIntegerInteger& theDMV)
915 {
916   Standard_Integer i, j, nV1, nF1, nF2, 
917                    aNbFF, aNbC, aNbP;
918   BOPDS_ListIteratorOfListOfPaveBlock aItLPB;
919   BOPCol_MapOfInteger aMF;
920   //
921   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
922   aNbFF=aFFs.Extent();
923   //
924   //1. Sections (curves, points);
925   for (i=0; i<aNbFF; ++i) {
926     BOPDS_InterfFF& aFF=aFFs(i);
927     aFF.Indices(nF1, nF2);
928     //
929     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
930     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
931     //
932     // 1.1. Section edges
933     BOPDS_VectorOfCurve& aVNC=aFF.ChangeCurves();
934     aNbC=aVNC.Extent();
935     for (j=0; j<aNbC; ++j) {
936       BOPDS_Curve& aNC=aVNC(j);
937       BOPDS_ListOfPaveBlock& aLPBC=aNC.ChangePaveBlocks();
938       //
939       // Add section edges to face info
940       aItLPB.Initialize(aLPBC);
941       for (; aItLPB.More(); ) {
942         const Handle(BOPDS_PaveBlock)& aPB=aItLPB.Value();
943         //
944         // Treat existing pave blocks
945         if (theDME.IsBound(aPB)) {
946           BOPDS_ListOfPaveBlock& aLPB=theDME.ChangeFind(aPB);
947           UpdateExistingPaveBlocks(aPB, aLPB, nF1, nF2);
948           aLPBC.Remove(aItLPB);
949           continue;
950         }
951         //
952         aFI1.ChangePaveBlocksSc().Add(aPB);
953         aFI2.ChangePaveBlocksSc().Add(aPB);
954         aItLPB.Next();
955       }
956     }
957     //
958     // 1.2. Section vertices
959     const BOPDS_VectorOfPoint& aVNP=aFF.Points();
960     aNbP=aVNP.Extent();
961     for (j=0; j<aNbP; ++j) {
962       const BOPDS_Point& aNP=aVNP(j);
963       nV1=aNP.Index();
964       if (nV1<0) {
965         continue;
966       }
967       aFI1.ChangeVerticesSc().Add(nV1);
968       aFI2.ChangeVerticesSc().Add(nV1);
969     }
970     //
971     aMF.Add(nF1);
972     aMF.Add(nF2);
973   }
974   //
975   Standard_Boolean bVerts, bEdges;
976   //
977   bVerts = theDMV.Extent() > 0;
978   bEdges = theDME.Extent() > 0;
979   //
980   if (!bVerts && !bEdges) {
981     return;
982   }
983   //
984   // 2. Update Face Info information with new vertices and new
985   //    pave blocks created in PostTreatFF from existing ones
986   Standard_Integer nV2, aNbPB;
987   BOPCol_MapIteratorOfMapOfInteger aItMF;
988   BOPCol_DataMapIteratorOfDataMapOfIntegerInteger aItMV;
989   //
990   aItMF.Initialize(aMF);
991   for (; aItMF.More(); aItMF.Next()) {
992     nF1 = aItMF.Value();
993     //
994     BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(nF1);
995     //
996     // 2.1. Update information about vertices
997     if (bVerts) {
998       BOPCol_MapOfInteger& aMVOn = aFI.ChangeVerticesOn();
999       BOPCol_MapOfInteger& aMVIn = aFI.ChangeVerticesIn();
1000       //
1001       aItMV.Initialize(theDMV);
1002       for (; aItMV.More(); aItMV.Next()) {
1003         nV1 = aItMV.Key();
1004         nV2 = aItMV.Value();
1005         //
1006         if (aMVOn.Remove(nV1)) {
1007           aMVOn.Add(nV2);
1008         }
1009         //
1010         if (aMVIn.Remove(nV1)) {
1011           aMVIn.Add(nV2);
1012         }
1013       } // for (; aItMV.More(); aItMV.Next()) {
1014     } // if (bVerts) {
1015     //
1016     // 2.2. Update information about pave blocks
1017     if (bEdges) {
1018       BOPDS_IndexedMapOfPaveBlock& aMPBOn = aFI.ChangePaveBlocksOn();
1019       BOPDS_IndexedMapOfPaveBlock& aMPBIn = aFI.ChangePaveBlocksIn();
1020       //
1021       BOPDS_IndexedMapOfPaveBlock aMPBCopy;
1022       for (i = 0; i < 2; ++i) {
1023         BOPDS_IndexedMapOfPaveBlock& aMPBOnIn = !i ? aMPBOn : aMPBIn;
1024         aMPBCopy = aMPBOnIn;
1025         aMPBOnIn.Clear();
1026         //
1027         aNbPB = aMPBCopy.Extent();
1028         for (j = 1; j <= aNbPB; ++j) {
1029           const Handle(BOPDS_PaveBlock)& aPB = aMPBCopy(j);
1030           if (theDME.IsBound(aPB)) {
1031             const BOPDS_ListOfPaveBlock& aLPB = theDME.Find(aPB);
1032             if (aLPB.IsEmpty()) {
1033               aMPBOnIn.Add(aPB);
1034               continue;
1035             }
1036             //
1037             aItLPB.Initialize(aLPB);
1038             for (; aItLPB.More(); aItLPB.Next()) {
1039               const Handle(BOPDS_PaveBlock)& aPB1 = aItLPB.Value();
1040               aMPBOnIn.Add(aPB1);
1041             }
1042           }
1043           else {
1044             aMPBOnIn.Add(aPB);
1045           }
1046         } // for (j = 1; j <= aNbPB; ++j) {
1047       } // for (i = 0; i < 2; ++i) {
1048     } // if (bEdges) {
1049   }
1050 }
1051 //=======================================================================
1052 //function : IsExistingVertex
1053 //purpose  : 
1054 //=======================================================================
1055 Standard_Boolean BOPAlgo_PaveFiller::IsExistingVertex
1056   (const gp_Pnt& aP,
1057    const Standard_Real theTolR3D,
1058    const BOPCol_MapOfInteger& aMVOnIn)const
1059 {
1060   Standard_Boolean bRet;
1061   Standard_Integer nV, iFlag;
1062   gp_Pnt aPV;
1063   Bnd_Box aBoxP;
1064   BOPCol_MapIteratorOfMapOfInteger aIt;
1065   //
1066   bRet=Standard_True;
1067   //
1068   aBoxP.Add(aP);
1069   aBoxP.Enlarge(theTolR3D);
1070   //
1071   aIt.Initialize(aMVOnIn);
1072   for (; aIt.More(); aIt.Next()) {
1073     nV=aIt.Value();
1074     const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1075     const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aSIV.Shape()));
1076     const Bnd_Box& aBoxV=aSIV.Box();
1077     //
1078     if (!aBoxP.IsOut(aBoxV)) {
1079       iFlag=BOPTools_AlgoTools::ComputeVV(aV, aP, theTolR3D);
1080       if (!iFlag) {
1081         return bRet;
1082       }
1083     }
1084   }
1085   return !bRet;
1086 }
1087 //=======================================================================
1088 //function : IsExistingPaveBlock
1089 //purpose  : 
1090 //=======================================================================
1091 Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
1092   (const Handle(BOPDS_PaveBlock)& thePB,
1093    const BOPDS_Curve& theNC,
1094    const BOPCol_ListOfInteger& theLSE)
1095 {
1096   Standard_Boolean bRet=Standard_True;
1097   //
1098   if (theLSE.IsEmpty()) {
1099     return !bRet;
1100   } 
1101   //
1102   Standard_Real aT1, aT2, aTm, aTx, aTol, aDist;
1103   Standard_Integer nE, iFlag, nV1, nV2;
1104   gp_Pnt aPm;
1105   Bnd_Box aBoxPm;
1106   BOPCol_ListIteratorOfListOfInteger aItLI;
1107   //
1108   thePB->Range(aT1, aT2);
1109   thePB->Indices(nV1, nV2);
1110   const TopoDS_Vertex &aV1 = TopoDS::Vertex(myDS->Shape(nV1)),
1111                       &aV2 = TopoDS::Vertex(myDS->Shape(nV2));
1112   const Standard_Real aTolV1 = BRep_Tool::Tolerance(aV1),
1113                       aTolV2 = BRep_Tool::Tolerance(aV2);
1114
1115   aTol = Max(aTolV1, aTolV2);
1116
1117   aTm=IntTools_Tools::IntermediatePoint (aT1, aT2);
1118   theNC.Curve().D0(aTm, aPm);
1119   aBoxPm.Add(aPm);
1120   aBoxPm.Enlarge(aTol);
1121   //
1122   aItLI.Initialize(theLSE);
1123   for (; aItLI.More(); aItLI.Next()) {
1124     nE=aItLI.Value();
1125     if (nE < 0)
1126       continue;
1127     const BOPDS_ShapeInfo& aSIE=myDS->ChangeShapeInfo(nE);
1128     const Bnd_Box& aBoxE=aSIE.Box();
1129     if (!aBoxE.IsOut(aBoxPm)) {
1130       const TopoDS_Edge& aE=(*(TopoDS_Edge *)(&aSIE.Shape()));
1131       const Standard_Real aTol1 = Max(BRep_Tool::Tolerance(aE), aTol);
1132       iFlag=myContext->ComputePE(aPm, aTol1, aE, aTx, aDist);
1133       if (!iFlag) {
1134         return bRet;
1135       }
1136     }
1137   }
1138   return !bRet;
1139 }
1140
1141 //=======================================================================
1142 //function : IsExistingPaveBlock
1143 //purpose  : 
1144 //=======================================================================
1145   Standard_Boolean BOPAlgo_PaveFiller::IsExistingPaveBlock
1146     (const Handle(BOPDS_PaveBlock)& thePB,
1147      const BOPDS_Curve& theNC,
1148      const Standard_Real theTolR3D,
1149      const BOPDS_IndexedMapOfPaveBlock& theMPBOnIn,
1150      Handle(BOPDS_PaveBlock)& aPBOut,
1151      Standard_Real& theTolNew)
1152 {
1153   Standard_Boolean bRet;
1154   Standard_Real aT1, aT2, aTm, aTx;
1155   Standard_Integer nSp, iFlag1, iFlag2, nV11, nV12, nV21, nV22, i, aNbPB;
1156   gp_Pnt aP1, aPm, aP2;
1157   Bnd_Box aBoxP1, aBoxPm, aBoxP2, aBoxTmp;
1158   //
1159   bRet=Standard_False;
1160   const IntTools_Curve& aIC=theNC.Curve();
1161   //
1162   thePB->Range(aT1, aT2);
1163   thePB->Indices(nV11, nV12);
1164   const Standard_Real aTolV11 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV11)));
1165   const Standard_Real aTolV12 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV12)));
1166   const Standard_Real aTolV1 = Max(aTolV11, aTolV12);
1167
1168   //first point
1169   aIC.D0(aT1, aP1);
1170   aBoxP1.Add(aP1);
1171   aBoxP1.Enlarge(aTolV11);
1172   //intermediate point
1173   aTm=IntTools_Tools::IntermediatePoint (aT1, aT2);
1174   aIC.D0(aTm, aPm);
1175   aBoxPm.Add(aPm);
1176   //last point
1177   aIC.D0(aT2, aP2);
1178   aBoxP2.Add(aP2);
1179   aBoxP2.Enlarge(aTolV12);
1180   //
1181   theTolNew = 0.;
1182   aNbPB = theMPBOnIn.Extent();
1183   for (i = 1; i <= aNbPB; ++i) {
1184     const Handle(BOPDS_PaveBlock)& aPB = theMPBOnIn(i);
1185     aPB->Indices(nV21, nV22);
1186     const Standard_Real aTolV21 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV21)));
1187     const Standard_Real aTolV22 = BRep_Tool::Tolerance(TopoDS::Vertex(myDS->Shape(nV22)));
1188     const Standard_Real aTolV2 = Max(aTolV21, aTolV22);
1189     nSp=aPB->Edge();
1190     if (nSp < 0)
1191       continue;
1192     const BOPDS_ShapeInfo& aSISp=myDS->ChangeShapeInfo(nSp);
1193     const TopoDS_Edge& aSp=(*(TopoDS_Edge *)(&aSISp.Shape()));
1194     const Bnd_Box& aBoxSp=aSISp.Box();
1195     //
1196     iFlag1 = (nV11 == nV21 || nV11 == nV22) ? 2 : 
1197       (!aBoxSp.IsOut(aBoxP1) ? 1 : 0);
1198     iFlag2 = (nV12 == nV21 || nV12 == nV22) ? 2 : 
1199       (!aBoxSp.IsOut(aBoxP2) ? 1 : 0);
1200     if (iFlag1 && iFlag2) {
1201       Standard_Real aDist;
1202
1203       const Standard_Real aRealTol = myDS->IsCommonBlock(aPB) ?
1204                                      Max(aTolV1, aTolV2) : theTolR3D;
1205
1206       aBoxTmp = aBoxPm;
1207       aBoxTmp.Enlarge(aRealTol);
1208
1209       if (aBoxSp.IsOut(aBoxTmp) || myContext->ComputePE(aPm, 
1210                                                         aRealTol,
1211                                                         aSp, 
1212                                                         aTx, theTolNew)) {
1213         continue;
1214       }
1215       //
1216       if (iFlag1 == 1) {
1217         iFlag1 = !myContext->ComputePE(aP1, aRealTol, aSp, aTx, aDist);
1218         if (theTolNew < aDist)
1219           theTolNew = aDist;
1220       }
1221       //
1222       if (iFlag2 == 1) {
1223         iFlag2 = !myContext->ComputePE(aP2, aRealTol, aSp, aTx, aDist);
1224         if (theTolNew < aDist)
1225           theTolNew = aDist;
1226       }
1227       //
1228       if (iFlag1 && iFlag2) {
1229         aPBOut = aPB;
1230         bRet=Standard_True;
1231         break;
1232       }
1233     }
1234   }
1235   return bRet;
1236 }
1237 //=======================================================================
1238 //function : PutBoundPaveOnCurve
1239 //purpose  : 
1240 //=======================================================================
1241   void BOPAlgo_PaveFiller::PutBoundPaveOnCurve(const TopoDS_Face& aF1,
1242                                                const TopoDS_Face& aF2,
1243                                                const Standard_Real aTolR3D,
1244                                                BOPDS_Curve& aNC,
1245                                                BOPCol_ListOfInteger& aLVB)
1246 {
1247   Standard_Boolean bVF;
1248   Standard_Integer nV, iFlag, nVn, j, aNbEP;
1249   Standard_Real aT[2], aTmin, aTmax, aTV, aTol, aTolVnew;
1250   gp_Pnt aP[2];
1251   TopoDS_Vertex aVn;
1252   BOPDS_ListIteratorOfListOfPave aItLP;
1253   BOPDS_Pave aPn, aPMM[2];
1254   //
1255   aTolVnew = Precision::Confusion();
1256   //
1257   const IntTools_Curve& aIC=aNC.Curve();
1258   aIC.Bounds(aT[0], aT[1], aP[0], aP[1]);
1259   //
1260   Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
1261   const BOPDS_ListOfPave& aLP=aPB->ExtPaves();
1262   //
1263   aNbEP=aLP.Extent();
1264   if (aNbEP) {
1265     aTmin=1.e10;
1266     aTmax=-aTmin;
1267     //
1268     aItLP.Initialize(aLP);
1269     for (; aItLP.More(); aItLP.Next()) {
1270       const BOPDS_Pave& aPv=aItLP.Value();
1271       aPv.Contents(nV, aTV);
1272       if (aTV<aTmin) {
1273         aPMM[0]=aPv;
1274         aTmin=aTV;
1275       }
1276       if (aTV>aTmax) {
1277         aPMM[1]=aPv;
1278         aTmax=aTV;
1279       }
1280     }
1281   }
1282   //
1283   for (j=0; j<2; ++j) {
1284     //if curve is closed, process only one bound
1285     if (j && aP[1].IsEqual(aP[0], aTolVnew)) {
1286       continue;
1287     }
1288     //
1289     iFlag=1;
1290     //
1291     if (aNbEP) {
1292       Bnd_Box aBoxP;
1293       //
1294       aBoxP.Set(aP[j]);
1295       aTol = aTolR3D+Precision::Confusion();
1296       aBoxP.Enlarge(aTol);
1297       const BOPDS_Pave& aPV=aPMM[j];
1298       nV=aPV.Index();
1299       const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1300       const TopoDS_Vertex& aV=(*(TopoDS_Vertex *)(&aSIV.Shape()));
1301       const Bnd_Box& aBoxV=aSIV.Box();
1302       if (!aBoxP.IsOut(aBoxV)){
1303         iFlag=BOPTools_AlgoTools::ComputeVV(aV, aP[j], aTol);
1304       }
1305     }
1306     if (iFlag) {
1307       // 900/L5
1308       bVF=myContext->IsValidPointForFaces (aP[j], aF1, aF2, aTolR3D);
1309       if (!bVF) {
1310         continue;
1311       }
1312       //
1313       BOPDS_ShapeInfo aSIVn;
1314       //
1315       BOPTools_AlgoTools::MakeNewVertex(aP[j], aTolR3D, aVn);
1316       aSIVn.SetShapeType(TopAbs_VERTEX);
1317       aSIVn.SetShape(aVn);
1318       //
1319       nVn=myDS->Append(aSIVn);
1320       //
1321       aPn.SetIndex(nVn);
1322       aPn.SetParameter(aT[j]);
1323       aPB->AppendExtPave(aPn);
1324       //
1325       aVn=(*(TopoDS_Vertex *)(&myDS->Shape(nVn)));
1326       BOPTools_AlgoTools::UpdateVertex (aIC, aT[j], aVn);
1327       //
1328       aTolVnew = BRep_Tool::Tolerance(aVn);
1329       //
1330       BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nVn);
1331       Bnd_Box& aBoxDS=aSIDS.ChangeBox();
1332       BRepBndLib::Add(aVn, aBoxDS);
1333       aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
1334       //
1335       aLVB.Append(nVn);
1336     }
1337   }
1338 }
1339
1340 //=======================================================================
1341 //function : PutPavesOnCurve
1342 //purpose  : 
1343 //=======================================================================
1344   void BOPAlgo_PaveFiller::PutPavesOnCurve
1345   (const BOPCol_MapOfInteger& aMVOnIn,
1346    const Standard_Real aTolR3D,
1347    BOPDS_Curve& aNC,
1348    const Standard_Integer nF1,
1349    const Standard_Integer nF2,
1350    const BOPCol_MapOfInteger& aMI,
1351    const BOPCol_MapOfInteger& aMVEF,
1352    BOPCol_DataMapOfIntegerReal& aMVTol)
1353 {
1354   Standard_Boolean bInBothFaces;
1355   Standard_Integer nV;
1356   BOPCol_MapIteratorOfMapOfInteger aIt;
1357   //
1358   const Bnd_Box& aBoxC=aNC.Box();
1359   //
1360   //Put EF vertices first
1361   aIt.Initialize(aMVEF);
1362   for (; aIt.More(); aIt.Next()) {
1363     nV=aIt.Value();
1364     PutPaveOnCurve(nV, aTolR3D, aNC, aMI, aMVTol, 2);
1365   }
1366   //Put all other vertices
1367   aIt.Initialize(aMVOnIn);
1368   for (; aIt.More(); aIt.Next()) {
1369     nV=aIt.Value();
1370     if (aMVEF.Contains(nV)) {
1371       continue;
1372     }
1373     //
1374     const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1375     const Bnd_Box& aBoxV=aSIV.Box();
1376     //
1377     if (aBoxC.IsOut(aBoxV)){
1378       continue;
1379     }
1380     if (!myDS->IsNewShape(nV)) {
1381       const BOPDS_FaceInfo& aFI1 = myDS->FaceInfo(nF1);
1382       const BOPDS_FaceInfo& aFI2 = myDS->FaceInfo(nF2);
1383       //
1384       bInBothFaces = (aFI1.VerticesOn().Contains(nV) ||
1385                       aFI1.VerticesIn().Contains(nV))&&
1386                      (aFI2.VerticesOn().Contains(nV) ||
1387                       aFI2.VerticesIn().Contains(nV));
1388       if (!bInBothFaces) {
1389         continue;
1390       }
1391     }
1392     //
1393     PutPaveOnCurve(nV, aTolR3D, aNC, aMI, aMVTol, 1);
1394   }
1395 }
1396
1397 //=======================================================================
1398 //function : ExtendedTolerance
1399 //purpose  : 
1400 //=======================================================================
1401 Standard_Boolean BOPAlgo_PaveFiller::ExtendedTolerance
1402   (const Standard_Integer nV,
1403    const BOPCol_MapOfInteger& aMI,
1404    Standard_Real& aTolVExt,
1405    const Standard_Integer aType)
1406 {
1407   Standard_Boolean bFound = Standard_False;
1408   if (!(myDS->IsNewShape(nV))) {
1409     return bFound;
1410   }
1411   //
1412   Standard_Integer i, k, aNbLines, aNbInt;
1413   Standard_Real aT11, aT12, aD1, aD2, aD;
1414   TopoDS_Vertex aV;
1415   gp_Pnt aPV, aP11, aP12;
1416   //
1417   k = 0;
1418   aNbInt = 2;
1419   if (aType == 1) {
1420     aNbInt = 1;
1421   } else if (aType == 2) {
1422     k = 1;
1423   }
1424   //
1425   aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
1426   aPV=BRep_Tool::Pnt(aV);
1427   //
1428   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
1429   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
1430   //
1431   for (; k<aNbInt; ++k) {
1432     aNbLines = !k ? aEEs.Extent() : aEFs.Extent();
1433     for (i = 0; i < aNbLines; ++i) {
1434       BOPDS_Interf *aInt = !k ? (BOPDS_Interf*) (&aEEs(i)) :
1435         (BOPDS_Interf*) (&aEFs(i));
1436       if (aInt->IndexNew() == nV) {
1437         if (aMI.Contains(aInt->Index1()) && 
1438             aMI.Contains(aInt->Index2())) {
1439           const IntTools_CommonPrt& aComPrt = !k ? aEEs(i).CommonPart() :
1440             aEFs(i).CommonPart();
1441           //
1442           const TopoDS_Edge& aE1=aComPrt.Edge1();
1443           aComPrt.Range1(aT11, aT12);
1444           BOPTools_AlgoTools::PointOnEdge(aE1, aT11, aP11);
1445           BOPTools_AlgoTools::PointOnEdge(aE1, aT12, aP12);
1446           aD1=aPV.Distance(aP11);
1447           aD2=aPV.Distance(aP12);
1448           aD=(aD1>aD2)? aD1 : aD2;
1449           if (aD>aTolVExt) {
1450             aTolVExt=aD;
1451           }
1452           return !bFound;
1453         }//if (aMI.Contains(aEF.Index1()) && aMI.Contains(aEF.Index2())) {
1454       }//if (aInt->IndexNew() == nV) {
1455     }//for (i = 0; i < aNbLines; ++i) {
1456   }//for (k=0; k<2; ++k) {
1457   return bFound;
1458 }
1459
1460 //=======================================================================
1461 //function : GetEFPnts
1462 //purpose  : 
1463 //=======================================================================
1464 void BOPAlgo_PaveFiller::GetEFPnts
1465   (const Standard_Integer nF1,
1466    const Standard_Integer nF2,
1467    IntSurf_ListOfPntOn2S& aListOfPnts)
1468 {
1469   Standard_Integer nE, nF, nFOpposite, aNbEFs, i;
1470   Standard_Real U1, U2, V1, V2, f, l;
1471   BOPCol_MapOfInteger aMI;
1472   //
1473   //collect indexes of all shapes from nF1 and nF2.
1474   GetFullShapeMap(nF1, aMI);
1475   GetFullShapeMap(nF2, aMI);
1476   //
1477   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
1478   aNbEFs = aEFs.Extent();
1479   //
1480   for(i = 0; i < aNbEFs; ++i) {
1481     const BOPDS_InterfEF& aEF = aEFs(i);
1482     if (aEF.HasIndexNew()) {
1483       aEF.Indices(nE, nFOpposite);
1484       if(aMI.Contains(nE) && aMI.Contains(nFOpposite)) {
1485         const IntTools_CommonPrt& aCP = aEF.CommonPart();
1486         Standard_Real aPar = aCP.VertexParameter1();
1487         const TopoDS_Edge& aE = (*(TopoDS_Edge*)(&myDS->Shape(nE)));
1488         const TopoDS_Face& aFOpposite = 
1489           (*(TopoDS_Face*)(&myDS->Shape(nFOpposite)));
1490         //
1491         const Handle(Geom_Curve)& aCurve = BRep_Tool::Curve(aE, f, l);
1492         //
1493         nF = (nFOpposite == nF1) ? nF2 : nF1;
1494         const TopoDS_Face& aF = (*(TopoDS_Face*)(&myDS->Shape(nF)));
1495         Handle(Geom2d_Curve) aPCurve = 
1496           BRep_Tool::CurveOnSurface(aE, aF, f, l);
1497         //
1498         GeomAPI_ProjectPointOnSurf& aProj=myContext->ProjPS(aFOpposite);
1499         //
1500         gp_Pnt aPoint;
1501         aCurve->D0(aPar, aPoint);
1502         IntSurf_PntOn2S aPnt;
1503         if(!aPCurve.IsNull()) {
1504           gp_Pnt2d aP2d = aPCurve->Value(aPar);
1505           aProj.Perform(aPoint);
1506           if(aProj.IsDone()) {
1507             aProj.LowerDistanceParameters(U1,V1);
1508             if (nF == nF1) {
1509               aPnt.SetValue(aP2d.X(),aP2d.Y(),U1,V1);
1510             } else {
1511               aPnt.SetValue(U1,V1,aP2d.X(),aP2d.Y());
1512             }
1513             aListOfPnts.Append(aPnt);
1514           }
1515         }
1516         else {
1517           GeomAPI_ProjectPointOnSurf& aProj1 = myContext->ProjPS(aF);
1518           aProj1.Perform(aPoint);
1519           aProj.Perform(aPoint);
1520           if(aProj1.IsDone() && aProj.IsDone()){
1521             aProj1.LowerDistanceParameters(U1,V1);
1522             aProj.LowerDistanceParameters(U2,V2);
1523             if (nF == nF1) {
1524               aPnt.SetValue(U1,V1,U2,V2);
1525             } else {
1526               aPnt.SetValue(U2,V2,U1,V1);
1527             }
1528             aListOfPnts.Append(aPnt);
1529           }
1530         }
1531       }
1532     }
1533   }
1534 }
1535
1536 //=======================================================================
1537 //function : ProcessUnUsedVertices
1538 //purpose  : 
1539 //=======================================================================
1540   void BOPAlgo_PaveFiller::PutEFPavesOnCurve
1541   (BOPDS_Curve& aNC,
1542    const BOPCol_MapOfInteger& aMI,
1543    const BOPCol_MapOfInteger& aMVEF,
1544    BOPCol_DataMapOfIntegerReal& aMVTol)
1545 {
1546   if (!aMVEF.Extent()) {
1547     return;
1548   }
1549   //
1550   const IntTools_Curve& aIC=aNC.Curve();
1551   GeomAbs_CurveType aTypeC;
1552   aTypeC=aIC.Type();
1553   if (!(aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve)) {
1554     return;
1555   }
1556   //
1557   Standard_Integer nV;
1558   BOPCol_MapOfInteger aMV;
1559   //
1560   aMV.Assign(aMVEF);
1561   RemoveUsedVertices(aNC, aMV);
1562   if (!aMV.Extent()) {
1563     return;
1564   }
1565   //
1566   Standard_Real aDist;
1567   BOPDS_Pave aPave;
1568   //
1569   const Handle(Geom_Curve)& aC3D=aIC.Curve();
1570   GeomAPI_ProjectPointOnCurve& aProjPT = myContext->ProjPT(aC3D);
1571   //
1572   BOPCol_MapIteratorOfMapOfInteger aItMI;
1573   aItMI.Initialize(aMV);
1574   for (; aItMI.More(); aItMI.Next()) {
1575     nV = aItMI.Value();
1576     const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
1577     gp_Pnt aPV = BRep_Tool::Pnt(aV);
1578     aProjPT.Perform(aPV);
1579     Standard_Integer aNbPoints = aProjPT.NbPoints();
1580     if (aNbPoints) {
1581       aDist = aProjPT.LowerDistance();
1582       PutPaveOnCurve(nV, aDist, aNC, aMI, aMVTol);
1583     }
1584   }
1585 }
1586
1587 //=======================================================================
1588 //function : ProcessUnUsedVertices
1589 //purpose  : 
1590 //=======================================================================
1591   void BOPAlgo_PaveFiller::PutStickPavesOnCurve
1592   (const TopoDS_Face& aF1,
1593    const TopoDS_Face& aF2,
1594    const BOPCol_MapOfInteger& aMI,
1595    BOPDS_Curve& aNC,
1596    const BOPCol_MapOfInteger& aMVStick,
1597    BOPCol_DataMapOfIntegerReal& aMVTol)
1598 {
1599   BOPCol_MapOfInteger aMV;
1600   aMV.Assign(aMVStick);
1601   RemoveUsedVertices(aNC, aMV);
1602   //
1603   if (!aMV.Extent()) {
1604     return;
1605   }
1606   //
1607   Handle(Geom_Surface) aS1=BRep_Tool::Surface(aF1);
1608   Handle(Geom_Surface) aS2=BRep_Tool::Surface(aF2);
1609   //
1610   const IntTools_Curve& aIC=aNC.Curve();
1611   //if (aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve) {
1612   Handle(Geom2d_Curve) aC2D[2];
1613   //
1614   aC2D[0]=aIC.FirstCurve2d();
1615   aC2D[1]=aIC.SecondCurve2d();
1616   if (!aC2D[0].IsNull() && !aC2D[1].IsNull()) {
1617     Standard_Integer nV, m, n;
1618     Standard_Real aTC[2], aD, aD2, u, v, aDT2, aScPr, aDScPr;
1619     gp_Pnt aPC[2], aPV;
1620     gp_Dir aDN[2];
1621     gp_Pnt2d aP2D;
1622     BOPCol_MapIteratorOfMapOfInteger aItMI, aItMI1;
1623     //
1624     aDT2=2e-7;     // the rich criteria
1625     aDScPr=5.e-9;  // the creasing criteria
1626     aIC.Bounds(aTC[0], aTC[1], aPC[0], aPC[1]);
1627     //
1628     aItMI.Initialize(aMV);
1629     for (; aItMI.More(); aItMI.Next()) {
1630       nV = aItMI.Value();
1631       const TopoDS_Vertex& aV=*((TopoDS_Vertex*)&myDS->Shape(nV));
1632       aPV=BRep_Tool::Pnt(aV);
1633       //
1634       for (m=0; m<2; ++m) {
1635         aD2=aPC[m].SquareDistance(aPV);
1636         if (aD2>aDT2) {// no rich
1637           continue; 
1638         }
1639         //
1640         for (n=0; n<2; ++n) {
1641           Handle(Geom_Surface)& aS=(!n)? aS1 : aS2;
1642           aC2D[n]->D0(aTC[m], aP2D);
1643           aP2D.Coord(u, v);
1644           BOPTools_AlgoTools3D::GetNormalToSurface(aS, u, v, aDN[n]);
1645         }
1646         // 
1647         aScPr=aDN[0]*aDN[1];
1648         if (aScPr<0.) {
1649           aScPr=-aScPr;
1650         }
1651         aScPr=1.-aScPr;
1652         //
1653         if (aScPr>aDScPr) {
1654           continue;
1655         }
1656         //
1657         // The intersection curve aIC is vanishing curve (the crease)
1658         aD=sqrt(aD2);
1659         //
1660         PutPaveOnCurve(nV, aD, aNC, aMI, aMVTol);
1661       }
1662     }//for (jVU=1; jVU=aNbVU; ++jVU) {
1663   }
1664   //}//if (aTypeC==GeomAbs_BezierCurve || aTypeC==GeomAbs_BSplineCurve) {
1665   //}//if(aType1==GeomAbs_Torus  || aType2==GeomAbs_Torus) {
1666 }
1667
1668 //=======================================================================
1669 //function : GetStickVertices
1670 //purpose  : 
1671 //=======================================================================
1672 void BOPAlgo_PaveFiller::GetStickVertices(const Standard_Integer nF1,
1673                                           const Standard_Integer nF2,
1674                                           BOPCol_MapOfInteger& aMVStick,
1675                                           BOPCol_MapOfInteger& aMVEF,
1676                                           BOPCol_MapOfInteger& aMI)
1677 {
1678   Standard_Integer nS1, nS2, nVNew, aTypeInt, i;
1679   //
1680   BOPDS_VectorOfInterfVV& aVVs=myDS->InterfVV();
1681   BOPDS_VectorOfInterfVE& aVEs=myDS->InterfVE();
1682   BOPDS_VectorOfInterfEE& aEEs=myDS->InterfEE();
1683   BOPDS_VectorOfInterfVF& aVFs=myDS->InterfVF();
1684   BOPDS_VectorOfInterfEF& aEFs=myDS->InterfEF();
1685   //
1686   Standard_Integer aNbLines[5] = {
1687     aVVs.Extent(), aVEs.Extent(), aEEs.Extent(),
1688     aVFs.Extent(), aEFs.Extent()
1689     };
1690   //collect indices of all shapes from nF1 and nF2.
1691   aMI.Clear();
1692   GetFullShapeMap(nF1, aMI);
1693   GetFullShapeMap(nF2, aMI);
1694   //
1695   //collect VV, VE, EE, VF interferences
1696   for (aTypeInt = 0; aTypeInt < 4; ++aTypeInt) {
1697     for (i = 0; i < aNbLines[aTypeInt]; ++i) {
1698       BOPDS_Interf* aInt = (aTypeInt==0) ? (BOPDS_Interf*)(&aVVs(i)) : 
1699         ((aTypeInt==1) ? (BOPDS_Interf*)(&aVEs(i)) :
1700          ((aTypeInt==2) ? (BOPDS_Interf*)(&aEEs(i)) : 
1701           (BOPDS_Interf*)(&aVFs(i))));
1702       if (aInt->HasIndexNew()) {
1703         aInt->Indices(nS1, nS2);
1704         if(aMI.Contains(nS1) && aMI.Contains(nS2)) {
1705           nVNew = aInt->IndexNew();
1706           aMVStick.Add(nVNew);
1707         }
1708       }
1709     }
1710   }
1711   //collect EF interferences
1712   for (i = 0; i < aNbLines[4]; ++i) {
1713     const BOPDS_InterfEF& aInt = aEFs(i);
1714     if (aInt.HasIndexNew()) {
1715       aInt.Indices(nS1, nS2);
1716       if(aMI.Contains(nS1) && aMI.Contains(nS2)) {
1717         nVNew = aInt.IndexNew();
1718         aMVStick.Add(nVNew);
1719         aMVEF.Add(nVNew);
1720       }
1721     }
1722   }
1723 }
1724
1725 //=======================================================================
1726 // function: GetFullShapeMap
1727 // purpose: 
1728 //=======================================================================
1729 void BOPAlgo_PaveFiller::GetFullShapeMap(const Standard_Integer nF,
1730                                          BOPCol_MapOfInteger& aMI)
1731 {
1732   BOPCol_ListIteratorOfListOfInteger aIt;
1733   Standard_Integer nS;
1734   //
1735   const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nF);
1736   const BOPCol_ListOfInteger& aLI = aSI.SubShapes();
1737   //
1738   aMI.Add(nF);
1739   aIt.Initialize(aLI);
1740   for (; aIt.More(); aIt.Next()) {
1741     nS = aIt.Value();
1742     aMI.Add(nS);
1743   }
1744 }
1745
1746 //=======================================================================
1747 // function: RemoveUsedVertices
1748 // purpose: 
1749 //=======================================================================
1750 void BOPAlgo_PaveFiller::RemoveUsedVertices(BOPDS_Curve& aNC,
1751                                             BOPCol_MapOfInteger& aMV)
1752 {
1753   if (!aMV.Extent()) {
1754     return;
1755   }
1756   Standard_Integer nV;
1757   BOPDS_Pave aPave;
1758   BOPDS_ListIteratorOfListOfPave aItLP;
1759   //
1760   Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
1761   const BOPDS_ListOfPave& aLP = aPB->ExtPaves();
1762   aItLP.Initialize(aLP);
1763   for (;aItLP.More();aItLP.Next()) {
1764     aPave = aItLP.Value();
1765     nV = aPave.Index();
1766     aMV.Remove(nV);
1767   }
1768 }
1769
1770 //=======================================================================
1771 //function : PutPaveOnCurve
1772 //purpose  : 
1773 //=======================================================================
1774   void BOPAlgo_PaveFiller::PutPaveOnCurve
1775   (const Standard_Integer nV,
1776    const Standard_Real aTolR3D,
1777    BOPDS_Curve& aNC,
1778    const BOPCol_MapOfInteger& aMI,
1779    BOPCol_DataMapOfIntegerReal& aMVTol,
1780    const Standard_Integer iCheckExtend)
1781 {
1782   Standard_Boolean bIsVertexOnLine;
1783   Standard_Real aT, aTolV;
1784   //
1785   const TopoDS_Vertex& aV = (*(TopoDS_Vertex *)(&myDS->Shape(nV)));
1786   Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
1787   const IntTools_Curve& aIC = aNC.Curve();
1788   //
1789   bIsVertexOnLine=myContext->IsVertexOnLine(aV, aIC, aTolR3D, aT);
1790   if (!bIsVertexOnLine && iCheckExtend) {
1791     aTolV = BRep_Tool::Tolerance(aV);
1792     //
1793     ExtendedTolerance(nV, aMI, aTolV, iCheckExtend);
1794     bIsVertexOnLine=myContext->IsVertexOnLine(aV, aTolV, aIC, aTolR3D, aT);
1795   }
1796   //
1797   if (bIsVertexOnLine) {
1798     // check if aPB contains the parameter aT
1799     Standard_Boolean bExist;
1800     Standard_Integer nVToUpdate;
1801     Standard_Real aPTol, aDist, aTolVNew, aTolV2, aDTol;
1802     TopoDS_Vertex aVToUpdate;
1803     gp_Pnt aP1, aP2;
1804     //
1805     aTolV2 = 0.;
1806     aDTol = 1.e-12;
1807     //
1808     GeomAdaptor_Curve aGAC(aIC.Curve());
1809     aPTol = aGAC.Resolution(aTolR3D);
1810     //
1811     bExist = aPB->ContainsParameter(aT, aPTol, nVToUpdate);
1812     if (bExist) {
1813       // use existing pave
1814       aP1 = BRep_Tool::Pnt(aV);
1815       aTolV2 = BRep_Tool::Tolerance(aV);
1816       aVToUpdate = (*(TopoDS_Vertex *)(&myDS->Shape(nVToUpdate)));
1817     }
1818     else {
1819       // add new pave
1820       BOPDS_Pave aPave;
1821       aPave.SetIndex(nV);
1822       aPave.SetParameter(aT);
1823       aPB->AppendExtPave(aPave);
1824       //
1825       aP1 = aGAC.Value(aT);
1826       nVToUpdate = nV;
1827       aVToUpdate = aV;
1828     }
1829     //
1830     aTolV = BRep_Tool::Tolerance(aVToUpdate);
1831     aP2 = BRep_Tool::Pnt(aVToUpdate);
1832     aDist = aP1.Distance(aP2);
1833     aTolVNew = Max(aDist - aTolV2, aTolR3D);
1834     //
1835     if (aTolVNew > aTolV) {
1836       BRep_Builder aBB;
1837       aBB.UpdateVertex(aVToUpdate, aTolVNew+aDTol);
1838       //
1839       if (!aMVTol.IsBound(nVToUpdate)) {
1840         aMVTol.Bind(nVToUpdate, aTolV);
1841       }
1842       // 
1843       BOPDS_ShapeInfo& aSIDS=myDS->ChangeShapeInfo(nVToUpdate);
1844       Bnd_Box& aBoxDS=aSIDS.ChangeBox();
1845       BRepBndLib::Add(aVToUpdate, aBoxDS);
1846       aBoxDS.SetGap(aBoxDS.GetGap() + Precision::Confusion());
1847     }
1848   }
1849 }
1850
1851 //=======================================================================
1852 //function : ProcessOldPaveBlocks
1853 //purpose  : 
1854 //=======================================================================
1855 void BOPAlgo_PaveFiller::ProcessExistingPaveBlocks
1856     (const Standard_Integer theInt,
1857      const BOPDS_IndexedMapOfPaveBlock& aMPBOnIn,
1858      const BOPCol_DataMapOfIntegerListOfInteger& aDMBV,
1859      BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& aMSCPB,
1860      BOPCol_DataMapOfShapeInteger& aMVI,
1861      BOPDS_MapOfPaveBlock& aMPB)
1862 {
1863   if (aDMBV.IsEmpty()) {
1864     return;
1865   }
1866   //
1867   Standard_Real aT, dummy;
1868   Standard_Integer i, nV, nE, iC, aNbPB, iFlag;
1869   BOPCol_ListIteratorOfListOfInteger aItLI;
1870   BOPCol_DataMapIteratorOfDataMapOfIntegerListOfInteger aItBV;
1871   //
1872   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
1873   BOPDS_InterfFF& aFF = aFFs(theInt);
1874   BOPDS_VectorOfCurve& aVC = aFF.ChangeCurves();
1875   //
1876   aNbPB = aMPBOnIn.Extent();
1877   //
1878   aItBV.Initialize(aDMBV);
1879   for (; aItBV.More(); aItBV.Next()) {
1880     iC = aItBV.Key();
1881     const BOPCol_ListOfInteger& aLBV = aItBV.Value();
1882     //
1883     BOPDS_Curve& aNC = aVC.ChangeValue(iC);
1884     BOPDS_ListOfPaveBlock& aLPBC = aNC.ChangePaveBlocks();
1885     //
1886     aItLI.Initialize(aLBV);
1887     for (; aItLI.More(); aItLI.Next()) {
1888       nV = aItLI.Value();
1889       const BOPDS_ShapeInfo& aSIV=myDS->ShapeInfo(nV);
1890       const Bnd_Box& aBoxV=aSIV.Box();
1891       const TopoDS_Vertex& aV = *(TopoDS_Vertex*)&aSIV.Shape();
1892       if (!aMVI.IsBound(aV)) {
1893         continue;
1894       }
1895       //
1896       for (i = 1; i <= aNbPB; ++i) {
1897         const Handle(BOPDS_PaveBlock)& aPB = aMPBOnIn(i);
1898         if (aPB->Pave1().Index() == nV || aPB->Pave2().Index() == nV) {
1899           continue;
1900         }
1901         //
1902         if (aMPB.Contains(aPB)) {
1903           continue;
1904         }
1905         if (myDS->ShapeInfo(aPB->OriginalEdge()).HasFlag()) { // skip degenerated edges
1906           continue;
1907         }
1908         //
1909         nE = aPB->Edge();
1910         const BOPDS_ShapeInfo& aSIE = myDS->ShapeInfo(nE);
1911         const Bnd_Box& aBoxE = aSIE.Box();
1912         //
1913         if (aBoxV.IsOut(aBoxE)) {
1914           continue;
1915         }
1916         //
1917         const TopoDS_Edge& aE = *(TopoDS_Edge*)&aSIE.Shape();
1918         //
1919         iFlag = myContext->ComputeVE(aV, aE, aT, dummy);
1920         if (!iFlag) {
1921           aMPB.Add(aPB);
1922           PreparePostTreatFF(theInt, iC, aPB, aMSCPB, aMVI, aLPBC);
1923         }
1924       }
1925     }
1926   }
1927 }
1928 //=======================================================================
1929 //function : UpdateExistingPaveBlocks
1930 //purpose  : 
1931 //=======================================================================
1932 void BOPAlgo_PaveFiller::UpdateExistingPaveBlocks
1933   (const Handle(BOPDS_PaveBlock)& aPBf,
1934    BOPDS_ListOfPaveBlock& aLPB,
1935    const Standard_Integer nF1,
1936    const Standard_Integer nF2) 
1937 {
1938   Standard_Integer nE;
1939   Standard_Boolean bCB;
1940   Handle(BOPDS_PaveBlock) aPB, aPB1, aPB2, aPB2n;
1941   Handle(BOPDS_CommonBlock) aCB;
1942   BOPDS_ListIteratorOfListOfPaveBlock aIt, aIt1, aIt2;
1943   //
1944   // 1. Remove micro edges from aLPB
1945   aIt.Initialize(aLPB);
1946   for (; aIt.More();) {
1947     aPB = aIt.Value();
1948     const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPB->Edge());
1949     if (BOPTools_AlgoTools::IsMicroEdge(aE, myContext)) {
1950       aLPB.Remove(aIt);
1951       continue;
1952     }
1953     aIt.Next();
1954   }
1955   //
1956   if (!aLPB.Extent()) {
1957     return;
1958   }
1959   //
1960   BOPDS_FaceInfo& aFI1 = myDS->ChangeFaceInfo(nF1);
1961   BOPDS_FaceInfo& aFI2 = myDS->ChangeFaceInfo(nF2);
1962   //
1963   BOPDS_IndexedMapOfPaveBlock& aMPBOn1 = aFI1.ChangePaveBlocksOn();
1964   BOPDS_IndexedMapOfPaveBlock& aMPBIn1 = aFI1.ChangePaveBlocksIn();
1965   BOPDS_IndexedMapOfPaveBlock& aMPBOn2 = aFI2.ChangePaveBlocksOn();
1966   BOPDS_IndexedMapOfPaveBlock& aMPBIn2 = aFI2.ChangePaveBlocksIn();
1967   //
1968   // 2. Remove old pave blocks
1969   const Handle(BOPDS_CommonBlock)& aCB1 = myDS->CommonBlock(aPBf);
1970   bCB = !aCB1.IsNull();
1971   BOPDS_ListOfPaveBlock aLPB1;
1972   //
1973   if (bCB) {
1974     aLPB1.Assign(aCB1->PaveBlocks());
1975   } else {
1976     aLPB1.Append(aPBf);
1977   }
1978   aIt1.Initialize(aLPB1);
1979   for (; aIt1.More(); aIt1.Next()) {
1980     aPB1 = aIt1.Value();
1981     nE = aPB1->OriginalEdge();
1982     //
1983     BOPDS_ListOfPaveBlock& aLPB2 = myDS->ChangePaveBlocks(nE);
1984     aIt2.Initialize(aLPB2);
1985     for (; aIt2.More(); aIt2.Next()) {
1986       aPB2 = aIt2.Value();
1987       if (aPB1 == aPB2) {
1988         aLPB2.Remove(aIt2);
1989         break;
1990       }
1991     }
1992   }
1993   //
1994   // 3. Update pave blocks
1995   if (bCB) {
1996     //create new common blocks
1997     BOPDS_ListOfPaveBlock aLPBNew;
1998     const BOPCol_ListOfInteger& aFaces = aCB1->Faces();
1999     aIt.Initialize(aLPB);
2000     for (; aIt.More(); aIt.Next()) {
2001       const Handle(BOPDS_PaveBlock)& aPBValue = aIt.Value();
2002       //
2003       aCB = new BOPDS_CommonBlock;
2004       aIt1.Initialize(aLPB1);
2005       for (; aIt1.More(); aIt1.Next()) {
2006         aPB2 = aIt1.Value();
2007         nE = aPB2->OriginalEdge();
2008         //
2009         aPB2n = new BOPDS_PaveBlock;
2010         aPB2n->SetPave1(aPBValue->Pave1());
2011         aPB2n->SetPave2(aPBValue->Pave2());
2012         aPB2n->SetEdge(aPBValue->Edge());
2013         aPB2n->SetOriginalEdge(nE);
2014         aCB->AddPaveBlock(aPB2n);
2015         myDS->SetCommonBlock(aPB2n, aCB);
2016         myDS->ChangePaveBlocks(nE).Append(aPB2n);
2017       }
2018       aCB->SetFaces(aFaces);
2019       myDS->SortPaveBlocks(aCB);
2020       //
2021       const Handle(BOPDS_PaveBlock)& aPBNew = aCB->PaveBlocks().First();
2022       aLPBNew.Append(aPBNew);
2023     }
2024     //
2025     aLPB = aLPBNew;
2026   } 
2027   else {
2028     nE = aPBf->OriginalEdge();
2029     BOPDS_ListOfPaveBlock& aLPBE = myDS->ChangePaveBlocks(nE);
2030     aIt.Initialize(aLPB);
2031     for (; aIt.More(); aIt.Next()) {
2032       aPB = aIt.Value();
2033       aLPBE.Append(aPB);
2034     }
2035   }
2036   //
2037   Standard_Boolean bIn1, bIn2;
2038   //
2039   bIn1 = aMPBOn1.Contains(aPBf) || aMPBIn1.Contains(aPBf);
2040   bIn2 = aMPBOn2.Contains(aPBf) || aMPBIn2.Contains(aPBf);
2041   //
2042   if (bIn1 && bIn2) {
2043     return;
2044   }
2045   //
2046   // 4. Check new pave blocks for coincidence 
2047   //    with the opposite face.
2048   //    In case of coincidence create common blocks
2049   Standard_Integer nF;
2050   Standard_Real aTolE, aTolF;
2051   //
2052   nF = bIn1 ? nF2 : nF1;
2053   const TopoDS_Face& aF = *(TopoDS_Face*)&myDS->Shape(nF);
2054   BOPDS_IndexedMapOfPaveBlock& aMPBIn = bIn1 ? aMPBIn2 : aMPBIn1;
2055   aTolF = BRep_Tool::Tolerance(aF);
2056   //
2057   aIt.Initialize(aLPB);
2058   for (; aIt.More(); aIt.Next()) {
2059     Handle(BOPDS_PaveBlock)& aPBChangeValue = aIt.ChangeValue();
2060     const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPBChangeValue->Edge());
2061     aTolE = BRep_Tool::Tolerance(aE);
2062     //
2063     IntTools_EdgeFace anEF;
2064     anEF.SetEdge(aE);
2065     anEF.SetFace(aF);
2066     anEF.SetTolE(aTolE);
2067     anEF.SetTolF(aTolF);
2068     anEF.SetRange(aPBChangeValue->Pave1().Parameter(), aPBChangeValue->Pave2().Parameter());
2069     anEF.SetContext(myContext);
2070     anEF.Perform();
2071     //
2072     const IntTools_SequenceOfCommonPrts& aCPrts=anEF.CommonParts();
2073     if (aCPrts.Length() == 1) {
2074       Standard_Boolean bCoinc = (aCPrts(1).Type() == TopAbs_EDGE);
2075       if (bCoinc) {
2076         if (bCB) {
2077           aCB = myDS->CommonBlock(aPBChangeValue);
2078         } else {
2079           aCB = new BOPDS_CommonBlock;
2080           aCB->AddPaveBlock(aPBChangeValue);
2081           myDS->SetCommonBlock(aPBChangeValue, aCB);
2082         }
2083         aCB->AddFace(nF);
2084         //
2085         aMPBIn.Add(aPBChangeValue);
2086       }
2087     }
2088   }
2089 }
2090 //=======================================================================
2091 // function: PutClosingPaveOnCurve
2092 // purpose:
2093 //=======================================================================
2094 void BOPAlgo_PaveFiller::PutClosingPaveOnCurve(BOPDS_Curve& aNC)
2095 {
2096   Standard_Boolean bIsClosed, bHasBounds, bAdded;
2097   Standard_Integer nVC, j;
2098   Standard_Real aT[2], aTC, dT, aTx;
2099   gp_Pnt aP[2] ; 
2100   BOPDS_Pave aPVx;
2101   BOPDS_ListIteratorOfListOfPave aItLP;
2102   //
2103   const IntTools_Curve& aIC=aNC.Curve();
2104   const Handle(Geom_Curve)& aC3D=aIC.Curve();
2105   if(aC3D.IsNull()) {
2106     return;
2107   }
2108   //
2109   bIsClosed=IntTools_Tools::IsClosed(aC3D);
2110   if (!bIsClosed) {
2111     return;
2112   }
2113   //
2114   bHasBounds=aIC.HasBounds ();
2115   if (!bHasBounds){
2116     return;
2117   }
2118   // 
2119   bAdded=Standard_False;
2120   dT=Precision::PConfusion();
2121   aIC.Bounds (aT[0], aT[1], aP[0], aP[1]);
2122   //
2123   Handle(BOPDS_PaveBlock)& aPB=aNC.ChangePaveBlock1();
2124   BOPDS_ListOfPave& aLP=aPB->ChangeExtPaves();
2125   //
2126   aItLP.Initialize(aLP);
2127   for (; aItLP.More() && !bAdded; aItLP.Next()) {
2128     const BOPDS_Pave& aPC=aItLP.Value();
2129     nVC=aPC.Index();
2130     aTC=aPC.Parameter();
2131     //
2132     for (j=0; j<2; ++j) {
2133       if (fabs(aTC-aT[j]) < dT) {
2134         aTx=(!j) ? aT[1] : aT[0];
2135         aPVx.SetIndex(nVC);
2136         aPVx.SetParameter(aTx);
2137         aLP.Append(aPVx);
2138         //
2139         bAdded=Standard_True;
2140         break;
2141       }
2142     }
2143   }
2144 }
2145 //=======================================================================
2146 //function : PreparePostTreatFF
2147 //purpose  : 
2148 //=======================================================================
2149 void BOPAlgo_PaveFiller::PreparePostTreatFF
2150     (const Standard_Integer aInt,
2151      const Standard_Integer aCur,
2152      const Handle(BOPDS_PaveBlock)& aPB,
2153      BOPDS_IndexedDataMapOfShapeCoupleOfPaveBlocks& aMSCPB,
2154      BOPCol_DataMapOfShapeInteger& aMVI,
2155      BOPDS_ListOfPaveBlock& aLPBC)
2156 {
2157   Standard_Integer nV1, nV2;
2158   //
2159   aLPBC.Append(aPB);
2160   //
2161   aPB->Indices(nV1, nV2);
2162   const TopoDS_Vertex& aV1=(*(TopoDS_Vertex *)(&myDS->Shape(nV1)));
2163   const TopoDS_Vertex& aV2=(*(TopoDS_Vertex *)(&myDS->Shape(nV2)));
2164   const TopoDS_Edge& aE = *(TopoDS_Edge*)&myDS->Shape(aPB->Edge());
2165   // Keep info for post treatment 
2166   BOPDS_CoupleOfPaveBlocks aCPB;
2167   aCPB.SetIndexInterf(aInt);
2168   aCPB.SetIndex(aCur);
2169   aCPB.SetPaveBlock1(aPB);
2170   //
2171   aMSCPB.Add(aE, aCPB);
2172   aMVI.Bind(aV1, nV1);
2173   aMVI.Bind(aV2, nV2);
2174 }
2175
2176 //=======================================================================
2177 //function : CheckPlanes
2178 //purpose  : 
2179 //=======================================================================
2180 Standard_Boolean BOPAlgo_PaveFiller::CheckPlanes
2181   (const Standard_Integer nF1,
2182    const Standard_Integer nF2)const
2183 {
2184   Standard_Boolean bToIntersect;
2185   Standard_Integer i, nV2, iCnt;
2186   BOPCol_MapIteratorOfMapOfInteger aIt;
2187   //
2188   bToIntersect=Standard_False;
2189   //
2190   const BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
2191   const BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
2192   //
2193   const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
2194   const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
2195   //
2196   iCnt=0;
2197   for (i=0; (i<2 && !bToIntersect); ++i) {
2198     const BOPCol_MapOfInteger& aMV2=(!i) ? aFI2.VerticesIn() 
2199       : aFI2.VerticesOn();
2200     //
2201     aIt.Initialize(aMV2);
2202     for (; aIt.More(); aIt.Next()) {
2203       nV2=aIt.Value();
2204       if (aMVIn1.Contains(nV2) || aMVOn1.Contains(nV2)) {
2205         ++iCnt;
2206         if (iCnt>1) {
2207           bToIntersect=!bToIntersect;
2208           break;
2209         }
2210       }
2211     }
2212   }
2213   //
2214   return bToIntersect;
2215 }
2216 //=======================================================================
2217 //function : UpdatePaveBlocks
2218 //purpose  : 
2219 //=======================================================================
2220 void BOPAlgo_PaveFiller::UpdatePaveBlocks
2221 (const BOPCol_DataMapOfIntegerInteger& aDMI)
2222 {
2223   if (aDMI.IsEmpty()) {
2224     return;
2225   }
2226   //
2227   Standard_Integer nSp, aNbPBP, nV[2], i, j;
2228   Standard_Real aT[2];
2229   Standard_Boolean bCB, bRebuild;
2230   BOPDS_ListIteratorOfListOfPaveBlock aItPB;
2231   BOPDS_MapOfPaveBlock aMPB;
2232   BOPCol_MapOfInteger aMicroEdges;
2233   //
2234   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
2235   aNbPBP = aPBP.Extent();
2236   for (i = 0; i < aNbPBP; ++i) {
2237     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2238     //
2239     aItPB.Initialize(aLPB);
2240     for (; aItPB.More(); aItPB.Next()) {
2241       Handle(BOPDS_PaveBlock) aPB = aItPB.Value();
2242       const Handle(BOPDS_CommonBlock)& aCB = myDS->CommonBlock(aPB);
2243       bCB = !aCB.IsNull();
2244       if (bCB) {
2245         aPB = aCB->PaveBlock1();
2246       }
2247       //
2248       if (aMPB.Add(aPB)) {
2249         bRebuild = Standard_False;
2250         aPB->Indices(nV[0], nV[1]);
2251         aPB->Range(aT[0], aT[1]);
2252         // remember the fact if the edge had different vertices before substitution
2253         Standard_Boolean wasRegularEdge = (nV[0] != nV[1]);
2254         //
2255         for (j = 0; j < 2; ++j) {
2256           if (aDMI.IsBound(nV[j])) {
2257             BOPDS_Pave aPave;
2258             //
2259             nV[j] = aDMI.Find(nV[j]);
2260             aPave.SetIndex(nV[j]);
2261             aPave.SetParameter(aT[j]);
2262             //
2263             bRebuild = Standard_True;
2264             if (!j) {
2265               aPB->SetPave1(aPave);
2266             }
2267             else {
2268               aPB->SetPave2(aPave);
2269             }
2270           }
2271         }
2272         //
2273         if (bRebuild) {
2274           Standard_Boolean isDegEdge = myDS->ShapeInfo(aPB->Edge()).HasFlag();
2275           if (wasRegularEdge && !isDegEdge && nV[0] == nV[1]) {
2276             // now edge has the same vertex on both ends;
2277             // check if it is not a regular closed curve.
2278             const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(aPB->Edge()));
2279             const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV[0]));
2280             Standard_Real aLength = IntTools::Length(aE);
2281             Standard_Real aTolV = BRep_Tool::Tolerance(aV);
2282             if (aLength <= aTolV * 2.) {
2283               // micro edge, so mark it for removal
2284               aMicroEdges.Add(aPB->Edge());
2285               continue;
2286             }
2287           }
2288           nSp = SplitEdge(aPB->OriginalEdge(), nV[0], aT[0], nV[1], aT[1]);
2289           if (bCB) {
2290             aCB->SetEdge(nSp);
2291           }
2292           else {
2293             aPB->SetEdge(nSp);
2294           }
2295         }// if (bRebuild) {
2296       }// if (aMPB.Add(aPB)) {
2297     }// for (; aItPB.More(); aItPB.Next()) {
2298   }// for (i=0; i<aNbPBP; ++i) {
2299   aMPB.Clear();
2300
2301   if (aMicroEdges.Extent())
2302     RemovePaveBlocks(aMicroEdges);
2303 }
2304 //=======================================================================
2305 //function : RemovePaveBlocks
2306 //purpose  : 
2307 //=======================================================================
2308 void BOPAlgo_PaveFiller::RemovePaveBlocks(const BOPCol_MapOfInteger theEdges)
2309 {
2310   // Remove all pave blocks referring to input edges:
2311   //
2312   // 1. from the Pave Blocks Pool
2313   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
2314   Standard_Integer aNbPBP = aPBP.Extent(), i;
2315   for (i = 0; i < aNbPBP; ++i) {
2316     BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2317     //
2318     BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
2319     while (aItPB.More()) {
2320       const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
2321       if (theEdges.Contains(aPB->Edge()))
2322         aLPB.Remove(aItPB);
2323       else
2324         aItPB.Next();
2325     }
2326   }
2327
2328   // 2. from Face Info and section curves
2329   BOPCol_MapOfInteger aMPassed;
2330   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2331   Standard_Integer aNbFF = aFFs.Extent(), j;
2332   for (i = 0; i < aNbFF; ++i) {
2333     BOPDS_InterfFF& aFF = aFFs(i);
2334     Standard_Integer nF1, nF2;
2335     aFF.Indices(nF1, nF2);
2336     //
2337     // rebuild pave block maps of face info
2338     for (j = 0; j < 2; j++) {
2339       Standard_Integer nF = (j == 0 ? nF1 : nF2);
2340       if (!aMPassed.Add(nF))
2341         continue;
2342       BOPDS_FaceInfo& aFI = myDS->ChangeFaceInfo(nF);
2343       BOPDS_IndexedMapOfPaveBlock* aIMPB[] = { &aFI.ChangePaveBlocksIn(),
2344         &aFI.ChangePaveBlocksOn(), &aFI.ChangePaveBlocksSc() };
2345       for (Standard_Integer k = 0; k < 3; k++) {
2346         Standard_Integer aNbPB = aIMPB[k]->Extent(), m;
2347         for (m = 1; m <= aNbPB; ++m) {
2348           const Handle(BOPDS_PaveBlock)& aPB = aIMPB[k]->FindKey(m);
2349           if (theEdges.Contains(aPB->Edge()))
2350             break;
2351         }
2352         if (m <= aNbPB) {
2353           BOPDS_IndexedMapOfPaveBlock aMPBCopy = *aIMPB[k];
2354           aIMPB[k]->Clear();
2355           for (m = 1; m <= aNbPB; ++m) {
2356             const Handle(BOPDS_PaveBlock)& aPB = aMPBCopy(m);
2357             if (!theEdges.Contains(aPB->Edge()))
2358               aIMPB[k]->Add(aPB);
2359           }
2360         }
2361       }
2362     }
2363     // remove from Section pave blocks
2364     BOPDS_VectorOfCurve& aVNC = aFF.ChangeCurves();
2365     Standard_Integer aNbC = aVNC.Extent();
2366     for (j = 0; j < aNbC; ++j) {
2367       BOPDS_Curve& aNC = aVNC(j);
2368       BOPDS_ListOfPaveBlock& aLPB = aNC.ChangePaveBlocks();
2369       BOPDS_ListIteratorOfListOfPaveBlock aItPB(aLPB);
2370       while (aItPB.More()) {
2371         const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
2372         if (theEdges.Contains(aPB->Edge()))
2373           aLPB.Remove(aItPB);
2374         else
2375           aItPB.Next();
2376       }
2377     }
2378   }
2379 }
2380
2381 //=======================================================================
2382 //function : ToleranceFF
2383 //purpose  : Computes the TolFF according to the tolerance value and 
2384 //           types of the faces.
2385 //=======================================================================
2386   void ToleranceFF(const BRepAdaptor_Surface& aBAS1,
2387                    const BRepAdaptor_Surface& aBAS2,
2388                    Standard_Real& aTolFF)
2389 {
2390   Standard_Real aTol1, aTol2;
2391   Standard_Boolean isAna1, isAna2;
2392   //
2393   aTol1 = aBAS1.Tolerance();
2394   aTol2 = aBAS2.Tolerance();
2395   aTolFF = Max(aTol1, aTol2);
2396   //
2397   isAna1 = (aBAS1.GetType() == GeomAbs_Plane ||
2398             aBAS1.GetType() == GeomAbs_Cylinder ||
2399             aBAS1.GetType() == GeomAbs_Cone ||
2400             aBAS1.GetType() == GeomAbs_Sphere ||
2401             aBAS1.GetType() == GeomAbs_Torus);
2402   //
2403   isAna2 = (aBAS2.GetType() == GeomAbs_Plane ||
2404             aBAS2.GetType() == GeomAbs_Cylinder ||
2405             aBAS2.GetType() == GeomAbs_Cone ||
2406             aBAS2.GetType() == GeomAbs_Sphere ||
2407             aBAS2.GetType() == GeomAbs_Torus);
2408   //
2409   if (!isAna1 || !isAna2) {
2410     aTolFF =  Max(aTolFF, 5.e-6);
2411   }
2412 }
2413 //=======================================================================
2414 //function : UpdateBlocksWithSharedVertices
2415 //purpose  : 
2416 //=======================================================================
2417 void BOPAlgo_PaveFiller::UpdateBlocksWithSharedVertices()
2418 {
2419   if (!myNonDestructive) {
2420     return;
2421   }
2422   //
2423   myErrorStatus=0;
2424   //
2425   Standard_Integer aNbFF;
2426   //
2427   BOPDS_VectorOfInterfFF& aFFs=myDS->InterfFF();
2428   aNbFF=aFFs.Extent();
2429   if (!aNbFF) {
2430     return;
2431   }
2432   //
2433   Standard_Boolean bOnCurve, bHasShapeSD;
2434   Standard_Integer i, nF1, nF2, aNbC, j, nV, nVSD;
2435   Standard_Real aTolR3D, aTolV;
2436   BOPCol_MapOfInteger aMF;
2437   //
2438   for (i=0; i<aNbFF; ++i) {
2439     BOPDS_InterfFF& aFF=aFFs(i);
2440     //
2441     BOPDS_VectorOfCurve& aVC=aFF.ChangeCurves();
2442     aNbC=aVC.Extent();
2443     if (!aNbC) {
2444       continue;
2445     }
2446     //
2447     aFF.Indices(nF1, nF2);
2448     aTolR3D=aFF.TolR3D();
2449     //
2450     if (aMF.Add(nF1)) {
2451       myDS->UpdateFaceInfoOn(nF1);
2452     }
2453     if (aMF.Add(nF2)) {
2454       myDS->UpdateFaceInfoOn(nF2);
2455     }
2456     //
2457     // Collect old vertices that are shared for nF1, nF2 ->aMI;
2458     BOPCol_MapOfInteger aMI;
2459     BOPCol_MapIteratorOfMapOfInteger aItMI;
2460     //
2461     BOPDS_FaceInfo& aFI1=myDS->ChangeFaceInfo(nF1);
2462     BOPDS_FaceInfo& aFI2=myDS->ChangeFaceInfo(nF2);
2463     //
2464     const BOPCol_MapOfInteger& aMVOn1=aFI1.VerticesOn();
2465     const BOPCol_MapOfInteger& aMVIn1=aFI1.VerticesIn();
2466     const BOPCol_MapOfInteger& aMVOn2=aFI2.VerticesOn();
2467     const BOPCol_MapOfInteger& aMVIn2=aFI2.VerticesIn();
2468     //
2469     for (j=0; j<2; ++j) {
2470       const BOPCol_MapOfInteger& aMV1=(!j) ? aMVOn1 : aMVIn1;
2471       aItMI.Initialize(aMV1);
2472       for (; aItMI.More(); aItMI.Next()) {
2473         nV=aItMI.Value();
2474         if (myDS->IsNewShape(nV)) {
2475           continue;
2476         }
2477         if (aMVOn2.Contains(nV) || aMVIn2.Contains(nV)) {
2478           aMI.Add(nV);
2479         }
2480       }
2481     }
2482     //
2483     // Try to put vertices aMI on curves
2484     for (j=0; j<aNbC; ++j) {
2485       BOPDS_Curve& aNC=aVC.ChangeValue(j);
2486       //const IntTools_Curve& aIC=aNC.Curve();
2487       //
2488       aItMI.Initialize(aMI);
2489       for (; aItMI.More(); aItMI.Next()) {
2490         nV=aItMI.Value();
2491         //
2492         bHasShapeSD=myDS->HasShapeSD(nV, nVSD);
2493         if (bHasShapeSD) {
2494           continue;
2495         }
2496         //
2497         bOnCurve=EstimatePaveOnCurve(nV, aNC, aTolR3D);
2498         if (!bOnCurve) {
2499           continue;
2500         }
2501         //
2502         const TopoDS_Vertex& aV=*((TopoDS_Vertex *)&myDS->Shape(nV));
2503         aTolV=BRep_Tool::Tolerance(aV);
2504         //
2505         UpdateVertex(nV, aTolV);
2506       }
2507     }//for (j=0; j<aNbC; ++j) {
2508   }//for (i=0; i<aNbFF; ++i) {
2509   //
2510   UpdateCommonBlocksWithSDVertices();
2511 }
2512 //=======================================================================
2513 //function : EstimatePaveOnCurve
2514 //purpose  : 
2515 //=======================================================================
2516 Standard_Boolean BOPAlgo_PaveFiller::EstimatePaveOnCurve
2517   (const Standard_Integer nV,
2518    const BOPDS_Curve& aNC,
2519    const Standard_Real aTolR3D)
2520 {
2521   Standard_Boolean bIsVertexOnLine;
2522   Standard_Real aT;
2523   //
2524   const TopoDS_Vertex& aV=*((TopoDS_Vertex *)&myDS->Shape(nV));
2525   const IntTools_Curve& aIC=aNC.Curve();
2526   //
2527   bIsVertexOnLine=myContext->IsVertexOnLine(aV, aIC, aTolR3D, aT);
2528   return bIsVertexOnLine;
2529 }
2530
2531 //=======================================================================
2532 //function : CorrectToleranceOfSE
2533 //purpose  : 
2534 //=======================================================================
2535 void BOPAlgo_PaveFiller::CorrectToleranceOfSE()
2536 {
2537   BOPDS_VectorOfInterfFF& aFFs = myDS->InterfFF();
2538   NCollection_IndexedDataMap<Standard_Integer,BOPDS_ListOfPaveBlock> aMVIPBs;
2539   BOPCol_MapOfInteger aMVIToReduce;
2540   //
2541   // 1. iterate on all sections F-F
2542   Standard_Integer aNb = aFFs.Extent(), i;
2543   for (i = 0; i < aNb; ++i) {
2544     const BOPDS_InterfFF& aFF = aFFs(i);
2545     Standard_Real aTolR3D = aFF.TolR3D();
2546     Standard_Real aTolReal = aFF.TolReal();
2547     Standard_Boolean bToReduce = aTolReal < aTolR3D;
2548     // tolerance of intersection has been increased, so process this intersection
2549     const BOPDS_VectorOfCurve& aVNC = aFF.Curves();
2550     Standard_Integer aNbC = aVNC.Extent(), k;
2551     for (k = 0; k < aNbC; ++k) {
2552       const BOPDS_Curve& aNC = aVNC(k);
2553       const BOPDS_ListOfPaveBlock& aLPB = aNC.PaveBlocks();
2554       BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
2555       for (; aItLPB.More(); aItLPB.Next()) {
2556         const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
2557         Standard_Integer nE;
2558         if (!aPB->HasEdge(nE)) {
2559           continue;
2560         }
2561         //
2562         Standard_Boolean bIsReduced = Standard_False;
2563         if (bToReduce && (aPB->OriginalEdge() < 0)) {
2564           const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
2565           Standard_Real aTolE = BRep_Tool::Tolerance(aE);
2566           if (aTolReal < aTolE) {
2567             // reduce edge tolerance
2568             reinterpret_cast<BRep_TEdge*>(aE.TShape().operator->())->Tolerance(aTolReal);
2569             bIsReduced = Standard_True;
2570           }
2571         }
2572         //
2573         // fill in the map vertex index - pave blocks
2574         for (Standard_Integer j=0; j < 2; j++) {
2575           Standard_Integer nV = (j == 0 ? aPB->Pave1().Index() : aPB->Pave2().Index());
2576           BOPDS_ListOfPaveBlock *pPBList = aMVIPBs.ChangeSeek(nV);
2577           if (!pPBList) {
2578             pPBList = &aMVIPBs.ChangeFromIndex(aMVIPBs.Add(nV, BOPDS_ListOfPaveBlock()));
2579           }
2580           pPBList->Append(aPB);
2581           if (bIsReduced) {
2582             aMVIToReduce.Add(nV);
2583           }
2584         }
2585       }
2586     }
2587   }
2588   //
2589   if (aMVIToReduce.IsEmpty()) {
2590     return;
2591   }
2592   //
2593   // 2. try to reduce tolerances of connected vertices
2594   // 2.1 find all other edges containing these connected vertices to avoid
2595   //     reducing the tolerance to the value less than the tolerances of edges,
2596   //     i.e. minimal tolerance for the vertex is the max tolerance of the
2597   //     edges containing this vertex
2598   BOPCol_DataMapOfIntegerReal aMVITol;
2599   BOPDS_VectorOfListOfPaveBlock& aPBP = myDS->ChangePaveBlocksPool();
2600   aNb = aPBP.Extent();
2601   for (i = 0; i < aNb; ++i) {
2602     const BOPDS_ListOfPaveBlock& aLPB = aPBP(i);
2603     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
2604     for (; aItLPB.More(); aItLPB.Next()) {
2605       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
2606       Standard_Integer nE;
2607       if (!aPB->HasEdge(nE)) {
2608         continue;
2609       }
2610       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
2611       Standard_Real aTolE = BRep_Tool::Tolerance(aE);
2612       //
2613       Standard_Integer nV[2];
2614       aPB->Indices(nV[0], nV[1]);
2615       //
2616       for (Standard_Integer j = 0; j < 2; j++) {
2617         if (aMVIToReduce.Contains(nV[j])) {
2618           Standard_Real *aMaxTol = aMVITol.ChangeSeek(nV[j]);
2619           if (!aMaxTol) {
2620             aMVITol.Bind(nV[j], aTolE);
2621           }
2622           else if (aTolE > *aMaxTol) {
2623             *aMaxTol = aTolE;
2624           }
2625         }
2626       }
2627     }
2628   }
2629   //
2630   // 2.2 reduce tolerances if possible
2631   aNb = aMVIPBs.Extent();
2632   for (i = 1; i <= aNb; ++i) {
2633     Standard_Integer nV = aMVIPBs.FindKey(i);
2634     if (!aMVIToReduce.Contains(nV)) {
2635       continue;
2636     }
2637     //
2638     const TopoDS_Vertex& aV = TopoDS::Vertex(myDS->Shape(nV));
2639     Standard_Real aTolV = BRep_Tool::Tolerance(aV);
2640     Standard_Real aMaxTol = aMVITol.IsBound(nV) ? aMVITol.Find(nV) : 0.;
2641     // it makes no sense to compute the real tolerance if it is
2642     // impossible to reduce the tolerance at least 0.1% of the current value
2643     if (aTolV - aMaxTol < 0.001 * aTolV) {
2644       continue;
2645     }
2646     //
2647     // compute the maximal distance from the vertex to the adjacent edges
2648     gp_Pnt aP = BRep_Tool::Pnt(aV);
2649     //
2650     const BOPDS_ListOfPaveBlock& aLPB = aMVIPBs.FindFromIndex(i);
2651     BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
2652     for (; aItLPB.More(); aItLPB.Next()) {
2653       const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
2654       Standard_Integer nE = aPB->Edge();
2655       const TopoDS_Edge& aE = TopoDS::Edge(myDS->Shape(nE));
2656       const BOPDS_Pave& aPave = (aPB->Pave1().Index() == nV ? aPB->Pave1() : aPB->Pave2());
2657       BRepAdaptor_Curve aC(aE);
2658       gp_Pnt aPonE = aC.Value(aPave.Parameter());
2659       Standard_Real aDist = aP.Distance(aPonE);
2660       aDist += BRep_Tool::Tolerance(aE);
2661       if (aDist > aMaxTol) {
2662         aMaxTol = aDist;
2663       }
2664     }
2665     //
2666     if (aMaxTol < aTolV) {
2667       reinterpret_cast<BRep_TVertex*>(aV.TShape().operator->())->Tolerance(aMaxTol);
2668     }
2669   }
2670 }