Monday, March 21, 2011

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.


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.


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

Wednesday, March 16, 2011

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.


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.

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.

Artificial Intelligence for Games by Ian Millington:

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

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.

Real-Time Collision Detection by Christer Ericson:

Perhaps the most popular book on Collision Detection in games.

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.

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:

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.

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


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


The most official news site for the games industry:

Game Career Guide:

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

Sunday, March 6, 2011

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?