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