Friday, February 18, 2011

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:

  1. A simplex is made up of faces, and each face of a simplex is also part of the simplicial complex.
  2. 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:

Closure of S
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:

Star of S
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:

A Vertex
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:

Closure of Star
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:

Star Of Closure
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:

Link
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.

http://vimeo.com/19692054

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 :)

Thursday, February 3, 2011

“Serious” Developments

Today is my first #AltDevBlogADay post, so I suppose a short introduction is in order to preface my post. Currently, I am a computer science student at Michigan State University and a game programmer for the Games for Entertainment and Learning Lab. In the GEL Lab we generally develop serious games for contract or research purposes, and this post is going to be about an aspect of serious game development that I think is often not realized.

If I were to ask any random developer as to why developing serious games is challenging, I think I would typically get a response about the game design challenges associated with serious games. While it's no cakewalk to try to make a game that is both fun AND teaches the player some other skill (such as financing a car or managing a power plant), there are some very likely pitfalls that will inevitably impact the entire team beyond the designers.

You can't go it Alone

The issue that I think often goes overlooked is that because an average game developer is just an expert at making games, a serious game developer will have to consult an external source that is an expert in the subject matter of the game. More often than not, that source of expertise is also the source of funding for a serious games project. An example is a company contracts a developer to make a game about workplace safety, and the developer will have to work with them to understand what that actually entails.

“The Client”

This places people outside of the development team, who typically know very little about game or even software development, in a very powerful position. The delicate relationship that arises out of this is, in my opinion, potentially more intricate than that of the developer-publisher relationship. Personally I suspect it is more like working with an IP holder on licensed work because they care much more about how their content appears in the game. Often if the client wants to be too hands on, the game ends up not being fun, but if the developer just runs wild, the game could end up not teaching the players what it's supposed to, which is just as much of a failure in serious game development. It has to be a symbiotic relationship to result in a successful game, and I've compiled a couple of pointers from my personal experiences from the past couple of years.

  1. Figure out if the client understands what a fun game is, even if they don't know how to make one. If they do, make playable versions of the game a high priority. If you're on the right track with your game , make sure your client can play it and be on the same page as you, or else they might demand you scrap your work and change directions without giving your hard work a chance.

  2. Be ready for change. If the game isn't meeting its goals, the design team is going to want a change, and that change is necessary. Huge design changes are in, my opinion, much more likely when you have to teach the player about something typically less than fun. Convincing the client that the change is needed can be hard though if they are worried about meeting deadlines, especially if your code base won't easily adapt to the new direction. Or the change could come at the demand of the client, which could be even more drastic, as one meeting can leave you commenting out half of your code base.

  3. Be afraid if your designers and client don't get along. You might notice that the client is portrayed in polar opposites in the past two points (wanting change and not wanting change), yet both can happen on the same project. Anything less than a good relationship between your designers and your client is an early sign of approaching trouble. As I said before, a successful serious game needs a balance between the entertainment and the game's subject matter.

  4. Keep in mind that sales is not the goal of the project. From a client's perspective, a failure to meet the goals doesn't always result in financial trouble. It can result in the client looking to fund a “do-over” of the project. If you didn't obey point #2 is reworking the entire game going to be a nightmare? This is especially possible if the project was funded by grants. A failure of one project just means that it is the basis of the next grant proposal to fund the fixing of the first game's shortcomings.

So there, a little peak into the world of serious game development. I've begun to wonder if the challenge of separated expertise is one of the reasons why it seems that there is a high concentration of serious games that are quite good at what they do because their purpose is to teach the player about game design.