]> SALOME platform Git repositories - modules/shaper.git/blob - src/GeomAlgoAPI/GeomAlgoAPI_SketchBuilder.cpp
Salome HOME
cba0974a5f18101631d2027e54ba359119fcc153
[modules/shaper.git] / src / GeomAlgoAPI / GeomAlgoAPI_SketchBuilder.cpp
1 // File:        GeomAlgoAPI_SketchBuilder.cpp
2 // Created:     02 Jun 2014
3 // Author:      Artem ZHIDKOV
4
5 #include <GeomAlgoAPI_SketchBuilder.h>
6
7 #include <set>
8
9 #include <gp_Dir.hxx>
10 #include <gp_Pln.hxx>
11
12 #include <BOPAlgo_Builder.hxx>
13 #include <BOPAlgo_Operation.hxx>
14 #include <BOPAlgo_PaveFiller.hxx>
15 #include <BOPTools.hxx>
16 #include <BRep_Builder.hxx>
17 #include <BRep_Curve3D.hxx>
18 #include <BRep_TEdge.hxx>
19 #include <BRep_TVertex.hxx>
20 #include <BRepAlgoAPI_Cut.hxx>
21 #include <BRepBuilderAPI_MakeFace.hxx>
22 #include <BRepClass_FaceClassifier.hxx>
23 #include <Geom_Curve.hxx>
24 #include <Geom_Plane.hxx>
25 #include <TopExp.hxx>
26 #include <TopExp_Explorer.hxx>
27 #include <TopoDS_Edge.hxx>
28 #include <TopoDS_Face.hxx>
29 #include <TopoDS_Vertex.hxx>
30 #include <TopoDS_Wire.hxx>
31
32 #include <Precision.hxx>
33
34 #ifndef DBL_MAX
35 #define DBL_MAX 1.7976931348623158e+308 
36 #endif
37
38
39 const double tolerance = Precision::Confusion();
40 // This value helps to find direction on the boundaries of curve.
41 // It is not significant for lines, but is used for circles to avoid 
42 // wrong directions of movement (when two edges are tangent on the certain vertex)
43 const double shift     = acos(1.0 - 2.0 * tolerance);
44
45 /// \brief Search first vertex - the vertex with lowest x coordinate, which is used in 2 edges at least
46 static const TopoDS_Shape& findStartVertex(
47           const BOPCol_IndexedDataMapOfShapeListOfShape& theMapVE,
48           const gp_Dir& theDirX, const gp_Dir& theDirY);
49
50 /// \brief Search the vertex on the sketch candidate to be the next one in the loop
51 static void findNextVertex(
52           const TopoDS_Shape&                            theStartVertex, 
53           const BOPCol_IndexedDataMapOfShapeListOfShape& theVertexEdgeMap,
54           const gp_Dir&                                  theStartDir,
55           const gp_Dir&                                  theNormal,
56                 TopoDS_Shape&                            theNextVertex,
57                 TopoDS_Shape&                            theNextEdge,
58                 gp_Dir&                                  theNextDir);
59
60 /// \brief Create planar face using the edges surrounding it
61 static void createFace(const TopoDS_Shape&                      theStartVertex,
62                        const std::list<TopoDS_Shape>::iterator& theStartEdge,
63                        const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
64                        const gp_Pln&                            thePlane,
65                              TopoDS_Face&                       theResFace);
66
67 /// \bief Create planar wire
68 static void createWireList(const TopoDS_Shape&                      theStartVertex,
69                            const std::list<TopoDS_Shape>::iterator& theStartEdge,
70                            const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
71                            const std::set<Handle(TopoDS_TShape)>&   theEdgesInLoops,
72                                  std::list<TopoDS_Wire>&            theResWires);
73
74 /// \brief Calculate outer tengency on the edge in specified vertex
75 static gp_Dir getOuterEdgeDirection(const TopoDS_Shape& theEdge,
76                                     const TopoDS_Shape& theVertex);
77
78 /// \brief Unnecessary edges will be removed from the map.
79 ///        Positions of iterator will be updated
80 static void removeWasteEdges(
81                 std::list<TopoDS_Shape>::iterator&  theStartVertex,
82                 std::list<TopoDS_Shape>::iterator&  theStartEdge,
83           const std::list<TopoDS_Shape>::iterator&  theEndOfVertexes,
84           const std::list<TopoDS_Shape>::iterator&  theEndOfEdges,
85           BOPCol_IndexedDataMapOfShapeListOfShape&  theMapVE);
86
87
88
89
90 void GeomAlgoAPI_SketchBuilder::createFaces(
91           const boost::shared_ptr<GeomAPI_Pnt>&                theOrigin,
92           const boost::shared_ptr<GeomAPI_Dir>&                theDirX,
93           const boost::shared_ptr<GeomAPI_Dir>&                theDirY,
94           const boost::shared_ptr<GeomAPI_Dir>&                theNorm,
95           const std::list< boost::shared_ptr<GeomAPI_Shape> >& theFeatures,
96                 std::list< boost::shared_ptr<GeomAPI_Shape> >& theResultFaces,
97                 std::list< boost::shared_ptr<GeomAPI_Shape> >& theResultWires)
98 {
99   if (theFeatures.empty())
100     return ;
101
102   // Create the list of edges with shared vertexes
103   BOPAlgo_Builder aBuilder;
104   BOPAlgo_PaveFiller aPF;
105   TopoDS_Shape aFeaturesCompound;
106
107   if (theFeatures.size() == 1)
108   { // If there is only one feature, BOPAlgo_Builder will decline to work. Need to process it anyway
109     aFeaturesCompound = theFeatures.front()->impl<TopoDS_Shape>();
110   }
111   else
112   {
113     std::list< boost::shared_ptr<GeomAPI_Shape> >::const_iterator anIt = theFeatures.begin();
114     for (; anIt != theFeatures.end(); anIt++)
115     {
116       boost::shared_ptr<GeomAPI_Shape> aPreview(*anIt);
117       aBuilder.AddArgument(aPreview->impl<TopoDS_Edge>());
118     }
119     aPF.SetArguments(aBuilder.Arguments());
120     aPF.Perform();
121     int aErr = aPF.ErrorStatus();
122     if (aErr) return ;
123     aBuilder.PerformWithFiller(aPF);
124     aErr = aBuilder.ErrorStatus();
125     if (aErr) return ;
126     aFeaturesCompound = aBuilder.Shape();
127   }
128
129   BOPCol_IndexedDataMapOfShapeListOfShape aMapVE; // map between vertexes and edges
130   BOPTools::MapShapesAndAncestors(aFeaturesCompound, TopAbs_VERTEX, TopAbs_EDGE, aMapVE);
131   if (aMapVE.IsEmpty()) // in case of not-initialized circle
132     return;
133
134   gp_Dir aDirX = theDirX->impl<gp_Dir>();
135   gp_Dir aDirY = theDirY->impl<gp_Dir>();
136   gp_Dir aNorm = theNorm->impl<gp_Dir>();
137
138   gp_Pln aPlane(theOrigin->impl<gp_Pnt>(), aNorm);
139
140   // Set of edges used in loops
141   std::set<Handle(TopoDS_TShape)> anEdgesInLoops;
142   // Lists for processed vertexes and edges
143   std::list<TopoDS_Shape> aProcVertexes;
144   std::list<TopoDS_Shape> aProcEdges;
145
146   // Search the start vertex
147   TopoDS_Shape aStartVertex = findStartVertex(aMapVE, aDirX, aDirY);
148   aProcVertexes.push_back(aStartVertex);
149
150   TopoDS_Shape aCurVertex = aStartVertex;
151   gp_Dir aCurDir = aDirY.Reversed();
152   gp_Dir aCurNorm = aNorm.Reversed();
153
154   // Go through the edges and find loops
155   TopoDS_Shape aNextVertex;
156   TopoDS_Shape aBindingEdge;
157   gp_Dir aNextDir;
158   while (aMapVE.Extent() > 0)
159   {
160     if (aCurVertex.IsNull())
161       return;
162     findNextVertex(aCurVertex, aMapVE, aCurDir, aCurNorm, aNextVertex, aBindingEdge, aNextDir);
163     aCurNorm = aNorm;
164
165     // Try to find next vertex in the list of already processed
166     std::list<TopoDS_Shape>::iterator          aVertIter = aProcVertexes.begin();
167     std::list<TopoDS_Shape>::iterator          anEdgeIter = aProcEdges.begin();
168     for ( ; aVertIter != aProcVertexes.end(); aVertIter++)
169     {
170       if (aVertIter->TShape() == aNextVertex.TShape())
171         break;
172       if (anEdgeIter != aProcEdges.end())
173         anEdgeIter++;
174     }
175
176     aProcVertexes.push_back(aNextVertex);
177     aProcEdges.push_back(aBindingEdge);
178
179     // The loop was found
180     if (aVertIter != aProcVertexes.end())
181     {
182       // If the binding edge is a full circle, then the list may be empty before addition. Need to update edge iterator
183       if (aProcEdges.size() == 1)
184         anEdgeIter = aProcEdges.begin();
185
186       if (aVertIter != aProcVertexes.begin())
187       {
188         // Check the orientation of the loop
189         gp_Dir aCN = getOuterEdgeDirection(*anEdgeIter, *aVertIter);
190         gp_Dir aCP = getOuterEdgeDirection(aProcEdges.back(), *aVertIter);
191         aCN.Reverse();
192         aCP.Reverse();
193         if (aCN.DotCross(aCP, aNorm) < -tolerance)
194         {
195           // The found loop has wrong orientation and may contain sub-loops.
196           // Need to check it onle again with another initial direction.
197           aCurVertex = *aVertIter;
198           do {
199             aProcVertexes.pop_back();
200             aProcEdges.pop_back();
201           } while (aCurVertex != aProcVertexes.back());
202           aCurDir = getOuterEdgeDirection(aProcEdges.back(), aCurVertex);
203           aCurNorm = aNorm.Reversed();
204           continue;
205         }
206       }
207
208       // When the orientation is correct or the edges looped through
209       // the first element, create new face and remove unnecessary edges.
210       TopoDS_Face aPatch;
211       createFace(*aVertIter, anEdgeIter, aProcEdges.end(), aPlane, aPatch);
212       if (!aPatch.IsNull())
213       {
214         boost::shared_ptr<GeomAPI_Shape> aFace(new GeomAPI_Shape);
215         aFace->setImpl(new TopoDS_Face(aPatch));
216         theResultFaces.push_back(aFace);
217       }
218       // push the edges used in the loop to the map
219       std::list<TopoDS_Shape>::iterator anIter;
220       for (anIter = anEdgeIter; anIter != aProcEdges.end(); anIter++)
221         anEdgesInLoops.insert(anIter->TShape());
222       // remove unnecessary edges
223       std::list<TopoDS_Shape>::iterator aCopyVLoop = aVertIter;
224       std::list<TopoDS_Shape>::iterator aCopyELoop = anEdgeIter;
225       removeWasteEdges(aVertIter, anEdgeIter, aProcVertexes.end(), aProcEdges.end(), aMapVE);
226
227       // revert the list of remaining edges
228       std::list<TopoDS_Shape> aRemainVertexes;
229       for ( ; aVertIter != aProcVertexes.end(); aVertIter++)
230         aRemainVertexes.push_front(*aVertIter);
231       std::list<TopoDS_Shape> aRemainEdges;
232       for ( ; anEdgeIter != aProcEdges.end(); anEdgeIter++)
233         aRemainEdges.push_front(*anEdgeIter);
234       // remove edges and vertexes used in the loop and add remaining ones
235       aProcVertexes.erase(aCopyVLoop, aProcVertexes.end());
236       aProcVertexes.insert(aProcVertexes.end(), aRemainVertexes.begin(), aRemainVertexes.end());
237       aProcEdges.erase(aCopyELoop, aProcEdges.end());
238       aProcEdges.insert(aProcEdges.end(), aRemainEdges.begin(), aRemainEdges.end());
239
240       // Recalculate current vertex and current direction
241       if (!aProcVertexes.empty())
242       {
243         aNextVertex = aProcVertexes.back();
244         if (!aProcEdges.empty())
245           aNextDir = getOuterEdgeDirection(aProcEdges.back(), aNextVertex);
246         else aNextDir = aDirY;
247       }
248     }
249
250     // if next vertex connected only to alone edge, this is a part of wire (not a closed loop),
251     // we need to go back through the list of already checked edges to find a branching vertex
252     if (!aMapVE.IsEmpty() && aMapVE.Contains(aNextVertex) && 
253         aMapVE.FindFromKey(aNextVertex).Size() == 1)
254     {
255       std::list<TopoDS_Shape>::reverse_iterator aVRIter = aProcVertexes.rbegin();
256       std::list<TopoDS_Shape>::reverse_iterator aERIter = aProcEdges.rbegin();
257       if (aVRIter != aProcVertexes.rend())
258         aVRIter++;
259       if (aERIter != aProcEdges.rend())
260         aERIter++;
261
262       for ( ; aERIter != aProcEdges.rend(); aERIter++, aVRIter++)
263         if (aMapVE.FindFromKey(*aVRIter).Size() > 2)
264           break;
265       if (aERIter != aProcEdges.rend() || 
266          (aVRIter != aProcVertexes.rend() && aMapVE.FindFromKey(*aVRIter).Size() == 1))
267       { // the branching vertex was found or current list of edges is a wire without branches
268         std::list<TopoDS_Shape>::iterator aEIter;
269         TopoDS_Shape aCurEdge;
270         if (aERIter != aProcEdges.rend())
271         {
272           aEIter = aERIter.base();
273           aCurEdge = *aERIter;
274         }
275         else
276           aEIter = aProcEdges.begin();
277         std::list<TopoDS_Wire> aTail;
278         createWireList(*aVRIter, aEIter, aProcEdges.end(), anEdgesInLoops, aTail);
279         std::list<TopoDS_Wire>::const_iterator aTailIter = aTail.begin();
280         for ( ; aTailIter != aTail.end(); aTailIter++)
281           if (!aTailIter->IsNull())
282           {
283             boost::shared_ptr<GeomAPI_Shape> aWire(new GeomAPI_Shape);
284             aWire->setImpl(new TopoDS_Shape(*aTailIter));
285             theResultWires.push_back(aWire);
286           }
287         std::list<TopoDS_Shape>::iterator aVIter = aVRIter.base();
288         std::list<TopoDS_Shape>::iterator aEItCopy = aEIter;
289         removeWasteEdges(--aVIter, aEItCopy, aProcVertexes.end(), aProcEdges.end(), aMapVE);
290
291         aProcEdges.erase(aEIter, aProcEdges.end());
292         aVIter = aVRIter.base();
293         aProcVertexes.erase(aVIter, aProcVertexes.end());
294
295         if (!aProcVertexes.empty())
296         {
297           aNextVertex = aProcVertexes.back();
298           if (!aCurEdge.IsNull())
299             aNextDir = getOuterEdgeDirection(aCurEdge, aNextVertex);
300         }
301       }
302       else
303       { // there is no branching vertex in the list of proceeded,
304         // so we should revert the list and go the opposite way
305         aProcVertexes.reverse();
306         aProcEdges.reverse();
307         aNextVertex = aProcVertexes.back();
308         aNextDir = aProcEdges.empty() ? aDirY : 
309                    getOuterEdgeDirection(aProcEdges.back(), aNextVertex);
310       }
311     }
312
313     // When all edges of current component of connectivity are processed,
314     // we should repeat procedure for finding initial vertex in the remaining
315     if (!aMapVE.IsEmpty() && !aMapVE.Contains(aNextVertex))
316     {
317       aProcVertexes.clear();
318       aProcEdges.clear();
319
320       TopoDS_Shape aStartEdge;
321       aStartVertex = findStartVertex(aMapVE, aDirX, aDirY);
322       aProcVertexes.push_back(aStartVertex);
323       aNextVertex = aStartVertex;
324       aNextDir = aDirY.Reversed();
325       aCurNorm = aNorm.Reversed();
326     }
327
328     aCurVertex = aNextVertex;
329     aCurDir = aNextDir;
330   }
331
332   if (theResultFaces.size() > 1)
333     fixIntersections(theResultFaces);
334 }
335
336 void GeomAlgoAPI_SketchBuilder::fixIntersections(
337           std::list< boost::shared_ptr<GeomAPI_Shape> >& theFaces)
338 {
339   BRepClass_FaceClassifier aClassifier;
340
341   std::list< boost::shared_ptr<GeomAPI_Shape> >::iterator anIter1 = theFaces.begin();
342   std::list< boost::shared_ptr<GeomAPI_Shape> >::iterator anIter2;
343   for ( ; anIter1 != theFaces.end(); anIter1++)
344   {
345     anIter2 = anIter1;
346     for (++anIter2; anIter2 != theFaces.end(); anIter2++)
347     {
348       const TopoDS_Face& aF1 = (*anIter1)->impl<TopoDS_Face>();
349       if (aF1.ShapeType() != TopAbs_FACE) // TODO: MPV - this workaround must be fixed later by AZV, now it just removes crash
350         continue;
351       TopExp_Explorer aVert2((*anIter2)->impl<TopoDS_Shape>(), TopAbs_VERTEX);
352       for ( ; aVert2.More(); aVert2.Next())
353       {
354         Handle(BRep_TVertex) aV = Handle(BRep_TVertex)::DownCast(aVert2.Current().TShape());
355         aClassifier.Perform(aF1, aV->Pnt(), tolerance);
356         if (aClassifier.State() != TopAbs_IN)
357           break;
358       }
359       if (aVert2.More())
360       { // second shape is not inside first, change the shapes order and repeat comparision
361         const TopoDS_Face& aF2 = (*anIter2)->impl<TopoDS_Face>();
362         TopExp_Explorer aVert1((*anIter1)->impl<TopoDS_Shape>(), TopAbs_VERTEX);
363         for ( ; aVert1.More(); aVert1.Next())
364         {
365           Handle(BRep_TVertex) aV = Handle(BRep_TVertex)::DownCast(aVert1.Current().TShape());
366           aClassifier.Perform(aF2, aV->Pnt(), tolerance);
367           if (aClassifier.State() != TopAbs_IN)
368             break;
369         }
370         if (!aVert1.More())
371         { // first shape should be cut from the second
372           BRepAlgoAPI_Cut aCut((*anIter2)->impl<TopoDS_Shape>(),
373                                (*anIter1)->impl<TopoDS_Shape>());
374           (*anIter2)->setImpl(new TopoDS_Shape(aCut.Shape()));
375         }
376       }
377       else
378       { // second shape should be cut from the first
379         BRepAlgoAPI_Cut aCut((*anIter1)->impl<TopoDS_Shape>(),
380                              (*anIter2)->impl<TopoDS_Shape>());
381         (*anIter1)->setImpl(new TopoDS_Shape(aCut.Shape()));
382       }
383     }
384   }
385 }
386
387
388 // =================== Auxiliary functions ====================================
389 const TopoDS_Shape& findStartVertex(
390           const BOPCol_IndexedDataMapOfShapeListOfShape& theMapVE,
391           const gp_Dir& theDirX, const gp_Dir& theDirY)
392 {
393   int aStartVertexInd = 1;
394   double aMaxX = -DBL_MAX;
395   double aMaxY = -DBL_MAX;
396   int aNbVert = theMapVE.Extent();
397   for (int i = 1; i <= aNbVert; i++)
398   {
399     const TopoDS_Vertex& aV = (const TopoDS_Vertex&)theMapVE.FindKey(i);
400     const Handle(BRep_TVertex)& aVert = (const Handle(BRep_TVertex)&)aV.TShape();
401     const gp_Pnt& aVertPnt = aVert->Pnt();
402
403     double aX = aVertPnt.XYZ().Dot(theDirX.XYZ());
404     double aY = aVertPnt.XYZ().Dot(theDirY.XYZ());
405     if ((aX > aMaxX || (fabs(aX - aMaxX) < tolerance && aY > aMaxY)) && 
406         theMapVE.FindFromIndex(i).Extent() > 1)
407     {
408       aMaxX = aX;
409       aMaxY = aY;
410       aStartVertexInd = i;
411     }
412   }
413   return theMapVE.FindKey(aStartVertexInd);
414 }
415
416 void findNextVertex(
417           const TopoDS_Shape&                            theStartVertex,
418           const BOPCol_IndexedDataMapOfShapeListOfShape& theVertexEdgeMap,
419           const gp_Dir&                                  theStartDir,
420           const gp_Dir&                                  theNormal,
421                 TopoDS_Shape&                            theNextVertex,
422                 TopoDS_Shape&                            theNextEdge,
423                 gp_Dir&                                  theNextDir)
424 {
425   const BOPCol_ListOfShape& anEdgesList = theVertexEdgeMap.FindFromKey(theStartVertex);
426   BOPCol_ListOfShape::Iterator aEdIter(anEdgesList);
427   double aBestEdgeProj = DBL_MAX;
428   for ( ; aEdIter.More(); aEdIter.Next())
429   {
430     gp_Dir aTang = getOuterEdgeDirection(aEdIter.Value(), theStartVertex);
431     aTang.Reverse();
432
433     // The projection is normalized in segment (-1, 1),
434     // where (-1, 0] corresponds to the angles (pi/2, 0] between theStartDir and aTang
435     // and [0, 1) corresponds to the angles [0, -pi/2)
436     double aProj = (aTang.Dot(theStartDir) - 1.0) * 0.5;
437     if (fabs(fabs(aProj) - 1) < tolerance)
438       continue;
439     if (theStartDir.DotCross(aTang, theNormal) < tolerance)
440       aProj *= -1.0;
441
442     if (aProj < aBestEdgeProj)
443     {
444       aBestEdgeProj = aProj;
445       theNextEdge = aEdIter.Value();
446       TopExp_Explorer aVertExp(theNextEdge, TopAbs_VERTEX);
447       for ( ; aVertExp.More(); aVertExp.Next())
448         if (aVertExp.Current().TShape() != theStartVertex.TShape())
449         {
450           theNextVertex = aVertExp.Current();
451           theNextDir = getOuterEdgeDirection(aEdIter.Value(), theNextVertex);
452           break;
453         }
454       if (!aVertExp.More())
455       { // This edge is a full circle
456         TopoDS_Vertex aV1, aV2;
457         TopExp::Vertices(*(const TopoDS_Edge*)(&theNextEdge), aV1, aV2);
458         if (aV1.Orientation() == theStartVertex.Orientation())
459           theNextVertex = aV2;
460         else
461           theNextVertex = aV1;
462         theNextDir = getOuterEdgeDirection(aEdIter.Value(), theNextVertex);
463       }
464     }
465   }
466 }
467
468 static void addEdgeToWire(const TopoDS_Edge&  theEdge,
469                           const BRep_Builder& theBuilder,
470                                 TopoDS_Shape& theSpliceVertex,
471                                 TopoDS_Wire&  theWire)
472 {
473   TopoDS_Edge anEdge = theEdge;
474   bool isCurVertChanged = false;
475   TopoDS_Shape aCurVertChanged;
476
477   TopExp_Explorer aVertExp(theEdge, TopAbs_VERTEX);
478   for ( ; aVertExp.More(); aVertExp.Next())
479   {
480     const TopoDS_Shape& aVertex = aVertExp.Current();
481     if (aVertex.TShape() == theSpliceVertex.TShape() && 
482         aVertex.Orientation() != theEdge.Orientation())
483     { // Current vertex is the last for the edge, so its orientation is wrong, need to revert the edge
484       anEdge.Reverse();
485       break;
486     }
487     if (aVertex.TShape() != theSpliceVertex.TShape())
488     {
489       aCurVertChanged = aVertex;
490       isCurVertChanged = true;
491     }
492   }
493   theSpliceVertex = isCurVertChanged ? aCurVertChanged : aVertExp.Current();
494
495   theBuilder.Add(theWire, anEdge);
496 }
497
498 void createFace(const TopoDS_Shape&                      theStartVertex,
499                 const std::list<TopoDS_Shape>::iterator& theStartEdge,
500                 const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
501                 const gp_Pln&                            thePlane,
502                       TopoDS_Face&                       theResFace)
503 {
504   TopoDS_Wire aResWire;
505   BRep_Builder aBuilder;
506   aBuilder.MakeWire(aResWire);
507
508   TopoDS_Shape aCurVertex = theStartVertex;
509   std::list<TopoDS_Shape>::const_iterator anEdgeIter = theStartEdge;
510   for ( ; anEdgeIter != theEndOfEdges; anEdgeIter++)
511   {
512     TopoDS_Edge anEdge = *((TopoDS_Edge*)(&(*anEdgeIter)));
513     if (!anEdge.IsNull())
514       addEdgeToWire(anEdge, aBuilder, aCurVertex, aResWire);
515   }
516
517   BRepBuilderAPI_MakeFace aFaceBuilder(thePlane, aResWire);
518   if (aFaceBuilder.Error() == BRepBuilderAPI_FaceDone)
519     theResFace = aFaceBuilder.Face();
520 }
521
522 void createWireList(const TopoDS_Shape&                      theStartVertex,
523                     const std::list<TopoDS_Shape>::iterator& theStartEdge,
524                     const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
525                     const std::set<Handle(TopoDS_TShape)>&   theEdgesInLoops,
526                           std::list<TopoDS_Wire>&            theResWires)
527 {
528   BRep_Builder aBuilder;
529   bool needNewWire = true;
530   TopoDS_Shape aCurVertex = theStartVertex;
531
532   std::list<TopoDS_Shape>::iterator anIter = theStartEdge;
533   while (anIter != theEndOfEdges)
534   {
535     while (anIter != theEndOfEdges && needNewWire && 
536            theEdgesInLoops.count(anIter->TShape()) != 0)
537     {
538       TopExp_Explorer aVertExp(*anIter, TopAbs_VERTEX);
539       for ( ; aVertExp.More(); aVertExp.Next())
540         if (aVertExp.Current().TShape() != aCurVertex.TShape())
541         {
542           aCurVertex = aVertExp.Current();
543           break;
544         }
545       anIter++;
546     }
547     if (anIter == theEndOfEdges)
548       break;
549
550     if (needNewWire)
551     { // The new wire should be created
552       TopoDS_Wire aWire;
553       aBuilder.MakeWire(aWire);
554       theResWires.push_back(aWire);
555       needNewWire = false;
556     }
557     else if (theEdgesInLoops.count(anIter->TShape()) != 0)
558     { // There was found the edge already used in loop.
559       // Current wire should be released and new one should started
560       needNewWire = true;
561       continue;
562     }
563
564     TopoDS_Edge anEdge = *((TopoDS_Edge*)(&(*anIter)));
565     addEdgeToWire(anEdge, aBuilder, aCurVertex, theResWires.back());
566     anIter++;
567   }
568 }
569
570
571 gp_Dir getOuterEdgeDirection(const TopoDS_Shape& theEdge,
572                              const TopoDS_Shape& theVertex)
573 {
574   const Handle(BRep_TVertex)& aVertex = (const Handle(BRep_TVertex)&)theVertex.TShape();
575   gp_Pnt aVertexPnt = aVertex->Pnt();
576
577   const Handle(BRep_TEdge)& anEdge = (const Handle(BRep_TEdge)&)theEdge.TShape();
578
579   // Convert the edge to the curve to calculate the tangency.
580   // There should be only one curve in the edge.
581   Handle(BRep_Curve3D) aEdCurve = 
582     Handle(BRep_Curve3D)::DownCast(anEdge->Curves().First());
583   double aFirst, aLast;
584   aEdCurve->Range(aFirst, aLast);
585   Handle(Geom_Curve) aCurve = aEdCurve->Curve3D();
586
587   gp_Pnt aPnt;
588   gp_Vec aTang;
589   aCurve->D1(aFirst + shift, aPnt, aTang);
590   aCurve->D0(aFirst, aPnt);
591   if (aVertexPnt.IsEqual(aPnt, tolerance))
592     return gp_Dir(aTang.Reversed());
593
594   aCurve->D1(aLast - shift, aPnt, aTang);
595   return gp_Dir(aTang);
596 }
597
598 void removeWasteEdges(
599                 std::list<TopoDS_Shape>::iterator&  theStartVertex,
600                 std::list<TopoDS_Shape>::iterator&  theStartEdge,
601           const std::list<TopoDS_Shape>::iterator&  theEndOfVertexes,
602           const std::list<TopoDS_Shape>::iterator&  theEndOfEdges,
603           BOPCol_IndexedDataMapOfShapeListOfShape&  theMapVE)
604 {
605   bool isVertStep = true;
606   while (theStartVertex != theEndOfVertexes && theStartEdge != theEndOfEdges)
607   {
608     BOPCol_ListOfShape& aBunch = theMapVE.ChangeFromKey(*theStartVertex);
609     BOPCol_ListOfShape::Iterator anApprEdge(aBunch);
610     for ( ; anApprEdge.More(); anApprEdge.Next())
611       if (anApprEdge.Value() == *theStartEdge)
612         break;
613     if (anApprEdge.More())
614       aBunch.Remove(anApprEdge);
615
616     if (isVertStep)
617       theStartVertex++;
618     else
619     {
620       theStartEdge++;
621       // check current vertex to be a branching point
622       // if so, it will be a new starting point to find a loop
623       if (aBunch.Size() > 1)
624         break;
625     }
626     isVertStep = !isVertStep;
627   }
628
629   // The map of vertex-edges may be changed
630   BOPCol_IndexedDataMapOfShapeListOfShape aMapVECopy;
631   BOPCol_IndexedDataMapOfShapeListOfShape::Iterator aMapIter(theMapVE);
632   for (int ind = 1; aMapIter.More(); aMapIter.Next(), ind++)
633     if (!aMapIter.Value().IsEmpty())
634       aMapVECopy.Add(theMapVE.FindKey(ind), aMapIter.Value());
635   theMapVE.Clear();
636   theMapVE.Exchange(aMapVECopy);
637 }
638