| Line 13... |
Line 13... |
| 13 |
{
|
13 |
{
|
| 14 |
class VertexCirculator;
|
14 |
class VertexCirculator;
|
| 15 |
class FaceCirculator;
|
15 |
class FaceCirculator;
|
| 16 |
|
16 |
|
| 17 |
/** \brief A Data structure representing an open or closed manifold.
|
17 |
/** \brief A Data structure representing an open or closed manifold.
|
| 18 |
|
- |
|
| 19 |
Manifold keeps lists of the entities making up a halfedge mesh
|
18 |
Manifold keeps lists of the entities making up a halfedge mesh
|
| 20 |
and provides basic functions for creating new faces, halfedges
|
19 |
and provides basic functions for creating new faces, halfedges
|
| 21 |
and vertices. There are also primitive operations for editing
|
20 |
and vertices. There are also primitive operations for editing
|
| 22 |
such as edge collapse. */
|
21 |
such as edge collapse. */
|
| 23 |
struct Manifold
|
22 |
struct Manifold
|
| Line 25... |
Line 24... |
| 25 |
std::list<Vertex> vertex_db;
|
24 |
std::list<Vertex> vertex_db;
|
| 26 |
std::list<Face> face_db;
|
25 |
std::list<Face> face_db;
|
| 27 |
std::list<HalfEdge> halfedge_db;
|
26 |
std::list<HalfEdge> halfedge_db;
|
| 28 |
|
27 |
|
| 29 |
/** Remove a face if it contains only two edges.
|
28 |
/** Remove a face if it contains only two edges.
|
| 30 |
|
- |
|
| 31 |
This is an auxiliary function called from collapse_halfedge. */
|
29 |
This is an auxiliary function called from collapse_halfedge. */
|
| 32 |
void remove_face_if_degenerate(HalfEdgeIter fi);
|
30 |
void remove_face_if_degenerate(HalfEdgeIter fi);
|
| 33 |
|
31 |
|
| 34 |
/** Empty copy constructor.
|
32 |
/** Empty copy constructor.
|
| 35 |
|
- |
|
| 36 |
Copying a manifold will not work, since faces, vertices, and
|
33 |
Copying a manifold will not work, since faces, vertices, and
|
| 37 |
halfedges contain iterators pointing to other faces, vertices,
|
34 |
halfedges contain iterators pointing to other faces, vertices,
|
| 38 |
and halfedges. These pointers would need to be changed if the
|
35 |
and halfedges. These pointers would need to be changed if the
|
| 39 |
mesh were copied. In other words, we would need to walk the
|
36 |
mesh were copied. In other words, we would need to walk the
|
| 40 |
entire mesh. This may be required but it should not be an
|
37 |
entire mesh. This may be required but it should not be an
|
| 41 |
operation that is easily invoked by calling the copy constructor.
|
38 |
operation that is easily invoked by calling the copy constructor.
|
| 42 |
Hence, this operator is made private. */
|
39 |
Hence, this operator is made private. */
|
| 43 |
Manifold(const Manifold& m2) {}
|
40 |
Manifold(const Manifold& m2) {}
|
| 44 |
|
41 |
|
| 45 |
/** Empty assignment operator.
|
42 |
/** Empty assignment operator.
|
| 46 |
|
- |
|
| 47 |
The assignment operator is private for the same reason that the
|
43 |
The assignment operator is private for the same reason that the
|
| 48 |
copy constructor is private. */
|
44 |
copy constructor is private. */
|
| 49 |
const Manifold& operator=(const Manifold& m2) {}
|
45 |
const Manifold& operator=(const Manifold& m2) {}
|
| 50 |
|
46 |
|
| 51 |
public:
|
47 |
public:
|
| 52 |
|
48 |
|
| Line 178... |
Line 174... |
| 178 |
in that case we create a vertex where two holes meet. A non manifold
|
174 |
in that case we create a vertex where two holes meet. A non manifold
|
| 179 |
situation. */
|
175 |
situation. */
|
| 180 |
bool collapse_precond(VertexIter, HalfEdgeIter);
|
176 |
bool collapse_precond(VertexIter, HalfEdgeIter);
|
| 181 |
|
177 |
|
| 182 |
/** Collapse the halfedge given as second argument.
|
178 |
/** Collapse the halfedge given as second argument.
|
| - |
|
179 |
The first argument is the vertex that is being removed. The
|
| - |
|
180 |
second is a halfedge pointing away from that vertex.
|
| 183 |
|
181 |
|
| 184 |
The first argument
|
182 |
The final argument is a boolean indicating whether the vertex
|
| 185 |
is the vertex that is being removed. The second is a halfedge pointing
|
183 |
that survives the collapse should have a position which is the
|
| 186 |
away from that vertex. This function is not guaranteed
|
184 |
average of its own position and the vertex that is removed.
|
| - |
|
185 |
By default false.
|
| - |
|
186 |
|
| - |
|
187 |
This function is not guaranteed to keep the mesh sane unless,
|
| 187 |
to keep the mesh sane unless, collapse_precond has returned true. */
|
188 |
collapse_precond has returned true.
|
| - |
|
189 |
*/
|
| 188 |
void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);
|
190 |
void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);
|
| 189 |
|
191 |
|
| - |
|
192 |
/** Split a face.
|
| 190 |
/** Split a face (first argument) by connecting two vertices (the
|
193 |
The face given as first argument is split by connecting two
|
| 191 |
next two arguments). */
|
194 |
vertices (the next two arguments). */
|
| 192 |
FaceIter split_face(FaceIter, VertexIter, VertexIter);
|
195 |
FaceIter split_face(FaceIter, VertexIter, VertexIter);
|
| 193 |
|
196 |
|
| 194 |
/** Insert a new vertex on the halfedge given as argument. */
|
197 |
/** Insert a new vertex on the halfedge given as argument.
|
| - |
|
198 |
The new halfedge is insterted as the previous edge to the one
|
| - |
|
199 |
given as argument.
|
| - |
|
200 |
*/
|
| 195 |
VertexIter Manifold::split_edge(HalfEdgeIter h);
|
201 |
VertexIter Manifold::split_edge(HalfEdgeIter h);
|
| 196 |
|
202 |
|
| 197 |
/** Triangulate a polygonal face by repeatedly calling splitface. */
|
203 |
/** Triangulate a polygonal face by repeatedly calling split_face.
|
| - |
|
204 |
Triangulate iteratively splits triangles off a polygon. The first
|
| - |
|
205 |
triangle split off is the one connecting f->last->vert and
|
| - |
|
206 |
f->last->next->next->vert.
|
| - |
|
207 |
*/
|
| 198 |
void triangulate(FaceIter);
|
208 |
void triangulate(FaceIter);
|
| 199 |
|
209 |
|
| 200 |
/** Triangulate a polygon by inserting a vertex at the barycenter and
|
210 |
/** Triangulate a polygon by inserting a vertex at the barycenter and
|
| 201 |
connecting all vertices to this vertex. */
|
211 |
connecting all vertices to this vertex.
|
| - |
|
212 |
|
| - |
|
213 |
The word "safe" means that it is less likely to create flipped
|
| - |
|
214 |
triangles than the normal triangulate. On the other hand, it
|
| - |
|
215 |
introduces more vertices and probably makes the triangles more
|
| - |
|
216 |
acute.
|
| - |
|
217 |
|
| - |
|
218 |
This function simply calls face_insert_point.
|
| - |
|
219 |
*/
|
| 202 |
VertexIter safe_triangulate(FaceIter f);
|
220 |
VertexIter safe_triangulate(FaceIter f);
|
| 203 |
|
221 |
|
| 204 |
/** Insert a new vertex (second arg.) in a face (first arg.).
|
222 |
/** Insert a new vertex (second arg.) in a face (first arg.).
|
| 205 |
This operation splits an N-gon into N triangles. */
|
223 |
This operation splits an N-gon into N triangles.
|
| - |
|
224 |
In the current implementation the original face is erased.
|
| - |
|
225 |
This means that the iterator is not valid after the function
|
| - |
|
226 |
returns.
|
| - |
|
227 |
*/
|
| 206 |
void face_insert_point(FaceIter f, VertexIter);
|
228 |
void face_insert_point(FaceIter f, VertexIter);
|
| 207 |
|
229 |
|
| 208 |
/** Merges two faces into a single polygon. The first face is the first
|
230 |
/** Merges two faces into a single polygon. The first face is the first
|
| 209 |
argument. The second face is adjacent to the first along the
|
231 |
argument. The second face is adjacent to the first along the
|
| 210 |
halfedge given as second argument. */
|
232 |
halfedge given as second argument. */
|
| 211 |
bool merge_faces(FaceIter f, HalfEdgeIter h);
|
233 |
bool merge_faces(FaceIter f, HalfEdgeIter h);
|
| 212 |
|
234 |
|
| 213 |
/** flips an edge. Returns false if flipping cannot be performed.
|
235 |
/** Flip an edge. Returns false if flipping cannot be performed.
|
| 214 |
This is either because one of the two adjacent faces is not
|
236 |
This is either because one of the two adjacent faces is not
|
| 215 |
a triangle, or because either end point has valency three or
|
237 |
a triangle, or because either end point has valency three or
|
| 216 |
because the vertices that will be connected already are. */
|
238 |
because the vertices that will be connected already are. */
|
| 217 |
bool flip(HalfEdgeIter);
|
239 |
bool flip(HalfEdgeIter);
|
| 218 |
|
240 |
|