I wonder where the 36x comes from. If we're talking about the storage cost of encoding connectivity, shouldn't it be proportional to the number of edges as well?
motoole2
@yuanzhec Yes, good question! I won't give you a complete answer (yet). :-) But allow me take this opportunity to give you a few hints on how to get there.
As mentioned in lecture, there is an important property associated with large triangle meshes that we need to compute these storage cost numbers: the ratio between the number of vertices, edges, faces in a mesh is (approximately) given by 1 : 3 : 2. That is, for every vertex in a mesh, there is approximately 3 edges and 2 faces. So with respect to the adjacency list which requires storing 3 vertex indices per face, the cost in terms of number of vertices is 6 indices per vertex, since there are approximately 2 faces for every vertex.
But where does this 1 : 3 : 2 ratio come from though? Here is a list of famous 3D models used in computer graphics; you will notice that there is consistently twice as many faces as vertices (too bad the number of edges is not listed here). This is not a coincidence.
For a closed triangular mesh, the first observation is that every edge is contained between 2 faces, and every face has 3 edges. From this, we have the following relationship of 2 * #edges = 3 * #faces. In other words, the ratio between the number of edges to faces is 3 : 2.
We can also take advantage of the Euler characteristic to determine the relationship between the number of vertices, edges, and faces. The surface of a convex polyhedron satisfy the following equation: #vertices - #edges + #faces = 2. Plugging in our ratio from before, we determine that there is 1 vertex for every 3 edges and 2 faces in a mesh.
As for the storage cost of incidence matrices and halfedge meshes, try to work them out yourself. :-) (FYI: You might get a slightly different answer.)
Doris
Is the reason for 24verstices that every edge has 2 vertices and every face has 3 edges? Since we have to store a pair of number to represent the index of the edge and vertex or the edge and face, the whole storage is about 2(32+23)*vertices.
motoole2
@Doris Got it! This is using a coordinate list (COO) storage scheme for encoding the sparse matrix. Of course, there are other ways to store a sparse matrix, all resulting in different storage cost values.
I wonder where the 36x comes from. If we're talking about the storage cost of encoding connectivity, shouldn't it be proportional to the number of edges as well?
@yuanzhec Yes, good question! I won't give you a complete answer (yet). :-) But allow me take this opportunity to give you a few hints on how to get there.
As mentioned in lecture, there is an important property associated with large triangle meshes that we need to compute these storage cost numbers: the ratio between the number of vertices, edges, faces in a mesh is (approximately) given by 1 : 3 : 2. That is, for every vertex in a mesh, there is approximately 3 edges and 2 faces. So with respect to the adjacency list which requires storing 3 vertex indices per face, the cost in terms of number of vertices is 6 indices per vertex, since there are approximately 2 faces for every vertex.
But where does this 1 : 3 : 2 ratio come from though? Here is a list of famous 3D models used in computer graphics; you will notice that there is consistently twice as many faces as vertices (too bad the number of edges is not listed here). This is not a coincidence.
For a closed triangular mesh, the first observation is that every edge is contained between 2 faces, and every face has 3 edges. From this, we have the following relationship of
2 * #edges = 3 * #faces. In other words, the ratio between the number of edges to faces is 3 : 2.We can also take advantage of the Euler characteristic to determine the relationship between the number of vertices, edges, and faces. The surface of a convex polyhedron satisfy the following equation:
#vertices - #edges + #faces = 2. Plugging in our ratio from before, we determine that there is 1 vertex for every 3 edges and 2 faces in a mesh.As for the storage cost of incidence matrices and halfedge meshes, try to work them out yourself. :-) (FYI: You might get a slightly different answer.)
Is the reason for 24verstices that every edge has 2 vertices and every face has 3 edges? Since we have to store a pair of number to represent the index of the edge and vertex or the edge and face, the whole storage is about 2(32+23)*vertices.
@Doris Got it! This is using a coordinate list (COO) storage scheme for encoding the sparse matrix. Of course, there are other ways to store a sparse matrix, all resulting in different storage cost values.