libsurf
Programmer's Documentation

Public Types | Public Member Functions | Protected Member Functions | Private Attributes | List of all members
DelaunayCore Class Reference

Detailed Description

Delaunay triangulations.

This class encapsulates some of the core algorithms needed for constructing and refining constrained Delaunay triangulations. DelaunayCore stores the triangulation connectivity data using a butterfly edge data structure kept in a hash table, but no vertex geometry; it is therefore restricted to purely topological operations.

Geometric functions such as an encroachment predicate or a triangle location function must therefore be supplied as function objects.

This class is meant to supersede DnMesh once it supports the same functionality.

See Also
DcEdge, DcFace, DcGeometry

#include <delaunaycore.h>

Collaboration diagram for DelaunayCore:
[legend]

Public Types

enum  InsertionFlag {
  NotInserted, EdgeSplit, FaceSplit, VertexPresent,
  ExtendedOutward
}
 
enum  StatusCode {
  StatusOk = 0, ConstraintIntersection, UnhandledMixedConstraint, CannotEnforceEdge,
  InconsistentTopology, InsertPointOutOfDomain, InsertCannotSplitEdge, InsertTriangledNotFound,
  ProtectedConstraintEncroached, NumberOfStatusCodes
}
 
typedef std::pair< DcEdge *, uint > EncPair
 
typedef std::vector< EncPair > FlipStack
 

Public Member Functions

 DelaunayCore (DcGeometry &geom, size_t reserveEdges=8192)
 empty triangulation
 
void enableExtension (bool flag)
 enable/disable mesh extension when vertex inserted beyond current mesh
 
uint addFace (uint a, uint b, uint c)
 add a new face
 
void addFaces (const Indices &tri)
 add multiple faces, will not check orientation (!)
 
void fixate ()
 compute edges from faces, update connectivity; call only in initialization
 
void eraseDetachedEdges ()
 erase edges which are not connected to any faces any more
 
void triangles (Indices &tri) const
 export triangles
 
void constrainedEdges (Indices &lns) const
 export constrained line segments
 
void vertexMap (uint nv, ConnectMap &v2f) const
 compute vertex-to-face connectivity
 
uint nAllFaces () const
 number of faces, inclusing invalid ones
 
uint nValidFaces () const
 number of valid faces
 
const DcFaceface (uint f) const
 access face f
 
int insertVertex (uint c, bool legalizeEdges=true)
 Vertex insertion. More...
 
uint insertConstraint (const Indices &c, int flags=DcEdge::Constrained, bool legalizeEdges=true)
 Constraint insertion. More...
 
void setEdgeFlags (int pattern, int flags)
 change internal treatment of special edges by setting flag bits
 
void unsetEdgeFlags (int pattern, int flags)
 change internal treatment of special edges by un-setting flag bits
 
void protectConstraints (bool flag)
 protect constrained edges by ball where insertions are forbidden
 
bool splitEdge (DcEdge *pab, uint c, bool legalizeEdges=true)
 split edge a-b, insert new vertex c in the middle
 
bool splitFace (uint f, uint x, bool legalizeEdges=true)
 split face f, insert vertex x
 
void addExternalVertex (DcEdge *pab, uint c, bool legalizeEdges=true)
 extend triangulation : construct triangle using pab and vertex c
 
const Indices & verticesOnConstraints () const
 access list of vertices inserted into constrained edges
 
Indices & verticesOnConstraints ()
 access list of vertices inserted into constrained edges
 
bool flipEdge (DcEdge *pe)
 flip edge, update connectivity
 
uint eatHole (uint f)
 eat triangles away, starting at face f, stop at constraints
 
uint eraseFacesTouching (const Indices &idx)
 erase all faces connected to any of the sorted vertices in idx
 
DcEdgefindEdge (uint s, uint t) const
 locate edge, return 0 if not found
 
DcEdgeconstructEdge (uint s, uint t)
 construct edge
 
bool diamond (DcEdge *pe, uint v[]) const
 collect vertex diamond for edge pe
 
bool isConvex (const uint v[]) const
 test whether a four-node neighborhood is convex
 
void constrainedVertices (std::vector< bool > &cvx, int edgeflag=DcEdge::Constrained) const
 mark all constrained vertices
 
void boundaryVertices (std::vector< bool > &bvx) const
 mark boundary vertices
 
void clear ()
 remove all contents, release memory
 
int lastStatusCode () const
 access status code (set when operation not successful)
 

Protected Member Functions

DcEdgeconstructEdge (const DcEdge &e)
 copy construct edge
 
void eraseEdge (DcEdge *pe)
 erase edge from set and cache
 
uint angOpposedVertex (uint t, uint topo) const
 given two adjacent faces, return vertex of topo not in t (Anglada 1997)
 
uint angOpposedFace (uint t, uint p) const
 return face adjacent to t which does not contain v
 
void triangulatePolygon (uint bs, uint bt, Indices::const_iterator vbeg, Indices::const_iterator vend)
 triangulate the polygon given by a sorted vertex set (vbeg,vend]
 
void eraseFace (uint k)
 invalidate face
 
void detachFace (uint k)
 detach reference to face k from the edges of k
 
void legalizeEdge (uint src, uint trg, uint v)
 legalize edge pe with respect to vertex v
 
void legalizeEdge (DcEdge *pe, uint v)
 legalize edge pe with respect to vertex v
 
DcEdgesearchCacheForFlip (uint s, uint t) const
 search face cache for edge which may be flipped to obtain (s,t)
 
bool extendCache ()
 extend face cache with immediate neighbor elements
 
DcEdgeimprintIntersectingEdge (uint csrc, uint ctrg)
 enforce the presence of edge (src,trg) by erasing and retriangulating
 
DcEdgeimprintOverlappingEdge (uint csrc, uint ctrg)
 enforce the presence of (src,trg) when it overlaps existing edges
 
void carveAndTriangulate (uint src, uint trg, const Indices &ifaces, Indices &vleft, Indices &vright)
 called by both edge imprinting routines
 
void legalizeStack (FlipStack &stack)
 process an edge flip stack
 
void startFaceCaching ()
 start caching new faces
 
void stopFaceCaching ()
 stop caching new faces
 

Private Attributes

DcGeometrygeo
 geometry evaluator
 
boost::pool edgePool
 pool allocator for edges
 
DcEdgeHash edges
 edges
 
DcFaceArray faces
 faces
 
Indices invalidFaces
 list of invalid faces
 
Indices faceCache
 keeps track of inserted faces
 
Indices vinConEdges
 vertices inserted on constrained edges
 
StatusCode status
 code set when error occurs
 
bool bProtectConstraints
 forbid insertion inside ball around constrained edges?
 
bool bCacheFaces
 flag indicating whether new faces should be cached
 
bool bInsertExtend
 is mesh extension by vertex insertion allowed?
 

Member Function Documentation

uint DelaunayCore::insertConstraint ( const Indices &  c,
int  flags = DcEdge::Constrained,
bool  legalizeEdges = true 
)

Constraint insertion.

Insert constrained edges along not-yet inserted vertices c. Returns c.size() if operation successfull; returns zero if all vertices could be inserted but an edge enforcement failed, or n < c.size() if vertex n could not be inserted at all (lying on non-splittable edge, outside the domain etc.).

int DelaunayCore::insertVertex ( uint  c,
bool  legalizeEdges = true 
)

Vertex insertion.

Attempts to insert vertex c, return flag (InsertionFlag) indicating whether edge or face was split or vertex was found present in mesh. Optionally enforce Delaunay property by flipping edges.


The documentation for this class was generated from the following files:
Generated on Mon Aug 15 2022 03:03:15 for libsurf by   doxygen 1.8.5