0022627: Change OCCT memory management defaults
[occt.git] / src / BRepFill / BRepFill_TrimShellCorner.cxx
1 // File:        BRepFill_TrimShellCorner.cxx
2 // Created:     Tue Oct 21 17:58:29 2003
3 // Author:      Mikhail KLOKOV
4 //              <mkk@kurox>
5
6 #include <BRepFill_TrimShellCorner.ixx>
7
8 #include <BRepAlgoAPI_Section.hxx>
9 #include <BRep_Builder.hxx>
10 #include <BRep_Tool.hxx>
11 #include <BRepLib_MakeEdge.hxx>
12 #include <BRepTools_ReShape.hxx>
13 #include <TopoDS.hxx>
14 #include <TopoDS_Shell.hxx>
15 #include <TopoDS_Compound.hxx>
16
17 #include <IntTools_BeanFaceIntersector.hxx>
18 #include <IntTools_Context.hxx>
19 #include <IntTools_Range.hxx>
20
21 #include <BOPTools_Pave.hxx>
22 #include <BOPTools_DSFiller.hxx>
23 #include <BOPTools_PaveFiller.hxx>
24 #include <BOPTools_CArray1OfVVInterference.hxx>
25 #include <BOPTools_CArray1OfVEInterference.hxx>
26 #include <BOPTools_CArray1OfEEInterference.hxx>
27 #include <BOPTools_CArray1OfSSInterference.hxx>
28 #include <BOPTools_VVInterference.hxx>
29 #include <BOPTools_VEInterference.hxx>
30 #include <BOPTools_EEInterference.hxx>
31 #include <BOPTools_SSInterference.hxx>
32 #include <BOPTools_InterferencePool.hxx>
33 #include <BOPTools_Curve.hxx>
34 #include <BOPTools_SequenceOfCurves.hxx>
35 #include <BOPTools_PaveBlock.hxx>
36 #include <BOPTools_CommonBlock.hxx>
37 #include <BOPTools_ListIteratorOfListOfPaveBlock.hxx>
38 #include <BOPTools_ListIteratorOfListOfCommonBlock.hxx>
39 #include <BOPTools_PaveSet.hxx>
40 #include <BOPTools_ListIteratorOfListOfPave.hxx>
41 #include <BooleanOperations_ShapesDataStructure.hxx>
42 #include <BOP_BuilderTools.hxx>
43
44 #include <Geom_Curve.hxx>
45 #include <Geom2d_Curve.hxx>
46 #include <gp_Pnt2d.hxx>
47
48 #include <TopLoc_Location.hxx>
49 #include <TopExp.hxx>
50 #include <TopExp_Explorer.hxx>
51 #include <TopTools_MapOfShape.hxx>
52 #include <TopTools_ListOfShape.hxx>
53 #include <TopTools_Array1OfListOfShape.hxx>
54 #include <TopTools_ListIteratorOfListOfShape.hxx>
55 #include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
56
57 #include <gp_Pln.hxx>
58 #include <TopoDS_Iterator.hxx>
59 #include <TColgp_Array1OfPnt.hxx>
60 #include <TColgp_Array2OfPnt.hxx>
61 #include <TColgp_Array1OfDir.hxx>
62 #include <TColStd_ListOfInteger.hxx>
63 #include <TColStd_ListIteratorOfListOfInteger.hxx>
64 #include <GCPnts_UniformAbscissa.hxx>
65 #include <GeomLib.hxx>
66 #include <BRepLib_MakeWire.hxx>
67 #include <TopTools_SequenceOfShape.hxx>
68 #include <TColStd_Array1OfBoolean.hxx>
69 #include <TColgp_SequenceOfPnt.hxx>
70 #include <gce_MakeLin.hxx>
71
72 static Standard_Boolean IsFromFirstToSecond(const TopoDS_Edge&   theEdge,
73                                             const Standard_Real  theParameterOnUEdge,
74                                             const TopoDS_Edge&   theUEdge1,
75                                             const TopoDS_Edge&   theUEdge2,
76                                             const TopoDS_Face&   theFace);
77
78 static Standard_Boolean FindParameter(const BOPTools_PaveSet&                     thePaveSet,
79                                       const BooleanOperations_KindOfInterference& theType,
80                                       const Standard_Integer                      theInterfIndex,
81                                       Standard_Real&                              theParam);
82
83 static Standard_Boolean FindCommonVertex(const BOPTools_DSFiller& theDSFiller,
84                                          const Standard_Integer   theEIndex1,
85                                          const Standard_Integer   theEIndex2,
86                                          TopoDS_Vertex&           theCommonVertex,
87                                          Standard_Real&           theParamOnE1,
88                                          Standard_Real&           theParamOnE2);
89
90 static Standard_Boolean MakeFacesNonSec(const Standard_Integer                     theIndex,
91                                         const Handle(TopTools_HArray2OfShape)&     theUEdges, 
92                                         const Handle(TopTools_HArray2OfShape)&     theBounds, 
93                                         const BOPTools_DSFiller&                   theDSFiller, 
94                                         const Standard_Integer                     theFaceIndex1, 
95                                         const Standard_Integer                     theFaceIndex2, 
96                                         TopTools_DataMapOfShapeListOfShape&        theHistMap);
97
98 static Standard_Boolean MakeFacesSec(const Standard_Integer                     theIndex,
99                                      const Handle(TopTools_HArray2OfShape)&     theUEdges, 
100                                      const Handle(TopTools_HArray2OfShape)&     theBounds, 
101                                      const BOPTools_DSFiller&                   theDSFiller, 
102                                      const Standard_Integer                     theFaceIndex1, 
103                                      const Standard_Integer                     theFaceIndex2, 
104                                      const Standard_Integer                     theSSInterfIndex,
105                                      const gp_Ax2&                              AxeOfBisPlane,
106                                      TopTools_DataMapOfShapeListOfShape&        theHistMap);
107
108 static Standard_Boolean SplitUEdges(const Handle(TopTools_HArray2OfShape)&     theUEdges, 
109                                     const BOPTools_DSFiller&                   theDSFiller, 
110                                     TopTools_DataMapOfShapeListOfShape&        theHistMap);
111
112 static void FindFreeVertices(const TopoDS_Shape&         theShape,
113                              const TopTools_MapOfShape&  theVerticesToAvoid,
114                              TopTools_ListOfShape&       theListOfVertex);
115
116 static Standard_Boolean CheckAndOrientEdges(const TopTools_ListOfShape&  theOrderedList,
117                                             const gp_Pnt2d&              theFirstPoint,
118                                             const gp_Pnt2d&              theLastPoint,
119                                             const TopoDS_Face&           theFace,
120                                             TopTools_ListOfShape&        theOrientedList);
121
122 static Standard_Boolean FillGap(const TopoDS_Vertex&   theFirstVertex,
123                                 const TopoDS_Vertex&   theLastVertex,
124                                 const gp_Pnt2d&        theFirstPoint,
125                                 const gp_Pnt2d&        theLastPoint,
126                                 const TopoDS_Face&     theFace,
127                                 const TopoDS_Compound& theSectionEdges,
128                                 TopTools_ListOfShape&  theOrderedList);
129
130 static Standard_Boolean FindNextEdge(const TopoDS_Vertex&   theFirstVertex,
131                                      const TopoDS_Vertex&   theLastVertex,
132                                      const TopTools_IndexedDataMapOfShapeListOfShape& theMapVE,
133                                      const TopTools_MapOfShape& theMapToAvoid,
134                                      TopTools_ListOfShape&  theOrderedList);
135
136 static Standard_Boolean FindVertex(const TopoDS_Edge&                        theEdge,
137                                    const Standard_Integer                    theRank, 
138                                    const BOPTools_DSFiller&                  theDSFiller, 
139                                    const TopTools_DataMapOfShapeListOfShape& theHistMap, 
140                                    TopoDS_Vertex&                            theVertex,
141                                    BOPTools_Pave&                            thePave);
142
143 static Standard_Boolean FindNextVertex(const Standard_Integer                    theEdgeIndex,
144                                        const BOPTools_Pave&                      thePrevPave,
145                                        const BOPTools_DSFiller&                  theDSFiller, 
146                                        TopoDS_Vertex&                            theNextVertex,
147                                        BOPTools_Pave&                            thePave);
148
149 static Standard_Boolean GetPave(const Standard_Integer   theEdgeIndex,
150                                 const Standard_Boolean   isFirst,
151                                 const BOPTools_DSFiller& theDSFiller, 
152                                 BOPTools_Pave&           thePave);
153
154 static Standard_Boolean FindFromUEdge(const TopoDS_Edge&                        theUE1Old, 
155                                       const TopoDS_Edge&                        theUE2Old, 
156                                       const TopoDS_Edge&                        theUE1New, 
157                                       const TopoDS_Edge&                        theUE2New, 
158                                       const TopoDS_Face&                        theFace, 
159                                       const TopoDS_Compound&                    theSecEdges, 
160                                       const Standard_Integer                    theRank, 
161                                       const TopoDS_Edge&                        theBoundEdge, 
162                                       const Standard_Integer                    theBoundEdgeIndex, 
163                                       const BOPTools_DSFiller&                  theDSFiller, 
164                                       const TopTools_DataMapOfShapeListOfShape& theHistMap,
165                                       TopoDS_Compound&                          theSecEdgesNew, 
166                                       TopTools_ListOfShape&                     theListOfWireEdges, 
167                                       BOPTools_Pave&                            theFoundPave, 
168                                       Standard_Boolean&                         isOnUEdge);
169
170 static Standard_Boolean FindFromVEdge(const BOPTools_Pave&                      thePrevPave,
171                                       const Standard_Boolean&                   isOnUEdge,
172                                       const TopoDS_Edge&                        theUE1Old, 
173                                       const TopoDS_Edge&                        theUE2Old, 
174                                       const TopoDS_Face&                        theFace, 
175                                       const TopoDS_Compound&                    theSecEdges, 
176                                       const Standard_Integer                    theRank, 
177                                       const TopoDS_Edge&                        theBoundEdge, 
178                                       const Standard_Integer                    theBoundEdgeIndex, 
179                                       const BOPTools_DSFiller&                  theDSFiller,
180                                       const TopTools_DataMapOfShapeListOfShape& theHistMap,
181                                       TopTools_ListOfShape&                     theListOfWireEdges, 
182                                       Standard_Boolean&                         isSectionFound);
183
184 static void RemoveEdges(const TopoDS_Compound&      theSourceComp,
185                         const TopTools_ListOfShape& theListToRemove,
186                         TopoDS_Compound&            theResultComp);
187
188 static Standard_Boolean FilterSectionEdges(const BOPTools_SequenceOfCurves& theBCurves,
189                                            const TopoDS_Face&               theSecPlane,
190                                            const BOPTools_DSFiller&         theDSFiller,
191                                            TopoDS_Compound&                 theResult);
192
193 static Standard_Boolean GetUEdges(const Standard_Integer                     theIndex,
194                                   const Standard_Integer                     theRank,
195                                   const Handle(TopTools_HArray2OfShape)&     theUEdges,
196                                   const TopoDS_Edge&                         theBoundEdge,
197                                   const TopoDS_Face&                         theFace,
198                                   TopoDS_Edge&                               theFirstUEdge,
199                                   TopoDS_Edge&                               theSecondUEdge);
200
201 static Standard_Real ComputeAveragePlaneAndMaxDeviation(const TopoDS_Shape& aWire,
202                                                         gp_Pln& thePlane,
203                                                         Standard_Boolean& IsSingular);
204
205 static Standard_Boolean ChooseSection(const TopoDS_Shape& Comp,
206                                       const gp_Ax2& bis,
207                                       TopoDS_Shape& resWire,
208                                       gp_Pln& resPlane,
209                                       Standard_Boolean& IsSingular);
210
211 static Standard_Boolean ChoosePlane(const TopoDS_Shape& Comp,
212                                     const gp_Ax2& bis,
213                                     gp_Pln& resPlane,
214                                     TopoDS_Compound& NewComp);
215
216
217 // ===========================================================================================
218 // function: Constructor
219 // purpose:
220 // ===========================================================================================
221 BRepFill_TrimShellCorner::BRepFill_TrimShellCorner(const Handle(TopTools_HArray2OfShape)& theFaces,
222                                                    const gp_Ax2&                          theAxeOfBisPlane,
223                                                    const TopoDS_Face&                     theSecPlane) :
224 myAxeOfBisPlane(theAxeOfBisPlane),
225 myDone(Standard_False),
226 myHasSection(Standard_False)
227 {
228   myFaces = new TopTools_HArray2OfShape(theFaces->LowerRow(), theFaces->UpperRow(), 
229                                         theFaces->LowerCol(), theFaces->UpperCol());
230   myFaces->ChangeArray2() = theFaces->Array2();
231   mySecPln = theSecPlane;
232 }
233
234 // ===========================================================================================
235 // function: Constructor
236 // purpose:
237 // ===========================================================================================
238 BRepFill_TrimShellCorner::BRepFill_TrimShellCorner(const Handle(TopTools_HArray2OfShape)& theFaces,
239                                                    const gp_Ax2&                          theAxeOfBisPlane,
240                                                    const TopoDS_Wire&                     theSpine,
241                                                    const TopoDS_Face&                     theSecPlane):
242 myAxeOfBisPlane(theAxeOfBisPlane),
243 myDone(Standard_False),
244 myHasSection(Standard_False)
245 {
246   myFaces = new TopTools_HArray2OfShape(theFaces->LowerRow(), theFaces->UpperRow(), 
247                                         theFaces->LowerCol(), theFaces->UpperCol());
248   myFaces->ChangeArray2() = theFaces->Array2();
249   mySpine = theSpine;
250   mySecPln = theSecPlane;
251 }
252
253 // ===========================================================================================
254 // function: SetSpine
255 // purpose:
256 // ===========================================================================================
257 void BRepFill_TrimShellCorner::SetSpine(const TopoDS_Wire& theSpine) 
258 {
259   mySpine = theSpine;
260 }
261
262 // ===========================================================================================
263 // function: AddBounds
264 // purpose:
265 // ===========================================================================================
266 void BRepFill_TrimShellCorner::AddBounds(const Handle(TopTools_HArray2OfShape)& theBounds) 
267 {
268   myBounds = new TopTools_HArray2OfShape(theBounds->LowerRow(), theBounds->UpperRow(), 
269                                          theBounds->LowerCol(), theBounds->UpperCol());
270   myBounds->ChangeArray2() = theBounds->Array2();
271 }
272
273 // ===========================================================================================
274 // function: AddUEdges
275 // purpose:
276 // ===========================================================================================
277 void BRepFill_TrimShellCorner::AddUEdges(const Handle(TopTools_HArray2OfShape)& theUEdges) 
278 {
279   myUEdges = new TopTools_HArray2OfShape(theUEdges->LowerRow(), theUEdges->UpperRow(), 
280                                          theUEdges->LowerCol(), theUEdges->UpperCol());
281   myUEdges->ChangeArray2() = theUEdges->Array2();
282 }
283
284 // ===========================================================================================
285 // function: Perform
286 // purpose:
287 // ===========================================================================================
288 void BRepFill_TrimShellCorner::Perform() 
289 {
290   myDone = Standard_False;
291   myHistMap.Clear();
292
293   if(myFaces->RowLength() != 2)
294     return;
295   Standard_Integer ii = 0, jj = 0;
296   BRep_Builder aBB;
297
298   for(jj = myFaces->LowerCol(); jj <= myFaces->UpperCol(); jj++) {
299     TopoDS_Shell aShell;
300     aBB.MakeShell(aShell);
301
302     for(ii = myFaces->LowerRow(); ii <= myFaces->UpperRow(); ii++) {
303       aBB.Add(aShell, myFaces->Value(ii, jj));
304     }
305
306     if(jj == myFaces->LowerCol()) {
307       myShape1 = aShell;
308     }
309     else {
310       myShape2 = aShell;
311     }
312   }
313
314   BOPTools_DSFiller aDSFiller;
315   aDSFiller.SetShapes(myShape1, myShape2);
316
317   if (!aDSFiller.IsDone()) {
318     return;
319   }
320   aDSFiller.Perform();
321
322   BRepAlgoAPI_Section aSectionAlgo(myShape1, myShape2, aDSFiller, Standard_False);
323   aSectionAlgo.ComputePCurveOn1(Standard_True);
324   aSectionAlgo.ComputePCurveOn2(Standard_True);
325   aSectionAlgo.Approximation(Standard_True);
326   aSectionAlgo.Build();
327
328   if(!aSectionAlgo.IsDone())
329     return;
330
331   const BooleanOperations_ShapesDataStructure& aDS = aDSFiller.DS();
332   const BOPTools_InterferencePool&             anInterfPool = aDSFiller.InterfPool();
333   BOPTools_InterferencePool* pInterfPool = 
334       (BOPTools_InterferencePool*) &anInterfPool;
335   BOPTools_CArray1OfSSInterference& aFFs =
336     pInterfPool->SSInterferences();
337   Standard_Integer aNbFFs = aFFs.Extent();
338
339   if(!SplitUEdges(myUEdges, aDSFiller, myHistMap)) {
340     return;
341   }
342
343   for(ii = myFaces->LowerRow(); ii <= myFaces->UpperRow(); ii++) {
344     TopoDS_Shape aF1 = myFaces->Value(ii, myFaces->LowerCol());
345     TopoDS_Shape aF2 = myFaces->Value(ii, myFaces->UpperCol());
346     Standard_Integer anIndex1 = aDS.ShapeIndex(aF1, 1);
347     Standard_Integer anIndex2 = aDS.ShapeIndex(aF2, 2);
348
349     if((anIndex1 == 0) || (anIndex1 == 0))
350       continue;
351     Standard_Integer i = 0;
352
353     for (i=1; i <= aNbFFs; i++) {
354       BOPTools_SSInterference& aFFi=aFFs(i);
355       //
356       Standard_Integer nF1 = aFFi.Index1();
357       Standard_Integer nF2 = aFFi.Index2();
358
359       if((nF1 == anIndex1) && (nF2 == anIndex2)) {
360         BOPTools_SequenceOfCurves& aBCurves = aFFi.Curves();
361         Standard_Integer aNbCurves = aBCurves.Length();
362         Standard_Integer j = 0;
363         Standard_Boolean bhassec = Standard_False;
364
365         for (j = 1; j <= aNbCurves; j++) {
366           const BOPTools_Curve& aBCurve = aBCurves(j);
367           const BOPTools_ListOfPaveBlock& aSectEdges = aBCurve.NewPaveBlocks();
368
369           if(!aSectEdges.IsEmpty()) {
370             bhassec = Standard_True;
371             break;
372           }
373         }
374
375         if(!bhassec) {
376           if(!MakeFacesNonSec(ii, myUEdges, myBounds, aDSFiller, anIndex1, anIndex2, myHistMap)) {
377             myHistMap.Clear();
378             return;
379           }
380         }
381         else {
382           if(!MakeFacesSec(ii, myUEdges, myBounds, aDSFiller, anIndex1, anIndex2, 
383                            i, myAxeOfBisPlane, myHistMap)) {
384             myHistMap.Clear();
385             return;
386           }
387         }
388         break;
389       }
390     }
391   }
392   myDone = Standard_True;
393 }
394
395 // ===========================================================================================
396 // function: IsDone
397 // purpose:
398 // ===========================================================================================
399 Standard_Boolean BRepFill_TrimShellCorner::IsDone() const
400 {
401   return myDone;
402 }
403
404 // ===========================================================================================
405 // function: HasSection
406 // purpose:
407 // ===========================================================================================
408 Standard_Boolean BRepFill_TrimShellCorner::HasSection() const
409 {
410   return myHasSection;
411 }
412
413 // ===========================================================================================
414 // function: Modified
415 // purpose:
416 // ===========================================================================================
417 void BRepFill_TrimShellCorner::Modified(const TopoDS_Shape&   theShape,
418                                         TopTools_ListOfShape& theModified) 
419 {
420   theModified.Clear();
421
422   if(myHistMap.IsBound(theShape)) {
423     theModified = myHistMap.Find(theShape);
424   }
425 }
426
427 // ----------------------------------------------------------------------------------------------------
428 // static function: MakeFacesNonSec
429 // purpose:
430 // ----------------------------------------------------------------------------------------------------
431 Standard_Boolean MakeFacesNonSec(const Standard_Integer                     theIndex,
432                                  const Handle(TopTools_HArray2OfShape)&     theUEdges, 
433                                  const Handle(TopTools_HArray2OfShape)&     theBounds, 
434                                  const BOPTools_DSFiller&                   theDSFiller, 
435                                  const Standard_Integer                     theFaceIndex1, 
436                                  const Standard_Integer                     theFaceIndex2, 
437                                  TopTools_DataMapOfShapeListOfShape&        theHistMap)
438 {
439
440   Standard_Boolean bHasNewEdge = Standard_False;
441   TopoDS_Edge aNewEdge;
442   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
443   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
444 //  BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
445 //  BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
446 //  const BOPTools_CArray1OfEEInterference& aEEs = pIntrPool->EEInterfs();
447   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
448
449   BRep_Builder aBB;
450   const TopoDS_Shape& aE1 = theBounds->Value(theIndex, 1);
451   const TopoDS_Shape& aE2 = theBounds->Value(theIndex, 2);
452
453   // search common vertex between bounds. begin
454   TopoDS_Vertex aCommonVertex;
455   Standard_Integer anIndex1 = aDS.ShapeIndex(aE1, 1);
456   Standard_Integer anIndex2 = aDS.ShapeIndex(aE2, 2);
457   Standard_Real apar1 = 0., apar2 = 0.;
458
459   Standard_Boolean bvertexfound = 
460     FindCommonVertex(theDSFiller, anIndex1, anIndex2, aCommonVertex, apar1, apar2);
461   // search common vertex between bounds. end
462
463   Handle(BRepTools_ReShape) aSubstitutor = new BRepTools_ReShape();
464
465   // search common vertices between uedges. begin
466   TopTools_ListOfShape aCommonVertices;
467   Standard_Boolean acommonflag = 0; // 0 - no, 1 - first pair, 2 - second pair, 3 - both
468   Standard_Integer ueit = 0, eindex = 0;
469
470   for(ueit = 1, eindex = theIndex; ueit <= 2; ueit++, eindex++) {
471     const TopoDS_Shape& aShape1 = theUEdges->Value(eindex, theUEdges->LowerCol());
472     const TopoDS_Shape& aShape2 = theUEdges->Value(eindex, theUEdges->UpperCol());
473     TopoDS_Edge aUE1 = TopoDS::Edge(aShape1);
474     TopoDS_Edge aUE2 = TopoDS::Edge(aShape2);
475
476     if(theHistMap.IsBound(aShape1)) {
477       const TopTools_ListOfShape& lst = theHistMap.Find(aShape1);
478
479       if(!lst.IsEmpty())
480         aUE1 = TopoDS::Edge(lst.First());
481     }
482
483     if(theHistMap.IsBound(aShape2)) {
484       const TopTools_ListOfShape& lst = theHistMap.Find(aShape2);
485
486       if(!lst.IsEmpty())
487         aUE2 = TopoDS::Edge(lst.First());
488     }
489
490     if(!aShape1.IsSame(aUE1))
491       aSubstitutor->Replace(aShape1.Oriented(TopAbs_FORWARD), aUE1.Oriented(TopAbs_FORWARD));
492
493     if(!aShape2.IsSame(aUE2))
494       aSubstitutor->Replace(aShape2.Oriented(TopAbs_FORWARD), aUE2.Oriented(TopAbs_FORWARD));
495
496     TopoDS_Vertex V1 = TopExp::LastVertex(aUE1);
497     TopoDS_Vertex V2 = TopExp::FirstVertex(aUE2);
498
499     if(V1.IsSame(V2)) {
500       acommonflag = (acommonflag == 0) ? ueit : 3;
501       aCommonVertices.Append(V1);
502     }
503   }
504   // search common vertices between uedges. end
505
506   if(bvertexfound) {
507     if(aCommonVertices.Extent() != 1)
508       return Standard_False;
509
510     if(acommonflag == 1)
511       aNewEdge = BRepLib_MakeEdge(TopoDS::Vertex(aCommonVertices.First()), aCommonVertex);
512     else
513       aNewEdge = BRepLib_MakeEdge(aCommonVertex, TopoDS::Vertex(aCommonVertices.First()));
514
515     bHasNewEdge = Standard_True;
516   }
517
518   if(aCommonVertices.Extent() == 2) {
519     aNewEdge = BRepLib_MakeEdge(TopoDS::Vertex(aCommonVertices.First()),
520                                 TopoDS::Vertex(aCommonVertices.Last()));
521     bHasNewEdge = Standard_True;
522   }
523   Standard_Integer fit = 0;
524
525   for(fit = 1; fit <= 2; fit++) {
526     TopoDS_Compound aComp;
527     TopTools_MapOfShape aMapV;
528     aBB.MakeCompound(aComp);
529
530     for(ueit = 1, eindex = theIndex; ueit <= 2; ueit++, eindex++) {
531       const TopoDS_Shape& aShape = theUEdges->Value(eindex, theUEdges->LowerCol() + fit - 1);
532       TopoDS_Shape aUE = aShape;
533
534       if(theHistMap.IsBound(aShape)) {
535         const TopTools_ListOfShape& lst = theHistMap.Find(aShape);
536
537         if(!lst.IsEmpty())
538           aUE = TopoDS::Edge(lst.First());
539       }
540       const TopoDS_Shape& aV = (fit == 1) ? TopExp::FirstVertex(TopoDS::Edge(aUE)) : TopExp::LastVertex(TopoDS::Edge(aUE));
541       aMapV.Add(aV);
542       aBB.Add(aComp, aUE);
543     }
544     if(bHasNewEdge) {
545       aBB.Add(aComp, aNewEdge);
546     }
547     TopTools_ListOfShape alonevertices;
548     FindFreeVertices(aComp, aMapV, alonevertices);
549
550     if(!alonevertices.IsEmpty() && (alonevertices.Extent() != 2))
551       return Standard_False;
552
553     Standard_Integer aFaceIndex = (fit == 1) ? theFaceIndex1 : theFaceIndex2;
554     TopoDS_Shape aFace          = aDS.Shape(aFaceIndex);
555     TopAbs_Orientation aFaceOri = aFace.Orientation();
556     TopAbs_Orientation anEdgeOri = TopAbs_FORWARD;
557     aFace.Orientation(TopAbs_FORWARD);
558
559     TopExp_Explorer anExpE(aFace, TopAbs_EDGE);
560     const TopoDS_Shape& aCheckEdge = (fit == 1) ? aE1 : aE2;
561
562     for(; anExpE.More(); anExpE.Next()) {
563       if(aCheckEdge.IsSame(anExpE.Current()))
564         anEdgeOri = anExpE.Current().Orientation();
565     }
566
567     if(bHasNewEdge) {
568       aNewEdge.Orientation(TopAbs_FORWARD);
569     }
570
571     TopTools_ListOfShape aOrderedList;
572
573     if(!alonevertices.IsEmpty()) {
574       Standard_Integer anEIndex = (fit == 1) ? anIndex1 : anIndex2;
575       const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(anEIndex));
576       BOPTools_ListIteratorOfListOfPave anPIt(aPaveSet.Set());
577       Standard_Boolean bfound1 = Standard_False;
578       Standard_Boolean bfound2 = Standard_False;
579       Standard_Real aparam1 = 0., aparam2 = 0.;
580
581       for(; anPIt.More(); anPIt.Next()) {
582         const BOPTools_Pave& aPave = anPIt.Value();
583         TopoDS_Shape aV = aDS.Shape(aPave.Index());
584
585         if(aV.IsSame(alonevertices.First())) {
586           if(!bfound1) {
587             aparam1 = aPave.Param();
588             bfound1 = Standard_True;
589           }
590         }
591
592         if(aV.IsSame(alonevertices.Last())) {
593           if(!bfound2) {
594             aparam2 = aPave.Param();
595             bfound2 = Standard_True;
596           }
597         }
598       }
599
600       if(bfound1 && bfound2) {
601         TopoDS_Edge aNewBoundE;
602
603         if(fit == 1) {
604           aNewBoundE = TopoDS::Edge(aE1.EmptyCopied());
605         }
606         else {
607           aNewBoundE = TopoDS::Edge(aE2.EmptyCopied());
608         }
609         TopoDS_Vertex aV1, aV2;
610
611         if(aparam1 < aparam2) {
612           aV1 = TopoDS::Vertex(alonevertices.First());
613           aV2 = TopoDS::Vertex(alonevertices.Last());
614         }
615         else {
616           aV1 = TopoDS::Vertex(alonevertices.Last());
617           aV2 = TopoDS::Vertex(alonevertices.First());
618           Standard_Real tmp = aparam1;
619           aparam1 = aparam2;
620           aparam2 = tmp;
621         }
622         aV1.Orientation(TopAbs_FORWARD);
623         aV2.Orientation(TopAbs_REVERSED);
624         aBB.Add(aNewBoundE, aV1);
625         aBB.Add(aNewBoundE, aV2);
626         aBB.Range(aNewBoundE, aparam1, aparam2);
627         aNewBoundE.Orientation(TopAbs_FORWARD);
628
629         aOrderedList.Append(aNewBoundE);
630
631         if(bHasNewEdge) {
632           TopExp_Explorer anExpV(aNewEdge, TopAbs_VERTEX);
633           Standard_Boolean bfoundv = Standard_False;
634
635           for(; !bfoundv && anExpV.More(); anExpV.Next()) {
636             if(aV2.IsSame(anExpV.Current()))
637               bfoundv = Standard_True;
638           }
639
640           if(bfoundv)
641             aOrderedList.Append(aNewEdge);
642           else
643             aOrderedList.Prepend(aNewEdge);
644         }
645       }
646       else {
647         return Standard_False;
648       }
649     }
650     else {
651       if(bHasNewEdge) {
652         aOrderedList.Append(aNewEdge);
653       }
654     }
655
656     if(!aOrderedList.IsEmpty()) {
657       TopoDS_Wire aW;
658       aBB.MakeWire(aW);
659       TopTools_ListIteratorOfListOfShape anItE(aOrderedList);
660
661       for(; anItE.More(); anItE.Next()) {
662         aBB.Add(aW, anItE.Value());
663       }
664       if(fit == 1)
665         aSubstitutor->Replace(aE1.Oriented(TopAbs_FORWARD), aW);
666       else
667         aSubstitutor->Replace(aE2.Oriented(TopAbs_FORWARD), aW);
668     }
669
670     aSubstitutor->Apply(aFace);
671     TopoDS_Shape aNewFace = aSubstitutor->Value(aFace);
672     aNewFace.Orientation(aFaceOri);
673     TopTools_ListOfShape atmpList;
674     atmpList.Append(aNewFace);
675     theHistMap.Bind(aFace, atmpList);
676
677     anExpE.Init(aFace, TopAbs_EDGE);
678
679     for(; anExpE.More(); anExpE.Next()) {
680       TopoDS_Shape aNewValue = aSubstitutor->Value(anExpE.Current());
681
682       if(aNewValue.IsNull() || aNewValue.IsSame(anExpE.Current()))
683         continue;
684
685       if(theHistMap.IsBound(anExpE.Current()))
686         continue;
687       TopTools_ListOfShape aListOfNewEdge;
688       TopExp_Explorer anExpE2(aNewValue, TopAbs_EDGE);
689
690       for(; anExpE2.More(); anExpE2.Next()) {
691         aListOfNewEdge.Append(anExpE2.Current());
692       }
693       theHistMap.Bind(anExpE.Current(), aListOfNewEdge);
694     }
695   }
696
697   return Standard_True;
698 }
699
700 // ----------------------------------------------------------------------------------------------------
701 // static function: MakeFacesSec
702 // purpose:
703 // ----------------------------------------------------------------------------------------------------
704 Standard_Boolean MakeFacesSec(const Standard_Integer                     theIndex,
705                               const Handle(TopTools_HArray2OfShape)&     theUEdges, 
706                               const Handle(TopTools_HArray2OfShape)&     theBounds, 
707                               const BOPTools_DSFiller&                   theDSFiller, 
708                               const Standard_Integer                     theFaceIndex1, 
709                               const Standard_Integer                     theFaceIndex2, 
710                               const Standard_Integer                     theSSInterfIndex,
711                               const gp_Ax2&                              AxeOfBisPlane,
712                               TopTools_DataMapOfShapeListOfShape&        theHistMap)
713 {
714   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
715 //  const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
716   BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
717   BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
718   BOPTools_CArray1OfSSInterference& aFFs = pIntrPool->SSInterferences();
719 //  const BOPTools_PavePool& aPavePool               = aPaveFiller.PavePool();
720 //  const BOPTools_SplitShapesPool& aSplitShapesPool = aPaveFiller.SplitShapesPool();
721
722   TopoDS_Compound aSecEdges;
723   BOPTools_SSInterference& aFFi = aFFs(theSSInterfIndex);
724   BOPTools_SequenceOfCurves& aBCurves = aFFi.Curves();
725   TopoDS_Face aSecPlane;
726
727   if(!FilterSectionEdges(aBCurves, aSecPlane, theDSFiller, aSecEdges))
728     return Standard_False;
729
730   TopoDS_Shape SecWire;
731   gp_Pln SecPlane;
732   Standard_Boolean IsSingular;
733   Standard_Boolean WireFound = ChooseSection( aSecEdges, AxeOfBisPlane, SecWire, SecPlane, IsSingular );
734
735   if(WireFound) {
736     //aSecEdges = SecWire;
737     TopoDS_Compound aComp;
738     BRep_Builder BB;
739     BB.MakeCompound(aComp);
740     TopExp_Explorer explo( SecWire, TopAbs_EDGE );
741
742     for (; explo.More(); explo.Next())
743       BB.Add( aComp, explo.Current() );
744     aSecEdges = aComp;
745   }
746
747   TopTools_ListOfShape aCommonVertices;
748 //  Standard_Boolean acommonflag = 0; // 0 - no, 1 - first pair, 2 - second pair, 3 - both
749   Standard_Integer fit = 0; //, ueit = 0, eindex = 0, i = 0;
750   Handle(BRepTools_ReShape) aSubstitutor = new BRepTools_ReShape();
751
752   for(fit = 1; fit <= 2; fit++) {
753     Standard_Integer aFaceIndex = (fit == 1) ? theFaceIndex1 : theFaceIndex2;
754     TopoDS_Face aFace = TopoDS::Face(aDS.Shape(aFaceIndex));
755     TopAbs_Orientation aFaceOri = aFace.Orientation();
756     TopoDS_Face aFaceF = aFace;
757     aFaceF.Orientation(TopAbs_FORWARD);
758     TopoDS_Edge aBoundEdge = TopoDS::Edge(theBounds->Value(theIndex, theBounds->LowerCol() + fit - 1));
759     Standard_Integer aBoundEdgeIndex = aDS.ShapeIndex(aBoundEdge, fit);
760     TopoDS_Edge aUE1;
761     TopoDS_Edge aUE2;
762
763     if(!GetUEdges(theIndex, fit, theUEdges, aBoundEdge, aFaceF, aUE1, aUE2))
764       return Standard_False;
765
766     TopoDS_Edge aUE1old = aUE1;
767     TopoDS_Edge aUE2old = aUE2;
768
769     if(theHistMap.IsBound(aUE1)) {
770       const TopTools_ListOfShape& lst = theHistMap.Find(aUE1);
771
772       if(!lst.IsEmpty()) {
773         const TopoDS_Shape& anEdge = lst.First().Oriented(aUE1.Orientation());
774
775         if(!aUE1.IsSame(anEdge))
776           aSubstitutor->Replace(aUE1.Oriented(TopAbs_FORWARD), anEdge.Oriented(TopAbs_FORWARD));
777         aUE1 = TopoDS::Edge(anEdge);
778       }
779     }
780
781     if(theHistMap.IsBound(aUE2)) {
782       const TopTools_ListOfShape& lst = theHistMap.Find(aUE2);
783
784       if(!lst.IsEmpty()) {
785         const TopoDS_Shape& anEdge = lst.First().Oriented(aUE2.Orientation());
786
787         if(!aUE2.IsSame(anEdge))
788           aSubstitutor->Replace(aUE2.Oriented(TopAbs_FORWARD), anEdge.Oriented(TopAbs_FORWARD));
789         aUE2 = TopoDS::Edge(anEdge);
790       }
791     }
792     TopoDS_Vertex aPrevVertex, aNextVertex;
793     TopoDS_Compound aCompOfSecEdges = aSecEdges;
794     TopTools_ListOfShape aListOfWireEdges;
795     BRep_Builder aBB;
796     BOPTools_Pave aPave1;
797     Standard_Boolean isPave1OnUEdge = Standard_True;
798
799     if(FindFromUEdge(aUE1old, aUE2old, aUE1, aUE2, aFace, aSecEdges, fit, aBoundEdge, aBoundEdgeIndex, 
800                      theDSFiller, theHistMap, aCompOfSecEdges, aListOfWireEdges, aPave1, isPave1OnUEdge)) {
801       TopTools_ListOfShape aSecondListOfEdges;
802       Standard_Boolean bisSectionFound = Standard_False;
803
804       if(!FindFromVEdge(aPave1, isPave1OnUEdge, aUE1old, aUE2old, aFace, aCompOfSecEdges, fit, aBoundEdge, 
805                         aBoundEdgeIndex, theDSFiller, theHistMap, aSecondListOfEdges, bisSectionFound)) {
806         return Standard_False;
807       }
808
809       if(!bisSectionFound && aListOfWireEdges.IsEmpty()) {
810         return Standard_False;
811       }
812       aListOfWireEdges.Append(aSecondListOfEdges);
813     }
814     else {
815       return Standard_False;
816     }
817
818     if(!aListOfWireEdges.IsEmpty()) {
819       TopoDS_Wire aW;
820       aBB.MakeWire(aW);
821       TopTools_ListIteratorOfListOfShape aEIt(aListOfWireEdges);
822
823       for(; aEIt.More(); aEIt.Next()) {
824         if(!aBoundEdge.IsSame(aEIt.Value()))
825           aBB.Add(aW, aEIt.Value());
826       }
827       aSubstitutor->Replace(aBoundEdge.Oriented(TopAbs_FORWARD), aW);
828     }
829
830     aSubstitutor->Apply(aFace);
831     TopoDS_Shape aNewFace = aSubstitutor->Value(aFace);
832     aNewFace.Orientation(aFaceOri);
833     TopTools_ListOfShape atmpList;
834     atmpList.Append(aNewFace);
835     theHistMap.Bind(aFace, atmpList);
836
837     TopExp_Explorer anExpE(aFace, TopAbs_EDGE);
838
839     for(; anExpE.More(); anExpE.Next()) {
840       TopoDS_Shape aNewValue = aSubstitutor->Value(anExpE.Current());
841
842       if(aNewValue.IsNull() || aNewValue.IsSame(anExpE.Current()))
843         continue;
844
845       if(theHistMap.IsBound(anExpE.Current()))
846         continue;
847       TopTools_ListOfShape aListOfNewEdge;
848       TopExp_Explorer anExpE2(aNewValue, TopAbs_EDGE);
849       
850       for(; anExpE2.More(); anExpE2.Next()) {
851         aListOfNewEdge.Append(anExpE2.Current());
852       }
853       theHistMap.Bind(anExpE.Current(), aListOfNewEdge);
854     }
855   }
856   return Standard_True;
857 }
858
859
860 // ------------------------------------------------------------------------------------------
861 // static function: SplitUEdges
862 // purpose:
863 // ------------------------------------------------------------------------------------------
864 Standard_Boolean SplitUEdges(const Handle(TopTools_HArray2OfShape)&     theUEdges, 
865                              const BOPTools_DSFiller&                   theDSFiller, 
866                              TopTools_DataMapOfShapeListOfShape&        theHistMap) {
867
868   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
869 //  const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
870 //  const BOPTools_SplitShapesPool& aSplitShapesPool = aPaveFiller.SplitShapesPool();
871   BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
872   BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
873   //   const BOPTools_CommonBlockPool& aCBPool = aPaveFiller.CommonBlockPool();
874 //  const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
875 //   const BOPTools_CArray1OfEEInterference& aEEs = pIntrPool->EEInterfs();
876   const BOPTools_CArray1OfVEInterference& aVEs = pIntrPool->VEInterferences();
877   const BOPTools_CArray1OfVVInterference& aVVs = pIntrPool->VVInterferences();
878
879   BRep_Builder aBB;
880   Standard_Integer ueit = 0;
881   TopTools_Array2OfShape aNewVertices(1,2,1,2);
882
883   for(ueit = theUEdges->LowerRow(); ueit <= theUEdges->UpperRow(); ueit++) {
884     const TopoDS_Shape& aE1 = theUEdges->Value(ueit, theUEdges->LowerCol());
885     const TopoDS_Shape& aE2 = theUEdges->Value(ueit, theUEdges->UpperCol());
886
887     if(theHistMap.IsBound(aE1) || theHistMap.IsBound(aE2))
888       continue;
889
890     Standard_Integer anEIndex1 = aDS.ShapeIndex(aE1, 1);
891     Standard_Integer anEIndex2 = aDS.ShapeIndex(aE2, 2);
892
893     TopoDS_Vertex aCommonVertex;
894     Standard_Real apar1 = 0., apar2 = 0.;
895     Standard_Boolean bvertexfound = 
896       FindCommonVertex(theDSFiller, anEIndex1, anEIndex2, aCommonVertex, apar1, apar2);
897
898     if(!bvertexfound) {
899       Standard_Integer j = 0;
900       for(j = 0; j < 2; j++) {
901         Standard_Integer veit = 0;
902
903         for(veit = 1; veit <= aVEs.Extent(); veit++) {
904           
905         }
906       }
907     }
908
909     if(!bvertexfound) {
910       TopoDS_Vertex V1 = TopExp::LastVertex(TopoDS::Edge(aE1));
911       TopoDS_Vertex V2 = TopExp::FirstVertex(TopoDS::Edge(aE2));
912       Standard_Integer vindex1 = aDS.ShapeIndex(V1, 1);
913       Standard_Integer vindex2 = aDS.ShapeIndex(V2, 2);
914       Standard_Integer vvit = 0;
915
916       for(vvit = 1; !bvertexfound && (vvit <= aVVs.Extent()); vvit++) {
917         const BOPTools_VVInterference& aVV = aVVs(vvit);
918
919         if(((vindex1 == aVV.Index1()) && (vindex2 = aVV.Index2())) ||
920            ((vindex1 == aVV.Index2()) && (vindex2 = aVV.Index1()))) {
921
922           if(aVV.NewShape() == 0) {
923             continue;
924           }
925           aCommonVertex = TopoDS::Vertex(aDS.Shape(aVV.NewShape()));
926           bvertexfound = Standard_True;
927           apar1 = BRep_Tool::Parameter(V1, TopoDS::Edge(aE1));
928           apar2 = BRep_Tool::Parameter(V2, TopoDS::Edge(aE2));
929         }
930       }
931     }
932
933     if(bvertexfound) {
934       TopoDS_Vertex aV1, aV2;
935       Standard_Real f = 0., l = 0.;
936       //
937       TopoDS_Edge aNewE1 = TopoDS::Edge(aE1.EmptyCopied());
938       TopExp::Vertices(TopoDS::Edge(aE1), aV1, aV2);
939       aNewE1.Orientation(TopAbs_FORWARD);
940       aV1.Orientation(TopAbs_FORWARD);
941       aBB.Add(aNewE1, aV1);
942       aCommonVertex.Orientation(TopAbs_REVERSED);
943       aBB.Add(aNewE1, aCommonVertex);
944       BRep_Tool::Range(TopoDS::Edge(aE1), f, l);
945       aBB.Range(aNewE1, f, apar1);
946
947       //
948       TopoDS_Edge aNewE2 = TopoDS::Edge(aE2.EmptyCopied());
949       TopExp::Vertices(TopoDS::Edge(aE2), aV1, aV2);
950       aNewE2.Orientation(TopAbs_FORWARD);
951       aCommonVertex.Orientation(TopAbs_FORWARD);
952       aBB.Add(aNewE2, aCommonVertex);
953       aBB.Add(aNewE2, aV2);
954       BRep_Tool::Range(TopoDS::Edge(aE2), f, l);
955       aBB.Range(aNewE2, apar2, l);
956
957       TopTools_ListOfShape lst;
958       lst.Append(aNewE1);
959       theHistMap.Bind(aE1, lst);
960       lst.Clear();
961       lst.Append(aNewE2);
962       theHistMap.Bind(aE2, lst);      
963     }
964   }
965   return Standard_True;
966 }
967
968 // ------------------------------------------------------------------------------------------
969 // static function: FindFreeVertices
970 // purpose:
971 // ------------------------------------------------------------------------------------------
972 void FindFreeVertices(const TopoDS_Shape&         theShape,
973                       const TopTools_MapOfShape&  theVerticesToAvoid,
974                       TopTools_ListOfShape&       theListOfVertex) {
975
976   theListOfVertex.Clear();
977   TopTools_IndexedDataMapOfShapeListOfShape aMap;
978   TopExp::MapShapesAndAncestors(theShape, TopAbs_VERTEX, TopAbs_EDGE, aMap);
979   Standard_Integer i = 0;
980
981   for(i = 1; i <= aMap.Extent(); i++) {
982     const TopoDS_Shape& aKey = aMap.FindKey(i);
983
984     if(theVerticesToAvoid.Contains(aKey))
985       continue;
986     const TopTools_ListOfShape& aList = aMap.FindFromIndex(i);
987
988     if(aList.Extent() < 2) {
989       theListOfVertex.Append(aKey);
990     }
991   }
992 }
993
994 // ------------------------------------------------------------------------------------------
995 // static function: FindParameter
996 // purpose:
997 // ------------------------------------------------------------------------------------------
998 Standard_Boolean FindParameter(const BOPTools_PaveSet&                     thePaveSet,
999                                const BooleanOperations_KindOfInterference& theType,
1000                                const Standard_Integer                      theInterfIndex,
1001                                Standard_Real&                              theParam) {
1002   BOPTools_ListIteratorOfListOfPave anPIt(thePaveSet.Set());
1003   Standard_Boolean bfound = Standard_False;
1004
1005   for(; anPIt.More(); anPIt.Next()) {
1006     const BOPTools_Pave& aPave = anPIt.Value();
1007
1008     if((aPave.Type() == theType) && 
1009        (aPave.Interference() == theInterfIndex)) {
1010       theParam = aPave.Param();
1011       bfound = Standard_True;
1012       break;
1013     }
1014   }
1015   return bfound;
1016 }
1017
1018 // ------------------------------------------------------------------------------------------
1019 // static function: FindCommonVertex
1020 // purpose:
1021 // ------------------------------------------------------------------------------------------
1022 Standard_Boolean FindCommonVertex(const BOPTools_DSFiller& theDSFiller,
1023                                   const Standard_Integer   theEIndex1,
1024                                   const Standard_Integer   theEIndex2,
1025                                   TopoDS_Vertex&           theCommonVertex,
1026                                   Standard_Real&           theParamOnE1,
1027                                   Standard_Real&           theParamOnE2) {
1028
1029   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1030   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1031   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1032   BOPTools_DSFiller& aDSFiller = (*((BOPTools_DSFiller*)&theDSFiller));
1033   BOPTools_InterferencePool* pIntrPool = (BOPTools_InterferencePool*)&aDSFiller.InterfPool();
1034   const BOPTools_CArray1OfEEInterference& aEEs = pIntrPool->EEInterfs();
1035
1036   Standard_Boolean bvertexfound = Standard_False;
1037   TopoDS_Vertex aCommonVertex;
1038   Standard_Integer eeit = 0;
1039
1040   for(eeit = 1; eeit <= aEEs.Extent(); eeit++) {
1041     const BOPTools_EEInterference& aEE = aEEs(eeit);
1042
1043     if((theEIndex1 == aEE.Index1() && theEIndex2 == aEE.Index2()) || 
1044        (theEIndex1 == aEE.Index2() && theEIndex2 == aEE.Index1())) {
1045
1046       if(aEE.NewShape() == 0)
1047         continue;
1048
1049       if(aDS.GetShapeType(aEE.NewShape()) == TopAbs_VERTEX) {
1050         theCommonVertex = TopoDS::Vertex(aDS.Shape(aEE.NewShape()));
1051
1052         bvertexfound = Standard_True;
1053         Standard_Integer i = 0;
1054
1055         for(i = 0; i < 2; i++) {
1056           Standard_Integer anEIndex = (i == 0) ? theEIndex1 : theEIndex2;
1057           const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(anEIndex));
1058           Standard_Boolean bfound = Standard_False;
1059
1060           if(i == 0)
1061             bfound = FindParameter(aPaveSet, BooleanOperations_EdgeEdge, eeit, theParamOnE1);
1062           else
1063             bfound = FindParameter(aPaveSet, BooleanOperations_EdgeEdge, eeit, theParamOnE2);
1064
1065           if(!bfound) {
1066             bvertexfound = Standard_False;
1067             break;
1068           }
1069         }
1070       }
1071       else if(aDS.GetShapeType(aEE.NewShape()) == TopAbs_EDGE) {
1072
1073       }
1074     }
1075   }
1076   return bvertexfound;
1077 }
1078
1079 // ------------------------------------------------------------------------------------------
1080 // static function: IsFromFirstToSecond
1081 // purpose:
1082 // ------------------------------------------------------------------------------------------
1083 Standard_Boolean IsFromFirstToSecond(const TopoDS_Edge&   theEdge,
1084                                      const Standard_Real  theParameterOnUEdge,
1085                                      const TopoDS_Edge&   theUEdge1,
1086                                      const TopoDS_Edge&   theUEdge2,
1087                                      const TopoDS_Face&   theFace) {
1088   TopoDS_Face aFace = theFace;
1089   aFace.Orientation(TopAbs_FORWARD);
1090   TopoDS_Edge E1, E2;
1091   TopExp_Explorer anExp(aFace, TopAbs_EDGE);
1092
1093   for(; anExp.More(); anExp.Next()) {
1094     if(E1.IsNull() && theUEdge1.IsSame(anExp.Current())) {
1095       E1 = TopoDS::Edge(anExp.Current());
1096     }
1097     else if(E2.IsNull() && theUEdge2.IsSame(anExp.Current())) {
1098       E2 = TopoDS::Edge(anExp.Current());
1099     }
1100   }
1101
1102   if(E1.IsNull() || E2.IsNull())
1103     return Standard_True;
1104
1105   gp_Pnt2d PU1, PU2, pf, pl;
1106   Standard_Real f, l;
1107   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1, aFace, f, l);
1108   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(E2, aFace, f, l);
1109   Handle(Geom2d_Curve) CC = BRep_Tool::CurveOnSurface(theEdge, aFace, f, l);
1110   PU1 = C1->Value(theParameterOnUEdge);
1111   PU2 = C2->Value(theParameterOnUEdge);
1112   BRep_Tool::Range(theEdge, f, l);
1113   pf = CC->Value(f);
1114   pl = CC->Value(l);
1115   Standard_Real aTolerance = Precision::Confusion();
1116
1117   if(pf.Distance(PU1) < aTolerance)
1118     return Standard_True;
1119
1120   if(pl.Distance(PU2) < aTolerance)
1121     return Standard_True;
1122   
1123   return Standard_False;
1124 }
1125
1126 // ----------------------------------------------------------------------------------------------------
1127 // static function: GetUEdges
1128 // purpose:
1129 // ----------------------------------------------------------------------------------------------------
1130 Standard_Boolean GetUEdges(const Standard_Integer                     theIndex,
1131                            const Standard_Integer                     theRank,
1132                            const Handle(TopTools_HArray2OfShape)&     theUEdges,
1133                            const TopoDS_Edge&                         theBoundEdge,
1134                            const TopoDS_Face&                         theFace,
1135                            TopoDS_Edge&                               theFirstUEdge,
1136                            TopoDS_Edge&                               theSecondUEdge) {
1137   const TopoDS_Shape& aUE1 = theUEdges->Value(theIndex, theUEdges->LowerCol() + theRank - 1);
1138   const TopoDS_Shape& aUE2 = theUEdges->Value(theIndex + 1, theUEdges->LowerCol() + theRank - 1);
1139
1140   TopoDS_Face aFace = theFace;
1141   aFace.Orientation(TopAbs_FORWARD);
1142   TopoDS_Edge E1, E2;
1143   TopExp_Explorer anExp(aFace, TopAbs_EDGE);
1144
1145   for(; anExp.More(); anExp.Next()) {
1146     if(E1.IsNull() && aUE1.IsSame(anExp.Current())) {
1147       E1 = TopoDS::Edge(anExp.Current());
1148     }
1149     else if(E2.IsNull() && aUE2.IsSame(anExp.Current())) {
1150       E2 = TopoDS::Edge(anExp.Current());
1151     }
1152   }
1153
1154   if(E1.IsNull() || E2.IsNull())
1155     return Standard_False;
1156
1157   Standard_Real f, l;
1158   Handle(Geom2d_Curve) C1 = BRep_Tool::CurveOnSurface(E1, aFace, f, l);
1159
1160   if(C1.IsNull())
1161      return Standard_False;
1162   gp_Pnt2d PU1 = (theRank == 1) ? C1->Value(l) : C1->Value(f);
1163   Handle(Geom2d_Curve) C2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFace, f, l);
1164
1165   if(C2.IsNull())
1166     return Standard_False;
1167   BRep_Tool::Range(theBoundEdge, f, l);
1168   gp_Pnt2d pf = C2->Value(f);
1169   TopoDS_Vertex aV = (theRank == 1) ? TopExp::LastVertex(E1) : TopExp::FirstVertex(E1);
1170   Standard_Real aTolerance = BRep_Tool::Tolerance(aV);
1171   BRepAdaptor_Surface aBAS(aFace, Standard_False);
1172
1173   if(pf.Distance(PU1) > aBAS.UResolution(aTolerance)) {
1174     TopoDS_Edge atmpE = E1;
1175     E1 = E2;
1176     E2 = atmpE;
1177   }
1178   theFirstUEdge = E1;
1179   theSecondUEdge = E2;
1180   return Standard_True;
1181 }
1182
1183 // ----------------------------------------------------------------------------------------------------
1184 // static function: FillGap
1185 // purpose:
1186 // ----------------------------------------------------------------------------------------------------
1187 Standard_Boolean FillGap(const TopoDS_Vertex&   theFirstVertex,
1188                          const TopoDS_Vertex&   theLastVertex,
1189                          const gp_Pnt2d&        theFirstPoint,
1190                          const gp_Pnt2d&        theLastPoint,
1191                          const TopoDS_Face&     theFace,
1192                          const TopoDS_Compound& theSectionEdges,
1193                          TopTools_ListOfShape&  theOrderedList) {
1194
1195   TopTools_IndexedDataMapOfShapeListOfShape aMap;
1196   TopExp::MapShapesAndAncestors(theSectionEdges, TopAbs_VERTEX, TopAbs_EDGE, aMap);
1197
1198   if(aMap.IsEmpty()) {
1199     return Standard_False;
1200   }
1201
1202   if(!aMap.Contains(theFirstVertex) || 
1203      !aMap.Contains(theLastVertex)) {
1204     return Standard_False;
1205   }
1206   TopTools_ListOfShape aListOfEdge;
1207 //  Standard_Integer i = 0;
1208 //  TopoDS_Vertex aCurVertex = theFirstVertex;
1209   TopTools_MapOfShape aMapToAvoid;
1210
1211   if(FindNextEdge(theFirstVertex, theLastVertex, aMap, aMapToAvoid, aListOfEdge)) {
1212     if(!aListOfEdge.IsEmpty()) {
1213       return CheckAndOrientEdges(aListOfEdge, theFirstPoint, theLastPoint, theFace, theOrderedList);
1214     }
1215   }
1216   return Standard_False;
1217 }
1218
1219 // ----------------------------------------------------------------------------------------------------
1220 // static function: FindNextEdge
1221 // purpose:
1222 // ----------------------------------------------------------------------------------------------------
1223 Standard_Boolean FindNextEdge(const TopoDS_Vertex&   theFirstVertex,
1224                               const TopoDS_Vertex&   theLastVertex,
1225                               const TopTools_IndexedDataMapOfShapeListOfShape& theMapVE,
1226                               const TopTools_MapOfShape& theMapToAvoid,
1227                               TopTools_ListOfShape&  theOrderedList) {
1228   TopoDS_Vertex aCurVertex = theFirstVertex;
1229   TopTools_MapOfShape aMapToAvoid;
1230   aMapToAvoid = theMapToAvoid;
1231   TopTools_ListOfShape aListOfEdge;
1232   Standard_Integer i = 0;
1233
1234   for(i = 1; i <= theMapVE.Extent(); i++) {
1235     if(!theMapVE.Contains(aCurVertex))
1236       break;
1237     const TopTools_ListOfShape& lste = theMapVE.FindFromKey(aCurVertex);
1238     Standard_Boolean befound = Standard_False;
1239
1240     TopTools_ListIteratorOfListOfShape anIt(lste);
1241
1242     for(; anIt.More(); anIt.Next()) {
1243       TopoDS_Shape anEdge = anIt.Value();
1244       TopoDS_Vertex aSaveCurVertex = aCurVertex;
1245
1246       if(!aMapToAvoid.Contains(anEdge)) {
1247         TopoDS_Vertex V1, V2;
1248         TopExp::Vertices(TopoDS::Edge(anEdge), V1, V2);
1249
1250         if(!aCurVertex.IsSame(V1)) {
1251           aCurVertex = V1;
1252         }
1253         else if(!aCurVertex.IsSame(V2)) {
1254           aCurVertex = V2;
1255         }
1256         aMapToAvoid.Add(anEdge);
1257         befound = Standard_True;
1258         aListOfEdge.Append(anEdge);
1259
1260         if(!aCurVertex.IsSame(theLastVertex)) {
1261           TopTools_ListOfShape aListtmp;
1262
1263           if(!FindNextEdge(aCurVertex, theLastVertex, theMapVE, aMapToAvoid, aListtmp)) {
1264             aListOfEdge.Clear();
1265             aCurVertex = aSaveCurVertex;
1266             continue;
1267           }
1268           else {
1269             aListOfEdge.Append(aListtmp);
1270             theOrderedList.Append(aListOfEdge);
1271             return Standard_True;
1272           }
1273         }
1274         break;
1275       }
1276     }
1277
1278     if(aCurVertex.IsSame(theLastVertex))
1279       break;
1280
1281     if(!befound) {
1282       return Standard_False;
1283     }
1284   }
1285
1286   if(aCurVertex.IsSame(theLastVertex)) {
1287     theOrderedList.Append(aListOfEdge);
1288     return Standard_True;
1289   }
1290   return Standard_False;
1291 }
1292
1293 // ----------------------------------------------------------------------------------------------------
1294 // static function: CheckAndOrientEdges
1295 // purpose:
1296 // ----------------------------------------------------------------------------------------------------
1297 Standard_Boolean CheckAndOrientEdges(const TopTools_ListOfShape&  theOrderedList,
1298                                      const gp_Pnt2d&              theFirstPoint,
1299                                      const gp_Pnt2d&              theLastPoint,
1300                                      const TopoDS_Face&           theFace,
1301                                      TopTools_ListOfShape&        theOrientedList) {
1302   TopTools_ListIteratorOfListOfShape anIt(theOrderedList);
1303
1304   if(!anIt.More())
1305     return Standard_True;
1306
1307   Standard_Real f, l;  
1308   TopoDS_Edge aEPrev = TopoDS::Edge(anIt.Value());
1309   anIt.Next();
1310
1311   Handle(Geom2d_Curve) aCurve = BRep_Tool::CurveOnSurface(aEPrev, theFace, f, l);
1312   TopoDS_Vertex Vf, Vl;
1313   TopExp::Vertices(aEPrev, Vf, Vl);
1314   BRepAdaptor_Surface aBAS(theFace, Standard_False);
1315
1316   Standard_Real aTolerance1 = (Vf.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(Vf);
1317   Standard_Real aTolerance2 = (Vl.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(Vl);
1318   Standard_Real utol = aBAS.UResolution(aTolerance1);
1319   Standard_Real vtol = aBAS.VResolution(aTolerance1);
1320   aTolerance1 = (utol > vtol) ? utol : vtol;
1321   utol = aBAS.UResolution(aTolerance2);
1322   vtol = aBAS.VResolution(aTolerance2);
1323   aTolerance2 = (utol > vtol) ? utol : vtol;
1324
1325   gp_Pnt2d ap = aCurve->Value(f);
1326   Standard_Boolean bFirstFound = Standard_False;
1327   Standard_Boolean bLastFound = Standard_False;
1328   Standard_Boolean bforward = Standard_True;
1329
1330   if(ap.Distance(theFirstPoint) < aTolerance1) {
1331     bforward = Standard_True;
1332     if(theOrientedList.IsEmpty())
1333       theOrientedList.Append(aEPrev.Oriented(TopAbs_FORWARD));
1334     bFirstFound = Standard_True;
1335   }
1336   else if(ap.Distance(theLastPoint) < aTolerance1) {
1337     bforward = Standard_False;
1338     if(theOrientedList.IsEmpty())
1339       theOrientedList.Append(aEPrev.Oriented(TopAbs_REVERSED));
1340     bLastFound = Standard_True;
1341   }
1342   ap = aCurve->Value(l);
1343
1344   if(ap.Distance(theLastPoint) < aTolerance2) {
1345     bforward = Standard_True;
1346
1347     if(theOrientedList.IsEmpty())
1348       theOrientedList.Append(aEPrev.Oriented(TopAbs_FORWARD));
1349     bLastFound = Standard_True;
1350   }
1351   else if(ap.Distance(theFirstPoint) < aTolerance2) {
1352     bforward = Standard_False;
1353
1354     if(theOrientedList.IsEmpty())
1355       theOrientedList.Append(aEPrev.Oriented(TopAbs_REVERSED));
1356     bFirstFound = Standard_True;
1357   }
1358
1359   for(; anIt.More(); anIt.Next()) {
1360     const TopoDS_Edge& aE = TopoDS::Edge(anIt.Value());
1361     TopoDS_Vertex aV11, aV12;
1362     TopExp::Vertices(aEPrev, aV11, aV12);
1363     TopoDS_Vertex aV21, aV22;
1364     TopExp::Vertices(aE, aV21, aV22);
1365     TopAbs_Orientation anOri = TopAbs_FORWARD;
1366
1367     if(aV12.IsSame(aV21) || aV11.IsSame(aV22)) {
1368       anOri = (bforward) ? TopAbs_FORWARD : TopAbs_REVERSED;
1369     }
1370     else {
1371       anOri = (bforward) ? TopAbs_REVERSED : TopAbs_FORWARD;
1372     }
1373     theOrientedList.Append(aE.Oriented(anOri));
1374     aEPrev = aE;
1375     aTolerance1 = (aV21.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(aV21);
1376     aTolerance2 = (aV22.IsNull()) ? Precision::Confusion() : BRep_Tool::Tolerance(aV22);
1377     utol = aBAS.UResolution(aTolerance1);
1378     vtol = aBAS.VResolution(aTolerance1);
1379     aTolerance1 = (utol > vtol) ? utol : vtol;
1380     utol = aBAS.UResolution(aTolerance2);
1381     vtol = aBAS.VResolution(aTolerance2);
1382     aTolerance2 = (utol > vtol) ? utol : vtol;
1383     aCurve = BRep_Tool::CurveOnSurface(aE, theFace, f, l);
1384     ap = aCurve->Value(f);
1385
1386     if(ap.Distance(theFirstPoint) < aTolerance1) {
1387       bFirstFound = Standard_True;
1388     }
1389     else if(ap.Distance(theLastPoint) < aTolerance1) {
1390       bLastFound = Standard_True;
1391     }
1392     ap = aCurve->Value(l);
1393
1394     if(ap.Distance(theFirstPoint) < aTolerance2) {
1395       bFirstFound = Standard_True;
1396     }
1397     else if(ap.Distance(theLastPoint) < aTolerance2) {
1398       bLastFound = Standard_True;
1399     }
1400   }
1401
1402   if(!bFirstFound || !bLastFound)
1403     return Standard_False;
1404   return Standard_True;
1405 }
1406
1407 // ----------------------------------------------------------------------------------------------------
1408 // static function: FindVertex
1409 // purpose:
1410 // ----------------------------------------------------------------------------------------------------
1411 Standard_Boolean FindVertex(const TopoDS_Edge&                        theEdge,
1412                             const Standard_Integer                    theRank, 
1413                             const BOPTools_DSFiller&                  theDSFiller, 
1414                             const TopTools_DataMapOfShapeListOfShape& theHistMap, 
1415                             TopoDS_Vertex&                            theVertex,
1416                             BOPTools_Pave&                            thePave) {
1417
1418   if(!theHistMap.IsBound(theEdge))
1419     return Standard_False;
1420
1421   const TopTools_ListOfShape& lst = theHistMap.Find(theEdge);
1422
1423   if(lst.IsEmpty())
1424     return Standard_False;
1425   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1426
1427   TopoDS_Edge aNewEdge = TopoDS::Edge(lst.First());
1428   Standard_Real f, l;
1429   BRep_Tool::Range(aNewEdge, f, l);
1430
1431   if(theRank == 1) {
1432     thePave.SetParam(l);
1433     theVertex = TopExp::LastVertex(aNewEdge);
1434   }
1435   else {
1436     thePave.SetParam(f);
1437     theVertex = TopExp::FirstVertex(aNewEdge);
1438   }
1439   Standard_Integer anIndex = aDS.ShapeIndex(theVertex, theRank);
1440
1441   if(anIndex == 0) {
1442     Standard_Integer i = 0;
1443
1444     for(i = aDS.NumberOfSourceShapes() + 1; i <= aDS.NumberOfInsertedShapes(); i++) {
1445       const TopoDS_Shape& aShape = aDS.Shape(i);
1446
1447       if(theVertex.IsSame(aShape)) {
1448         anIndex = i;
1449         break;
1450       }
1451     }
1452   }
1453   thePave.SetIndex(anIndex);
1454
1455   return Standard_True;
1456 }
1457
1458 // ----------------------------------------------------------------------------------------------------
1459 // static function: FindNextVertex
1460 // purpose:
1461 // ----------------------------------------------------------------------------------------------------
1462 Standard_Boolean FindNextVertex(const Standard_Integer                    theEdgeIndex,
1463                                 const BOPTools_Pave&                      thePrevPave,
1464                                 const BOPTools_DSFiller&                  theDSFiller, 
1465                                 TopoDS_Vertex&                            theNextVertex,
1466                                 BOPTools_Pave&                            thePave) {
1467
1468   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1469   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1470   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1471   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theEdgeIndex));
1472   BOPTools_PaveSet aSortedPaveSet;
1473   aSortedPaveSet = aPaveSet;
1474   aSortedPaveSet.SortSet();
1475
1476   BOPTools_ListIteratorOfListOfPave anIt(aSortedPaveSet.Set());
1477   BOPTools_Pave anullpave(0, 0.);
1478   Standard_Boolean btakepave = (thePrevPave.IsEqual(anullpave));
1479   Standard_Boolean bfound = Standard_False;
1480   BOPTools_Pave atmppave;
1481
1482   for(; anIt.More(); anIt.Next()) {
1483     if(btakepave) {
1484       atmppave = anIt.Value();
1485
1486       if(atmppave.Type() != BooleanOperations_UnknownInterference) {
1487         theNextVertex = TopoDS::Vertex(aDS.Shape(atmppave.Index()));
1488         thePave = atmppave;
1489         bfound = Standard_True;
1490         break;
1491       }
1492     }
1493
1494     if(thePrevPave.IsEqual(anIt.Value())) {
1495       btakepave = Standard_True;
1496     }
1497   }
1498
1499   return bfound;
1500 }
1501
1502 // ----------------------------------------------------------------------------------------------------
1503 // static function: GetPave
1504 // purpose:
1505 // ----------------------------------------------------------------------------------------------------
1506 Standard_Boolean GetPave(const Standard_Integer   theEdgeIndex,
1507                          const Standard_Boolean   isFirst,
1508                          const BOPTools_DSFiller& theDSFiller, 
1509                          BOPTools_Pave&           thePave) {
1510   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1511   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1512   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1513
1514   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theEdgeIndex));
1515   BOPTools_PaveSet aSortedPaveSet;
1516   aSortedPaveSet = aPaveSet;
1517   aSortedPaveSet.SortSet();
1518
1519   if(aSortedPaveSet.Set().IsEmpty())
1520     return Standard_False;
1521
1522   if(isFirst) {
1523     thePave = aSortedPaveSet.Set().First();
1524   }
1525   else {
1526     thePave = aSortedPaveSet.Set().Last();
1527   }
1528   return Standard_True;
1529 }
1530
1531
1532 // ----------------------------------------------------------------------------------------------------
1533 // static function: FindFromUEdge
1534 // purpose:
1535 // ----------------------------------------------------------------------------------------------------
1536 Standard_Boolean FindFromUEdge(const TopoDS_Edge&                        theUE1Old, 
1537                                const TopoDS_Edge&                        theUE2Old, 
1538                                const TopoDS_Edge&                        theUE1New, 
1539                                const TopoDS_Edge&                        theUE2New, 
1540                                const TopoDS_Face&                        theFace, 
1541                                const TopoDS_Compound&                    theSecEdges, 
1542                                const Standard_Integer                    theRank, 
1543                                const TopoDS_Edge&                        theBoundEdge, 
1544                                const Standard_Integer                    theBoundEdgeIndex, 
1545                                const BOPTools_DSFiller&                  theDSFiller, 
1546                                const TopTools_DataMapOfShapeListOfShape& theHistMap,
1547                                TopoDS_Compound&                          theSecEdgesNew, 
1548                                TopTools_ListOfShape&                     theListOfWireEdges, 
1549                                BOPTools_Pave&                            theFoundPave, 
1550                                Standard_Boolean&                         isOnUEdge) {
1551   theFoundPave.SetIndex(0);
1552   theFoundPave.SetParam(0.);
1553   isOnUEdge = Standard_True;
1554
1555   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1556   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1557   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1558
1559   TopoDS_Face aFaceF = theFace;
1560   aFaceF.Orientation(TopAbs_FORWARD);
1561   TopoDS_Vertex aPrevVertex, aNextVertex;
1562   TopoDS_Compound aCompOfSecEdges = theSecEdges;
1563   TopTools_ListOfShape aListOfWireEdges;
1564 //  BRep_Builder aBB;
1565
1566   BOPTools_Pave aPave1(0, 0.), aPave2(0, 0.);
1567   Standard_Real f = 0., l = 0.;
1568   gp_Pnt2d p1, p2;
1569   TopoDS_Vertex aFirstV, aLastV;
1570   BOPTools_Pave atmpPave;
1571
1572   if(!FindVertex(theUE1Old, theRank, theDSFiller, theHistMap, aPrevVertex, atmpPave)) {
1573     return Standard_True;
1574   }
1575
1576   if(aPrevVertex.IsNull()) {
1577     return Standard_False;
1578   }
1579
1580   aFirstV = aPrevVertex;
1581   Standard_Boolean bSecFound = Standard_False;
1582   Handle(Geom2d_Curve) aC1 = BRep_Tool::CurveOnSurface(theUE1New, aFaceF, f, l);
1583   p1 = (theRank == 1) ? aC1->Value(l) : aC1->Value(f);
1584   BOPTools_Pave afoundpave(0, 0.);
1585   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theBoundEdgeIndex));
1586   Standard_Integer nbpave = aPaveSet.Set().Extent();
1587   Standard_Integer pit = 0;
1588
1589   while(FindNextVertex(theBoundEdgeIndex, aPave1, theDSFiller, aNextVertex, aPave2) && (pit < nbpave)) {
1590     aLastV = aNextVertex;
1591     Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFaceF, f, l);
1592     p2 = aC2->Value(aPave2.Param());
1593     TopTools_ListOfShape aOrderedList;
1594
1595     if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1596       // remove found edges...
1597       TopoDS_Compound aComp;
1598       RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1599       aCompOfSecEdges = aComp;
1600       aListOfWireEdges.Append(aOrderedList);
1601       afoundpave = aPave2;
1602       isOnUEdge = Standard_False;
1603       bSecFound = Standard_True;
1604       break;
1605     }
1606     aPrevVertex = aNextVertex;
1607     aPave1 = aPave2;
1608     pit++;
1609   }
1610
1611   if(!bSecFound && FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, aNextVertex, aPave2)) {
1612     aLastV = aNextVertex;
1613     Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theUE2New, aFaceF, f, l);
1614     p2 = aC2->Value(aPave2.Param());
1615     TopTools_ListOfShape aOrderedList;
1616
1617     if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1618       // remove found edges...
1619       TopoDS_Compound aComp;
1620
1621       RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1622       aCompOfSecEdges = aComp;
1623       aListOfWireEdges.Append(aOrderedList);
1624       afoundpave = aPave2;
1625       bSecFound = Standard_True;
1626       isOnUEdge = Standard_True;
1627     }
1628   }
1629
1630   if(bSecFound) {
1631     theFoundPave = afoundpave;
1632     theListOfWireEdges = aListOfWireEdges;
1633     theSecEdgesNew = aCompOfSecEdges;
1634   }
1635   return Standard_True;
1636 }
1637
1638
1639 // ----------------------------------------------------------------------------------------------------
1640 // static function: FindFromVEdge
1641 // purpose:
1642 // ----------------------------------------------------------------------------------------------------
1643 Standard_Boolean FindFromVEdge(const BOPTools_Pave&                      thePrevPave,
1644                                const Standard_Boolean&                   isOnUEdge,
1645                                const TopoDS_Edge&                        theUE1Old, 
1646                                const TopoDS_Edge&                        theUE2Old, 
1647                                const TopoDS_Face&                        theFace, 
1648                                const TopoDS_Compound&                    theSecEdges, 
1649                                const Standard_Integer                    theRank, 
1650                                const TopoDS_Edge&                        theBoundEdge, 
1651                                const Standard_Integer                    theBoundEdgeIndex, 
1652                                const BOPTools_DSFiller&                  theDSFiller,
1653                                const TopTools_DataMapOfShapeListOfShape& theHistMap,
1654                                TopTools_ListOfShape&                     theListOfWireEdges, 
1655                                Standard_Boolean&                         isSectionFound) {
1656   theListOfWireEdges.Clear();
1657   isSectionFound = Standard_False;
1658   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
1659   const BOPTools_PaveFiller&           aPaveFiller = theDSFiller.PaveFiller();
1660   const BOPTools_SplitShapesPool& aSplitShapesPool = aPaveFiller.SplitShapesPool();
1661   const BOPTools_PavePool& aPavePool = aPaveFiller.PavePool();
1662
1663   TopoDS_Face aFaceF = theFace;
1664   aFaceF.Orientation(TopAbs_FORWARD);
1665   TopoDS_Vertex aPrevVertex, aNextVertex;
1666   TopoDS_Compound aCompOfSecEdges = theSecEdges;
1667   TopTools_ListOfShape aListOfWireEdges;
1668 //  BRep_Builder aBB;
1669
1670   BOPTools_Pave aPave1(0, 0.), aPave2(0, 0.);
1671
1672   if(isOnUEdge) {
1673     TopoDS_Vertex atmpVertex;
1674     BOPTools_Pave aPaveOfE2;
1675
1676     if(FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, atmpVertex, aPaveOfE2)) {
1677       if(thePrevPave.IsEqual(aPaveOfE2))
1678         return Standard_True;
1679     }
1680   }
1681
1682   Standard_Real f = 0., l = 0.;
1683   gp_Pnt2d p1(0., 0.), p2(0., 0.);
1684   TopoDS_Vertex aFirstV, aLastV;
1685   Handle(Geom2d_Curve) aC1 = BRep_Tool::CurveOnSurface(theUE1Old, aFaceF, f, l);
1686   Handle(Geom2d_Curve) aC2 = BRep_Tool::CurveOnSurface(theBoundEdge, aFaceF, f, l);
1687   Standard_Boolean bSecFound = Standard_False;
1688
1689   aPave1 = thePrevPave;
1690
1691   if(isOnUEdge) {
1692     BOPTools_Pave atmpPave;
1693
1694     if(!GetPave(theBoundEdgeIndex, Standard_True, theDSFiller, atmpPave)) {
1695       return Standard_False;
1696     }
1697     aPave1 = atmpPave;
1698   }
1699   p1 = aC2->Value(aPave1.Param());
1700   aPrevVertex = TopoDS::Vertex(aDS.Shape(aPave1.Index()));
1701
1702   const BOPTools_PaveSet& aPaveSet = aPavePool(aDS.RefEdge(theBoundEdgeIndex));
1703   Standard_Integer nbpave = aPaveSet.Set().Extent();
1704   Standard_Integer pit = 0;
1705   TopTools_Array1OfListOfShape anArrayOfListOfSec(1, nbpave);
1706
1707   // by pairs non continuously. begin
1708   Standard_Integer k = 0;
1709   BOPTools_Pave aFirstPave = aPave1;
1710   TopoDS_Vertex aFirstVertex = aPrevVertex;
1711   gp_Pnt2d apfirst = p1;
1712   BOPTools_ListOfPave aFirstPaves, aLastPaves;
1713   TColStd_ListOfInteger aListOfFlags;
1714   Standard_Integer apaircounter = 1;
1715
1716   for(k = 0; k < nbpave; k++) {
1717     aPave1 = aFirstPave;
1718     p1 = apfirst;
1719     aPrevVertex = aFirstVertex;
1720     Standard_Boolean bfound = Standard_False;
1721     pit = 0;
1722
1723     while(FindNextVertex(theBoundEdgeIndex, aPave1, theDSFiller, aNextVertex, aPave2) && (pit < nbpave)) {
1724       aFirstV = aPrevVertex;
1725       aLastV = aNextVertex;
1726       p2 = aC2->Value(aPave2.Param());
1727
1728       TopTools_ListOfShape aOrderedList;
1729
1730       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1731         TopoDS_Compound aComp;
1732         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1733         aCompOfSecEdges = aComp;
1734
1735         anArrayOfListOfSec(apaircounter++).Append(aOrderedList);
1736         BOPTools_PaveBlock aPB(theBoundEdgeIndex, aFirstPave, aPave2);
1737         aFirstPaves.Append(aFirstPave);
1738         aLastPaves.Append(aPave2);
1739         aListOfFlags.Append(1);
1740         aFirstPave = aPave2;
1741         aFirstVertex = aNextVertex;
1742         apfirst = p2;
1743         aPrevVertex = aNextVertex;
1744         bSecFound = Standard_True;
1745         bfound = Standard_True;
1746       }
1747       aPave1 = aPave2;
1748       pit++;
1749     }
1750
1751     if(FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, aNextVertex, aPave2)) {
1752       aFirstV = aPrevVertex;
1753       aLastV = aNextVertex;
1754       Handle(Geom2d_Curve) aC3 = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1755       p2 = aC3->Value(aPave2.Param());
1756
1757       TopTools_ListOfShape aOrderedList;
1758
1759       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1760         TopoDS_Compound aComp;
1761         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1762         aCompOfSecEdges = aComp;
1763         anArrayOfListOfSec(apaircounter++).Append(aOrderedList);
1764         BOPTools_PaveBlock aPB(-1, aFirstPave, aPave2);
1765         aFirstPaves.Append(aFirstPave);
1766         aLastPaves.Append(aPave2);
1767         aListOfFlags.Append(0);
1768         bSecFound = Standard_True;
1769         break;
1770       }
1771     }
1772
1773     if(!bfound) {
1774       if(!FindNextVertex(theBoundEdgeIndex, aFirstPave, theDSFiller, aNextVertex, aPave2)) {
1775         break;
1776       }
1777       aFirstPave = aPave2;
1778       apfirst = aC2->Value(aPave2.Param());
1779       aFirstVertex = aNextVertex;
1780     }
1781   }
1782   // by pairs non continuously. end
1783
1784   // by pairs continuously. begin
1785   aPave1 = thePrevPave;
1786
1787   if(isOnUEdge) {
1788     BOPTools_Pave atmpPave;
1789
1790     if(!GetPave(theBoundEdgeIndex, Standard_True, theDSFiller, atmpPave)) {
1791       return Standard_False;
1792     }
1793     aPave1 = atmpPave;
1794   }
1795   p1 = aC2->Value(aPave1.Param());
1796   aPrevVertex = TopoDS::Vertex(aDS.Shape(aPave1.Index()));
1797
1798   pit = 0;
1799
1800   while(FindNextVertex(theBoundEdgeIndex, aPave1, theDSFiller, aNextVertex, aPave2) && (pit < nbpave)) {
1801     aFirstV = aPrevVertex;
1802     aLastV = aNextVertex;
1803     p2 = aC2->Value(aPave2.Param());
1804
1805     Standard_Boolean bisinside = Standard_False;
1806     Standard_Integer apbindex = 0;
1807     Standard_Integer apbcounter = 1;
1808     BOPTools_ListIteratorOfListOfPaveBlock aPBIt;
1809     BOPTools_ListIteratorOfListOfPave aPIt1, aPIt2;
1810     TColStd_ListIteratorOfListOfInteger aFlagIt;
1811
1812     for(aPIt1.Initialize(aFirstPaves), aPIt2.Initialize(aLastPaves), aFlagIt.Initialize(aListOfFlags); 
1813         aPIt1.More() && aPIt2.More() && aFlagIt.More(); 
1814         aPIt1.Next(), aPIt2.Next(), aFlagIt.Next(), apbcounter++) {
1815
1816       Standard_Boolean bfin = Standard_False;
1817       Standard_Boolean blin = Standard_False;
1818
1819       if(aPave1.IsEqual(aPIt1.Value())) {
1820         bfin = Standard_True;
1821       }
1822       else {
1823         bfin = (aPave1.Param() > aPIt1.Value().Param());
1824       }
1825
1826       if(aFlagIt.Value()) {
1827         if(aPave2.IsEqual(aPIt2.Value())) {
1828           blin = Standard_True;
1829         }
1830         else {
1831           blin = (aPave2.Param() < aPIt2.Value().Param());
1832         }
1833       }
1834       else {
1835         if((aPave2.Index() == aPIt2.Value().Index()) && (aPave2.Index() > 0)) {
1836           Handle(Geom2d_Curve) pc = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1837           gp_Pnt2d p3 = pc->Value(aPIt2.Value().Param());
1838           TopoDS_Vertex aV = TopoDS::Vertex(aDS.Shape(aPave2.Index()));
1839           BRepAdaptor_Surface aBAS(aFaceF, Standard_False);
1840           Standard_Real aTolerance = BRep_Tool::Tolerance(aV);
1841           Standard_Real utol = aBAS.UResolution(aTolerance);
1842           Standard_Real vtol = aBAS.VResolution(aTolerance);
1843           aTolerance = (utol > vtol) ? utol : vtol;
1844
1845           if(p2.Distance(p3) < aTolerance)
1846             blin = Standard_True;
1847         }
1848       }
1849
1850       if(bfin && blin) {
1851         apbindex = apbcounter;
1852         bisinside = Standard_True;
1853         break;
1854       }
1855     }
1856
1857     if(!bisinside) {
1858
1859       TopTools_ListOfShape aOrderedList;
1860
1861       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1862         TopoDS_Compound aComp;
1863         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1864         aCompOfSecEdges = aComp;
1865         aListOfWireEdges.Append(aOrderedList);
1866
1867         bSecFound = Standard_True;
1868       }
1869       else {
1870         TopoDS_Edge aESplit;
1871         BOPTools_PaveBlock aPB(theBoundEdgeIndex, aPave1, aPave2);
1872         // get split
1873         aPBIt.Initialize(aSplitShapesPool(aDS.RefEdge(theBoundEdgeIndex)));
1874
1875         for(; aPBIt.More(); aPBIt.Next()) {
1876           if(aPB.IsEqual(aPBIt.Value())) {
1877             if(aPBIt.Value().Edge() > 0) {
1878               aESplit = TopoDS::Edge(aDS.Shape(aPBIt.Value().Edge()));
1879               break;
1880             }
1881           }
1882         }
1883         
1884         if(!aESplit.IsNull()) {
1885           aListOfWireEdges.Append(aESplit);
1886         }
1887       }
1888     }
1889     else {
1890       if(apbindex > 0) {
1891         TopTools_ListOfShape& aListOfSec = anArrayOfListOfSec(apbindex);
1892         aListOfWireEdges.Append(aListOfSec);
1893       }
1894     }
1895     aPave1 = aPave2;
1896     aPrevVertex = aNextVertex;
1897     p1 = p2;
1898     pit++;
1899   }
1900
1901   if(FindVertex(theUE2Old, theRank, theDSFiller, theHistMap, aNextVertex, aPave2)) {
1902     aFirstV = aPrevVertex;
1903     aLastV = aNextVertex;
1904     Handle(Geom2d_Curve) aC3 = BRep_Tool::CurveOnSurface(theUE2Old, aFaceF, f, l);
1905     p2 = aC3->Value(aPave2.Param());
1906
1907     Standard_Boolean bisinside = Standard_False;
1908     Standard_Integer apbindex = 0;
1909     Standard_Integer apbcounter = 1;
1910     BOPTools_ListIteratorOfListOfPaveBlock aPBIt;
1911     BOPTools_ListIteratorOfListOfPave aPIt1, aPIt2;
1912     TColStd_ListIteratorOfListOfInteger aFlagIt;
1913
1914     for(aPIt1.Initialize(aFirstPaves), aPIt2.Initialize(aLastPaves), aFlagIt.Initialize(aListOfFlags); 
1915         aPIt1.More() && aPIt2.More() && aFlagIt.More(); 
1916         aPIt1.Next(), aPIt2.Next(), aFlagIt.Next(), apbcounter++) {
1917
1918       Standard_Boolean bfin = Standard_False;
1919       Standard_Boolean blin = Standard_False;
1920
1921       if(aPave1.IsEqual(aPIt1.Value())) {
1922         bfin = Standard_True;
1923       }
1924       else {
1925         bfin = (aPave1.Param() > aPIt1.Value().Param());
1926       }
1927
1928       if(aFlagIt.Value()) {
1929         if(aPave2.IsEqual(aPIt2.Value())) {
1930           blin = Standard_True;
1931         }
1932         else {
1933           blin = (aPave2.Param() < aPIt2.Value().Param());
1934         }
1935       }
1936       else {
1937         blin = Standard_True;
1938       }
1939
1940       if(bfin && blin) {
1941         apbindex = apbcounter;
1942         bisinside = Standard_True;
1943         break;
1944       }
1945     }
1946
1947     if(!bisinside) {
1948
1949       TopTools_ListOfShape aOrderedList;
1950
1951       if(FillGap(aFirstV, aLastV, p1, p2, aFaceF, aCompOfSecEdges, aOrderedList)) {
1952         TopoDS_Compound aComp;
1953         RemoveEdges(aCompOfSecEdges, aOrderedList, aComp);
1954         aCompOfSecEdges = aComp;
1955         aListOfWireEdges.Append(aOrderedList);
1956
1957         bSecFound = Standard_True;
1958       }
1959       else {
1960         //add split
1961         TopoDS_Edge aESplit;
1962         // get split
1963         if(!GetPave(theBoundEdgeIndex, Standard_False, theDSFiller, aPave2))
1964           return Standard_False;
1965         BOPTools_PaveBlock aPB(theBoundEdgeIndex, aPave1, aPave2);
1966         aPBIt.Initialize(aSplitShapesPool(aDS.RefEdge(theBoundEdgeIndex)));
1967
1968         for(; aPBIt.More(); aPBIt.Next()) {
1969           if(aPB.IsEqual(aPBIt.Value())) {
1970             if(aPBIt.Value().Edge() > 0) {
1971               aESplit = TopoDS::Edge(aDS.Shape(aPBIt.Value().Edge()));
1972               break;
1973             }
1974           }
1975         }
1976
1977         if(!aESplit.IsNull()) {
1978           aListOfWireEdges.Append(aESplit);
1979         }
1980       }
1981     }
1982     else {
1983       if(apbindex > 0) {
1984         TopTools_ListOfShape& aListOfSec = anArrayOfListOfSec(apbindex);
1985         aListOfWireEdges.Append(aListOfSec);
1986       }
1987     }
1988   }
1989   else {
1990     //add split
1991     TopoDS_Edge aESplit;
1992     // get split
1993     if(!GetPave(theBoundEdgeIndex, Standard_False, theDSFiller, aPave2))
1994       return Standard_False;
1995     BOPTools_PaveBlock aPB(theBoundEdgeIndex, aPave1, aPave2);
1996     BOPTools_ListIteratorOfListOfPaveBlock aPBIt;
1997     aPBIt.Initialize(aSplitShapesPool(aDS.RefEdge(theBoundEdgeIndex)));
1998
1999     for(; aPBIt.More(); aPBIt.Next()) {
2000       if(aPB.IsEqual(aPBIt.Value())) {
2001         if(aPBIt.Value().Edge() > 0) {
2002           aESplit = TopoDS::Edge(aDS.Shape(aPBIt.Value().Edge()));
2003           break;
2004         }
2005       }
2006     }
2007
2008     if(!aESplit.IsNull()) {
2009       aListOfWireEdges.Append(aESplit);
2010     }
2011   }
2012   
2013   // by pairs continuously. end
2014   theListOfWireEdges = aListOfWireEdges;
2015   isSectionFound = bSecFound;
2016   return Standard_True;
2017 }
2018
2019 // ----------------------------------------------------------------------------------------------------
2020 // static function: RemoveEdges
2021 // purpose:
2022 // ----------------------------------------------------------------------------------------------------
2023 void RemoveEdges(const TopoDS_Compound&      theSourceComp,
2024                  const TopTools_ListOfShape& theListToRemove,
2025                  TopoDS_Compound&            theResultComp) {
2026   BRep_Builder aBB;
2027   TopoDS_Compound aComp;
2028   aBB.MakeCompound(aComp);
2029   TopExp_Explorer anExp(theSourceComp, TopAbs_EDGE);
2030
2031   for(; anExp.More(); anExp.Next()) {
2032     Standard_Boolean bfound = Standard_False;
2033     TopTools_ListIteratorOfListOfShape anIt(theListToRemove);
2034     
2035     for(; !bfound && anIt.More(); anIt.Next()) {
2036       bfound = anExp.Current().IsSame(anIt.Value());
2037     }
2038
2039     if(!bfound) {
2040       aBB.Add(aComp, anExp.Current());
2041     }
2042   }
2043   theResultComp = aComp;
2044 }
2045
2046 // ----------------------------------------------------------------------------------------------------
2047 // static function: FilterSectionEdges
2048 // purpose:
2049 // ----------------------------------------------------------------------------------------------------
2050 Standard_Boolean FilterSectionEdges(const BOPTools_SequenceOfCurves& theBCurves,
2051                                     const TopoDS_Face&               theSecPlane,
2052                                     const BOPTools_DSFiller&         theDSFiller,
2053                                     TopoDS_Compound&                 theResult) {
2054
2055   theResult.Nullify();
2056   const BooleanOperations_ShapesDataStructure& aDS = theDSFiller.DS();
2057
2058   BRep_Builder aBB;
2059   aBB.MakeCompound(theResult);
2060   Standard_Integer aNbCurves = theBCurves.Length();
2061   Standard_Integer cit = 0;
2062
2063   for(cit = 1; cit <= aNbCurves; cit++) {
2064     const BOPTools_Curve& aBCurve = theBCurves(cit);
2065     const BOPTools_ListOfPaveBlock& aSectEdges = aBCurve.NewPaveBlocks();
2066
2067     BOPTools_ListIteratorOfListOfPaveBlock aPBIt(aSectEdges);
2068
2069     for (; aPBIt.More(); aPBIt.Next()) {
2070       BOPTools_PaveBlock& aPB = aPBIt.Value();
2071       Standard_Integer nSect = aPB.Edge();
2072       const TopoDS_Shape& aS = aDS.GetShape(nSect);
2073       TopoDS_Edge anEdge = TopoDS::Edge(aS);
2074       Standard_Boolean bAddEdge = Standard_True;
2075
2076       if(!theSecPlane.IsNull()) {
2077         IntTools_BeanFaceIntersector anIntersector(anEdge, theSecPlane);
2078         Standard_Real f = 0., l = 0.;
2079         BRep_Tool::Range(anEdge, f, l);
2080         anIntersector.SetBeanParameters(f, l);
2081         //
2082         IntTools_Context aContext;
2083         anIntersector.SetContext(&aContext);
2084         //
2085         anIntersector.Perform();
2086
2087         if(anIntersector.IsDone()) {
2088           bAddEdge = Standard_False;
2089           Standard_Integer r = 0;
2090
2091           for(r = 1; r <= anIntersector.Result().Length(); r++) {
2092             const IntTools_Range& aRange = anIntersector.Result().Value(r);
2093
2094             if(((aRange.First() - f) < Precision::PConfusion()) &&
2095                ((l - aRange.Last()) < Precision::PConfusion())) {
2096               bAddEdge = Standard_True;
2097             }
2098           }
2099         }
2100         else {
2101 //        cout << "not done..."   << endl;
2102         }
2103       }
2104
2105       if(bAddEdge) {
2106         aBB.Add(theResult, aS);
2107       }
2108     }
2109   }
2110   return Standard_True;
2111 }
2112
2113
2114 //=======================================================================
2115 //function : ComputeAveragePlaneAndMaxDeviation
2116 //purpose  : 
2117 //=======================================================================
2118 static Standard_Real ComputeAveragePlaneAndMaxDeviation(const TopoDS_Shape& aWire,
2119                                                         gp_Pln& thePlane,
2120                                                         Standard_Boolean& IsSingular)
2121 {
2122   Standard_Integer N = 40, nedges = 0;
2123
2124   TopoDS_Iterator iter( aWire );
2125   for (; iter.More(); iter.Next())
2126     nedges++;
2127
2128   TColgp_Array1OfPnt Pnts( 1, nedges*N );
2129   Standard_Integer ind = 1, i;
2130   for (iter.Initialize(aWire); iter.More(); iter.Next())
2131     {
2132       const TopoDS_Edge& anEdge = TopoDS::Edge( iter.Value() );
2133       BRepAdaptor_Curve aCurve(anEdge);
2134       GCPnts_UniformAbscissa Distribution( aCurve, N+1 );
2135       for (i = 1; i <= N; i++)
2136         {
2137           Standard_Real par = Distribution.Parameter(i);
2138           Pnts( ind++ ) = aCurve.Value(par);
2139         }
2140     }
2141
2142   gp_Ax2 Axe;
2143   GeomLib::AxeOfInertia( Pnts, Axe, IsSingular );
2144   if (IsSingular)
2145     return -1;
2146
2147   thePlane = gp_Pln( Axe );
2148   Standard_Real MaxDeviation = 0;
2149   for (i = 1; i <= Pnts.Length(); i++)
2150     {
2151       Standard_Real dist = thePlane.Distance( Pnts(i) );
2152       if (dist > MaxDeviation)
2153         MaxDeviation = dist;
2154     }
2155   return MaxDeviation;
2156 }
2157
2158 //=======================================================================
2159 //function : ChooseSection
2160 //purpose  : 
2161 //=======================================================================
2162 static Standard_Boolean ChooseSection(const TopoDS_Shape& Comp,
2163                                       const gp_Ax2& bis,
2164                                       TopoDS_Shape& resWire,
2165                                       gp_Pln& resPlane,
2166                                       Standard_Boolean& IsSingular)
2167 {
2168   IsSingular = Standard_False;
2169   Standard_Real TolDeviation = 0.01; //, TolConf = 1.e-4, TolAng = 1.e-5;
2170
2171 //  Standard_Integer N = 100;
2172   Standard_Integer ind, i, j;
2173
2174   //Simplest case
2175   TopoDS_Compound OldComp;
2176   BRep_Builder B;
2177   B.MakeCompound( OldComp );
2178   TopoDS_Iterator iter( Comp );
2179   for (; iter.More(); iter.Next())
2180     B.Add( OldComp, iter.Value() );
2181
2182   Standard_Boolean anError = Standard_False;
2183   //TopoDS_Wire NewWire [2];
2184   TopTools_SequenceOfShape Wseq;
2185   for (;;)
2186     {
2187       TopExp_Explorer explo( OldComp, TopAbs_EDGE );
2188       if (!explo.More())
2189         break;
2190       TopoDS_Edge FirstEdge = TopoDS::Edge( explo.Current() );
2191       TopoDS_Wire NewWire = BRepLib_MakeWire( FirstEdge );
2192       B.Remove( OldComp, FirstEdge );
2193       if (NewWire.Closed())
2194         {
2195           Wseq.Append(NewWire);
2196           continue;
2197         }
2198
2199       for (;;)
2200         {
2201           TopoDS_Vertex Extremity [2];
2202           TopExp::Vertices( NewWire, Extremity[0], Extremity[1] );
2203           if (Extremity[0].IsNull() || Extremity[1].IsNull())
2204             {
2205               anError = Standard_True;
2206               break;
2207             }
2208           TopTools_IndexedDataMapOfShapeListOfShape VEmap;
2209           TopExp::MapShapesAndAncestors( OldComp, TopAbs_VERTEX, TopAbs_EDGE, VEmap );
2210           TopTools_ListOfShape Vedges [2];
2211           for (j = 0; j < 2; j++)
2212             if (VEmap.Contains( Extremity[j] ))
2213               Vedges[j] = VEmap.FindFromKey( Extremity[j] );
2214           if (Vedges[0].IsEmpty() && Vedges[1].IsEmpty())
2215             //no more edges in OldComp to continue NewWire
2216             break;
2217           Standard_Boolean Modified = Standard_False;
2218           for (j = 0; j < 2; j++)
2219             {
2220               if (Vedges[j].Extent() == 1)
2221                 {
2222                   const TopoDS_Edge& anEdge = TopoDS::Edge( Vedges[j].First() );
2223                   NewWire = BRepLib_MakeWire( NewWire, anEdge );
2224                   B.Remove( OldComp, anEdge );
2225                   Modified = Standard_True;
2226                 }
2227             }
2228           if (!Modified) //only multiple connections
2229             {
2230               ind = (Vedges[0].IsEmpty())? 1 : 0;
2231               TopTools_SequenceOfShape Edges;
2232               TopTools_ListIteratorOfListOfShape itl( Vedges[ind] );
2233               for (; itl.More(); itl.Next())
2234                 Edges.Append( itl.Value() );
2235               Standard_Integer theind=0;
2236               Standard_Real MinDeviation = RealLast();
2237               for (j = 1; j <= Edges.Length(); j++)
2238                 {
2239                   TopoDS_Wire aWire = BRepLib_MakeWire( NewWire, TopoDS::Edge(Edges(j)) );
2240                   gp_Pln aPlane;
2241                   Standard_Boolean issing;
2242                   Standard_Real Deviation = ComputeAveragePlaneAndMaxDeviation( aWire, aPlane, issing );
2243                   if (Deviation < MinDeviation)
2244                     {
2245                       MinDeviation = Deviation;
2246                       theind = j;
2247                     }
2248                 }
2249               NewWire = BRepLib_MakeWire( NewWire, TopoDS::Edge(Edges(theind)) );
2250               B.Remove( OldComp, Edges(theind) );
2251             }
2252           if (NewWire.Closed())
2253             break;
2254         }
2255       Wseq.Append(NewWire);
2256       if (anError)
2257         break;
2258     }
2259
2260   Standard_Real Deviation=0.;
2261   Standard_Real MinAngle = RealLast();
2262   TopExp_Explorer Explo( OldComp, TopAbs_EDGE );
2263   if (!anError && !Explo.More())
2264     {
2265       if (Wseq.Length() == 1)
2266         {
2267           resWire = Wseq.First();
2268           Deviation = ComputeAveragePlaneAndMaxDeviation( resWire, resPlane, IsSingular );
2269           return Standard_True;
2270         }
2271       else
2272         {
2273           for (i = 1; i <= Wseq.Length(); i++)
2274             {
2275               TopoDS_Wire aWire = TopoDS::Wire( Wseq(i) );
2276               gp_Pln aPln;
2277               Standard_Boolean issing;
2278               Standard_Real aDeviation =
2279                 ComputeAveragePlaneAndMaxDeviation( aWire, aPln, issing );
2280               if (issing)
2281                 continue;
2282
2283               Standard_Real Angle = aPln.Axis().Angle( bis.Axis() );
2284               if (Angle > M_PI/2)
2285                 Angle = M_PI - Angle;
2286               
2287               if (Angle < MinAngle)
2288                 {
2289                   MinAngle = Angle;
2290                   resWire = aWire;
2291                   resPlane = aPln;
2292                   Deviation = aDeviation;
2293                 }
2294             }
2295           if (Deviation <= TolDeviation)
2296             return Standard_True;
2297         }
2298     }
2299   return Standard_False;
2300   //end of simplest case
2301 }
2302
2303 //=======================================================================
2304 //function : ChoosePlane
2305 //purpose  : 
2306 //=======================================================================
2307 static Standard_Boolean ChoosePlane(const TopoDS_Shape& Comp,
2308                                     const gp_Ax2& bis,
2309                                     gp_Pln& resPlane,
2310                                     TopoDS_Compound& NewComp)
2311 {
2312   Standard_Real TolConf = 1.e-4, TolAng = 1.e-5;
2313
2314   Standard_Integer N = 100;
2315   Standard_Integer Eind, ind, i, j;
2316   TopTools_SequenceOfShape Eseq;
2317   TopExp_Explorer Explo( Comp, TopAbs_EDGE );
2318   for (; Explo.More(); Explo.Next())
2319     Eseq.Append( Explo.Current() );
2320
2321   Standard_Integer NumberOfEdges = Eseq.Length();
2322   TColgp_Array2OfPnt Points( 0, NumberOfEdges*2-1, 1, N/4 );
2323
2324   for (Eind = 0; Eind < NumberOfEdges; Eind++)
2325     {
2326       TopoDS_Edge anEdge = TopoDS::Edge( Eseq(Eind+1) );
2327       BRepAdaptor_Curve aCurve(anEdge);
2328       GCPnts_UniformAbscissa Distribution( aCurve, N+1 );
2329       for (i = 1; i <= N/4; i++)
2330         {
2331           Standard_Real par = Distribution.Parameter(i);
2332           Points( Eind*2, i ) = aCurve.Value(par);
2333         }
2334       for (i = 3*N/4+2; i <= N+1; i++)
2335         {
2336           Standard_Real par = Distribution.Parameter(i);
2337           Points( Eind*2+1, i-3*N/4-1 ) = aCurve.Value(par);
2338         }
2339     }
2340
2341   TColgp_Array1OfPnt Origins( 0, NumberOfEdges*2-1 );
2342   TColgp_Array1OfDir Normals( 0, NumberOfEdges*2-1 );
2343   TColStd_Array1OfBoolean IsSingular( 0, NumberOfEdges*2-1 );
2344   Standard_Real MinAngle = M_PI/2;
2345   Standard_Integer MinInd;
2346   for (ind = 0; ind < NumberOfEdges*2; ind++)
2347     {
2348       TColgp_Array1OfPnt pnts( 1, N/4 );
2349       for (i = 1; i <= N/4; i++)
2350         pnts(i) = Points( ind, i );
2351       gp_Ax2 Axe;
2352       GeomLib::AxeOfInertia( pnts, Axe, IsSingular(ind) );
2353       if (!IsSingular(ind))
2354         {
2355           Origins(ind) = Axe.Location();
2356           Normals(ind) = Axe.Direction();
2357           Standard_Real Angle = bis.Angle( Axe );
2358           if (Angle > M_PI/2)
2359             Angle = M_PI - Angle;
2360           if (Angle < MinAngle)
2361             {
2362               MinAngle = Angle;
2363               MinInd = ind;
2364             }
2365         }
2366     }
2367
2368   gp_Ax2 TheAxe( Origins(MinInd), Normals(MinInd) );
2369   Standard_Real MaxAngleWithPln = M_PI/16;
2370   TColStd_SequenceOfInteger iseq;
2371   TColgp_SequenceOfPnt Pseq;
2372   for (ind = 0; ind < NumberOfEdges*2; ind++)
2373     if (!IsSingular(ind))
2374       {
2375         Standard_Real Angle = Normals(ind).Angle( TheAxe.Direction() );
2376           if (Angle > M_PI/2)
2377             Angle = M_PI - Angle;
2378         if (Angle <= MaxAngleWithPln)
2379           {
2380             iseq.Append(ind);
2381             for (j = 1; j <= N/4; j++)
2382               Pseq.Append( Points(ind,j) );
2383           }
2384       }
2385
2386   TColgp_Array1OfPnt Parray( 1, Pseq.Length() );
2387   for (i = 1; i <= Parray.Length(); i++)
2388     Parray(i) = Pseq(i);
2389   Standard_Boolean issing;
2390   GeomLib::AxeOfInertia( Parray, TheAxe, issing );
2391   resPlane = gp_Pln( TheAxe );
2392   
2393   i = 1;
2394   BRep_Builder B;
2395   B.MakeCompound(NewComp);
2396   while (i <= iseq.Length())
2397     {
2398       Standard_Integer ind0 = iseq(i);
2399       if (IsEven(ind0) && i < iseq.Length() && iseq(i+1) == ind0+1) //the whole edge
2400         {
2401           B.Add( NewComp, Eseq(ind0/2+1) );
2402           i += 2;
2403         }
2404       else
2405         i++;
2406     }
2407
2408   Standard_Integer slen = Pseq.Length();
2409   for (ind = 0; ind < NumberOfEdges*2; ind += 2)
2410     {
2411       Standard_Integer IndSing = -1, IndNotSing = -1;
2412       gp_Lin aLine;
2413       if (IsSingular(ind) && IsSingular(ind+1))
2414         {
2415           Standard_Boolean OnPlane0 = Standard_False, OnPlane1 = Standard_False;
2416           aLine = gce_MakeLin( Points(ind, 1), Points(ind, N/4) );
2417           if (resPlane.Contains( aLine, TolConf, TolAng ))
2418             {
2419               for (j = 1; j <= N/4; j++)
2420                 Pseq.Append( Points(ind,j) );
2421               OnPlane0 = Standard_True;
2422             }
2423           aLine = gce_MakeLin( Points(ind+1, 1), Points(ind+1, N/4) );
2424           if (resPlane.Contains( aLine, TolConf, TolAng ))
2425             {
2426               for (j = 1; j <= N/4; j++)
2427                 Pseq.Append( Points(ind+1,j) );
2428               OnPlane1 = Standard_True;
2429             }
2430           if (OnPlane0 && OnPlane1)
2431             B.Add( NewComp, Eseq(ind/2+1) );
2432         }
2433       else if (IsSingular(ind))
2434         {
2435           IndSing    = ind;
2436           IndNotSing = ind+1;
2437         }
2438       else if (IsSingular(ind+1))
2439         {
2440           IndNotSing = ind;
2441           IndSing    = ind+1;
2442         }
2443       if (IndSing != -1 && IndNotSing != -1)
2444         {
2445           aLine = gce_MakeLin( Points(IndSing, 1), Points(IndSing, N/4) );
2446           if (resPlane.Contains( aLine, TolConf, TolAng ))
2447             {
2448               for (j = 1; j <= N/4; j++)
2449                 Pseq.Append( Points(IndSing,j) );
2450
2451               for (i = 1; i <= iseq.Length(); i++)
2452                 if (iseq(i) == IndNotSing)
2453                   break;
2454               if (i <= iseq.Length())
2455                 B.Add( NewComp, Eseq(ind/2+1) );
2456             }
2457         }
2458     }
2459
2460   //Recompute the axe of plane
2461   if (Pseq.Length() > slen)
2462     {
2463       TColgp_Array1OfPnt Parray2( 1, Pseq.Length() );
2464       for (i = 1; i <= Parray2.Length(); i++)
2465         Parray2(i) = Pseq(i);
2466       GeomLib::AxeOfInertia( Parray2, TheAxe, issing );
2467       resPlane = gp_Pln( TheAxe );
2468     }
2469
2470   //Temporary
2471   return Standard_True;
2472 }