libsurf
Programmer's Documentation

delaunaycore.h (r6227/r5937)
1 
2 /* Copyright (C) 2015 David Eller <david@larosterna.com>
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 david@larosterna.com .
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  */
14 
15 #ifndef SURF_DELAUNAYCORE_H
16 #define SURF_DELAUNAYCORE_H
17 
18 #include "dcedge.h"
19 #include "dcface.h"
20 #include <boost/pool/object_pool.hpp>
21 
22 class DcGeometry;
23 class ConnectMap;
24 
43 {
44 public:
45 
46  enum InsertionFlag {NotInserted, EdgeSplit, FaceSplit,
47  VertexPresent, ExtendedOutward};
48 
49  enum StatusCode { StatusOk = 0,
50  ConstraintIntersection,
51  UnhandledMixedConstraint,
52  CannotEnforceEdge,
53  InconsistentTopology,
54  InsertPointOutOfDomain,
55  InsertCannotSplitEdge,
56  InsertTriangledNotFound,
57  ProtectedConstraintEncroached,
58  NumberOfStatusCodes };
59 
60  typedef std::pair<DcEdge*, uint> EncPair;
61  typedef std::vector<EncPair> FlipStack;
62 
64  DelaunayCore(DcGeometry & geom, size_t reserveEdges=8192);
65 
67  void enableExtension(bool flag) { bInsertExtend = flag; }
68 
70  uint addFace(uint a, uint b, uint c);
71 
73  void addFaces(const Indices & tri);
74 
76  void fixate();
77 
79  void eraseDetachedEdges();
80 
82  void triangles(Indices & tri) const;
83 
85  void constrainedEdges(Indices &lns) const;
86 
88  void vertexMap(uint nv, ConnectMap & v2f) const;
89 
91  uint nAllFaces() const {return faces.size();}
92 
94  uint nValidFaces() const {return faces.size() - invalidFaces.size();}
95 
97  const DcFace & face(uint f) const {
98  assert(f < faces.size());
99  return faces[f];
100  }
101 
106  int insertVertex(uint c, bool legalizeEdges=true);
107 
113  uint insertConstraint(const Indices & c,
114  int flags = DcEdge::Constrained,
115  bool legalizeEdges=true);
116 
118  void setEdgeFlags(int pattern, int flags);
119 
121  void unsetEdgeFlags(int pattern, int flags);
122 
124  void protectConstraints(bool flag) { bProtectConstraints = flag; }
125 
127  bool splitEdge(DcEdge *pab, uint c, bool legalizeEdges=true);
128 
130  bool splitFace(uint f, uint x, bool legalizeEdges=true);
131 
133  void addExternalVertex(DcEdge *pab, uint c, bool legalizeEdges=true);
134 
136  const Indices & verticesOnConstraints() const {return vinConEdges;}
137 
139  Indices & verticesOnConstraints() {return vinConEdges;}
140 
142  bool flipEdge(DcEdge *pe);
143 
145  uint eatHole(uint f);
146 
148  uint eraseFacesTouching(const Indices &idx);
149 
151  DcEdge *findEdge(uint s, uint t) const {
152  if (s != t) {
153  DcEdge etest(s, t);
154  DcEdgeItr pos = edges.find(&etest);
155  return (pos != edges.end()) ? *pos : nullptr;
156  }
157  return nullptr;
158  }
159 
161  DcEdge *constructEdge(uint s, uint t) {
162  assert(s != t);
163  DcEdge *ep = (DcEdge *) edgePool.malloc();
164  assert(ep != 0);
165  return (new(ep) DcEdge(s, t)); // placed at ep
166  }
167 
169  bool diamond(DcEdge *pe, uint v[]) const;
170 
172  bool isConvex(const uint v[]) const;
173 
175  void constrainedVertices(std::vector<bool> & cvx,
176  int edgeflag = DcEdge::Constrained) const;
177 
179  void boundaryVertices(std::vector<bool> & bvx) const;
180 
182  void clear();
183 
185  int lastStatusCode() const {return status;}
186 
187 protected:
188 
191  assert(e.source() != e.target());
192  DcEdge *ep = (DcEdge *) edgePool.malloc();
193  assert(ep != 0);
194  return (new(ep) DcEdge(e)); // placed at ep
195  }
196 
198  void eraseEdge(DcEdge *pe) {
199  edges.erase(pe);
200  if (pe != 0)
201  pe->invalidate();
202  // for (int i=0; i<edge_cache_size; ++i)
203  // if (edgeCache[i] == pe)
204  // edgeCache[i] = 0;
205  }
206 
208  uint angOpposedVertex(uint t, uint topo) const {
209  assert(t < faces.size());
210  assert(topo < faces.size());
211  const uint *vtopo = faces[topo].vertices();
212  for (int k=0; k<3; ++k)
213  if ( faces[t].find(vtopo[k]) == NotFound )
214  return vtopo[k];
215  return NotFound;
216  }
217 
219  uint angOpposedFace(uint t, uint p) const {
220  assert(t < faces.size());
221  const uint *vi = faces[t].vertices();
222  for (int k=0; k<3; ++k) {
223  const uint src = vi[k];
224  const uint trg = vi[(k+1)%3];
225  if (src == p or trg == p)
226  continue;
227  const DcEdge *pe = findEdge( src, trg );
228  assert(pe != 0);
229  assert(pe->left() == t or pe->right() == t);
230  if (pe->left() == t)
231  return pe->right();
232  else
233  return pe->left();
234  }
235  return NotFound;
236  }
237 
239  void triangulatePolygon(uint bs, uint bt,
240  Indices::const_iterator vbeg,
241  Indices::const_iterator vend);
242 
244  void eraseFace(uint k);
245 
247  void detachFace(uint k);
248 
250  void legalizeEdge(uint src, uint trg, uint v);
251 
253  void legalizeEdge(DcEdge *pe, uint v);
254 
256  DcEdge *searchCacheForFlip(uint s, uint t) const;
257 
259  bool extendCache();
260 
262  DcEdge *imprintIntersectingEdge(uint csrc, uint ctrg);
263 
265  DcEdge *imprintOverlappingEdge(uint csrc, uint ctrg);
266 
268  void carveAndTriangulate(uint src, uint trg, const Indices &ifaces,
269  Indices &vleft, Indices &vright);
270 
272  void legalizeStack(FlipStack & stack);
273 
276  faceCache.clear();
277  bCacheFaces = true;
278  }
279 
282  bCacheFaces = false;
283  }
284 
285 private:
286 
289 
291  boost::pool<> edgePool;
292 
294  DcEdgeHash edges;
295 
297  DcFaceArray faces;
298 
300  Indices invalidFaces;
301 
303  Indices faceCache;
304 
306  Indices vinConEdges;
307 
309  StatusCode status;
310 
313 
316 
319 };
320 
321 #endif // DELAUNAYCORE_H
DcEdgeHash edges
edges
Definition: delaunaycore.h:294
Edge is part of a constraint.
Definition: dcedge.h:44
void unsetEdgeFlags(int pattern, int flags)
change internal treatment of special edges by un-setting flag bits
Definition: delaunaycore.cpp:1367
Indices & verticesOnConstraints()
access list of vertices inserted into constrained edges
Definition: delaunaycore.h:139
bool flipEdge(DcEdge *pe)
flip edge, update connectivity
Definition: delaunaycore.cpp:226
DcEdge * imprintOverlappingEdge(uint csrc, uint ctrg)
enforce the presence of (src,trg) when it overlaps existing edges
Definition: delaunaycore.cpp:846
Indices faceCache
keeps track of inserted faces
Definition: delaunaycore.h:303
void legalizeStack(FlipStack &stack)
process an edge flip stack
Definition: delaunaycore.cpp:1162
void eraseFace(uint k)
invalidate face
Definition: delaunaycore.cpp:1282
uint32_t right() const
access left neighbor face
Definition: dcedge.h:128
DelaunayCore(DcGeometry &geom, size_t reserveEdges=8192)
empty triangulation
Definition: delaunaycore.cpp:29
bool bInsertExtend
is mesh extension by vertex insertion allowed?
Definition: delaunaycore.h:318
Indices vinConEdges
vertices inserted on constrained edges
Definition: delaunaycore.h:306
uint32_t source() const
access source vertex
Definition: dcedge.h:103
void triangles(Indices &tri) const
export triangles
Definition: delaunaycore.cpp:1323
Delaunay triangulations.
Definition: delaunaycore.h:42
Geometric criteria used in Delaunay triangulation.
Definition: dcgeometry.h:38
uint insertConstraint(const Indices &c, int flags=DcEdge::Constrained, bool legalizeEdges=true)
Constraint insertion.
Definition: delaunaycore.cpp:577
uint nValidFaces() const
number of valid faces
Definition: delaunaycore.h:94
int insertVertex(uint c, bool legalizeEdges=true)
Vertex insertion.
Definition: delaunaycore.cpp:516
void carveAndTriangulate(uint src, uint trg, const Indices &ifaces, Indices &vleft, Indices &vright)
called by both edge imprinting routines
Definition: delaunaycore.cpp:1059
bool isConvex(const uint v[]) const
test whether a four-node neighborhood is convex
Definition: delaunaycore.cpp:213
bool splitFace(uint f, uint x, bool legalizeEdges=true)
split face f, insert vertex x
Definition: delaunaycore.cpp:419
DcEdge * constructEdge(uint s, uint t)
construct edge
Definition: delaunaycore.h:161
void invalidate()
mark as invalid
Definition: dcedge.h:100
void constrainedVertices(std::vector< bool > &cvx, int edgeflag=DcEdge::Constrained) const
mark all constrained vertices
Definition: delaunaycore.cpp:1379
uint nAllFaces() const
number of faces, inclusing invalid ones
Definition: delaunaycore.h:91
void vertexMap(uint nv, ConnectMap &v2f) const
compute vertex-to-face connectivity
Definition: delaunaycore.cpp:162
const Indices & verticesOnConstraints() const
access list of vertices inserted into constrained edges
Definition: delaunaycore.h:136
void legalizeEdge(uint src, uint trg, uint v)
legalize edge pe with respect to vertex v
Definition: delaunaycore.cpp:1115
void clear()
remove all contents, release memory
Definition: delaunaycore.cpp:1411
StatusCode status
code set when error occurs
Definition: delaunaycore.h:309
uint32_t left() const
access left neighbor face
Definition: dcedge.h:125
bool bProtectConstraints
forbid insertion inside ball around constrained edges?
Definition: delaunaycore.h:312
uint angOpposedFace(uint t, uint p) const
return face adjacent to t which does not contain v
Definition: delaunaycore.h:219
void addFaces(const Indices &tri)
add multiple faces, will not check orientation (!)
Definition: delaunaycore.cpp:71
void constrainedEdges(Indices &lns) const
export constrained line segments
Definition: delaunaycore.cpp:1341
void startFaceCaching()
start caching new faces
Definition: delaunaycore.h:275
int lastStatusCode() const
access status code (set when operation not successful)
Definition: delaunaycore.h:185
bool bCacheFaces
flag indicating whether new faces should be cached
Definition: delaunaycore.h:315
void fixate()
compute edges from faces, update connectivity; call only in initialization
Definition: delaunaycore.cpp:118
void eraseEdge(DcEdge *pe)
erase edge from set and cache
Definition: delaunaycore.h:198
uint eraseFacesTouching(const Indices &idx)
erase all faces connected to any of the sorted vertices in idx
Definition: delaunaycore.cpp:81
void detachFace(uint k)
detach reference to face k from the edges of k
Definition: delaunaycore.cpp:103
DcEdge * searchCacheForFlip(uint s, uint t) const
search face cache for edge which may be flipped to obtain (s,t)
Definition: delaunaycore.cpp:667
void eraseDetachedEdges()
erase edges which are not connected to any faces any more
Definition: delaunaycore.cpp:146
DcEdge * constructEdge(const DcEdge &e)
copy construct edge
Definition: delaunaycore.h:190
const DcFace & face(uint f) const
access face f
Definition: delaunaycore.h:97
uint eatHole(uint f)
eat triangles away, starting at face f, stop at constraints
Definition: delaunaycore.cpp:1294
Face in a plane Delaunay triangulation.
Definition: dcface.h:36
void addExternalVertex(DcEdge *pab, uint c, bool legalizeEdges=true)
extend triangulation : construct triangle using pab and vertex c
Definition: delaunaycore.cpp:482
bool diamond(DcEdge *pe, uint v[]) const
collect vertex diamond for edge pe
Definition: delaunaycore.cpp:187
Indices invalidFaces
list of invalid faces
Definition: delaunaycore.h:300
boost::pool edgePool
pool allocator for edges
Definition: delaunaycore.h:291
DcGeometry & geo
geometry evaluator
Definition: delaunaycore.h:288
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]
Definition: delaunaycore.cpp:1218
void setEdgeFlags(int pattern, int flags)
change internal treatment of special edges by setting flag bits
Definition: delaunaycore.cpp:1355
DcEdge * imprintIntersectingEdge(uint csrc, uint ctrg)
enforce the presence of edge (src,trg) by erasing and retriangulating
Definition: delaunaycore.cpp:691
uint angOpposedVertex(uint t, uint topo) const
given two adjacent faces, return vertex of topo not in t (Anglada 1997)
Definition: delaunaycore.h:208
uint addFace(uint a, uint b, uint c)
add a new face
Definition: delaunaycore.cpp:37
Butterfly edge for Delaunay algorithms.
Definition: dcedge.h:39
DcFaceArray faces
faces
Definition: delaunaycore.h:297
void stopFaceCaching()
stop caching new faces
Definition: delaunaycore.h:281
bool extendCache()
extend face cache with immediate neighbor elements
Definition: delaunaycore.cpp:1081
void protectConstraints(bool flag)
protect constrained edges by ball where insertions are forbidden
Definition: delaunaycore.h:124
void boundaryVertices(std::vector< bool > &bvx) const
mark boundary vertices
Definition: delaunaycore.cpp:1396
DcEdge * findEdge(uint s, uint t) const
locate edge, return 0 if not found
Definition: delaunaycore.h:151
bool splitEdge(DcEdge *pab, uint c, bool legalizeEdges=true)
split edge a-b, insert new vertex c in the middle
Definition: delaunaycore.cpp:293
uint32_t target() const
access target vertex
Definition: dcedge.h:106
void enableExtension(bool flag)
enable/disable mesh extension when vertex inserted beyond current mesh
Definition: delaunaycore.h:67
Generated on Wed Jan 19 2022 03:03:15 for libsurf by   doxygen 1.8.5