A little more Theory with your Mesh
I promised a technical post at the end of my last one, although I suppose that technical might not be the word so much as “mathy.” Last fall, I took the graduate level graphics course at my University, which was taught by Prof. Yiying Tong. The interesting thing about Prof. Tong is that he is a guru of surfaces and differential geometry, which is not my focus at all (I kick around shader code all day), but the class ended up being really interesting.
As such, I'm going to talk about some basic mathematical aspects that apply to our friend, the 3D mesh. This is the type of thing that will probably cause many rendering programmers to have violent flashbacks to "Intro to Graphics" courses, but I think people not as intimately involved in graphics might find this interesting. The entire motivation for this is because my group for a class project where we did some terrain generation with a procedurally raised race track, had no idea what our professor was talking about when he told us that our track generation always formed a star from our seed node. We thought he was talking about a star shape (you know, like the sun), and not the mathematical operation, but I'll get back to that later.
Lesson 1: The Euler Characteristic
Unless you live in a 2D only world, I'm going to bet that most of the people reading this have been living in a forest of 3D meshes for years. And I know that a lot of artists have little rules of thumb that they use for what the ratio of faces to vertices their meshes should have to figure out if there are hidden faces or holes floating around, but theres are actually some hard math behind the number of vertices, faces, and edges in a given mesh (triangular or not).
This is the Euler Characteristic:
χ = V – E + F
Less Formally:
Euler Characteristic = Vertices – Edges + Faces
Whoah, what does that mean? Back as a newbie game developer that didn't know the difference between a heap and a memory pool, I would've thought that was the least useful thing ever. However, what's interesting is that the Euler Characteristic is actually constrained based off the topology of the mesh, and not by vertex or face count as it first appears.
This is Euler's Formula:
2 = V – E + F
This is the Euler Characteristic for a sphere mesh, and more importantly it holds true for any mesh that can be smoothly deformed to a sphere has this characteristic, as does any convex polyhedra. You can think of the Euler Characteristic as being controlled by the number of “holes” in the mesh, with the number of vertices, edges, and faces dependent on the characteristic.
χ = 2 * (1 – G)
Where G is the number of holes in the polyhedron. So a sphere is a closed mesh with no holes, meaning it has a G of 0, which results in an Euler Characteristic of 2. Consider the tetrahedron:
- A Tetrahedron in Maya
A tetrahedron has 4 faces, 4 vertices, and 6 edges. It also has a G value of zero for having no holes. So:
χ = V – E + F = 2 * (1 – G)
χ = 4 – 6 + 4 = 2 * (1 – 0) = 2
χ = 2 = 2 =2
= Win!
This math holds up with other meshes and also can be proved in a variety of ways. Cool right? Direct application? – probably not, but at least you're a better person for knowing a little more math from our friend Leonhard Euler. Now go impress your friends at parties by knowing yet another Euler Formula.
Lesson 2: Closure, Link, and Star
So now I'm going to change gears a little bit and talk about some math terms that apply to meshes, but really could apply to other sets as well. Specifically, these are operations that apply to a simplicial complex. A simplicial complex is a set of simplices that follow two conditions:
- A simplex is made up of faces, and each face of a simplex is also part of the simplicial complex.
- The intersection of any two simplices in the the simplicial complex is a face of each of those simplices.
Triangular meshes, the simplicial complexes we care about, are made up of points, lines, and triangles, but other simplicial complexes can contain higher dimensional components, such as tetrahedra. So there's a mathematical concept correlating to our lists of vertices and triangles, and theres also some mathematical operators that go along with a that structure. Also note that a face of a given simplex is a lower dimensinal component that forms it. So the face of a triangle is an edge. That edge is in turn a simplex that has vertices for faces.
The Closure
The closure of a set of simplices in a simplicial complex is the smallest subcomplex that contains each simplex in the set. Now say that ten times fast. Yeah, if I read that description in a paper I would probably stop reading. But this where fancy diagrams come to the rescue! Here's a relatively basic simplicial complex made of triangles, vertices, and edges:
Consider a single edge being our entire set of simplices we are performing the closure operation on:
- S = {one edge}
Any subcomplex that contains this edge becomes part of the closure. An edge cannot exist without the two vertices so they become part of the set to form the smallest containing subcomplex:
- Cl S
The Star
The star is another simple operation on a set of simplices in a simplicial complex. And yes, my previous lack of knowledge about it last Spring led me to have a very misled conversation about what a star was during a presentation.
A star is the set of all simplices in the complex have a face in the set of simplices that the star is being computed for. Once again, taking the star of a set of simplices is also relatively straightforward once you get past all the wordage and see a picture of it in action. We'll use the same edge for set S as we did before:
- St S
The Link
Computing the link is a little bit more involved than bit more involved than computing the star or the closure alone. That is because for a set of simplices S, the link is the closure of the star of S minus the star of the closure of S. This is much easier to comprehend when visualized. We'll use the center vertex for the set S this time:
- S = {one vertex}
First consider the closure of the star of S, where the star of S will be the vertex, the 4 edges that contain it, and the 4 triangles that contain it, and then the closure will expand that to be the complete subcomplex that contains those faces, so the 4 edges and 4 vertices around the edge are added as well:
- Cl St S
And then the star of the closure of S, where the closure of S will just be the vertex again, and the star of that will include the 4 edges and 4 triangles that include the vertex:
- St Cl S
Finally, by taking the difference of the closure of the star of S and the star of the closure of S, we get the link, which in this case resembles a boundary around the triangles in containing our initial vertex:
- Lk S = Cl St S - St (Cl S - ø)
So that covers the link, star, and closure. Applications? Just like with the Euler Characteristic you could probably go on living your life without knowing them... but that would be no fun! In the context that I learned about the link, star, and closure it had relevance to types of information that might be stored in a data structure defining a 3D mesh. For instance, you might want to store the star and the link of every vertex in the mesh to be able to find the triangles and edges that surround each vertex.
You Made It! Rejoice and be silly!
Hopefully if you made it this far you actually found some of this to be interesting. If not, well you probably won't be any worse off for it. But because I'm a college student and just wrote about a whole bunch of mathematical concepts, even though college students are supposed to spend their time doing silly things... I leave you with this: a video of Kris, my roommate, convincing the chemical engineer that lives across the hall from us that "Wumbopixels" are the metric equivalent to Megapixels. Luckily this conversation was captured by another guy at the the table learning how to use the video feature of his fancy new phone.
He believed that "Wumbopixels" were real for several days before we finally decided that we should inform him of the truth before the damage could become permanent :)