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