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