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