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