libsurf
Programmer's Documentation

Public Member Functions | Private Member Functions | Private Attributes | List of all members
DnMesh Class Reference

Detailed Description

Mesh generation engine.

DnMesh implements generation of unstructured surface meshes using Delaunay triangulation. Both plane Delaunay triangulation and Chew's variant for curved surfaces are supported. For three-dimensional surfaces, Chew's algorithm yields vastly superior meshes, but puts stringent requirements on the initial state if used for refinement.

Note:* This is the legacy surface mesh generator still used in sumo but to be replaced by DelaunayCore in the future.

See Also
DelaunayCore

#include <dnmesh.h>

Collaboration diagram for DnMesh:
[legend]

Public Member Functions

 DnMesh (SurfacePtr s, DnType t)
 create generator for surface s
 
Vct3 eval (Real u, Real v) const
 evaluate the surface
 
void init (uint nu, uint nv)
 initialize with an equidistant mesh spaced nu x nv
 
void init (const Vector &up, const Vector &vp)
 initialize with structured mesh
 
void init (const PointGrid< 2 > &pg)
 initialize with arbitrary point grid
 
void init (const PointGrid< 2 > &pg, Real maxstretch, uint kins=9)
 initialize point grid and cascade to remove stretched triangles
 
bool initBoundary (const PointList< 2 > &pts)
 start with (optionally constrained) boundary, return true on success
 
bool initPolygon (const PointList< 2 > &pts)
 fill a polygonal boundary for initialization
 
uint importMesh (const PointList< 2 > &pts, const Indices &qtri)
 import a triangular mesh
 
uint exportMesh (PointList< 2 > &pts, Indices &qtri) const
 export a triangular mesh (2D)
 
uint exportMesh (PointList< 2 > &pp, PointList< 3 > &vtx, PointList< 3 > &nrm, Indices &qtri) const
 export a triangular mesh (3D)
 
uint nvertices () const
 current number of vertices
 
uint nedges () const
 current number of edges
 
uint nfaces () const
 current number of triangles
 
uint nAllTriangles () const
 number of triangles, including invalid ones (!)
 
const Vct2 & parpos (uint i) const
 access parametric vertex position
 
const Vct3 & position (uint i) const
 access 3D space position of vertex i
 
const Vct3 & normal (uint i) const
 access surface normal of vertex i
 
const uint * triangleVertices (uint k) const
 access vertex indices of triangle k, may return 0 for invalid triangle
 
void switchMode (DnType t)
 change triangulation mode (hope that you know what you are doing)
 
uint elimNeedles (Real maxstretch, Real maxphi)
 does not work yet
 
Indices addConstraint (const PointList< 2 > &pts, bool allowSplit=false)
 Add constrained segments, return indices of constrained vertices. More...
 
void markKinks (Real dphi)
 constrain an edge if it separates components with a normal jump between them
 
void disableBoundarySplit ()
 disable splitting of boundary edges
 
void enableBoundarySplit ()
 enable splitting of boundary edges
 
uint insertVertex (const Vct2 &p, bool &onBoundary)
 insert vertex, sustain Delaunay property
 
uint insertBoundaryVertex (const Vct2 &p, Real ptol=gmepsilon)
 insert a point into a boundary edge
 
uint addHole (const Vct2 &p)
 place a hole at p and remove affected triangles
 
void destretch (uint nmax, Real maxstretch)
 remove stretched triangles
 
uint refine (const DnRefineCriterion &c)
 refine according to criteria (queue-based procedure)
 
void iterativeRefine (const DnRefineCriterion &c)
 refine according to criteria (plain loop)
 
void refineAround (const Indices &vlist, const DnRefineCriterion &c)
 split triangles near vertices in vlist
 
void smooth (uint niter=1, Real omega=1.0)
 plain laplacian smoothing (all unconstrained vertices)
 
void smooth (const Indices &idx, uint niter, Real omega=1.0)
 smooth using vertex subset
 
void smoothStretched (Real maxstretch)
 smooth only vertices in stretched triangles
 
void smoothStretched (Real maxstretch, std::vector< BndRect > &bxs)
 smooth stretched inside boxes only
 
XmlElement toXml () const
 write 3D mesh to xml representation (MeshFields)
 
XmlElement pToXml () const
 parameter space mesh to xml
 
void fixate ()
 recompute all connectivity
 
void setAbortFlag (bool flag)
 set interruption flag to stop refinement
 
void cleanup (Real xyzt, Real uvt)
 merge vertices closer than threshold
 
const std::string & lastError () const
 access error message
 

Private Member Functions

uint addEdge (uint a, uint b)
 add edge to triangulation, return index (no connectivity updates)
 
uint addTriangle (uint a, uint b, uint c)
 add triangle to triangulation, return index (no connectivity updates)
 
void addQuad (uint a, uint b, uint c, uint d)
 try to add two triangles for the quad a-d, intelligently
 
void fixDirection (DnTriangle &t)
 fix direction of triangle normal
 
uint findEdgeSorted (uint a, uint b) const
 find edge index, requires sorted edge array
 
uint findEdgeTopo (uint a, uint b) const
 find edge index by topological search
 
bool canFlip (uint i) const
 check if edge may be flipped
 
bool isKink (uint i) const
 check if edge is on kink
 
bool canSplit (uint i) const
 check if edge may be split
 
void forbidFlip (uint i)
 register edge i as non-flippable
 
void forbidSplit (uint i)
 register edge i as non-flippable
 
int locateTriangle (const Vct2 &p, uint vnear, uint &ti) const
 locate triangle which contains position vertex p (2D algorithm)
 
int locateTriangle (uint ni, uint vnear, uint &ti) const
 locate triangle which contains vertex ni (flexible algorithm)
 
void killTriangle (uint ti)
 delete triangle, detach from vertices
 
void killEdge (uint ei)
 delete edge (no connectivity updates)
 
void splitTriangle (uint ti, uint ni)
 split one triangle into three
 
bool splitEdge (uint ei, uint ni)
 split two triangles into four
 
bool refineEdge (uint ei, Real minlen)
 insert new vertex at midpoint if possible
 
uint findDivider (uint ei, Real minlen)
 find point to insert when refining edge ei
 
bool refineTriangle (uint tix, Real mxs, Real minlen)
 determine if and how to refine triangle t
 
void smoothVertex (uint v)
 move v to its barycenter, if legal
 
bool flipEdge (uint ei)
 flip edge
 
bool legalizeEdge (uint ei, uint v)
 recusively flip edges to establish Delauny property
 
uint enforceEdge (uint a, uint b)
 make sure that edge a,b occurs in triangulation
 
uint findNeighborhood (uint ei, uint v[4], uint nbe[4], uint nbf[2]) const
 compute edge neighborhood
 
void collectNbEdges (uint i, Indices &edg, bool allEdges=false) const
 collect all edges which run into vertex i
 
uint recursiveErase (uint ti)
 kill triangles starting from ti until constrained edges are encountered
 
uint carveHole (uint ti)
 collect triangles to erase
 
uint insertSegment (uint a, uint b)
 insert edge which cannot be inserted using edge flips alone
 
Real orientation (uint a, uint b, uint c) const
 suitable orientation test sepending on mesh type
 
Real pOrientation (uint a, uint b, uint c) const
 orientation test in 2D
 
Real sOrientation (uint a, uint b, uint c) const
 orientation test in 3D
 
int isInside (uint ti, uint ni) const
 test if vertex ni is inside triangle ti
 
int sIsInside (uint ti, uint ni) const
 test if vertex ni is inside triangle ti
 
int sIsOnBoundaryEdge (uint ti, uint ni) const
 special case of vertex on wrapped boundary
 
int pIsInside (uint ti, uint ni) const
 test if vertex ni is inside triangle ti
 
bool intersects (uint ei, uint a, uint b) const
 test if edge ei intersects line a-b
 
bool sIntersects (uint ei, uint a, uint b) const
 test if a and b lie on different side of ei (intersection)
 
bool triangulatePolygon (uint ei, const Indices &v)
 triangulate the polygon above the edge ei
 
void classify (uint ti, Real maxstretch, DnTriangleShape &shp) const
 compute edge lengths, return triangle area
 
bool collapseEdge (uint eshort)
 try to merge source and target of eshort
 
void fuseVertices (uint vdrop, uint vkeep)
 change vdrop to vkeep in all faces connected to vdrop
 
bool destroyHat (uint ti, uint elong)
 refine a triangle with one long side and a large angle
 
bool isConvexSet (uint v[4]) const
 check if the neighborhood v is convex
 
void centerVertex (uint i, Real omega=1.0)
 displace a vertex to the barycenter of its ring-1 neighborhood
 
void constructPolygon (uint v, Indices &ip) const
 collect the surrounding polygon for an interior point
 
bool ptInPolygon (const Vct2 &pt, const Indices &ip) const
 check if pt is inside polygon determined by ip
 
bool vertexCanMove (uint v, const Vct2 &pt) const
 check if vertex v can be moved to pt without tangling the mesh
 
uint checkConnectivity (uint v, Indices &nbv) const
 debugging : check local connectivity for consistency (aborts on error)
 
void clear ()
 delete everything
 
uint nntriangles ()
 prepare list of changed triangles
 
uint nnedges ()
 prepare list of changed edges
 

Private Attributes

DnType type
 Delaunay algorithm used.
 
SurfacePtr psf
 underlying continuous surface
 
DnVertexArray vertices
 vertex array
 
DnEdgeArray edges
 edge array
 
DnTriangleArray triangles
 triangle array
 
RSearchTree btree
 point search tree
 
Indices iDeadEdges
 dead edges and triangles
 
Indices iDeadTriangles
 
Indices iNoFlip
 edges which may not be flipped or split
 
Indices iKinkEdge
 
Indices iNoSplit
 
Indices newEdges
 newly created edges or modified triangles
 
Indices newTriangles
 
bool uwrap
 flag which indicates if geometry is wrapped in u-direction
 
bool depinsert
 
bool nowrefining
 
bool bAbort
 refinement is interrupted if this flag is set to true
 
std::string errmsg
 error message
 

Member Function Documentation

Indices DnMesh::addConstraint ( const PointList< 2 > &  pts,
bool  allowSplit = false 
)

Add constrained segments, return indices of constrained vertices.

This method returns an empty set if insertion failed because of colliding constraints.


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