Programmer's Documentation

dnmesh.h (r6227/r5385)
2 /* Copyright (C) 2015 David Eller <>
3  *
4  * Commercial License Usage
5  * Licensees holding valid commercial licenses may use this file in accordance
6  * with the terms contained in their respective non-exclusive license agreement.
7  * For further information contact .
8  *
9  * GNU General Public License Usage
10  * Alternatively, this file may be used under the terms of the GNU General
11  * Public License version 3.0 as published by the Free Software Foundation and
12  * appearing in the file gpl.txt included in the packaging of this file.
13  */
15 #ifndef SURF_DNMESH_H
16 #define SURF_DNMESH_H
18 #include <vector>
19 #include <set>
20 #include <genua/boxsearchtree.h>
21 #include <genua/rsearchtree.h>
22 #include <genua/xmlelement.h>
23 #include <surf/surface.h>
24 #include "dnvertex.h"
25 #include "dnedge.h"
26 #include "dntriangle.h"
28 typedef enum {DnPlane, DnSpatial} DnType;
30 struct DnTriangleShape;
31 class DnRefineCriterion;
47 class DnMesh
48 {
49  public:
52  DnMesh(SurfacePtr s, DnType t);
55  Vct3 eval(Real u, Real v) const {return psf->eval(u,v);}
58  void init(uint nu, uint nv);
61  void init(const Vector & up, const Vector & vp);
64  void init(const PointGrid<2> & pg);
67  void init(const PointGrid<2> & pg, Real maxstretch, uint kins=9);
70  bool initBoundary(const PointList<2> & pts);
73  bool initPolygon(const PointList<2> & pts);
76  uint importMesh(const PointList<2> & pts, const Indices & qtri);
79  uint exportMesh(PointList<2> & pts, Indices & qtri) const;
82  uint exportMesh(PointList<2> & pp, PointList<3> & vtx,
83  PointList<3> & nrm, Indices & qtri) const;
86  uint nvertices() const {return vertices.size();}
89  uint nedges() const {return edges.size()-iDeadEdges.size();}
92  uint nfaces() const {return triangles.size()-iDeadTriangles.size();}
95  uint nAllTriangles() const {return triangles.size();}
98  const Vct2 & parpos(uint i) const {
99  assert(i < vertices.size());
100  return vertices[i].parpos();
101  }
104  const Vct3 & position(uint i) const {
105  assert(i < vertices.size());
106  return vertices[i].eval();
107  }
110  const Vct3 & normal(uint i) const {
111  assert(i < vertices.size());
112  return vertices[i].normal();
113  }
116  const uint *triangleVertices(uint k) const {
117  assert(k < triangles.size());
118  const DnTriangle & t( triangles[k] );
119  return t.isValid() ? t.vertices() : 0;
120  }
123  void switchMode(DnType t) {type = t;}
126  uint elimNeedles(Real maxstretch, Real maxphi);
131  Indices addConstraint(const PointList<2> & pts, bool allowSplit = false);
134  void markKinks(Real dphi);
137  void disableBoundarySplit();
140  void enableBoundarySplit();
143  uint insertVertex(const Vct2 & p, bool & onBoundary);
146  uint insertBoundaryVertex(const Vct2 & p, Real ptol=gmepsilon);
149  uint addHole(const Vct2 & p);
152  void destretch(uint nmax, Real maxstretch);
155  uint refine(const DnRefineCriterion & c);
158  void iterativeRefine(const DnRefineCriterion & c);
161  void refineAround(const Indices & vlist, const DnRefineCriterion & c);
164  void smooth(uint niter = 1, Real omega = 1.0);
167  void smooth(const Indices & idx, uint niter, Real omega = 1.0);
170  void smoothStretched(Real maxstretch);
173  void smoothStretched(Real maxstretch, std::vector<BndRect> & bxs);
176  XmlElement toXml() const;
179  XmlElement pToXml() const;
182  void fixate();
185  void setAbortFlag(bool flag) {bAbort = flag;}
188  void cleanup(Real xyzt, Real uvt);
191  const std::string & lastError() const {return errmsg;}
193  private:
196  uint addEdge(uint a, uint b);
199  uint addTriangle(uint a, uint b, uint c);
202  void addQuad(uint a, uint b, uint c, uint d);
206  if (type == DnSpatial)
208  else
210  }
213  uint findEdgeSorted(uint a, uint b) const {
214  DnEdge etest(a,b);
215  DnEdgeArray::const_iterator pos;
216  pos = std::lower_bound(edges.begin(), edges.end(), etest);
217  if (pos != edges.end() and *pos == etest)
218  return std::distance(edges.begin(), pos);
219  else
220  return NotFound;
221  }
224  uint findEdgeTopo(uint a, uint b) const;
227  bool canFlip(uint i) const {
228  return (not binary_search(iNoFlip.begin(), iNoFlip.end(), i));
229  }
232  bool isKink(uint i) const {
233  return binary_search(iKinkEdge.begin(), iKinkEdge.end(), i);
234  }
237  bool canSplit(uint i) const {
238  return (not binary_search(iNoSplit.begin(), iNoSplit.end(), i));
239  }
242  void forbidFlip(uint i) {
243  Indices::iterator pos;
244  pos = std::lower_bound(iNoFlip.begin(), iNoFlip.end(), i);
245  if (pos == iNoFlip.end() or *pos != i)
246  iNoFlip.insert(pos, i);
247  }
250  void forbidSplit(uint i) {
251  Indices::iterator pos;
252  pos = std::lower_bound(iNoSplit.begin(), iNoSplit.end(), i);
253  if (pos == iNoSplit.end() or *pos != i)
254  iNoSplit.insert(pos, i);
255  }
258  int locateTriangle(const Vct2 & p, uint vnear, uint & ti) const;
261  int locateTriangle(uint ni, uint vnear, uint & ti) const;
264  void killTriangle(uint ti);
267  void killEdge(uint ei);
270  void splitTriangle(uint ti, uint ni);
273  bool splitEdge(uint ei, uint ni);
276  bool refineEdge(uint ei, Real minlen);
279  uint findDivider(uint ei, Real minlen);
282  bool refineTriangle(uint tix, Real mxs, Real minlen);
285  void smoothVertex(uint v);
288  bool flipEdge(uint ei);
291  bool legalizeEdge(uint ei, uint v);
294  uint enforceEdge(uint a, uint b);
297  uint findNeighborhood(uint ei, uint v[4], uint nbe[4], uint nbf[2]) const;
300  void collectNbEdges(uint i, Indices & edg, bool allEdges=false) const;
303  uint recursiveErase(uint ti);
306  uint carveHole(uint ti);
309  uint insertSegment(uint a, uint b);
312  Real orientation(uint a, uint b, uint c) const {
313  if (type == DnSpatial)
314  return sOrientation(a, b, c);
315  else
316  return pOrientation(a, b, c);
317  }
320  Real pOrientation(uint a, uint b, uint c) const;
323  Real sOrientation(uint a, uint b, uint c) const;
326  int isInside(uint ti, uint ni) const {
327  if (type == DnSpatial)
328  return sIsInside(ti, ni);
329  else
330  return pIsInside(ti, ni);
331  }
334  int sIsInside(uint ti, uint ni) const;
337  int sIsOnBoundaryEdge(uint ti, uint ni) const;
340  int pIsInside(uint ti, uint ni) const;
343  bool intersects(uint ei, uint a, uint b) const {
344  if (type == DnSpatial)
345  return sIntersects(ei, a, b);
346  else
347  return edges[ei].pIntersects(vertices, a, b);
348  }
351  bool sIntersects(uint ei, uint a, uint b) const;
354  bool triangulatePolygon(uint ei, const Indices & v);
357  void classify(uint ti, Real maxstretch, DnTriangleShape & shp) const;
360  bool collapseEdge(uint eshort);
363  void fuseVertices(uint vdrop, uint vkeep);
366  bool destroyHat(uint ti, uint elong);
369  bool isConvexSet(uint v[4]) const;
372  void centerVertex(uint i, Real omega = 1.0);
375  void constructPolygon(uint v, Indices & ip) const;
378  bool ptInPolygon(const Vct2 & pt, const Indices & ip) const;
381  bool vertexCanMove(uint v, const Vct2 & pt) const;
384  uint checkConnectivity(uint v, Indices & nbv) const;
387  void clear();
390  uint nntriangles() {
391  sort_unique(newTriangles);
392  if ((not newTriangles.empty()) and newTriangles.back() == NotFound)
393  newTriangles.pop_back();
394  return newTriangles.size();
395  }
398  uint nnedges() {
399  sort_unique(newEdges);
400  if ((not newEdges.empty()) and newEdges.back() == NotFound)
401  newEdges.pop_back();
402  return newEdges.size();
403  }
405  private:
408  DnType type;
411  SurfacePtr psf;
414  DnVertexArray vertices;
417  DnEdgeArray edges;
420  DnTriangleArray triangles;
426  Indices iDeadEdges, iDeadTriangles;
429  Indices iNoFlip, iKinkEdge, iNoSplit;
432  Indices newEdges, newTriangles;
435  bool uwrap, depinsert, nowrefining;
438  bool bAbort;
441  std::string errmsg;
442 };
444 #endif
void fixate()
recompute all connectivity
Definition: dnmesh.cpp:2382
DnType type
Delaunay algorithm used.
Definition: dnmesh.h:408
uint nntriangles()
prepare list of changed triangles
Definition: dnmesh.h:390
void enableBoundarySplit()
enable splitting of boundary edges
Definition: dnmesh.cpp:210
uint findDivider(uint ei, Real minlen)
find point to insert when refining edge ei
Definition: dnmesh.cpp:2768
bool triangulatePolygon(uint ei, const Indices &v)
triangulate the polygon above the edge ei
Definition: dnmesh.cpp:2228
SurfacePtr psf
underlying continuous surface
Definition: dnmesh.h:411
RSearchTree btree
point search tree
Definition: dnmesh.h:423
void constructPolygon(uint v, Indices &ip) const
collect the surrounding polygon for an interior point
Definition: dnmesh.cpp:3666
Mesh generation engine.
Definition: dnmesh.h:47
void cleanup(Real xyzt, Real uvt)
merge vertices closer than threshold
Definition: dnmesh.cpp:274
int sIsInside(uint ti, uint ni) const
test if vertex ni is inside triangle ti
Definition: dnmesh.cpp:2098
void disableBoundarySplit()
disable splitting of boundary edges
Definition: dnmesh.cpp:198
bool splitEdge(uint ei, uint ni)
split two triangles into four
Definition: dnmesh.cpp:1261
uint findEdgeTopo(uint a, uint b) const
find edge index by topological search
Definition: dnmesh.cpp:2476
void pFixDirection(const DnVertexArray &vtx)
make sure that the normal direction is correct (u,v space)
Definition: dntriangle.h:419
uint insertBoundaryVertex(const Vct2 &p, Real ptol=gmepsilon)
insert a point into a boundary edge
Definition: dnmesh.cpp:864
uint enforceEdge(uint a, uint b)
make sure that edge a,b occurs in triangulation
Definition: dnmesh.cpp:1580
void iterativeRefine(const DnRefineCriterion &c)
refine according to criteria (plain loop)
Definition: dnmesh.cpp:2544
uint nvertices() const
current number of vertices
Definition: dnmesh.h:86
bool canFlip(uint i) const
check if edge may be flipped
Definition: dnmesh.h:227
const Vct2 & parpos(uint i) const
access parametric vertex position
Definition: dnmesh.h:98
bool bAbort
refinement is interrupted if this flag is set to true
Definition: dnmesh.h:438
void init(uint nu, uint nv)
initialize with an equidistant mesh spaced nu x nv
Definition: dnmesh.cpp:90
uint insertSegment(uint a, uint b)
insert edge which cannot be inserted using edge flips alone
Definition: dnmesh.cpp:1779
DnMesh(SurfacePtr s, DnType t)
create generator for surface s
Definition: dnmesh.cpp:60
const uint * triangleVertices(uint k) const
access vertex indices of triangle k, may return 0 for invalid triangle
Definition: dnmesh.h:116
uint nfaces() const
current number of triangles
Definition: dnmesh.h:92
int locateTriangle(const Vct2 &p, uint vnear, uint &ti) const
locate triangle which contains position vertex p (2D algorithm)
Definition: dnmesh.cpp:1095
uint refine(const DnRefineCriterion &c)
refine according to criteria (queue-based procedure)
Definition: dnmesh.cpp:2652
Edge in a Delaunay triangulation.
Definition: dnedge.h:28
uint importMesh(const PointList< 2 > &pts, const Indices &qtri)
import a triangular mesh
Definition: dnmesh.cpp:427
uint findNeighborhood(uint ei, uint v[4], uint nbe[4], uint nbf[2]) const
compute edge neighborhood
Definition: dnmesh.cpp:1517
void clear()
delete everything
Definition: dnmesh.cpp:2500
bool legalizeEdge(uint ei, uint v)
recusively flip edges to establish Delauny property
Definition: dnmesh.cpp:1430
uint addTriangle(uint a, uint b, uint c)
add triangle to triangulation, return index (no connectivity updates)
Definition: dnmesh.cpp:525
void forbidFlip(uint i)
register edge i as non-flippable
Definition: dnmesh.h:242
void destretch(uint nmax, Real maxstretch)
remove stretched triangles
Definition: dnmesh.cpp:3312
void smoothStretched(Real maxstretch)
smooth only vertices in stretched triangles
Definition: dnmesh.cpp:3430
Real pOrientation(uint a, uint b, uint c) const
orientation test in 2D
Definition: dnmesh.cpp:2004
uint nAllTriangles() const
number of triangles, including invalid ones (!)
Definition: dnmesh.h:95
bool refineTriangle(uint tix, Real mxs, Real minlen)
determine if and how to refine triangle t
Definition: dnmesh.cpp:2605
uint elimNeedles(Real maxstretch, Real maxphi)
does not work yet
Definition: dnmesh.cpp:575
uint nedges() const
current number of edges
Definition: dnmesh.h:89
Triangle in 3D Delaunay triangulation.
Definition: dntriangle.h:31
uint recursiveErase(uint ti)
kill triangles starting from ti until constrained edges are encountered
Definition: dnmesh.cpp:1674
bool uwrap
flag which indicates if geometry is wrapped in u-direction
Definition: dnmesh.h:435
bool intersects(uint ei, uint a, uint b) const
test if edge ei intersects line a-b
Definition: dnmesh.h:343
uint addHole(const Vct2 &p)
place a hole at p and remove affected triangles
Definition: dnmesh.cpp:1059
void killTriangle(uint ti)
delete triangle, detach from vertices
Definition: dnmesh.cpp:549
Real orientation(uint a, uint b, uint c) const
suitable orientation test sepending on mesh type
Definition: dnmesh.h:312
Indices addConstraint(const PointList< 2 > &pts, bool allowSplit=false)
Add constrained segments, return indices of constrained vertices.
Definition: dnmesh.cpp:653
void addQuad(uint a, uint b, uint c, uint d)
try to add two triangles for the quad a-d, intelligently
Definition: dnmesh.cpp:226
bool initPolygon(const PointList< 2 > &pts)
fill a polygonal boundary for initialization
Definition: dnmesh.cpp:170
DnVertexArray vertices
vertex array
Definition: dnmesh.h:414
void killEdge(uint ei)
delete edge (no connectivity updates)
Definition: dnmesh.cpp:566
uint carveHole(uint ti)
collect triangles to erase
Definition: dnmesh.cpp:1716
void splitTriangle(uint ti, uint ni)
split one triangle into three
Definition: dnmesh.cpp:1214
const Vct3 & position(uint i) const
access 3D space position of vertex i
Definition: dnmesh.h:104
void setAbortFlag(bool flag)
set interruption flag to stop refinement
Definition: dnmesh.h:185
int pIsInside(uint ti, uint ni) const
test if vertex ni is inside triangle ti
Definition: dnmesh.cpp:2051
std::string errmsg
error message
Definition: dnmesh.h:441
const Vct3 & normal(uint i) const
access surface normal of vertex i
Definition: dnmesh.h:110
Indices iNoFlip
edges which may not be flipped or split
Definition: dnmesh.h:429
bool isConvexSet(uint v[4]) const
check if the neighborhood v is convex
Definition: dnmesh.cpp:3287
uint findEdgeSorted(uint a, uint b) const
find edge index, requires sorted edge array
Definition: dnmesh.h:213
void classify(uint ti, Real maxstretch, DnTriangleShape &shp) const
compute edge lengths, return triangle area
Definition: dnmesh.cpp:2950
Real sOrientation(uint a, uint b, uint c) const
orientation test in 3D
Definition: dnmesh.cpp:2017
XmlElement pToXml() const
parameter space mesh to xml
Definition: dnmesh.cpp:2526
bool collapseEdge(uint eshort)
try to merge source and target of eshort
Definition: dnmesh.cpp:2990
bool destroyHat(uint ti, uint elong)
refine a triangle with one long side and a large angle
Definition: dnmesh.cpp:3210
void markKinks(Real dphi)
constrain an edge if it separates components with a normal jump between them
Definition: dnmesh.cpp:3754
bool ptInPolygon(const Vct2 &pt, const Indices &ip) const
check if pt is inside polygon determined by ip
Definition: dnmesh.cpp:3724
int sIsOnBoundaryEdge(uint ti, uint ni) const
special case of vertex on wrapped boundary
Definition: dnmesh.cpp:2163
void smoothVertex(uint v)
move v to its barycenter, if legal
Definition: dnmesh.cpp:2923
Indices iDeadEdges
dead edges and triangles
Definition: dnmesh.h:426
bool refineEdge(uint ei, Real minlen)
insert new vertex at midpoint if possible
Definition: dnmesh.cpp:2732
void fixDirection(DnTriangle &t)
fix direction of triangle normal
Definition: dnmesh.h:205
uint insertVertex(const Vct2 &p, bool &onBoundary)
insert vertex, sustain Delaunay property
Definition: dnmesh.cpp:815
void refineAround(const Indices &vlist, const DnRefineCriterion &c)
split triangles near vertices in vlist
Definition: dnmesh.cpp:2582
bool vertexCanMove(uint v, const Vct2 &pt) const
check if vertex v can be moved to pt without tangling the mesh
Definition: dnmesh.cpp:3602
uint nnedges()
prepare list of changed edges
Definition: dnmesh.h:398
uint addEdge(uint a, uint b)
add edge to triangulation, return index (no connectivity updates)
Definition: dnmesh.cpp:511
XmlElement toXml() const
write 3D mesh to xml representation (MeshFields)
Definition: dnmesh.cpp:2509
void forbidSplit(uint i)
register edge i as non-flippable
Definition: dnmesh.h:250
bool initBoundary(const PointList< 2 > &pts)
start with (optionally constrained) boundary, return true on success
Definition: dnmesh.cpp:348
void sFixDirection(const DnVertexArray &vtx)
make sure that the normal direction is correct (3-space)
Definition: dntriangle.h:433
DnTriangleArray triangles
triangle array
Definition: dnmesh.h:420
uint checkConnectivity(uint v, Indices &nbv) const
debugging : check local connectivity for consistency (aborts on error)
Definition: dnmesh.cpp:3838
const std::string & lastError() const
access error message
Definition: dnmesh.h:191
void smooth(uint niter=1, Real omega=1.0)
plain laplacian smoothing (all unconstrained vertices)
Definition: dnmesh.cpp:3368
DnEdgeArray edges
edge array
Definition: dnmesh.h:417
void collectNbEdges(uint i, Indices &edg, bool allEdges=false) const
collect all edges which run into vertex i
Definition: dnmesh.cpp:1495
void centerVertex(uint i, Real omega=1.0)
displace a vertex to the barycenter of its ring-1 neighborhood
Definition: dnmesh.cpp:3545
Indices newEdges
newly created edges or modified triangles
Definition: dnmesh.h:432
int isInside(uint ti, uint ni) const
test if vertex ni is inside triangle ti
Definition: dnmesh.h:326
bool isKink(uint i) const
check if edge is on kink
Definition: dnmesh.h:232
bool flipEdge(uint ei)
flip edge
Definition: dnmesh.cpp:1358
void switchMode(DnType t)
change triangulation mode (hope that you know what you are doing)
Definition: dnmesh.h:123
Simplest mesh refinement criterion.
Definition: dnrefine.h:43
bool sIntersects(uint ei, uint a, uint b) const
test if a and b lie on different side of ei (intersection)
Definition: dnmesh.cpp:1966
uint exportMesh(PointList< 2 > &pts, Indices &qtri) const
export a triangular mesh (2D)
Definition: dnmesh.cpp:453
void fuseVertices(uint vdrop, uint vkeep)
change vdrop to vkeep in all faces connected to vdrop
Definition: dnmesh.cpp:3153
bool canSplit(uint i) const
check if edge may be split
Definition: dnmesh.h:237
Vct3 eval(Real u, Real v) const
evaluate the surface
Definition: dnmesh.h:55
Generated on Wed Jan 19 2022 03:03:15 for libsurf by   doxygen 1.8.5