1 // File: GeomAlgoAPI_SketchBuilder.cpp
2 // Created: 02 Jun 2014
3 // Author: Artem ZHIDKOV
5 #include <GeomAlgoAPI_SketchBuilder.h>
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>
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>
32 #include <Precision.hxx>
35 #define DBL_MAX 1.7976931348623158e+308
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);
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);
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,
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);
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);
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);
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);
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)
99 if (theFeatures.empty())
102 // Create the list of edges with shared vertexes
103 BOPAlgo_Builder aBuilder;
104 BOPAlgo_PaveFiller aPF;
105 TopoDS_Shape aFeaturesCompound;
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>();
113 std::list< boost::shared_ptr<GeomAPI_Shape> >::const_iterator anIt = theFeatures.begin();
114 for (; anIt != theFeatures.end(); anIt++)
116 boost::shared_ptr<GeomAPI_Shape> aPreview(*anIt);
117 aBuilder.AddArgument(aPreview->impl<TopoDS_Edge>());
119 aPF.SetArguments(aBuilder.Arguments());
121 int aErr = aPF.ErrorStatus();
123 aBuilder.PerformWithFiller(aPF);
124 aErr = aBuilder.ErrorStatus();
126 aFeaturesCompound = aBuilder.Shape();
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
134 gp_Dir aDirX = theDirX->impl<gp_Dir>();
135 gp_Dir aDirY = theDirY->impl<gp_Dir>();
136 gp_Dir aNorm = theNorm->impl<gp_Dir>();
138 gp_Pln aPlane(theOrigin->impl<gp_Pnt>(), aNorm);
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;
146 // Search the start vertex
147 TopoDS_Shape aStartVertex = findStartVertex(aMapVE, aDirX, aDirY);
148 aProcVertexes.push_back(aStartVertex);
150 TopoDS_Shape aCurVertex = aStartVertex;
151 gp_Dir aCurDir = aDirY.Reversed();
152 gp_Dir aCurNorm = aNorm.Reversed();
154 // Go through the edges and find loops
155 TopoDS_Shape aNextVertex;
156 TopoDS_Shape aBindingEdge;
158 while (aMapVE.Extent() > 0)
160 findNextVertex(aCurVertex, aMapVE, aCurDir, aCurNorm, aNextVertex, aBindingEdge, aNextDir);
163 // Try to find next vertex in the list of already processed
164 std::list<TopoDS_Shape>::iterator aVertIter = aProcVertexes.begin();
165 std::list<TopoDS_Shape>::iterator anEdgeIter = aProcEdges.begin();
166 for ( ; aVertIter != aProcVertexes.end(); aVertIter++)
168 if (aVertIter->TShape() == aNextVertex.TShape())
170 if (anEdgeIter != aProcEdges.end())
174 aProcVertexes.push_back(aNextVertex);
175 aProcEdges.push_back(aBindingEdge);
177 // The loop was found
178 if (aVertIter != aProcVertexes.end())
180 // If the binding edge is a full circle, then the list may be empty before addition. Need to update edge iterator
181 if (aProcEdges.size() == 1)
182 anEdgeIter = aProcEdges.begin();
184 if (aVertIter != aProcVertexes.begin())
186 // Check the orientation of the loop
187 gp_Dir aCN = getOuterEdgeDirection(*anEdgeIter, *aVertIter);
188 gp_Dir aCP = getOuterEdgeDirection(aProcEdges.back(), *aVertIter);
191 if (aCN.DotCross(aCP, aNorm) < -tolerance)
193 // The found loop has wrong orientation and may contain sub-loops.
194 // Need to check it onle again with another initial direction.
195 aCurVertex = *aVertIter;
197 aProcVertexes.pop_back();
198 aProcEdges.pop_back();
199 } while (aCurVertex != aProcVertexes.back());
200 aCurDir = getOuterEdgeDirection(aProcEdges.back(), aCurVertex);
201 aCurNorm = aNorm.Reversed();
206 // When the orientation is correct or the edges looped through
207 // the first element, create new face and remove unnecessary edges.
209 createFace(*aVertIter, anEdgeIter, aProcEdges.end(), aPlane, aPatch);
210 if (!aPatch.IsNull())
212 boost::shared_ptr<GeomAPI_Shape> aFace(new GeomAPI_Shape);
213 aFace->setImpl(new TopoDS_Shape(aPatch));
214 theResultFaces.push_back(aFace);
216 // push the edges used in the loop to the map
217 std::list<TopoDS_Shape>::iterator anIter;
218 for (anIter = anEdgeIter; anIter != aProcEdges.end(); anIter++)
219 anEdgesInLoops.insert(anIter->TShape());
220 // remove unnecessary edges
221 std::list<TopoDS_Shape>::iterator aCopyVLoop = aVertIter;
222 std::list<TopoDS_Shape>::iterator aCopyELoop = anEdgeIter;
223 removeWasteEdges(aVertIter, anEdgeIter, aProcVertexes.end(), aProcEdges.end(), aMapVE);
225 // revert the list of remaining edges
226 std::list<TopoDS_Shape> aRemainVertexes;
227 for ( ; aVertIter != aProcVertexes.end(); aVertIter++)
228 aRemainVertexes.push_front(*aVertIter);
229 std::list<TopoDS_Shape> aRemainEdges;
230 for ( ; anEdgeIter != aProcEdges.end(); anEdgeIter++)
231 aRemainEdges.push_front(*anEdgeIter);
232 // remove edges and vertexes used in the loop and add remaining ones
233 aProcVertexes.erase(aCopyVLoop, aProcVertexes.end());
234 aProcVertexes.insert(aProcVertexes.end(), aRemainVertexes.begin(), aRemainVertexes.end());
235 aProcEdges.erase(aCopyELoop, aProcEdges.end());
236 aProcEdges.insert(aProcEdges.end(), aRemainEdges.begin(), aRemainEdges.end());
238 // Recalculate current vertex and current direction
239 if (!aProcVertexes.empty())
241 aNextVertex = aProcVertexes.back();
242 if (!aProcEdges.empty())
243 aNextDir = getOuterEdgeDirection(aProcEdges.back(), aNextVertex);
244 else aNextDir = aDirY;
248 // if next vertex connected only to alone edge, this is a part of wire (not a closed loop),
249 // we need to go back through the list of already checked edges to find a branching vertex
250 if (!aMapVE.IsEmpty() && aMapVE.Contains(aNextVertex) &&
251 aMapVE.FindFromKey(aNextVertex).Size() == 1)
253 std::list<TopoDS_Shape>::reverse_iterator aVRIter = aProcVertexes.rbegin();
254 std::list<TopoDS_Shape>::reverse_iterator aERIter = aProcEdges.rbegin();
255 if (aVRIter != aProcVertexes.rend())
257 if (aERIter != aProcEdges.rend())
260 for ( ; aERIter != aProcEdges.rend(); aERIter++, aVRIter++)
261 if (aMapVE.FindFromKey(*aVRIter).Size() > 2)
263 if (aERIter != aProcEdges.rend() ||
264 (aVRIter != aProcVertexes.rend() && aMapVE.FindFromKey(*aVRIter).Size() == 1))
265 { // the branching vertex was found or current list of edges is a wire without branches
266 std::list<TopoDS_Shape>::iterator aEIter;
267 TopoDS_Shape aCurEdge;
268 if (aERIter != aProcEdges.rend())
270 aEIter = aERIter.base();
274 aEIter = aProcEdges.begin();
275 std::list<TopoDS_Wire> aTail;
276 createWireList(*aVRIter, aEIter, aProcEdges.end(), anEdgesInLoops, aTail);
277 std::list<TopoDS_Wire>::const_iterator aTailIter = aTail.begin();
278 for ( ; aTailIter != aTail.end(); aTailIter++)
279 if (!aTailIter->IsNull())
281 boost::shared_ptr<GeomAPI_Shape> aWire(new GeomAPI_Shape);
282 aWire->setImpl(new TopoDS_Shape(*aTailIter));
283 theResultWires.push_back(aWire);
285 std::list<TopoDS_Shape>::iterator aVIter = aVRIter.base();
286 std::list<TopoDS_Shape>::iterator aEItCopy = aEIter;
287 removeWasteEdges(--aVIter, aEItCopy, aProcVertexes.end(), aProcEdges.end(), aMapVE);
289 aProcEdges.erase(aEIter, aProcEdges.end());
290 aVIter = aVRIter.base();
291 aProcVertexes.erase(aVIter, aProcVertexes.end());
293 if (!aProcVertexes.empty())
295 aNextVertex = aProcVertexes.back();
296 if (!aCurEdge.IsNull())
297 aNextDir = getOuterEdgeDirection(aCurEdge, aNextVertex);
301 { // there is no branching vertex in the list of proceeded,
302 // so we should revert the list and go the opposite way
303 aProcVertexes.reverse();
304 aProcEdges.reverse();
305 aNextVertex = aProcVertexes.back();
306 aNextDir = aProcEdges.empty() ? aDirY :
307 getOuterEdgeDirection(aProcEdges.back(), aNextVertex);
311 // When all edges of current component of connectivity are processed,
312 // we should repeat procedure for finding initial vertex in the remaining
313 if (!aMapVE.IsEmpty() && !aMapVE.Contains(aNextVertex))
315 aProcVertexes.clear();
318 TopoDS_Shape aStartEdge;
319 aStartVertex = findStartVertex(aMapVE, aDirX, aDirY);
320 aProcVertexes.push_back(aStartVertex);
321 aNextVertex = aStartVertex;
322 aNextDir = aDirY.Reversed();
323 aCurNorm = aNorm.Reversed();
326 aCurVertex = aNextVertex;
330 if (theResultFaces.size() > 1)
331 fixIntersections(theResultFaces);
334 void GeomAlgoAPI_SketchBuilder::fixIntersections(
335 std::list< boost::shared_ptr<GeomAPI_Shape> >& theFaces)
337 BRepClass_FaceClassifier aClassifier;
339 std::list< boost::shared_ptr<GeomAPI_Shape> >::iterator anIter1 = theFaces.begin();
340 std::list< boost::shared_ptr<GeomAPI_Shape> >::iterator anIter2;
341 for ( ; anIter1 != theFaces.end(); anIter1++)
344 for (++anIter2; anIter2 != theFaces.end(); anIter2++)
346 const TopoDS_Face& aF1 = (*anIter1)->impl<TopoDS_Face>();
347 TopExp_Explorer aVert2((*anIter2)->impl<TopoDS_Shape>(), TopAbs_VERTEX);
348 for ( ; aVert2.More(); aVert2.Next())
350 Handle(BRep_TVertex) aV = Handle(BRep_TVertex)::DownCast(aVert2.Current().TShape());
351 aClassifier.Perform(aF1, aV->Pnt(), tolerance);
352 if (aClassifier.State() != TopAbs_IN)
356 { // second shape is not inside first, change the shapes order and repeat comparision
357 const TopoDS_Face& aF2 = (*anIter2)->impl<TopoDS_Face>();
358 TopExp_Explorer aVert1((*anIter1)->impl<TopoDS_Shape>(), TopAbs_VERTEX);
359 for ( ; aVert1.More(); aVert1.Next())
361 Handle(BRep_TVertex) aV = Handle(BRep_TVertex)::DownCast(aVert1.Current().TShape());
362 aClassifier.Perform(aF2, aV->Pnt(), tolerance);
363 if (aClassifier.State() != TopAbs_IN)
367 { // first shape should be cut from the second
368 BRepAlgoAPI_Cut aCut((*anIter2)->impl<TopoDS_Shape>(),
369 (*anIter1)->impl<TopoDS_Shape>());
370 (*anIter2)->setImpl(new TopoDS_Shape(aCut.Shape()));
374 { // second shape should be cut from the first
375 BRepAlgoAPI_Cut aCut((*anIter1)->impl<TopoDS_Shape>(),
376 (*anIter2)->impl<TopoDS_Shape>());
377 (*anIter1)->setImpl(new TopoDS_Shape(aCut.Shape()));
384 // =================== Auxiliary functions ====================================
385 const TopoDS_Shape& findStartVertex(
386 const BOPCol_IndexedDataMapOfShapeListOfShape& theMapVE,
387 const gp_Dir& theDirX, const gp_Dir& theDirY)
389 int aStartVertexInd = 1;
390 double aMaxX = -DBL_MAX;
391 double aMaxY = -DBL_MAX;
392 int aNbVert = theMapVE.Extent();
393 for (int i = 1; i <= aNbVert; i++)
395 const TopoDS_Vertex& aV = (const TopoDS_Vertex&)theMapVE.FindKey(i);
396 const Handle(BRep_TVertex)& aVert = (const Handle(BRep_TVertex)&)aV.TShape();
397 const gp_Pnt& aVertPnt = aVert->Pnt();
399 double aX = aVertPnt.XYZ().Dot(theDirX.XYZ());
400 double aY = aVertPnt.XYZ().Dot(theDirY.XYZ());
401 if ((aX > aMaxX || (fabs(aX - aMaxX) < tolerance && aY > aMaxY)) &&
402 theMapVE.FindFromIndex(i).Extent() > 1)
409 return theMapVE.FindKey(aStartVertexInd);
413 const TopoDS_Shape& theStartVertex,
414 const BOPCol_IndexedDataMapOfShapeListOfShape& theVertexEdgeMap,
415 const gp_Dir& theStartDir,
416 const gp_Dir& theNormal,
417 TopoDS_Shape& theNextVertex,
418 TopoDS_Shape& theNextEdge,
421 const BOPCol_ListOfShape& anEdgesList = theVertexEdgeMap.FindFromKey(theStartVertex);
422 BOPCol_ListOfShape::Iterator aEdIter(anEdgesList);
423 double aBestEdgeProj = DBL_MAX;
424 for ( ; aEdIter.More(); aEdIter.Next())
426 gp_Dir aTang = getOuterEdgeDirection(aEdIter.Value(), theStartVertex);
429 // The projection is normalized in segment (-1, 1),
430 // where (-1, 0] corresponds to the angles (pi/2, 0] between theStartDir and aTang
431 // and [0, 1) corresponds to the angles [0, -pi/2)
432 double aProj = (aTang.Dot(theStartDir) - 1.0) * 0.5;
433 if (fabs(fabs(aProj) - 1) < tolerance)
435 if (theStartDir.DotCross(aTang, theNormal) < tolerance)
438 if (aProj < aBestEdgeProj)
440 aBestEdgeProj = aProj;
441 theNextEdge = aEdIter.Value();
442 TopExp_Explorer aVertExp(theNextEdge, TopAbs_VERTEX);
443 for ( ; aVertExp.More(); aVertExp.Next())
444 if (aVertExp.Current().TShape() != theStartVertex.TShape())
446 theNextVertex = aVertExp.Current();
447 theNextDir = getOuterEdgeDirection(aEdIter.Value(), theNextVertex);
450 if (!aVertExp.More())
451 { // This edge is a full circle
452 TopoDS_Vertex aV1, aV2;
453 TopExp::Vertices(*(const TopoDS_Edge*)(&theNextEdge), aV1, aV2);
454 if (aV1.Orientation() == theStartVertex.Orientation())
458 theNextDir = getOuterEdgeDirection(aEdIter.Value(), theNextVertex);
464 static void addEdgeToWire(const TopoDS_Edge& theEdge,
465 const BRep_Builder& theBuilder,
466 TopoDS_Shape& theSpliceVertex,
467 TopoDS_Wire& theWire)
469 TopoDS_Edge anEdge = theEdge;
470 bool isCurVertChanged = false;
471 TopoDS_Shape aCurVertChanged;
473 TopExp_Explorer aVertExp(theEdge, TopAbs_VERTEX);
474 for ( ; aVertExp.More(); aVertExp.Next())
476 const TopoDS_Shape& aVertex = aVertExp.Current();
477 if (aVertex.TShape() == theSpliceVertex.TShape() &&
478 aVertex.Orientation() != theEdge.Orientation())
479 { // Current vertex is the last for the edge, so its orientation is wrong, need to revert the edge
483 if (aVertex.TShape() != theSpliceVertex.TShape())
485 aCurVertChanged = aVertex;
486 isCurVertChanged = true;
489 theSpliceVertex = isCurVertChanged ? aCurVertChanged : aVertExp.Current();
491 theBuilder.Add(theWire, anEdge);
494 void createFace(const TopoDS_Shape& theStartVertex,
495 const std::list<TopoDS_Shape>::iterator& theStartEdge,
496 const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
497 const gp_Pln& thePlane,
498 TopoDS_Face& theResFace)
500 TopoDS_Wire aResWire;
501 BRep_Builder aBuilder;
502 aBuilder.MakeWire(aResWire);
504 TopoDS_Shape aCurVertex = theStartVertex;
505 std::list<TopoDS_Shape>::const_iterator anEdgeIter = theStartEdge;
506 for ( ; anEdgeIter != theEndOfEdges; anEdgeIter++)
508 TopoDS_Edge anEdge = *((TopoDS_Edge*)(&(*anEdgeIter)));
509 if (!anEdge.IsNull())
510 addEdgeToWire(anEdge, aBuilder, aCurVertex, aResWire);
513 BRepBuilderAPI_MakeFace aFaceBuilder(thePlane, aResWire);
514 if (aFaceBuilder.Error() == BRepBuilderAPI_FaceDone)
515 theResFace = aFaceBuilder.Face();
518 void createWireList(const TopoDS_Shape& theStartVertex,
519 const std::list<TopoDS_Shape>::iterator& theStartEdge,
520 const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
521 const std::set<Handle(TopoDS_TShape)>& theEdgesInLoops,
522 std::list<TopoDS_Wire>& theResWires)
524 BRep_Builder aBuilder;
525 bool needNewWire = true;
526 TopoDS_Shape aCurVertex = theStartVertex;
528 std::list<TopoDS_Shape>::iterator anIter = theStartEdge;
529 while (anIter != theEndOfEdges)
531 while (anIter != theEndOfEdges && needNewWire &&
532 theEdgesInLoops.count(anIter->TShape()) != 0)
534 TopExp_Explorer aVertExp(*anIter, TopAbs_VERTEX);
535 for ( ; aVertExp.More(); aVertExp.Next())
536 if (aVertExp.Current().TShape() != aCurVertex.TShape())
538 aCurVertex = aVertExp.Current();
543 if (anIter == theEndOfEdges)
547 { // The new wire should be created
549 aBuilder.MakeWire(aWire);
550 theResWires.push_back(aWire);
553 else if (theEdgesInLoops.count(anIter->TShape()) != 0)
554 { // There was found the edge already used in loop.
555 // Current wire should be released and new one should started
560 TopoDS_Edge anEdge = *((TopoDS_Edge*)(&(*anIter)));
561 addEdgeToWire(anEdge, aBuilder, aCurVertex, theResWires.back());
567 gp_Dir getOuterEdgeDirection(const TopoDS_Shape& theEdge,
568 const TopoDS_Shape& theVertex)
570 const Handle(BRep_TVertex)& aVertex = (const Handle(BRep_TVertex)&)theVertex.TShape();
571 gp_Pnt aVertexPnt = aVertex->Pnt();
573 const Handle(BRep_TEdge)& anEdge = (const Handle(BRep_TEdge)&)theEdge.TShape();
575 // Convert the edge to the curve to calculate the tangency.
576 // There should be only one curve in the edge.
577 Handle(BRep_Curve3D) aEdCurve =
578 Handle(BRep_Curve3D)::DownCast(anEdge->Curves().First());
579 double aFirst, aLast;
580 aEdCurve->Range(aFirst, aLast);
581 Handle(Geom_Curve) aCurve = aEdCurve->Curve3D();
585 aCurve->D1(aFirst + shift, aPnt, aTang);
586 aCurve->D0(aFirst, aPnt);
587 if (aVertexPnt.IsEqual(aPnt, tolerance))
588 return gp_Dir(aTang.Reversed());
590 aCurve->D1(aLast - shift, aPnt, aTang);
591 return gp_Dir(aTang);
594 void removeWasteEdges(
595 std::list<TopoDS_Shape>::iterator& theStartVertex,
596 std::list<TopoDS_Shape>::iterator& theStartEdge,
597 const std::list<TopoDS_Shape>::iterator& theEndOfVertexes,
598 const std::list<TopoDS_Shape>::iterator& theEndOfEdges,
599 BOPCol_IndexedDataMapOfShapeListOfShape& theMapVE)
601 bool isVertStep = true;
602 while (theStartVertex != theEndOfVertexes && theStartEdge != theEndOfEdges)
604 BOPCol_ListOfShape& aBunch = theMapVE.ChangeFromKey(*theStartVertex);
605 BOPCol_ListOfShape::Iterator anApprEdge(aBunch);
606 for ( ; anApprEdge.More(); anApprEdge.Next())
607 if (anApprEdge.Value() == *theStartEdge)
609 if (anApprEdge.More())
610 aBunch.Remove(anApprEdge);
617 // check current vertex to be a branching point
618 // if so, it will be a new starting point to find a loop
619 if (aBunch.Size() > 1)
622 isVertStep = !isVertStep;
625 // The map of vertex-edges may be changed
626 BOPCol_IndexedDataMapOfShapeListOfShape aMapVECopy;
627 BOPCol_IndexedDataMapOfShapeListOfShape::Iterator aMapIter(theMapVE);
628 for (int ind = 1; aMapIter.More(); aMapIter.Next(), ind++)
629 if (!aMapIter.Value().IsEmpty())
630 aMapVECopy.Add(theMapVE.FindKey(ind), aMapIter.Value());
632 theMapVE.Exchange(aMapVECopy);