src/BRepMesh/BRepMesh_Delaun.hxx

   1 // Copyright (c) 2013 OPEN CASCADE SAS
   2 //
   3 // The content of this file is subject to the Open CASCADE Technology Public
   4 // License Version 6.5 (the "License"). You may not use the content of this file
   5 // except in compliance with the License. Please obtain a copy of the License
   6 // at http://www.opencascade.org and read it completely before using this file.
   7 //
   8 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
   9 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  10 //
  11 // The Original Code and all software distributed under the License is
  12 // distributed on an "AS IS" basis, without warranty of any kind, and the
  13 // Initial Developer hereby disclaims all such warranties, including without
  14 // limitation, any warranties of merchantability, fitness for a particular
  15 // purpose or non-infringement. Please see the License for the specific terms
  16 // and conditions governing the rights and limitations under the License.
  17
  18 #ifndef _BRepMesh_Delaun_HeaderFile
  19 #define _BRepMesh_Delaun_HeaderFile
  20
  21 #include <Standard.hxx>
  22 #include <Standard_DefineAlloc.hxx>
  23 #include <Standard_Macro.hxx>
  24
  25 #include <BRepMesh_CircleTool.hxx>
  26 #include <BRepMesh_Triangle.hxx>
  27 #include <BRepMesh_Edge.hxx>
  28 #include <BRepMesh_MapOfInteger.hxx>
  29 #include <BRepMesh_MapOfIntegerInteger.hxx>
  30 #include <BRepMesh_DataStructureOfDelaun.hxx>
  31 #include <NCollection_Sequence.hxx>
  32
  33 class Bnd_B2d;
  34 class Bnd_Box2d;
  35 class BRepMesh_Array1OfVertexOfDelaun;
  36 class BRepMesh_Vertex;
  37 class TColStd_Array1OfInteger;
  38 class TColStd_SequenceOfInteger;
  39 class TColStd_MapOfInteger;
  40
  41 //! Compute the Delaunay's triangulation with the <br>
  42 //! algorithm of Watson. <br>
  43 class BRepMesh_Delaun  {
  44 public:
  45
  46   DEFINE_STANDARD_ALLOC
  47
  48   //! Creates the triangulation with an empty Mesh <br>
  49   //! data structure. <br>
  50   Standard_EXPORT BRepMesh_Delaun( BRepMesh_Array1OfVertexOfDelaun& theVertices,
  51                                    const Standard_Boolean           isPositive = Standard_True );
  52
  53   //! Creates the triangulation with and existent <br>
  54   //! Mesh data structure. <br>
  55   Standard_EXPORT BRepMesh_Delaun( const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
  56                                    BRepMesh_Array1OfVertexOfDelaun&              theVertices,
  57                                    const Standard_Boolean                        isPositive = Standard_True );
  58
  59   //! Creates the triangulation with and existant <br>
  60   //! Mesh data structure. <br>
  61   Standard_EXPORT BRepMesh_Delaun( const Handle(BRepMesh_DataStructureOfDelaun)& theOldMesh,
  62                                    TColStd_Array1OfInteger&                      theVertexIndices,
  63                                    const Standard_Boolean                        isPositive = Standard_True );
  64
  65   //! Initializes the triangulation with an array of <br>
  66   //! vertices. <br>
  67   Standard_EXPORT void Init( BRepMesh_Array1OfVertexOfDelaun& theVertices );
  68
  69   //! Removes a vertex from the triangulation. <br>
  70   Standard_EXPORT void RemoveVertex( const BRepMesh_Vertex& theVertex );
  71
  72   //! Adds some vertices into the triangulation. <br>
  73   Standard_EXPORT void AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices );
  74
  75   //! Modify mesh to use the edge. Return True if done. <br>
  76   Standard_EXPORT Standard_Boolean UseEdge( const Standard_Integer theEdge );
  77
  78   //! Gives the Mesh data structure. <br>
  79   Standard_EXPORT const Handle(BRepMesh_DataStructureOfDelaun)& Result() const
  80   {
  81     return myMeshData;
  82   }
  83
  84   //! Gives the list of frontier edges <br>
  85   inline Handle(BRepMesh_MapOfInteger) Frontier() const
  86   {
  87     return getEdgesByType( BRepMesh_Frontier );
  88   }
  89
  90   //! Gives the list of internal edges <br>
  91   inline Handle(BRepMesh_MapOfInteger) InternalEdges() const
  92   {
  93     return getEdgesByType( BRepMesh_Fixed );
  94   }
  95
  96   //! Gives the list of free edges used only one time <br>
  97   inline Handle(BRepMesh_MapOfInteger) FreeEdges() const
  98   {
  99     return getEdgesByType( BRepMesh_Free );
 100   }
 101
 102   //! Gives vertex with the given index <br>
 103   inline const BRepMesh_Vertex& GetVertex( const Standard_Integer theIndex ) const
 104   {
 105     return myMeshData->GetNode( theIndex );
 106   }
 107
 108   //! Gives edge with the given index <br>
 109   inline const BRepMesh_Edge& GetEdge( const Standard_Integer theIndex ) const
 110   {
 111     return myMeshData->GetLink( theIndex );
 112   }
 113
 114   //! Gives triangle with the given index <br>
 115   inline const BRepMesh_Triangle& GetTriangle( const Standard_Integer theIndex ) const
 116   {
 117     return myMeshData->GetElement( theIndex );
 118   }
 119
 120   //! Test is the given triangle contains the given vertex. <br>
 121   //! If <theEdgeOn> != 0 the vertex lies onto the edge index <br>
 122   //! returned through this parameter. <br>
 123   Standard_EXPORT Standard_Boolean Contains( const Standard_Integer theTriangleId,
 124                                              const BRepMesh_Vertex& theVertex,
 125                                              Standard_Integer&      theEdgeOn ) const;
 126
 127 private:
 128
 129   enum IntFlag
 130   {
 131     NoIntersection,
 132     Cross,
 133     EndPointTouch,
 134     PointOnEdge,
 135     Glued,
 136     Same
 137   };
 138
 139   enum ReplaceFlag
 140   {
 141     Replace,
 142     InsertAfter,
 143     InsertBefore
 144   };
 145
 146   typedef NCollection_DataMap<Standard_Integer, NCollection_Map<Standard_Integer> > DataMapOfMap;
 147
 148   typedef NCollection_Handle<NCollection_Map<Standard_Integer> > HandleOfMapOfInteger;
 149
 150   //! Add boundig box for edge defined by start & end point to <br>
 151   //! the given vector of bounding boxes for triangulation edges  <br>
 152   void fillBndBox( NCollection_Sequence<Bnd_B2d>&   theBoxes,
 153                    const BRepMesh_Vertex&           theV1,
 154                    const BRepMesh_Vertex&           theV2 );
 155
 156   //! Gives the list of edges with type defined by the input parameter. <br>
 157   //! If the given type is BRepMesh_Free returns list of edges <br>
 158   //! that have number of connected elements less or equal 1  <br>
 159   Handle(BRepMesh_MapOfInteger) getEdgesByType( const BRepMesh_DegreeOfFreedom theEdgeType ) const;
 160
 161   //! Create super mesh and run triangulation procedure <br>
 162   void perform( Bnd_Box2d&               theBndBox,
 163                 TColStd_Array1OfInteger& theVertexIndices );
 164
 165   //! Build the super mesh. <br>
 166   void superMesh( const Bnd_Box2d& theBox );
 167
 168   //! Computes the triangulation and adds the vertices, <br>
 169   //! edges and triangles to the Mesh data structure. <br>
 170   void compute( TColStd_Array1OfInteger& theVertexIndices );
 171
 172   //! Adjust the mesh on the frontier. <br>
 173   void frontierAdjust();
 174
 175   //! Find left polygon of the given edge and call meshPolygon. <br>
 176   Standard_Boolean meshLeftPolygonOf( const Standard_Integer theEdgeIndex,
 177                                       const Standard_Boolean isForward,
 178                                       HandleOfMapOfInteger   theSkipped = NULL );
 179
 180   //! Find next link starting from the given node and has maximum <br>
 181   //! angle respect the given reference link. <br>
 182   //! Each time the next link is found other neighbor links at the pivot <br>
 183   //! node are marked as leprous and will be excluded from consideration <br>
 184   //! next time until a hanging end is occured. <br>
 185   Standard_Integer findNextPolygonLink( const Standard_Integer&              theFirstNode,
 186                                         const Standard_Integer&              thePivotNode,
 187                                         const BRepMesh_Vertex&               thePivotVertex,
 188                                         const gp_Vec2d&                      theRefLinkDir,
 189                                         const NCollection_Sequence<Bnd_B2d>& theBoxes,
 190                                         const TColStd_SequenceOfInteger&     thePolygon,
 191                                         const HandleOfMapOfInteger           theSkipped,
 192                                         const Standard_Boolean&              isSkipLeprous,
 193                                         NCollection_Map<Standard_Integer>&   theLeprousLinks,
 194                                         NCollection_Map<Standard_Integer>&   theDeadLinks,
 195                                         Standard_Integer&                    theNextPivotNode,
 196                                         gp_Vec2d&                            theNextLinkDir,
 197                                         Bnd_B2d&                             theNextLinkBndBox );
 198
 199   //! Check is the given link intersects the polygon boundaries. <br>
 200   //! Returns bounding box for the given link trough the <theLinkBndBox> parameter. <br>
 201   Standard_Boolean checkIntersection( const BRepMesh_Edge&                 theLink,
 202                                       const TColStd_SequenceOfInteger&     thePolygon,
 203                                       const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
 204                                       const Standard_Boolean               isConsiderEndPointTouch,
 205                                       const Standard_Boolean               isConsiderPointOnEdge,
 206                                       const Standard_Boolean               isSkipLastEdge,
 207                                       Bnd_B2d&                             theLinkBndBox ) const;
 208
 209   //! Triangulatiion of a closed polygon described by the list <br>
 210   //! of indexes of its edges in the structure. <br>
 211   //! (negative index means reversed edge) <br>
 212   void meshPolygon( TColStd_SequenceOfInteger&     thePolygon,
 213                     NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
 214                     HandleOfMapOfInteger           theSkipped = NULL );
 215
 216   //! Triangulatiion of a closed simple polygon (polygon without glued edges and loops) <br>
 217   //! described by the list of indexes of its edges in the structure. <br>
 218   //! (negative index means reversed edge) <br>
 219   void meshSimplePolygon( TColStd_SequenceOfInteger&     thePolygon,
 220                           NCollection_Sequence<Bnd_B2d>& thePolyBoxes );
 221
 222   //! Triangulation of closed polygon containing only three edges.
 223   inline Standard_Boolean meshElementaryPolygon( const TColStd_SequenceOfInteger& thePolygon );
 224
 225   //! Creates the triangles beetween the given node <br>
 226   //! and the given polyline. <br>
 227   void createTriangles( const Standard_Integer        theVertexIndex,
 228                         BRepMesh_MapOfIntegerInteger& thePoly );
 229
 230   //! Add a triangle based on the given oriented edges into mesh <br>
 231   inline void addTriangle( const Standard_Integer (&theEdgesId)[3],
 232                            const Standard_Boolean (&theEdgesOri)[3],
 233                            const Standard_Integer (&theNodesId)[3] );
 234
 235   //! Deletes the triangle with the given index and <br>
 236   //! adds the free edges into the map. <br>
 237   //! When an edge is suppressed more than one time <br>
 238   //! it is destroyed. <br>
 239   void deleteTriangle( const Standard_Integer        theIndex,
 240                        BRepMesh_MapOfIntegerInteger& theLoopEdges );
 241
 242   //! Returns start and end nodes of the given edge <br>
 243   //! in respect to its orientation. <br>
 244   void getOrientedNodes(const BRepMesh_Edge&   theEdge,
 245                         const Standard_Boolean isForward,
 246                         Standard_Integer       *theNodes) const;
 247
 248   //! Processes loop within the given polygon formed by range of its <br>
 249   //! links specified by start and end link indices. <br>
 250   void processLoop(const Standard_Integer               theLinkFrom,
 251                    const Standard_Integer               theLinkTo,
 252                    const TColStd_SequenceOfInteger&     thePolygon,
 253                    const NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
 254
 255   //! Creates new link based on the given nodes and updates the given polygon.
 256   Standard_Integer createAndReplacePolygonLink(const Standard_Integer         theNodes[],
 257                                                const gp_Pnt2d                 thePnts [],
 258                                                const Standard_Integer         theRootIndex,
 259                                                const ReplaceFlag              theReplaceFlag,
 260                                                TColStd_SequenceOfInteger&     thePolygon,
 261                                                NCollection_Sequence<Bnd_B2d>& thePolyBoxes);
 262
 263   //! Creates the triangles on new nodes <br>
 264   void createTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndices );
 265
 266   //! Cleanup mesh from the free triangles <br>
 267   void cleanupMesh();
 268
 269   //! Goes through the neighbour triangles around the given node started
 270   //! from the given link, returns TRUE if some triangle has a bounding
 271   //! frontier edge or FALSE elsewhere.
 272   //! Stop link is used to prevent cycles.
 273   //! Previous element Id is used to identify next neighbor element.
 274   Standard_Boolean isBoundToFrontier(const Standard_Integer theRefNodeId,
 275                                      const Standard_Integer theRefLinkId,
 276                                      const Standard_Integer theStopLinkId,
 277                                      const Standard_Integer thePrevElementId);
 278
 279   //! Remove internal triangles from the given polygon <br>
 280   void cleanupPolygon( const TColStd_SequenceOfInteger&     thePolygon,
 281                        const NCollection_Sequence<Bnd_B2d>& thePolyBoxes );
 282
 283   //! Checks is the given vertex lies inside the polygon <br>
 284   Standard_Boolean isVertexInsidePolygon( const Standard_Integer&                     theVertexId,
 285                                           const NCollection_Vector<Standard_Integer>& thePolygonVertices ) const;
 286
 287   //! Remove all triangles and edges that are placed <br>
 288   //! inside the polygon or crossed it. <br>
 289   void killTrianglesAroundVertex( const Standard_Integer                      theZombieNodeId,
 290                                   const NCollection_Vector<Standard_Integer>& thePolyVertices,
 291                                   const NCollection_Map<Standard_Integer>&    thePolyVerticesFindMap,
 292                                   const TColStd_SequenceOfInteger&            thePolygon,
 293                                   const NCollection_Sequence<Bnd_B2d>&        thePolyBoxes,
 294                                   NCollection_Map<Standard_Integer>&          theSurvivedLinks,
 295                                   BRepMesh_MapOfIntegerInteger&               theLoopEdges );
 296
 297   //! Checks is the given link crosses the polygon boundary. <br>
 298   //! If yes, kills its triangles and checks neighbor links on <br>
 299   //! boundary intersection. Does nothing elsewhere. <br>
 300   void killTrianglesOnIntersectingLinks( const Standard_Integer&              theLinkToCheckId,
 301                                          const BRepMesh_Edge&                 theLinkToCheck,
 302                                          const Standard_Integer&              theEndPoint,
 303                                          const TColStd_SequenceOfInteger&     thePolygon,
 304                                          const NCollection_Sequence<Bnd_B2d>& thePolyBoxes,
 305                                          NCollection_Map<Standard_Integer>&   theSurvivedLinks,
 306                                          BRepMesh_MapOfIntegerInteger&        theLoopEdges );
 307
 308   //! Kill triangles bound to the given link. <br>
 309   void killLinkTriangles( const Standard_Integer&       theLinkId,
 310                           BRepMesh_MapOfIntegerInteger& theLoopEdges );
 311
 312   //! Calculates distances between the given point <br>
 313   //! and edges of triangle. <br>
 314   Standard_Real calculateDist( const gp_XY            theVEdges[3],
 315                                const gp_XY            thePoints[3],
 316                                const Standard_Integer theEdgesId[3],
 317                                const BRepMesh_Vertex& theVertex,
 318                                Standard_Real          theDistance[3],
 319                                Standard_Real          theSqModulus[3],
 320                                Standard_Integer&      theEdgeOn ) const;
 321
 322   //! Classifies the point in case of coincidence of two vectors. <br>
 323   //! Returns zero value if point is out of segment and non zero  <br>
 324   //! value if point is between the first and the second point of segment. <br>
 325   //! thePoint1       - the start point of a segment (base point) <br>
 326   //! thePoint2       - the end point of a segment <br>
 327   //! thePointToCheck - the point to classify <br>
 328   Standard_Integer classifyPoint( const gp_XY& thePoint1,
 329                                   const gp_XY& thePoint2,
 330                                   const gp_XY& thePointToCheck ) const;
 331
 332   //! Checks intersection between the two segments. <br>
 333   IntFlag intSegSeg( const BRepMesh_Edge&   theEdge1,
 334                      const BRepMesh_Edge&   theEdge2,
 335                      const Standard_Boolean isConsiderEndPointTouch,
 336                      const Standard_Boolean isConsiderPointOnEdge,
 337                      gp_Pnt2d&              theIntPnt) const;
 338
 339   //! Returns area of the loop of the given polygon defined by <br>
 340   //! indices of its start and end links. <br>
 341   Standard_Real polyArea( const TColStd_SequenceOfInteger& thePolygon,
 342                           const Standard_Integer           theStartIndex,
 343                           const Standard_Integer           theEndIndex ) const;
 344 private:
 345
 346   Handle(BRepMesh_DataStructureOfDelaun)          myMeshData;
 347   Standard_Boolean                                myIsPositiveOrientation;
 348   BRepMesh_CircleTool                             myCircles;
 349   Standard_Integer                                mySupVert[3];
 350   BRepMesh_Triangle                               mySupTrian;
 351 };
 352
 353 #endif