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