if you keep following next, you'll traverse a loop of halfedges that form a face
if you follow twin, you'll get the other "side" / halfedge of the edge
if you follow next->twin, you'll travel to the next edge, and also the other side of that edge
But how do you get vertices from following next->twin? Is it that each "side" of the edge is associated with one endpoint of the edge?
ecdeo
the twin function mapping a halfedge to its twin is a nontrivial involution
evannw
I think we can also get all the boundaries by checking if the halfedge does not have a twin.
0x484884
@enzyme Each side of the edge is associated with one of the endpoints in a way since each half edge stores its starting vertex but not the ending vertex. I'm not sure if this answers your question, but when you follow next->twin, you wrap around a vertex and you visit all of the edges that touch that vertex.
atarng
If a vertex is on a boundary, does this break the idea of being able to get all incident edges by using next->twin? Or do we just have to be careful about which halfedge is stored in the vertex?
keenan
@ecdeo Yep, that's another way of saying all this: if you have two permutations on a set of $2n$ things, and one of those permutations is an involution with no fixed points, then you have a manifold polygon mesh.
keenan
@evannw I should have mentioned this, but the easiest way to deal with boundaries is just to make every boundary loop its own polygon, and store a flag that marks this polygon as "boundary" or "not boundary." This way, there are no special cases to check (other than checking the flag if you need to).
keenan
@tarng See my previous comment. If you add a "fictional" face for every boundary loop (and, as usual, have halfedges going around this face) then you don't need to do any special-case handling of boundary vertices. Just loop around them with twin->next as usual.
keenan
By the way, the slide should say twin->next, not next->twin!
Arthas007
The boundary techniques works for inside boundary it seems. However, when there is an outside boundary (which diverges) how do we handle the hypothetical faces?
emmaloool
@Arthas007 The boundary face here is just an internal "virtual" representation of a face and associated structures to make iteration and reasoning about boundary edges easier. What would a diverging boundary look like, and how can you have an infinite boundary? (What kind of mesh would you have to have?)
Sherwin
Must my twin's next and my next on different faces? In other words, can we have AB's next = BC and CB's next = BA?
I am not sure if the definitions of "twin", "next" etc themselves are also implicit conditions. If all we have are just the three conditions, then shouldn't the third geometry satisfy the conditions? (Let the center edge be AB, other five vertices be C,D,E,F,G. Then as AB->BC->CA->AD->DB->BE->EA->AF->FB->BG->GA->AB and its reverse, every he is someone's "next")
keenan
@Sherwin Nope, for instance my twin's next could be me! This example is a little hard to visualize. Consider a halfedge mesh with just two halfedges h1 and h2, which are twins, and let next(h1) = h2 and next(h2) = h1. If I keep following "next", I get a loop of length two, i.e., a polygon with only two edges. If I keep following "twin of next" starting at either h1 or h2 I get two distinct vertices v1, v2. You can draw this connectivity as a sphere with two points v1, v2 connected by an edge. The "sphere minus the edge" is your two-edge polygon. (Can you draw it?). Of course, this mesh can't be nicely visualized using planar polygons! In other words, you have valid connectivity, but can't assign nice (piecewise linear) geometry.
Slightly easier, perhaps, is the cone mesh on the next slide: here, the halfedges ij and ji are twins, but belong to the same triangle.
These are of course pretty crazy examples! Most meshes won't behave like this. But it's nice to be able to handle these "corner cases," which do come up sometimes in mesh processing. And it can simplify your code/thinking a lot to allow this very general treatment of mesh connectivity---rather than trying to handle all sorts of special cases.
keenan
@Sherwin Regarding your example with the star: the list of "next" pointers you've given traces out a single polygon with 11 sides, rather than give triangles. Also you run into trouble with the "twin" pointers: the twin of each twin should be itself, but you can't pair up twins around the center edge.
In general, it's helpful to think about the following question:
Suppose I was just given the "next" and "twin" pointers (and no vertex positions), and needed to determine the vertices, edges, and polygons from this data. What would my mesh look like?
Sherwin
Thanks for your answer! I am still confused about what you said "you can't pair up twins around the center edge". Can't we just pair each half edge with its reverse(any half edge AB's twin is BA, so AB's twin's twin is AB itself)?
So my understanding of this is:
next, you'll traverse a loop of halfedges that form a facetwin, you'll get the other "side" / halfedge of the edgenext->twin, you'll travel to the next edge, and also the other side of that edgeBut how do you get vertices from following
next->twin? Is it that each "side" of the edge is associated with one endpoint of the edge?the
twinfunction mapping a halfedge to its twin is a nontrivial involutionI think we can also get all the boundaries by checking if the halfedge does not have a twin.
@enzyme Each side of the edge is associated with one of the endpoints in a way since each half edge stores its starting vertex but not the ending vertex. I'm not sure if this answers your question, but when you follow next->twin, you wrap around a vertex and you visit all of the edges that touch that vertex.
If a vertex is on a boundary, does this break the idea of being able to get all incident edges by using next->twin? Or do we just have to be careful about which halfedge is stored in the vertex?
@ecdeo Yep, that's another way of saying all this: if you have two permutations on a set of $2n$ things, and one of those permutations is an involution with no fixed points, then you have a manifold polygon mesh.
@evannw I should have mentioned this, but the easiest way to deal with boundaries is just to make every boundary loop its own polygon, and store a flag that marks this polygon as "boundary" or "not boundary." This way, there are no special cases to check (other than checking the flag if you need to).
@tarng See my previous comment. If you add a "fictional" face for every boundary loop (and, as usual, have halfedges going around this face) then you don't need to do any special-case handling of boundary vertices. Just loop around them with twin->next as usual.
By the way, the slide should say twin->next, not next->twin!
The boundary techniques works for inside boundary it seems. However, when there is an outside boundary (which diverges) how do we handle the hypothetical faces?
@Arthas007 The boundary face here is just an internal "virtual" representation of a face and associated structures to make iteration and reasoning about boundary edges easier. What would a diverging boundary look like, and how can you have an infinite boundary? (What kind of mesh would you have to have?)
Must my twin's next and my next on different faces? In other words, can we have AB's next = BC and CB's next = BA?
I am not sure if the definitions of "twin", "next" etc themselves are also implicit conditions. If all we have are just the three conditions, then shouldn't the third geometry satisfy the conditions? (Let the center edge be AB, other five vertices be C,D,E,F,G. Then as AB->BC->CA->AD->DB->BE->EA->AF->FB->BG->GA->AB and its reverse, every he is someone's "next")
@Sherwin Nope, for instance my twin's next could be me! This example is a little hard to visualize. Consider a halfedge mesh with just two halfedges h1 and h2, which are twins, and let next(h1) = h2 and next(h2) = h1. If I keep following "next", I get a loop of length two, i.e., a polygon with only two edges. If I keep following "twin of next" starting at either h1 or h2 I get two distinct vertices v1, v2. You can draw this connectivity as a sphere with two points v1, v2 connected by an edge. The "sphere minus the edge" is your two-edge polygon. (Can you draw it?). Of course, this mesh can't be nicely visualized using planar polygons! In other words, you have valid connectivity, but can't assign nice (piecewise linear) geometry.
Slightly easier, perhaps, is the cone mesh on the next slide: here, the halfedges ij and ji are twins, but belong to the same triangle.
These are of course pretty crazy examples! Most meshes won't behave like this. But it's nice to be able to handle these "corner cases," which do come up sometimes in mesh processing. And it can simplify your code/thinking a lot to allow this very general treatment of mesh connectivity---rather than trying to handle all sorts of special cases.
@Sherwin Regarding your example with the star: the list of "next" pointers you've given traces out a single polygon with 11 sides, rather than give triangles. Also you run into trouble with the "twin" pointers: the twin of each twin should be itself, but you can't pair up twins around the center edge.
In general, it's helpful to think about the following question:
Suppose I was just given the "next" and "twin" pointers (and no vertex positions), and needed to determine the vertices, edges, and polygons from this data. What would my mesh look like?
Thanks for your answer! I am still confused about what you said "you can't pair up twins around the center edge". Can't we just pair each half edge with its reverse(any half edge AB's twin is BA, so AB's twin's twin is AB itself)?