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

#include <dnmesh.h>

Collaboration diagram for DnMesh:

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