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