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