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