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