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