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