In Edge, why there is only one single Halfedge is being referred to? I thought it would be 2.
moridin22
This is similar to why (for example) each vertex only references one of its halfedges instead of all of them - we're able to use the single halfedge that an edge references to access both halfedges, namely by using the "twin" pointer within that halfedge. The later slides provide some other examples of how you can use the limited information that each individual struct provides in order to access all of the adjacent elements of the mesh.
aparikh98
For this set of triangles, there are numerous ways to label the various components, but once you've set the "half edge" there is only one consistent labelling. This seems really useful as the remainder of the definitions are derived from how you define the half edge!
dtseng
Yeah I was a bit confused as to why the vertex only needs a reference to only one of its half edges. However, it turns out that you can still access all of the other edges that contain the vertex by iterating through each edge's twin and next edge.
SeungjinYang
To clarify, the vertex that halfedge points to is the 'source' vertex of the halfedge, right? Then, to get the 'destination' vertex, I would have to look at the vertex of the twin halfedge?
raghav-cs184
What happens to the triangle at the edge of a surface? Do you just have an imaginary "triangle" outside to indicate the end of a triangle? Or does every halfedge not have to have a twin and so we know we are at a boundary?
ricli
With this structure isn't there a lot of redundancy? Multiple halfedges can share a face, edge, or vertex and each of the respective structs only have a single pointer to a halfedge. For example, in the picture shown the halfedge and its twin both share an edge; so I am led to believe there will be two edge structs one for each halfedge. As we work with larger meshes it seems this will result in a lot of wasted space.
Staffantiamoeba
@ricli this is true, in a sense there is redundancy. Yet, at the same time, this helps keep things clean in that a half edge bounds exactly one face, while a normal edge bounds two faces. It turns out there's another related data structure called the quadedge that deals with some of the redundancy you mentioned.
Staffantiamoeba
@SeungjinYang you are correct. You can also look at the source vertex of the next half-edge.
Staffantiamoeba
@raghav-cs184 from what I understand, both approaches are valid, but I think usually in terms of theory people usually think of an imaginary face that borders all the triangles on the edge of the polygon.
ellenluo
Are half-edges used primarily in the graphics industry? I'm curious if this is how apps like Blender represent triangular meshes and how they account for cases of meshes that aren't manifold.
Staffkatamarisun
@ellenluo, half-edge meshes (and one of their counterparts, winged-edge meshes) are mainly used for mesh transformations and traversal, while internally many software packages actually store indexed-meshes (arrays of points, edges, faces) to better interface with GPU storage. A good stack answer: https://stackoverflow.com/questions/30198451/mesh-data-structure-used-in-popular-3d-software
hershg
Say a vertex touches a large number of cycles, so a large number of halfedges have that vertex. I agree that using halfedge->twin and ->next, we can traverse the entire mesh and get where we want. But since it is somewhat arbitrary which specific halfedge/triangles the vertex's datastructure stores, how would we know precisely how to traverse the mesh from a given vertex A to vertex B?
tl;dr it seems halfedge based approaches are great for problems like "traverse all neighbors"/"traverse the whole triangle"/..., but aren't well suited for problems where we have a given start and finish vertex (or any problem involving traversal in a specific direction for that matter) since the vertex -> halfedge and face->halfedge mappings are abitrary
In particular starting page 3 and the appendix, you can see they traverse the mesh using the same logic.
leslie0224
for "each edge and face points to one of its half edges", are there any specific rules for which half edge the edge/face should point to?
arilato
I think typically there doesn't need to be specific rules, since the computational cost of traversing to the other half-edge is trivial. You just call twin() which is a single memory access.
arilato
It seems that half-edge data structures don't have to be just limited to triangles. See the wikipedia article here: https://en.wikipedia.org/wiki/Doubly_connected_edge_list
They work with any polygon mesh. In fact, given any non-triangular polygon, the structures defined here would still be the same! That's really interesting to think about, since when I first learned about half-edges I only thought about it from a triangular mesh context.
In Edge, why there is only one single Halfedge is being referred to? I thought it would be 2.
This is similar to why (for example) each vertex only references one of its halfedges instead of all of them - we're able to use the single halfedge that an edge references to access both halfedges, namely by using the "twin" pointer within that halfedge. The later slides provide some other examples of how you can use the limited information that each individual struct provides in order to access all of the adjacent elements of the mesh.
For this set of triangles, there are numerous ways to label the various components, but once you've set the "half edge" there is only one consistent labelling. This seems really useful as the remainder of the definitions are derived from how you define the half edge!
Yeah I was a bit confused as to why the vertex only needs a reference to only one of its half edges. However, it turns out that you can still access all of the other edges that contain the vertex by iterating through each edge's twin and next edge.
To clarify, the vertex that halfedge points to is the 'source' vertex of the halfedge, right? Then, to get the 'destination' vertex, I would have to look at the vertex of the twin halfedge?
What happens to the triangle at the edge of a surface? Do you just have an imaginary "triangle" outside to indicate the end of a triangle? Or does every halfedge not have to have a twin and so we know we are at a boundary?
With this structure isn't there a lot of redundancy? Multiple halfedges can share a face, edge, or vertex and each of the respective structs only have a single pointer to a halfedge. For example, in the picture shown the halfedge and its twin both share an edge; so I am led to believe there will be two edge structs one for each halfedge. As we work with larger meshes it seems this will result in a lot of wasted space.
@ricli this is true, in a sense there is redundancy. Yet, at the same time, this helps keep things clean in that a half edge bounds exactly one face, while a normal edge bounds two faces. It turns out there's another related data structure called the quadedge that deals with some of the redundancy you mentioned.
@SeungjinYang you are correct. You can also look at the source vertex of the next half-edge.
@raghav-cs184 from what I understand, both approaches are valid, but I think usually in terms of theory people usually think of an imaginary face that borders all the triangles on the edge of the polygon.
Are half-edges used primarily in the graphics industry? I'm curious if this is how apps like Blender represent triangular meshes and how they account for cases of meshes that aren't manifold.
@ellenluo, half-edge meshes (and one of their counterparts, winged-edge meshes) are mainly used for mesh transformations and traversal, while internally many software packages actually store indexed-meshes (arrays of points, edges, faces) to better interface with GPU storage. A good stack answer: https://stackoverflow.com/questions/30198451/mesh-data-structure-used-in-popular-3d-software
Say a vertex touches a large number of cycles, so a large number of halfedges have that vertex. I agree that using halfedge->twin and ->next, we can traverse the entire mesh and get where we want. But since it is somewhat arbitrary which specific halfedge/triangles the vertex's datastructure stores, how would we know precisely how to traverse the mesh from a given vertex A to vertex B?
tl;dr it seems halfedge based approaches are great for problems like "traverse all neighbors"/"traverse the whole triangle"/..., but aren't well suited for problems where we have a given start and finish vertex (or any problem involving traversal in a specific direction for that matter) since the vertex -> halfedge and face->halfedge mappings are abitrary
Interesting to see original paper:
https://apps.dtic.mil/dtic/tr/fulltext/u2/a056889.pdf.
In particular starting page 3 and the appendix, you can see they traverse the mesh using the same logic.
for "each edge and face points to one of its half edges", are there any specific rules for which half edge the edge/face should point to?
I think typically there doesn't need to be specific rules, since the computational cost of traversing to the other half-edge is trivial. You just call twin() which is a single memory access.
It seems that half-edge data structures don't have to be just limited to triangles. See the wikipedia article here: https://en.wikipedia.org/wiki/Doubly_connected_edge_list
They work with any polygon mesh. In fact, given any non-triangular polygon, the structures defined here would still be the same! That's really interesting to think about, since when I first learned about half-edges I only thought about it from a triangular mesh context.