Image Space for Beginners

I'm doing a relatively simple post today because I've had way too many milestones and sleepless nights in the past 7 days. This is why I'm going to talk about a very basic concept for graphics programming: doing image space calculations and effects. I realize that there are many seasoned game developers that frequent this blog, but this one is for the ones who are just getting started.

Tools and Motivation

As a developer of a real-time graphics technology (video games), you are almost certainly going to be making use of a GPU to accelerate your graphics processing. The GPU exploits high parallelization of rendering to speed up its work, and is responsible for transforming your 3D world into a 2D plane that is displayed to the player on their computer scene. However, not all effects are easy to simulate in a 3 dimensional space. Thats where leveraging further work on the GPU to perform additional image space calculations can come in handy. Some of these are quite obvious, such as depth of field calculations, being that depth of field is an artifact of lenses. Other popular image space effects include motion blur, color correction, and anti-aliasing. Image space calculations are also the foundations of deferred shading and lighting, rendering techniques that are becoming increasingly popular to handle a large number of lights in a scene.

The Actual Technique

Image space calculations can be performed on the CPU, but as with most things in graphics that would slow and booorrrriiinng (unless you're playing with SPUs, in which case carry on). The main point is that iterating over an image in the main thread while performing per-pixel calculations on the CPU would most likely be in bad taste. Instead you might consider the following GPU based solution:

  1. Render your scene normally, except to a texture if you are not already.
  2. Render a quad that covers the entire screen, with the texture from the previous step as a texture applied across the quad.
  3. Perform your calculations in the shader code used to render that full screen quad, modifying the how the texture is applied.

There are several catches with this that you have to keep in mind. First and foremost, each fragment's calculations cannot be too dependent on other locations on the screen. If you have to sample your frame many times, then those texture accesses will quickly add up, which is one of the big considerations that comes into play when performing screen space blurs. Secondly, while this might provide an effect for much cheaper than trying to model a similar effect in 3 dimensional space, keep in mind the actual performance is dependent on the resolution of the screen, which may be less than desirable. As resolution increases, so does the number of fragments being processed. In the end, it's all about picking when and where to perform different calculations in your game.

An Example

Here's a sample of a very simple post-processing fragment shader, written in CG. It does a simple screen space distortion based off of the x and y channels of a texture. The vertex shader doesn't do anything particularly special other than set up uvs that are interpolated from 0 to 1 across the quad. In general, most of the action happens in the fragment shader when doing post-processing.

uniform sampler2D _MainTex;

uniform sampler2D _DistortionMap;

uniform float _Distortion;

float4 frag (v2f i) : COLOR

{

float2 distortedOffset = (tex2D(_DistortionMap, i.uv).xy * 2 - 1);

distortedOffset *= _Distortion;

float2 distortedUV = i.uv + distortedOffset;

return tex2D(_MainTex, distortedUV);

}

The shader itself is really only a few lines of code! So easy! Here's what is happening a little more in depth. The float2 “distortedOffset” is simply the interpolated uv coordinate plus a lookup into the normal map which is then unpacked to fit into the range [-1,1] instead of the [0,1] range returned by tex2D(sampler2D, float2), which is then finally multiplied by _Distortion to control the strength of the distortion. Finally, a lookup into sampler2D MainTex is performed, where _MainTex is the previously rendered image. If there is no distortion, then the call would be equivalent to tex2D(_MainTex, i.uv), which would just copy the source image's color to the new target. Speaking of targets, you might consider rendering this post-processing pass into a texture as well, besides just your initial rendering of your 3D scene. This is so that you can pump the output of this post-processing into another post process you are implementing to be able to stack effects on top of each other.

Here is a sample of this particular distortion shader in action.
The original rendered scene:

Before Post-Processing

Texture that the distortion is calculated from in the shader:

Distortion Map

The final result:

After Post-Processing

Conclusion

Great success! The important question here should always be: how hard/expensive would it be to achieve the same effect in a different space? What do you gain/lose by doing it in image space? And also important is the question of whether or not this actually makes your game look any better. In the end, I personally think that post processing is great fun, especially used in terrible crazy ways on personal projects. You never know what you'll come up with when you play around with ideas in a different space, for example here's one paper exploring the possibility of moving skin rendering into screen space:http://jbit.net/~sparky/subsurf/cbf_skin.pdf. Finally, fun fact of the day: I modeled and textured that fish in the sample images way back when I was a Freshman, which is why it's so shoddy and terrible.

Moving beyond the Linear Bezier

Every beginner game programmer becomes familiar with the concept of needing to move from a value between point A to point B. It comes up all the time in game programming, especially as you sit there trying to figure out how to do something as simple as move a box across the screen. It is then that they learn about the linear interpolation (abbreviated to "lerp") as a way to smoothly fade between two values, finding any point between them with a simple [0,1] t value. The formula is simple:

Lerp(t) = (1 - t) * StartPoint + t * EndPoint

And before you know it, those beginner programmers are Lerping all over the place, using it to help overcome all sorts of challenged in game development from moving an object in 3D space to fading between two audio clips. In reality, this is actually just accomplishing one thing- it is just a straight line segment, reworked into a form that makes it easy to sample any point on that line. Anyone that's taken high school level math knows that there is more to life than just straight lines. What if we need a curve?

So let's consider how we might go about making this curve. An approach that I've seen many beginner programmers, including myself, to try to get around the problem by stringing several lines together as an approximation. This might be alright in some situations, but it fails in many. For one, it requires the placement of a lot of points and then storage of that data, which can be painful. Secondly, and perhaps more importantly, it will suffer from being jagged. Maybe at a certain distance we will have enough points that it will appear smooth enough, but when examined closely enough the lack of smoothness will always become apparent (unless the number of points approach infinity).

Enter: Bezier Curves

Moving to a more complex equation can allow us to overcome these difficulties. We know we can create curved functions with polynomial equations, but does this actually help us? We can write these as parametric equations much like the linear interpolation equation shown above, but we don't want to write a new equation each time we want to generate a curve. We want to generate different curves between points, not just the same curve between them each time. Before this was not an issue, as we only ever used a straight line. What we can do is store additional data that factors into our equation with additional data points beyond just the start and end points of the curve. This is where quadratic and cubic bezier curves come into play.

If you're new to bezier curves, you may find them a little intimidating due to the implication that there is some more complex math happening. I used to think they were outside my league of math just because Adobe has released entire applications based around drawing with bezier curves. Little did I know that I already used the 1st-degree, linear bezier equation all the time. Here it is:

LinearBezier(t) = (t - 1) * StartPoint + t * EndPoint

As you can probably tell, the linear bezier is actually just the linear interpolation equation. Higher degree bezier curves introduce control points into their equations and the math only gets a little bit worse, but the similarities are still very visible to our friend linear interpolation.

These 2nd and 3rd degree bezier curves can be defined as:

QuadraticBezier(t) = (1 – t)^2 * StartPoint + 2(1 – t) * t * ControlPoint + t^2 * EndPoint

CubicBezier(t) = (1 – t)^3 * StartPoint + 3(1 – t)^2 * t * ControlPoint1

+ 3(1 – t) * t^2 * ControlPoint2 + t^3 * EndPoint

Let's look at what happened. Our computations are a bit more expensive, but can now craft more intricate curves. These equations allow for the manipulation of continuously defined curves between the start point and end point by adjusting our control points. Take a look at a couple of shots showing examples of these:

A Quadratic Bezier Curve

A Cubic Bezier Curve

The interface for modifying these curves is quite simply the same as the start and end points of a line, being that a control point is just another point in the same vector space as our start and end points. Increasingly complex curves can be generated with higher degree bezier curves, but we don't actually want that because the computation becomes increasingly expensive and the increases in control points can become cumbersome. This is where turning to piecewise equations becomes a good solution.

B-Splines

Quadratic and cubic bezier curves do offer a lot more flexibility, but they also offer something else, the ability to be chained together without losing continuity, forming a piecewise function for your curve. So instead of using higher degree equations to create more intricate curves, we can create a series of cubic bezier curves and restrict them a bit to meet continuity requirements. Just as a refresher, a function meets different levels of continuity based depending on how many derivatives of the function are continuously defined. The previously mentioned chain of straight lines only has a continuity of C0, meaning that all points along the spline are defined, but because it lacks C1 continuity, the first derivative is not continuously defined. The more derivatives that are continuously defined, the smoother our curve will be, but it will also result in less and less control over the spline as a consequence.

Now that we have moved to a chain of cubic bezier curves, we can easily obtain C1 continuity by requiring that the line formed between an end point and the second control point, is the equal and opposite of the start control point on the curve that is being transitioned to. This looks like this:

Piecewise Bezier with C1 Continuity

However, even with that restriction we can still have relatively sharp corners occur. If we require a smoother curve, we can convert our piecewise curve to a B-spline. This will allow us to achieve C2 continuity, meaning that the second derivative is continuously defined. Our bezier control points are now moved to being controlled by a new set of points known as deBoor points. A cubic bezier curve that always has C2 continuity will be defined by these deBoor points. Perhaps the biggest drawback is that the start and endpoints of a segment are no longer directly controllable either, but it is still relatively easy to work with from just the control points. Here are the equations for the generating the cubic bezier from the deBoor points, note that I name the variables based off of examining a particular segment in the spline:

CubicControlPoint1 = (2 * deBoorStartPoint + deBoorEndPoint) / 3

CubicControlPoint2 = (2 * deBoorEndPoint + deBoorStartPoint) / 3

CubicStartPoint = (deBoorPreviousStartPoint + 4 * deBoorStartPoint + deBoorEndPoint) / 6

CubicEndPoint = (deBoorStartPoint + 4 * deBoorEndPoint + deBoorNextEndPoint) / 6

We can then build our cubic bezier with these values. These relationships are a lot easier to visualize in a picture:

A B-spline defined with deBoor Points

As you can probably see, these are a bit more mathematically involved than just a bezier curve. They are still relatively easy to manipulate through the deBoor points, and they have the added benefit of not requiring any additional data beyond that of a bezier curve and any bezier code that you currently have can be fit to work as a B-spline. This is exactly what I did when I most recently used B-splines to obtain C2 continuity on a project, I took advantage of the fact that the deBoor points could control the cubic curve entirely tool-side, while my in-game bezier code functioned exactly the same.

Conclusion

As you can see, math is fun and can lead to better better solutions to the engineering challenges in game development. Bezier curves naturally extend into many areas, and many useful uses have been cooked up for them. For a really great example of bezier curves at work, check out this article from GPU Gems 3 about rendering vector graphics on the GPU:http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html. Keep in mind that all this awesomeness comes with the cautionary wisdom that moving to higher degree curves is not always worth the increased computational complexity. As always, make sure you evaluate what the right tool is to get the job done.

Resources for the Aspiring Game Programmer

A little while back I was asked to put together a list of some resources for people interested in learning game programming at a professional level. These are some of the most useful resources I've found, many are straight from my book shelf / browser history. I'll try to remember to update this if I come across new things. Feel free to ask question or make suggestions in the comments.

Books:

Game Engine Architecture by Jason Gregory:

A good read for anyone looking to go into game development professionally, covers many topics related to 3D game development, and covers many of the topics that could be covered in typical game programming interview or programming test.

http://www.amazon.com/Game-Engine-Architecture-Jason-Gregory/dp/1568814135/ref=sr_1_1?ie=UTF8&qid=1300117839&sr=8-1

Programming AI by Example by Matt Buckland:

An excellent introduction to programming game Artificial Intelligence, something which is quite different from AI in an academic setting, as is the case with the class offerings.

http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782/ref=sr_1_1?s=books&ie=UTF8&qid=1300118409&sr=1-1

Artificial Intelligence for Games by Ian Millington:

Another AI book that is structured more like a traditional textbook. Makes for a good reference.

http://www.amazon.com/Artificial-Intelligence-Games-Second-Millington/dp/0123747317/ref=sr_1_1?s=books&ie=UTF8&qid=1300118482&sr=1-1

Real-Time Rendering by Tomas Akenine-Moller:

The definitive text on graphics in real-time applications, I have rarely met a graphics programmer that hasn't read this cover to cover. Very math and theory heavy, light on code.

http://www.amazon.com/Real-Time-Rendering-Third-Tomas-Akenine-Moller/dp/1568814240/ref=sr_1_1?s=books&ie=UTF8&qid=1300118547&sr=1-1

Real-Time Collision Detection by Christer Ericson:

Perhaps the most popular book on Collision Detection in games.

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=wl_it_dp_o?ie=UTF8&coliid=I2I02492N3ZKNN&colid=1PXQOGX25DY1T

Essential Math for Games and Interactive Applications by James M. Van Verth:

An Excellent reference on common mathematical concepts that repeatedly come up in 3D game development.

http://www.amazon.com/Essential-Mathematics-Interactive-Applications-Second/dp/0123742978/ref=sr_1_2?s=books&ie=UTF8&qid=1300118975&sr=1-2

Web Resources:



Unity 3D:

Unity is a free 3D game engine that is used in the Game Specialization and several research labs at MSU. Easy to pick up, well documented, and has a strong online community:

www.unity3d.com

NVIDIA Developer Zone:

NVIDIA has several free books available in their developer zone. These often have excellent information that applies across all hardware and are not just NVIDIA's, this includes the excellent GPU Gems series.

http://developer.nvidia.com/page/home.html

Unreal Development Kit:

UDK is a free to use version of the well known Unreal Engine. It is a bit larger and harder to use than other engines (Unreal is meant to be used by large teams at professional studios), but experience with it looks quite good with studios that use it (Gearbox, Irrational, Epic, etc).


http://www.udk.com/

AltDevBlogADay:

AltDevBlogADay is a collective blog run by Mike Acton, the Engine Lead at Insomniac. It features daily articles from programmers all across the industry:

http://www.AltDevBlogADay.org

Gamasutra:

The most official news site for the games industry:

http://www.gamasutra.com

Game Career Guide:

This is a sister site to Gamasutra that features articles for aspiring game developers:

http://www.gamecareerguide.com


Students and Quality of Life

The basis for this post is partly me realizing that I rant about bits and pieces of being a game development student on a semi-frequent basis, and partly because GDC is keeping me from fully fleshing out a more technical post. So as a result, I decided to compile together some of my thoughts about what being a student is like these days and what sorts of possible implications it might have for the future. I met up with @MikeActon and a few other #AltDevBlogADay contributors at a cigar bar earlier this week in the gigantic blur that was another GDC. Myself and Shawn (@qtbon), the other half of the programming team in the GEL lab, were the only current students in attendance.

Shortly after we arrived the conversation turned to quality of life, something that Mike has been talking about quite a bit as of late, including an excellent presentation at Game Forum Germany. One of the points brought up was that the huge influx of students interested in game development allows companies to basically burn through their employees and easily refresh themselves from a deep pool of people desperately looking for work. I didn't end up contributing my thoughts on the subject from a student perspective, but I later realized that maybe I did have a relevant perspective to add to the discussion. Especially because I'm currently in the weird spot in my life where I've found myself fitting into many different sides of the fence dividing developers and those aspiring to become developers, which as a warning, might make me sound like I jump perspectives a few times throughout this. I might be wrong about some of this, so feel free to flame me in the comments in that case :)

When Start-ups are “Safe”

I attended GDC with a handful of other Michigan State students this week, many of which are actively in the hunt for jobs. However, Shawn and a couple others weren't looking for work because as their current projects wrap up and they begin to graduate, they've decided to form Adventure Club Games, a start-up, doing a combination of contract work and smaller independent projects. They've already landed a few serious games related contracts through the professors with grants at the university, so they may be well on their way to surviving the first year as a start-up.

What worries me is that some of the students looking for jobs have told me this week that they feel that the guys involved in Shawn's company have the “safe bet.” This is quite honestly one of the most terrifying things that I have ever heard students say. I'm intentionally not letting myself get roped into Shawn's company, even though they're all great guys and I know they'd be excited to have me on board. I've been involved in two start-ups in the past (not all game related), and I think that the stress that comes along with that could quite honestly kill me at this point in my life. Going into an industry where a start-up feels like a safer bet than finding a job is just... unbelievable.

Let's circle back real quick to what I mentioned earlier, this conversation started because we were talking about crunch, and the thought that there is an endless pool of fresh talent ready to get killed in a vicious cycle of burnout is quite troubling. These kids would work well over 80 hours a week and throw themselves under a bus for the opportunity to work on “game X,” and they still feel like it would be easier to get involved in a start-up. In my experience, being in a start-up is a whole different devil, it's a world where the crunch is endless because the sole determinant of success is yourself. The amount of time you spend on your work is a bottomless pit of stress, business, and development, but the reward is that you get ownership and control. People at Mike's get together mentioned staying with a death march development because of loyalty to the studio or loyalty to the project, but think about it, in a start-up, you are the entire show. You either rise or die, and it's a very difficult thing to do. To see students thinking starting a business as a more secure temptation than sticking through the hurdles of landing a job with an established studio- it shows just how crazy this all is.

I feel like students might be getting the wrong messages from the industry as to what should be expected of them. After spending time in the career pavilion, several students told me that they basically felt like 4 years of college had absolutely no relevance to them getting a job. Something is not right if people feel like that, especially if they're part of a program that is apparently ranked among the top in North America. We don't want people to drop out of school and try to make games in their basements. We want people to rise above their degrees and push their programs to new heights, even if the piece of paper you get at the end isn't as important as what you learned along the way. Game development education is still in its infancy, we need to be encouraging programs to grow and mature.

To be a Student

This all really gets to me because I think that this perception finding work as a student game developer being impossible might be having a negative impact on the the student culture as a whole. This ties back into how uncomfortable it makes me when design students want to make games that are marketable instead of games that are art. Are we suffocating creativity out of students? I always thought design students would be stubbornly optimistic about games as art, wanting to experiment and create as they find themselves suddenly empowered to create virtual worlds. Shouldn't students be encouraged to make use of their time in college to experiment and take risks? They're getting an opportunity to make the games they want to make, as they exist in an environment free of the weight of money and the reponsibilities associated with a formal job. This is why I think the student showcase is such an important part of the Independent Games Festival- it encourages students to take a risk and do something creative.

This applies to disciplines beyond design as well. Programmers and artists should be encouraged to try new or unconventional techniques. In school, it's alright to fail at an implementation and learn from our mistakes. We need to encourage people to experiment with ways to make their games interesting, optimized, beautiful, and every other thing that we want to achieve as developers when we work on professional projects.

From A to B

When I started college, it was also the beginning of me truly becoming serious about game development. I took a long look at myself and realized where I thought I might need to be as a developer by the time I graduate. I imagined the quality of game I thought that I might need to be capable of producing to “break in,” those devilish words that give an aspiring student the chills.

At the time, it seemed impossible. There was so much to learn, and improving the quality of my work was such a tedious process, I wondered if I would be heading to grad school at the end of my four years to continue my education. Now that I'm three years in, I feel a little foolish for thinking that during my earlier years. However, there's something important there- that envisioning of where I wanted to be at the end has been vitally important for my growth as a developer. It was something that I did on my own that I really wish more people had been saying because I think it

In all honesty, I feel like we need to be telling students a bit more than just “you have to make games,” which is something that I've heard over and over again. That's not enough. There's so much more to becoming a good developer.

What I think we should be saying:

Based off of my own experiences over the past years, here's a short list of what I think we should actually be telling students:

  1. Set your goals. How long do you have until you will be looking for a job? The clock is ticking. But the harder you work early on, the easier it will get. Make sure you include getting team based experience in that road plan if you don't intend to be a one man show your whole life.

  2. You have to be good at what you want to do. Can you produce work of the quality of studios that you want to work at? Realize that basic skills across your broader discipline is important (art, programming, etc), but specialize in one or two areas is important as well (animation, rendering, etc).

  3. Speed counts too. Artists hear this sometimes, but its important for everyone. If you are given a programming test, it will almost certainly be timed. If you are asked a design question in an interview, you have to be quick on your feet. This comes naturally with practice. If things aren't slowly becoming second nature to you, you need to be committing more time to your work.

  4. Live beyond your tools. Getting stuck inside a bubble will result in sloppy work and messy solutions to problems. Consider an animator that spends all their time playing in Maya or Max but doesn't study natural motion, or a character artist that hasn't studied anatomy, or a rendering programmer that isn't familiar with linear algebra. You can cripple yourself if you're not careful.

  5. Try new and unconventional things in some of the free time you might have (if you're like me this time is usually in between midnight and 4 am). Read white papers about the latest research, try new art tools, prototype an unconventional design, the list goes on and on. Like I said earlier, trying new things is especially important in college.

  6. Your professors don't tell the whole story. You'd better learn what they have to teach you, but quite often realize that they don't always have the same goals in mind. This hearkens back to my feelings about how little my current roommate (@krismicinski) needs the capstone class that my school touts for it's Engineering programs, being that he studies compilers and just got accepted into half dozen PhD programs. The class is designed to help people get jobs as the more generic breed of software engineers, not as game developers, and most certainly not as academics. You'll have to learn a lot on your own no matter where you are, and this trend will continue into professional work.

  7. Your free time is a commodity. One of my closest friends is part of my school's brutal Biochemistry curriculum, which has been compared to doing graduate level work straight out of high school. He has a saying that “in college you can work, socialize, and sleep. We only get to pick two.” Playing games is, in my opinion, a dangerous culprit here. Playing through an entire AAA game is a time consuming process, so pick your games wisely.

  8. Save up to attend GDC. Get at least a main conference level pass. I personally equate a week of cutting edge development talks to be worth an entire semester of college. Sound like a lot of money? How many 60 dollar games do you buy in a year that you don't actually have enough time to play?

  9. Keep a development blog. It'll help you be coherent when people ask about what type of work you do.

  10. Make a Twitter and follow developers. It's an easy way to keep up to date on the latest research, techniques, and thoughts of some of the brightest people in the games industry.

Concluding Thoughts

So here's where the hypocrisy comes in a bit. Even though I act like I've done a good job growing as a game developer, I still don't know if I could resist accepting a position at a studio that has abusive dev cycles. I feel like I could at this point in my life, but at the same time I wonder what a dozen rejected applications would do to me after I graduate next year. I used to keep myself up wondering if I could actually cut it as a game developer. After three years of doing the ten things I just mentioned, I feel confident that I'll be at the level I want to be in a year's time for graduation. What keeps me up now is whether or not I'll be able to live a healthy life style after college. There's too many stories of developers who have let parts of their lives be wrecked by abusive work environments, too many developers who get up to accept an award and thank their wives for putting up with endless hours of overtime. So what are your opinions? I'd love to hear what advice you have for students, whether or not an endless pool of applicants enables a burnout dev cycle, and why I'm just straight up wrong. Flame on?

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

Page 1 ... 3 4 5 6 7 ... 15 Next 5 Entries »