libsurf
Programmer's Documentation
libsurf
Programmer's Documentation
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.
#include <delaunaycore.h>
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 DcFace & | face (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 | |
| DcEdge * | findEdge (uint s, uint t) const |
| locate edge, return 0 if not found | |
| DcEdge * | constructEdge (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 | |
| DcEdge * | constructEdge (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 | |
| DcEdge * | searchCacheForFlip (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 | |
| DcEdge * | imprintIntersectingEdge (uint csrc, uint ctrg) |
| enforce the presence of edge (src,trg) by erasing and retriangulating | |
| DcEdge * | imprintOverlappingEdge (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 | |
| DcGeometry & | geo |
| 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? | |
| 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.
1.8.5