Using the storage idea on this slide, what could be the size of the data needed for storing this David mesh?
keenan
@ChrisZzh You tell me! :-). Let's say the mesh contains 1 billion polygons, all polygons have four sides, and all vertices have three coordinates. Also, assume that the coordinates are stored in double precision, i.e., 64-bit floating point. Can you give me a close estimate of the exact storage needed for this mesh? Is it possible to get this number 100% correct, or do you need additional information?
ChrisZzh
I guess additional information such as an indexing system is needed to speed up certain processes like the examples you mentioned in class.
mdsavage
I'll take a stab at it. Let's say we store literally only the raw matrices, as shown on the slide.
First, we need how many unique vertices there are.
It doesn't look like there are any holes that go all the way through this model of David, so the model should topologically be a surface of genus 0. We can think of the polygons as being the faces of an embedding of a graph on this surface, where the vertices and edges of the graph are the vertices and edges of the polygons. Then, by Euler's formula, we know that V - E + F = 2.
Hmm... but then we need to know E to solve for V. Let's apply more graph theory.
In a planar triangulation, E = 3V - 6; this is also true for a triangulation on a sphere (this can be shown with stereographic projection), and therefore any surface of genus 0. Therefore, if we add one more edge to every face in order to subdivide it into two triangles, the resulting graph will have that many edges. This gives us E + F = 3V - 6.
Adding these two equations together, we get V + 2F = 3V - 4, or after reorganizing, V = F + 2. (It shouldn't be too surprising that V and F are very close together; consider tackling the same counting problem on a cylinder.)
Armed with this knowledge, we can make a good estimate.
To store the vertices: ((F + 2) vertices) * (3 coordinates/vertex) * (8 bytes/coordinate) = (24F + 48) bytes
To store the polygons: (F polygons) * (4 vertices/polygon) * (4 bytes/vertex) = 16F bytes
Note that we can reference each vertex with 4 bytes since there are fewer than 2^32 of them, and also that we assume the densest possible representation (so that we don't have to worry about any address alignment or similar issues).
This gives us a total of (40F + 48) bytes. Substituting in 1 billion for F, we get 40000000048 bytes, or approximately 37.25GiB.
keenan
@mdsavage Terrific! Yes, Euler's polyhedral formula is definitely the right tool here. (By the way, if you like this kind of stuff you might be interested in my course in the spring---you've already done part of the first homework. :-))
Using the storage idea on this slide, what could be the size of the data needed for storing this David mesh?
@ChrisZzh You tell me! :-). Let's say the mesh contains 1 billion polygons, all polygons have four sides, and all vertices have three coordinates. Also, assume that the coordinates are stored in double precision, i.e., 64-bit floating point. Can you give me a close estimate of the exact storage needed for this mesh? Is it possible to get this number 100% correct, or do you need additional information?
I guess additional information such as an indexing system is needed to speed up certain processes like the examples you mentioned in class.
I'll take a stab at it. Let's say we store literally only the raw matrices, as shown on the slide.
First, we need how many unique vertices there are.
It doesn't look like there are any holes that go all the way through this model of David, so the model should topologically be a surface of genus 0. We can think of the polygons as being the faces of an embedding of a graph on this surface, where the vertices and edges of the graph are the vertices and edges of the polygons. Then, by Euler's formula, we know that V - E + F = 2.
Hmm... but then we need to know E to solve for V. Let's apply more graph theory.
In a planar triangulation, E = 3V - 6; this is also true for a triangulation on a sphere (this can be shown with stereographic projection), and therefore any surface of genus 0. Therefore, if we add one more edge to every face in order to subdivide it into two triangles, the resulting graph will have that many edges. This gives us E + F = 3V - 6.
Adding these two equations together, we get V + 2F = 3V - 4, or after reorganizing, V = F + 2. (It shouldn't be too surprising that V and F are very close together; consider tackling the same counting problem on a cylinder.)
Armed with this knowledge, we can make a good estimate.
To store the vertices: ((F + 2) vertices) * (3 coordinates/vertex) * (8 bytes/coordinate) = (24F + 48) bytes
To store the polygons: (F polygons) * (4 vertices/polygon) * (4 bytes/vertex) = 16F bytes
Note that we can reference each vertex with 4 bytes since there are fewer than 2^32 of them, and also that we assume the densest possible representation (so that we don't have to worry about any address alignment or similar issues).
This gives us a total of (40F + 48) bytes. Substituting in 1 billion for F, we get 40000000048 bytes, or approximately 37.25GiB.
@mdsavage Terrific! Yes, Euler's polyhedral formula is definitely the right tool here. (By the way, if you like this kind of stuff you might be interested in my course in the spring---you've already done part of the first homework. :-))