It seems like there is a lot of extra work involved to flip edges that touch old and new vertices. Would it be possible to just place new vertices at the midpoints of the edges, and then connect them? Or would doing that violate rules about making sure that every face is a triangle?
Arthas007
I have trouble understanding why spilting edge result in the figure above
keenan
@enzyme Yes, you can definitely do that. For instance, you could just write a method subdivideTriangle that does all the low-level halfedge manipulations to insert three vertices in the edges of a triangle, delete the middle triangle, allocate the four new triangles and three new edges, and the 12 new halfedges, and connect up all the pointers. After doing that, you'd have to think about how to subdivide the neighboring "triangles" because they're no longer triangles: they're now quadrilaterals (you inserted the midpoint of one of their vertices). So you'd also have to keep track of which vertices were "original" and which were "new," and generalize your subdivideTriangle routine to only split edges where there's not already a new vertex in the middle.
...this is the motivation for doing it in terms of edge splits and flips. In general it's a win if you can break down a higher-level algorithm into lower-level algorithms that can be more easily implemented (and verified).
keenan
@Arthas007 Think about splitting the edges sequentially. In fact, try drawing a single triangle, then doing edge splits to insert the three midpoints of the three original edges. Maybe that clears it up?
It seems like there is a lot of extra work involved to flip edges that touch old and new vertices. Would it be possible to just place new vertices at the midpoints of the edges, and then connect them? Or would doing that violate rules about making sure that every face is a triangle?
I have trouble understanding why spilting edge result in the figure above
@enzyme Yes, you can definitely do that. For instance, you could just write a method
subdivideTrianglethat does all the low-level halfedge manipulations to insert three vertices in the edges of a triangle, delete the middle triangle, allocate the four new triangles and three new edges, and the 12 new halfedges, and connect up all the pointers. After doing that, you'd have to think about how to subdivide the neighboring "triangles" because they're no longer triangles: they're now quadrilaterals (you inserted the midpoint of one of their vertices). So you'd also have to keep track of which vertices were "original" and which were "new," and generalize yoursubdivideTriangleroutine to only split edges where there's not already a new vertex in the middle....this is the motivation for doing it in terms of edge splits and flips. In general it's a win if you can break down a higher-level algorithm into lower-level algorithms that can be more easily implemented (and verified).
@Arthas007 Think about splitting the edges sequentially. In fact, try drawing a single triangle, then doing edge splits to insert the three midpoints of the three original edges. Maybe that clears it up?