If half edges are really good for adding and removing elements but not non-manifold geometry, how are polygons actually stored because I'm sure there are several non-manifold shapes that need to be represented? Is it some sort of combination of these techniques?
keenan
@rbunny It's just a pain, that people gripe about all the time. :-). Data structures that work well for changing combinatorics aren't great for nonmanifold meshes and vice versa. The reason is the one we discussed at the beginning of the lecture: making simplifying assumptions about connectivity makes data structures more "sane" and easy to work with (especially for intricate operations like inserting/removing elements). But simplifying assumptions are also sometimes oversimplifications!
My student Nick Sharp recently wrote a paper that has a nice data structure for nonmanifold meshes, where the connectivity is still pretty easy to modify, and everything is stored in flat arrays (rather than scattered pointers).
penguin
In terms of actual storage, would the halfedge still be superior? I think not since each halfedge contains so much information. Though I guess the incidence matrices and adjacency list would be still pretty bad.
L100magikarp
Here's my guesses for storage costs.
Assuming a sparse data structure for the incidence matrices, I think they should all be of the same order in terms of memory, since none of them are storing redundant information and scale roughly linearly with number of vertices and edges.
The scaling factor for adjacency list should be smallest (all it's storing is the bare minimum vertex locations and edges), then incidence matrices (a lot more pointers), and finally half edges (even more pointers).
keenan
@L100magikarp Is right that the order of cost is the same; none of these representations are asymptotically better or worse.
Interestingly enough, the cost of storing the connectivity for a vertex-triangle adjacency list and a halfedge mesh are identical (not just asymptotically, but in terms of absolute cost). To see this, consider that you can recover the connectivity of a halfedge mesh from nothing more than:
the twin pointers, and
the next pointers,
since the edges, faces, and vertices are orbits of the twin, next, and "next of twin"s (e.g., keep following next and you'll trace out the faces). How much storage do you need for these pointers? Well, a clever trick is to enumerate each halfedge with its twin in sequence. So, 0 and 1 are twins, 2 and 3 are twins, and so forth; in general, if n is even then n and n+1 are twins. So, you don't have to explicitly store the twin pointers: you just increment an even integer or decrement an odd integer to get its twin. All that's left to store, then, are the halfedge pointers, and you have two per edge. The ratio of vertices to edges to faces in a triangle is roughly
V:E:F = 1:3:2
(proof omitted). So, the cost of storing a halfedge mesh is roughly 2E = 6V integers to specify next. To store a vertex-face adjacency list, you have three integers per triangle, and 3F is again roughly 6V.
(Both data structures use the same amount of storage for vertex positions: three coordinates per vertex.)
If half edges are really good for adding and removing elements but not non-manifold geometry, how are polygons actually stored because I'm sure there are several non-manifold shapes that need to be represented? Is it some sort of combination of these techniques?
@rbunny It's just a pain, that people gripe about all the time. :-). Data structures that work well for changing combinatorics aren't great for nonmanifold meshes and vice versa. The reason is the one we discussed at the beginning of the lecture: making simplifying assumptions about connectivity makes data structures more "sane" and easy to work with (especially for intricate operations like inserting/removing elements). But simplifying assumptions are also sometimes oversimplifications!
My student Nick Sharp recently wrote a paper that has a nice data structure for nonmanifold meshes, where the connectivity is still pretty easy to modify, and everything is stored in flat arrays (rather than scattered pointers).
In terms of actual storage, would the halfedge still be superior? I think not since each halfedge contains so much information. Though I guess the incidence matrices and adjacency list would be still pretty bad.
Here's my guesses for storage costs.
Assuming a sparse data structure for the incidence matrices, I think they should all be of the same order in terms of memory, since none of them are storing redundant information and scale roughly linearly with number of vertices and edges.
The scaling factor for adjacency list should be smallest (all it's storing is the bare minimum vertex locations and edges), then incidence matrices (a lot more pointers), and finally half edges (even more pointers).
@L100magikarp Is right that the order of cost is the same; none of these representations are asymptotically better or worse.
Interestingly enough, the cost of storing the connectivity for a vertex-triangle adjacency list and a halfedge mesh are identical (not just asymptotically, but in terms of absolute cost). To see this, consider that you can recover the connectivity of a halfedge mesh from nothing more than:
twinpointers, andnextpointers,since the edges, faces, and vertices are orbits of the twin, next, and "next of twin"s (e.g., keep following
nextand you'll trace out the faces). How much storage do you need for these pointers? Well, a clever trick is to enumerate each halfedge with its twin in sequence. So, 0 and 1 are twins, 2 and 3 are twins, and so forth; in general, if n is even then n and n+1 are twins. So, you don't have to explicitly store the twin pointers: you just increment an even integer or decrement an odd integer to get its twin. All that's left to store, then, are the halfedge pointers, and you have two per edge. The ratio of vertices to edges to faces in a triangle is roughlyV:E:F = 1:3:2
(proof omitted). So, the cost of storing a halfedge mesh is roughly 2E = 6V integers to specify
next. To store a vertex-face adjacency list, you have three integers per triangle, and 3F is again roughly 6V.(Both data structures use the same amount of storage for vertex positions: three coordinates per vertex.)