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