src/BRepMesh/BRepMesh_Delaun.hxx

   1 // Copyright (c) 2013-2014 OPEN CASCADE SAS
   2 //
   3 // This file is part of Open CASCADE Technology software library.
   4 //
   5 // This library is free software; you can redistribute it and/or modify it under
   6 // the terms of the GNU Lesser General Public License version 2.1 as published
   7 // by the Free Software Foundation, with special exception defined in the file
   8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
   9 // distribution for complete text of the license and disclaimer of any warranty.
  10 //
  11 // Alternatively, this file may be used under the terms of Open CASCADE
  12 // commercial license or contractual agreement.
  13
  14 #ifndef _BRepMesh_Delaun_HeaderFile
  15 #define _BRepMesh_Delaun_HeaderFile
  16
  17 #include <Standard.hxx>
  18 #include <Standard_DefineAlloc.hxx>
  19 #include <Standard_Macro.hxx>
  20
  21 #include <gp_XY.hxx>
  22 #include <gp_XYZ.hxx>
  23 #include <BRepMesh_CircleTool.hxx>
  24 #include <BRepMesh_Triangle.hxx>
  25 #include <BRepMesh_Edge.hxx>
  26 #include <BRepMesh.hxx>
  27 #include <BRepMesh_DataStructureOfDelaun.hxx>
  28 #include <BRepMesh_GeomTool.hxx>
  29 #include <TColStd_Array1OfInteger.hxx>
  30 #include <TColStd_SequenceOfInteger.hxx>
  31 #include <TColStd_MapOfInteger.hxx>
  32
  33 class Bnd_B2d;
  34 class Bnd_Box2d;
  35 class BRepMesh_Vertex;
  36
  37 //! Compute the Delaunay's triangulation with the algorithm of Watson.
  38 class BRepMesh_Delaun
  39 {
  40 public:
  41
  42   DEFINE_STANDARD_ALLOC
  43
  44   //! Creates the triangulation with an empty Mesh data structure.
  45   Standard_EXPORT BRepMesh_Delaun (BRepMesh::Array1OfVertexOfDelaun& theVertices);
  46
  47   //! Creates the triangulation with an existent Mesh data structure.
  48   Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
  49                                    BRepMesh::Array1OfVertexOfDelaun&             theVertices);
  50
  51   //! Creates the triangulation with an existant Mesh data structure.
  52   Standard_EXPORT BRepMesh_Delaun (const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
  53                                    BRepMesh::Array1OfInteger&                    theVertexIndices);
  54
  55   //! Initializes the triangulation with an array of vertices.
  56   Standard_EXPORT void Init (BRepMesh::Array1OfVertexOfDelaun& theVertices);
  57
  58   //! Removes a vertex from the triangulation.
  59   Standard_EXPORT void RemoveVertex (const BRepMesh_Vertex& theVertex);
  60
  61   //! Adds some vertices into the triangulation.
  62   Standard_EXPORT void AddVertices (BRepMesh::Array1OfVertexOfDelaun& theVertices);
  63
  64   //! Modify mesh to use the edge.
  65   //! @return True if done
  66   Standard_EXPORT Standard_Boolean UseEdge (const Standard_Integer theEdge);
  67
  68   //! Gives the Mesh data structure.
  69   inline const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
  70   {
  71     return myMeshData;
  72   }
  73
  74   //! Gives the list of frontier edges.
  75   inline BRepMesh::HMapOfInteger Frontier() const
  76   {
  77     return getEdgesByType (BRepMesh_Frontier);
  78   }
  79
  80   //! Gives the list of internal edges.
  81   inline BRepMesh::HMapOfInteger InternalEdges() const
  82   {
  83     return getEdgesByType (BRepMesh_Fixed);
  84   }
  85
  86   //! Gives the list of free edges used only one time
  87   inline BRepMesh::HMapOfInteger FreeEdges() const
  88   {
  89     return getEdgesByType (BRepMesh_Free);
  90   }
  91
  92   //! Gives vertex with the given index
  93   inline const BRepMesh_Vertex& GetVertex (const Standard_Integer theIndex) const
  94   {
  95     return myMeshData->GetNode (theIndex);
  96   }
  97
  98   //! Gives edge with the given index
  99   inline const BRepMesh_Edge& GetEdge (const Standard_Integer theIndex) const
 100   {
 101     return myMeshData->GetLink (theIndex);
 102   }
 103
 104   //! Gives triangle with the given index
 105   inline const BRepMesh_Triangle& GetTriangle (const Standard_Integer theIndex) const
 106   {
 107     return myMeshData->GetElement (theIndex);
 108   }
 109
 110   //! Returns tool used to build mesh consistent to Delaunay criteria.
 111   inline const BRepMesh_CircleTool& Circles() const
 112   {
 113     return myCircles;
 114   }
 115
 116   //! Test is the given triangle contains the given vertex.
 117   //! @param theSqTolerance square tolerance to check closeness to some edge
 118   //! @param theEdgeOn If it is != 0 the vertex lies onto the edge index
 119   //!        returned through this parameter.
 120   Standard_EXPORT Standard_Boolean Contains (const Standard_Integer theTriangleId,
 121                                              const BRepMesh_Vertex& theVertex,
 122                                              const Standard_Real    theSqTolerance,
 123                                              Standard_Integer&      theEdgeOn) const;
 124
 125 private:
 126
 127   enum ReplaceFlag
 128   {
 129     Replace,
 130     InsertAfter,
 131     InsertBefore
 132   };
 133
 134   typedef NCollection_DataMap<Standard_Integer, BRepMesh::MapOfInteger> DataMapOfMap;
 135
 136   //! Add boundig box for edge defined by start & end point to
 137   //! the given vector of bounding boxes for triangulation edges.
 138   void fillBndBox (BRepMesh::SequenceOfBndB2d&   theBoxes,
 139                    const BRepMesh_Vertex&        theV1,
 140                    const BRepMesh_Vertex&        theV2);
 141
 142   //! Gives the list of edges with type defined by the input parameter.
 143   //! If the given type is BRepMesh_Free returns list of edges
 144   //! that have number of connected elements less or equal 1.
 145   BRepMesh::HMapOfInteger getEdgesByType (const BRepMesh_DegreeOfFreedom theEdgeType) const;
 146
 147   //! Create super mesh and run triangulation procedure.
 148   void perform (Bnd_Box2d&                 theBndBox,
 149                 BRepMesh::Array1OfInteger& theVertexIndices);
 150
 151   //! Build the super mesh.
 152   void superMesh (const Bnd_Box2d& theBox);
 153
 154   //! Computes the triangulation and adds the vertices,
 155   //! edges and triangles to the Mesh data structure.
 156   void compute (BRepMesh::Array1OfInteger& theVertexIndices);
 157
 158   //! Adjust the mesh on the frontier.
 159   void frontierAdjust();
 160
 161   //! Find left polygon of the given edge and call meshPolygon.
 162   Standard_Boolean meshLeftPolygonOf(
 163     const Standard_Integer  theEdgeIndex,
 164     const Standard_Boolean  isForward,
 165     BRepMesh::HMapOfInteger theSkipped = NULL);
 166
 167   //! Find next link starting from the given node and has maximum
 168   //! angle respect the given reference link.
 169   //! Each time the next link is found other neighbor links at the pivot
 170   //! node are marked as leprous and will be excluded from consideration
 171   //! next time until a hanging end is occured.
 172   Standard_Integer findNextPolygonLink (const Standard_Integer&            theFirstNode,
 173                                         const Standard_Integer&            thePivotNode,
 174                                         const BRepMesh_Vertex&             thePivotVertex,
 175                                         const gp_Vec2d&                    theRefLinkDir,
 176                                         const BRepMesh::SequenceOfBndB2d&  theBoxes,
 177                                         const BRepMesh::SequenceOfInteger& thePolygon,
 178                                         const BRepMesh::HMapOfInteger      theSkipped,
 179                                         const Standard_Boolean&            isSkipLeprous,
 180                                         BRepMesh::MapOfInteger&            theLeprousLinks,
 181                                         BRepMesh::MapOfInteger&            theDeadLinks,
 182                                         Standard_Integer&                  theNextPivotNode,
 183                                         gp_Vec2d&                          theNextLinkDir,
 184                                         Bnd_B2d&                           theNextLinkBndBox);
 185
 186   //! Check is the given link intersects the polygon boundaries.
 187   //! Returns bounding box for the given link trough the theLinkBndBox parameter.
 188   Standard_Boolean checkIntersection (const BRepMesh_Edge&               theLink,
 189                                       const BRepMesh::SequenceOfInteger& thePolygon,
 190                                       const BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
 191                                       const Standard_Boolean             isConsiderEndPointTouch,
 192                                       const Standard_Boolean             isConsiderPointOnEdge,
 193                                       const Standard_Boolean             isSkipLastEdge,
 194                                       Bnd_B2d&                           theLinkBndBox) const;
 195
 196   //! Triangulatiion of a closed polygon described by the list
 197   //! of indexes of its edges in the structure.
 198   //! (negative index means reversed edge)
 199   void meshPolygon (BRepMesh::SequenceOfInteger& thePolygon,
 200                     BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
 201                     BRepMesh::HMapOfInteger      theSkipped = NULL);
 202
 203   //! Decomposes the given closed simple polygon (polygon without glued edges
 204   //! and loops) on two simpler ones by adding new link at the most thin part
 205   //! in respect to end point of the first link.
 206   //! In case if source polygon consists of three links, creates new triangle
 207   //! and clears source container.
 208   //! @param thePolygon source polygon to be decomposed (first part of decomposition).
 209   //! @param thePolyBoxes bounding boxes corresponded to source polygon's links.
 210   //! @param thePolygonCut product of decomposition of source polygon (second part of decomposition).
 211   //! @param thePolyBoxesCut bounding boxes corresponded to resulting polygon's links.
 212   void decomposeSimplePolygon (
 213     BRepMesh::SequenceOfInteger& thePolygon,
 214     BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
 215     BRepMesh::SequenceOfInteger& thePolygonCut,
 216     BRepMesh::SequenceOfBndB2d&  thePolyBoxesCut);
 217
 218   //! Triangulation of closed polygon containing only three edges.
 219   inline Standard_Boolean meshElementaryPolygon (const BRepMesh::SequenceOfInteger& thePolygon);
 220
 221   //! Creates the triangles beetween the given node and the given polyline.
 222   void createTriangles (const Standard_Integer         theVertexIndex,
 223                         BRepMesh::MapOfIntegerInteger& thePoly);
 224
 225   //! Add a triangle based on the given oriented edges into mesh
 226   inline void addTriangle (const Standard_Integer (&theEdgesId)[3],
 227                            const Standard_Boolean (&theEdgesOri)[3],
 228                            const Standard_Integer (&theNodesId)[3]);
 229
 230   //! Deletes the triangle with the given index and adds the free edges into the map.
 231   //! When an edge is suppressed more than one time it is destroyed.
 232   void deleteTriangle (const Standard_Integer         theIndex,
 233                        BRepMesh::MapOfIntegerInteger& theLoopEdges);
 234
 235   //! Returns start and end nodes of the given edge in respect to its orientation.
 236   void getOrientedNodes (const BRepMesh_Edge&   theEdge,
 237                          const Standard_Boolean isForward,
 238                          Standard_Integer*      theNodes) const;
 239
 240   //! Processes loop within the given polygon formed by range of its
 241   //! links specified by start and end link indices.
 242   void processLoop (const Standard_Integer             theLinkFrom,
 243                     const Standard_Integer             theLinkTo,
 244                     const BRepMesh::SequenceOfInteger& thePolygon,
 245                     const BRepMesh::SequenceOfBndB2d&  thePolyBoxes);
 246
 247   //! Creates new link based on the given nodes and updates the given polygon.
 248   Standard_Integer createAndReplacePolygonLink (const Standard_Integer       theNodes[],
 249                                                 const gp_Pnt2d               thePnts [],
 250                                                 const Standard_Integer       theRootIndex,
 251                                                 const ReplaceFlag            theReplaceFlag,
 252                                                 BRepMesh::SequenceOfInteger& thePolygon,
 253                                                 BRepMesh::SequenceOfBndB2d&  thePolyBoxes);
 254
 255   //! Creates the triangles on new nodes.
 256   void createTrianglesOnNewVertices (BRepMesh::Array1OfInteger& theVertexIndices);
 257
 258   //! Cleanup mesh from the free triangles.
 259   void cleanupMesh();
 260
 261   //! Goes through the neighbour triangles around the given node started
 262   //! from the given link, returns TRUE if some triangle has a bounding
 263   //! frontier edge or FALSE elsewhere.
 264   //! Stop link is used to prevent cycles.
 265   //! Previous element Id is used to identify next neighbor element.
 266   Standard_Boolean isBoundToFrontier (const Standard_Integer theRefNodeId,
 267                                       const Standard_Integer theRefLinkId,
 268                                       const Standard_Integer theStopLinkId,
 269                                       const Standard_Integer thePrevElementId);
 270
 271   //! Remove internal triangles from the given polygon.
 272   void cleanupPolygon (const BRepMesh::SequenceOfInteger& thePolygon,
 273                        const BRepMesh::SequenceOfBndB2d&  thePolyBoxes);
 274
 275   //! Checks is the given vertex lies inside the polygon.
 276   Standard_Boolean isVertexInsidePolygon (const Standard_Integer&          theVertexId,
 277                                           const BRepMesh::VectorOfInteger& thePolygonVertices) const;
 278
 279   //! Remove all triangles and edges that are placed inside the polygon or crossed it.
 280   void killTrianglesAroundVertex (const Standard_Integer             theZombieNodeId,
 281                                   const BRepMesh::VectorOfInteger&   thePolyVertices,
 282                                   const BRepMesh::MapOfInteger&      thePolyVerticesFindMap,
 283                                   const BRepMesh::SequenceOfInteger& thePolygon,
 284                                   const BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
 285                                   BRepMesh::MapOfInteger&            theSurvivedLinks,
 286                                   BRepMesh::MapOfIntegerInteger&     theLoopEdges);
 287
 288   //! Checks is the given link crosses the polygon boundary.
 289   //! If yes, kills its triangles and checks neighbor links on boundary intersection. Does nothing elsewhere.
 290   void killTrianglesOnIntersectingLinks (const Standard_Integer&             theLinkToCheckId,
 291                                          const BRepMesh_Edge&                theLinkToCheck,
 292                                          const Standard_Integer&             theEndPoint,
 293                                          const BRepMesh::SequenceOfInteger&  thePolygon,
 294                                          const BRepMesh::SequenceOfBndB2d&   thePolyBoxes,
 295                                          BRepMesh::MapOfInteger&             theSurvivedLinks,
 296                                          BRepMesh::MapOfIntegerInteger&      theLoopEdges);
 297
 298   //! Kill triangles bound to the given link.
 299   void killLinkTriangles (const Standard_Integer&        theLinkId,
 300                           BRepMesh::MapOfIntegerInteger& theLoopEdges);
 301
 302   //! Calculates distances between the given point and edges of triangle.
 303   Standard_Real calculateDist (const gp_XY            theVEdges[3],
 304                                const gp_XY            thePoints[3],
 305                                const BRepMesh_Vertex& theVertex,
 306                                Standard_Real          theDistance[3],
 307                                Standard_Real          theSqModulus[3],
 308                                Standard_Integer&      theEdgeOn) const;
 309
 310   //! Checks intersection between the two segments.
 311   BRepMesh_GeomTool::IntFlag intSegSeg(
 312     const BRepMesh_Edge&   theEdge1,
 313     const BRepMesh_Edge&   theEdge2,
 314     const Standard_Boolean isConsiderEndPointTouch,
 315     const Standard_Boolean isConsiderPointOnEdge,
 316     gp_Pnt2d&              theIntPnt) const;
 317
 318   //! Returns area of the loop of the given polygon defined by indices of its start and end links.
 319   Standard_Real polyArea (const BRepMesh::SequenceOfInteger& thePolygon,
 320                           const Standard_Integer             theStartIndex,
 321                           const Standard_Integer             theEndIndex) const;
 322
 323 private:
 324
 325   Handle(BRepMesh_DataStructureOfDelaun) myMeshData;
 326   BRepMesh_CircleTool                    myCircles;
 327   Standard_Integer                       mySupVert[3];
 328   BRepMesh_Triangle                      mySupTrian;
 329
 330 };
 331
 332 #endif