Is there a data structure that is easy to add/remove elements and can also do nonmanifold geometry?
StickyBitz
I'm sure you could compromise to allow nonmanifold geometry through some sort of 'sorted' list of faces/vertexes/edges that can be looked-up in less than O(n) time - But does something like this already exist?
ryanmelon
I noticed that although half edge could not represent nonmanifold geometry, the operations on a manifold mesh represented by half edges could create nonmanifold geometry. For example, there's a cylinder while a circle of edges on the middle. If you collapse all the edges, it will create a nonmanifold mesh, which may also vary, depending on the implementation.
Lavender
I think this table gives us a good sense of the advantages of the three mainstream data structures for representing meshes
msfernan
How do you get the calculations for storage?
ilovecg
I am reviewing the comments for Fall 2019 and I want to know why the ratio between the number of vertices, edges, faces in a mesh is (approximately) given by 1 : 3 : 2?
Max
@ryanmelon not exactly - a (valid) halfedge mesh always represents a manifold surface. In the situation you describe, the center loop isn't collapsed to a single point -- it still contains one edge, so it only renders like a point. But really, from a connectivity perspective the inside of the cylinder could still have 'volume,' so the region around the point is not necessarily non-manifold. You can try this out yourself, and you should find that the twin-next relationship about the center point is actually preserved.
@msfernan These are just approximations based on how many values you may have to store - the first could just be 3 vertex indices per triangle, the second might be 5 or so sparse matrix entries, and the third could be a vertex, 3 edges, 2 faces, 6 halfedges (vertex/edge/face/twin/next each), which is 36 values.
@ilovecg One way to think about this is considering that the only way to add elements to a strictly triangular mesh, and keep it triangular, is to sub-divide a triangle into three. This operation adds one vertex, three edges, and two new faces. In the limit, adding elements at these rates gives the global ratio.
Is there a data structure that is easy to add/remove elements and can also do nonmanifold geometry?
I'm sure you could compromise to allow nonmanifold geometry through some sort of 'sorted' list of faces/vertexes/edges that can be looked-up in less than O(n) time - But does something like this already exist?
I noticed that although half edge could not represent nonmanifold geometry, the operations on a manifold mesh represented by half edges could create nonmanifold geometry. For example, there's a cylinder while a circle of edges on the middle. If you collapse all the edges, it will create a nonmanifold mesh, which may also vary, depending on the implementation.
I think this table gives us a good sense of the advantages of the three mainstream data structures for representing meshes
How do you get the calculations for storage?
I am reviewing the comments for Fall 2019 and I want to know why the ratio between the number of vertices, edges, faces in a mesh is (approximately) given by 1 : 3 : 2?
@ryanmelon not exactly - a (valid) halfedge mesh always represents a manifold surface. In the situation you describe, the center loop isn't collapsed to a single point -- it still contains one edge, so it only renders like a point. But really, from a connectivity perspective the inside of the cylinder could still have 'volume,' so the region around the point is not necessarily non-manifold. You can try this out yourself, and you should find that the twin-next relationship about the center point is actually preserved.
@msfernan These are just approximations based on how many values you may have to store - the first could just be 3 vertex indices per triangle, the second might be 5 or so sparse matrix entries, and the third could be a vertex, 3 edges, 2 faces, 6 halfedges (vertex/edge/face/twin/next each), which is 36 values.
@ilovecg One way to think about this is considering that the only way to add elements to a strictly triangular mesh, and keep it triangular, is to sub-divide a triangle into three. This operation adds one vertex, three edges, and two new faces. In the limit, adding elements at these rates gives the global ratio.