libsurf
Programmer's Documentation
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.
#include <dnmesh.h>
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 | |
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.