Mesh generation manifold FAIL. Ideas?
category: code [glöplog]
I'm working on a mesh generator, which allows simple operations like face extrusion, vertex displacement and subdivision.
The datastructure I'm using (half-edge) requires that the mesh is manifold after inserting a new face. I'm having some trouble keeping the mesh manifold while doing operations on it.
For a quick intuitive idea of what non-manifold meshes look like, look at the illustration here: http://download.autodesk.com/global/docs/maya2012/en_us/index.html?url=files/Polygons_overview_Twomanifold_vs._nonmanifold_polygonal_geometry.htm,topicNumber=d28e120238
Specifically, my problem is with the middle case, two or more faces share a single vertex but no edge.
In that situation I cannot correctly find all outgoing edges from a vertex by iterating over the edge connectivity (which would normally be a near O(1) operation).
This is a problem for edge insertion, where the first step is to check if there is already an edge between the two vertices A and B. Now, normally I would just iterate over all edges going out from A and check if any of them connect to B. As mentioned, this is close to a O(1) operation. But if I cannot rely on the manifoldness of the graph, I have to search ALL edges, which makes it closer to a O(n) operation just to insert an edge. And this really kills performance.
Now, this is almost fast enough to not be a problem in practice, but not quite. I could probably live with it.
(But can YOU live with EVEN MORE precalc time in our 64k intros? :-)
I see the following options:
1) I'm a retard for trying to use this kind of data structure. It's just as easy to do X, and I should do that instead.
2) I'm a retard for not knowing about trick Y, which always ensures that the mesh is manifold while operating on it.
3) I'm a retard because you would normally expect the mesh to automagically be manifold, and clearly there is a problem with my code or my approach.
Please educate me.
PS. I should note that none of the operations create non-manifold meshes as the end product. It's only a problem while the operation is in the process of building/changing the mesh.
The datastructure I'm using (half-edge) requires that the mesh is manifold after inserting a new face. I'm having some trouble keeping the mesh manifold while doing operations on it.
For a quick intuitive idea of what non-manifold meshes look like, look at the illustration here: http://download.autodesk.com/global/docs/maya2012/en_us/index.html?url=files/Polygons_overview_Twomanifold_vs._nonmanifold_polygonal_geometry.htm,topicNumber=d28e120238
Specifically, my problem is with the middle case, two or more faces share a single vertex but no edge.
In that situation I cannot correctly find all outgoing edges from a vertex by iterating over the edge connectivity (which would normally be a near O(1) operation).
This is a problem for edge insertion, where the first step is to check if there is already an edge between the two vertices A and B. Now, normally I would just iterate over all edges going out from A and check if any of them connect to B. As mentioned, this is close to a O(1) operation. But if I cannot rely on the manifoldness of the graph, I have to search ALL edges, which makes it closer to a O(n) operation just to insert an edge. And this really kills performance.
Now, this is almost fast enough to not be a problem in practice, but not quite. I could probably live with it.
(But can YOU live with EVEN MORE precalc time in our 64k intros? :-)
I see the following options:
1) I'm a retard for trying to use this kind of data structure. It's just as easy to do X, and I should do that instead.
2) I'm a retard for not knowing about trick Y, which always ensures that the mesh is manifold while operating on it.
3) I'm a retard because you would normally expect the mesh to automagically be manifold, and clearly there is a problem with my code or my approach.
Please educate me.
PS. I should note that none of the operations create non-manifold meshes as the end product. It's only a problem while the operation is in the process of building/changing the mesh.
just use subdivision instead.
revival: candytron, kkrieger and debris all use a half-edge based mesh generator, so it's definitely doable. however: do not, ever, break the invariants, or you'll be sorry. don't support operations that break 2-manifoldness if you work with half-edges. this is not a laughing matter. your sanity is at stake here :)
that said: fuck explicit link-based half-edge data structures. they're a royal pain. at some point i realized that you really want to keep that half-edges implicit, it's much nicer to work with.
the point here is that you have the mesh as a flat list of verts/faces if you want to ignore the half-edge connectivity for some operations where it's convenient. then just write a helper routine that rebuilds "opposite edge" information by pairing off edges (either sort- or hash-based) after such destructive operations.
it's far easier than dealing with half-edges everywhere. usually produces smaller code too. oh, and you want to pick "MaxVertPerFace" properly of course; the two sane choices are 4 and 8 :)
that said: fuck explicit link-based half-edge data structures. they're a royal pain. at some point i realized that you really want to keep that half-edges implicit, it's much nicer to work with.
Code:
static const int MaxVertPerFace = 8;
typedef uint VertexId;
typedef uint FaceId;
typedef uint HalfEdgeId; // HalfEdgeId = (faceId * MaxVertPerFace) + vertInFace;
struct Vertex { ... };
struct Face {
// Vertices for this face, counter-clockwise
VertexId Vertex[MaxVertPerFace];
// Opposite half-edge id for the half-edge originating from vertex i
HalfEdgeId OppositeEdge[MaxVertPerFace];
uint Count; // Number of edges for this face
};
struct Mesh {
Array<Vertex> Verts;
Array<Face> Faces;
// Primitive accessors
FaceId FaceIdFromHalfEdge(HalfEdgeId id) const
{
return id / MaxVertPerFace;
}
const Face &FaceFromHalfEdge(HalfEdgeId id) const
{
return Faces[FaceIdFromHalfEdge(id)];
}
uint VertIndFromHalfEdge(HalfEdgeId id) const
{
return id % MaxVertPerFace;
}
VertexId StartVertexId(HalfEdgeId id) const
{
return FaceFromHalfEdge(id).Vertex[VertIndFromHalfEdge(id)];
}
HalfEdgeId OppositeEdge(HalfEdgeId id) const
{
return FaceFromHalfEdge(id).Opposite[VertIndFromHalfEdge(id)];
}
HalfEdgeId MakeHalfEdge(FaceId face, uint index) const
{
assert(Index < MaxVertPerFace);
return face * MaxVertPerFace + index;
}
// Half-edge traversal
HalfEdgeId NextFaceEdge(HalfEdgeId id) const
{
FaceId face = FaceIdFromHalfEdge(id);
uint index = VertIndFromHalfEdge(id);
if (++index == Faces[face].Count)
index = 0;
return MakeHalfEdge(face, index);
}
// PrevFaceEdge analogous
HalfEdgeId NextVertEdge(HalfEdgeId id) const
{
return OppositeEdge(PrevFaceEdge(id));
}
// and so on...
};
the point here is that you have the mesh as a flat list of verts/faces if you want to ignore the half-edge connectivity for some operations where it's convenient. then just write a helper routine that rebuilds "opposite edge" information by pairing off edges (either sort- or hash-based) after such destructive operations.
it's far easier than dealing with half-edges everywhere. usually produces smaller code too. oh, and you want to pick "MaxVertPerFace" properly of course; the two sane choices are 4 and 8 :)
ryg:
That's very encouraging, thanks!
I hear what you're saying about the implicit representation. It seems to me in hindsight that the major benifit of the explicit representation is that you can quickly update the explicit representation to satify the invariants.
There would probably be a bit of a performance hit in reconstructing the edge pairs, but it would be absolutely negligible compared to the linear edge search I'm doing now.
So I'll probably switch to your approach eventually, but it's getting a bit late for a rewrite for Solskogen, but fortunately I seem to have a fix for the original problem:
In addition to looking for edges from A to B, also look for edges from B to A.
While this doesn't solve the problem generally, it fixes it *just enough* for the operations I'm doing currently, so my acute pain is fixed, but I clearly still have a longerterm one.
Thanks again.
That's very encouraging, thanks!
I hear what you're saying about the implicit representation. It seems to me in hindsight that the major benifit of the explicit representation is that you can quickly update the explicit representation to satify the invariants.
There would probably be a bit of a performance hit in reconstructing the edge pairs, but it would be absolutely negligible compared to the linear edge search I'm doing now.
So I'll probably switch to your approach eventually, but it's getting a bit late for a rewrite for Solskogen, but fortunately I seem to have a fix for the original problem:
In addition to looking for edges from A to B, also look for edges from B to A.
While this doesn't solve the problem generally, it fixes it *just enough* for the operations I'm doing currently, so my acute pain is fixed, but I clearly still have a longerterm one.
Thanks again.
As an avid mesh fiddler myself, I'm curious to why you're getting the bowties in the first place. Do you actually want to keep non-manifold meshes or is it a middle step in of one of the operations that cause them?
Related thread:
http://www.pouet.net/topic.php?which=7744
Just for fun:
http://www.viz.tamu.edu/faculty/ergun/research/topology/images.html
Related thread:
http://www.pouet.net/topic.php?which=7744
Just for fun:
http://www.viz.tamu.edu/faculty/ergun/research/topology/images.html
Ah, "bowties", nice and succint.
Yes, this happens in an intermediate step, e.g. in the middle of doing subdivision.
If you imagine that the source mesh faces were selected for subdivision in *random* order, it's easy to see how this could happen. Of course I don't do it in random order, but some operation chains cause the problem anyway.
Yeah, I've played with TopMod, it's pretty cool :-)
Yes, this happens in an intermediate step, e.g. in the middle of doing subdivision.
If you imagine that the source mesh faces were selected for subdivision in *random* order, it's easy to see how this could happen. Of course I don't do it in random order, but some operation chains cause the problem anyway.
Yeah, I've played with TopMod, it's pretty cool :-)