There are different formats for polygon models, sometimes called polygon soup. Most common are formats are based on triangles, so far the most common way of representing meshes. Triangles are the smallest and explicit entry to span a plane, they are easy to work with and very well-supported by the graphics hardware. Triangle meshes are a form of boundary representation (B-rep) that separates topology and geometry. I hope that you remember the Euler-Poincare
V - E + F - ( L - F) - 2 (S - G) = 0
Lets elaborate the above notations:
- V - number of vertices.
- E - number of edges.
- F - number of faces.
- L - number of loops.
- S - number of shells.
- G - genus.
A loop is the unique ring( along edges ) in the mesh. For triangle meshes this simplifies loop counting a lot. Since there is exactly one loop within each face, as shown in the following figure, the number of loops is equal to the number of faces, L = F.
 |
| Loop counting for polygons. the left one is a triangle with one loop and to the right is a polygon with two loops |
Furthermore, we normally only work with one shell (S = 1)
V - E + F - 2(1 - G) = 0
The above allows for easy classification of the genus of a closed manifold mesh.
Mesh formats
In the following i shall use the above abbreviations, and also assume an entity Vertex defined such as
Here, i assume that the storage space for each float is 4 bytes. This is true for most of the platforms. In the simplest form a triangle mesh can be described by
where every face stores its corresponding vertices. It is simple to see the memory footprint of this data structures is 3*F* sizeof(Vertex) = 36F bytes per mesh. It is also clear that this data structure has a large degree of redundancy, since many vertices will be duplicated. If we get rid of the vertex redundancy we get another mesh structure as follows:
The above data structure uses V * sizeof(Vertex) = 12V bytes for the geometry and 3 * F * sizeof(Vertex*) = 12F for the topology. It can be shown that the relationship between the number of vertices and the number of faces is
for the triangle manifold mesh. Using this relationship we calculate the necessary memory usage to 18F bytes per mesh, roughly halving the size. This is considered as the lower limit for the data structures with random access to individual triangles. The two above mentioned mesh data structures are fast when it comes to linear traversal through the triangles, for example when rendering. But consider the neighborhood information; how can we access neighboring triangles from a given vertex ? For the simple mesh data structures we have provided so far, we need to search through the whole face list and find all the triangles containing this vertex. This is O(F) operations, and linear might not be so bad, but if this needs to be done for every vertex it becomes O(V(F)) which is quadratic in complexity. The following rendered image is structured with simple mesh we have described so far.
 |
| Stanford Bunny generated with SimpleMesh Data structure |
This has motivated a lot of research into the alternative mesh data structure that trade memory consumption for the faster neighborhood traversal. Half-edge, winged-edge, directed edge, are some of the examples of this.
I think i have taken a while to get to the core of this post. My apology if you are bored!!
The mesh formats considered so far have stored information vertices and faces ( triangles ). To get more efficient access to the neighborhood, we may also add edge information to the mesh. One of the most common ways of doing this, is using the so called half-edge data structure as shown in the following figure:
 |
| Half-edge data structure as seen from the bold half-edge |
It is called half-edge because every edge is split down to its length, so that only information about the left face is stored explicitly. Information about the "right" face can be accessed through the half-edge's pair. The following listing will elaborate more of this data structure:
 |
| Half-edge data structure |
To walk around the left face, i can use the next and prev pointers which will take you to the half-edges surrounding that face. Explicit information is indicated by the blue lines in the figure, whereas dashed lines show implicit information which can be accessed through the pairs. I am using the convention of using counter clockwise orientation of faces.
In the above code listing, i augment each Vertex with a half-edge pointer edge. Note that there is several possible half-edges connected to a single vertex, but it does not matter which half-edge we choose. In any choice, given a vertex, we can now access information about the topological neighborhood through this half-edge. Similarly, each Face is also augmented with half-edge pointer edge, which can be any of the face's edge. For the triangle mesh, this structure needs
bytes per mesh. Furthermore, it is limited to manifold meshes since every edge must have two faces. in order to represent non-closed geometry with borders we need to allow storage empty faces, usually initiated by NULL pointers to the left face. Note that this data structure contains redundancies. For example, since we are dealing with triangles we know that edge prev equals to next->next. Another possible data reduction is to not store faces explicitly but instead letting every three edges implicitly define a triangle. However, this does not allow us to store additional face information like colors, etc.
Differential properties deal with how a surface changes. The simplest of the geometric differentials is the normal vector which has the property of being perpendicular to a small local surface neighborhood. Approximating the triangle as sufficiently small we can use it as a support plane. Given counter clockwise orientation of vertices in a triangle, when viewed from the outside of the manifold, we can construct a plane normal as the cross product (v2 - v1) and (v3 - v1). This forms a vector with the desired properties, perpendicular to the plane spanned by the three vertices and pointing outwards. This is however, is only enough to do the flat shading and clearly shows the linear property of the mesh as follows:
 |
| Flat and Smooth shading |
By assigning normals at vertices and interpolates across the triangle we can squeeze some extra smoothness out of the linear surface. There exist many techniques for doing so, the easiest one being weighted equally defined as the normalized sum of the adjacent face normals.
N1(i) is called the 1-ring neighborhood, and is simply all the faces sharing the vertex vi. Interpolated normals do not change the surface, they only effect lighting calculations.
Once i calculate the normals along with the half-edge data structure i get the following output :
 |
| Stanford Bunny with Half-edge Data structure |
So far i assume the the half-edge mesh data structure we have represented is closed, all loops will eventually be inner loops, there fore it is enough to set the half-edge pointers for the inner loop. In order to represent the non-closed surfaces with boundaries we need to correctly set the outer half-edge loop after adding the triangle. We quickly see that there are 4 different cases as follows:
- The new triangle has 3 border edges. This triangle is the entire mesh as follows:
- The new triangle has 2 border edges.
- The new triangle has 1 border edges.
- The new triangle has 0 border edges. This corresponds to a triangle that fills a hole in the mesh.
I get the following bunny with many holes once i check the above conditions while traversing the mesh represented by the half-edge mesh:
 |
| Stanford Bunny with holes in it represented by the half-edge data structure |
No comments:
Post a Comment