Build a strong math foundation!

A strong math background is an vital tool for game development. That may sound completely obvious to you, but it wasn’t to the 12-18 year old me. I was a good student and enjoyed my math classes and all, but the light just wasn’t on. I never took a formal linear algebra class, so the best I had was the primer you get in every game development book. It’s enough to understand basic vector algebra and affine transformations, but not much more. I mostly just used the equations and maintained a very surface-level understanding. The dangerous part was that I somehow fostered a false confidence in my math skills. I was good until I started prodding.

Man, was I missing out.

Last year, I had the opportunity to interview for a game development studio. Sure enough, my interviewer gave me a vector algebra problem, and I totally choked. I eventually made it through, but not without lots of coaxing and hand holding. It was a pivotal moment for me: I realized just how much I was holding myself back by not building a strong foundation. So I decided to change!

I immediately picked up Introduction to Linear Algebra by Gilbert Strang and began working through his M.I.T. course online. I also registered for Calculus III for Fall 2012, and Differential Equations, and Computational Geometry for my last semester. I picked up Real-Time Rendering and Physically Based Rendering, which are two fantastic and math-heavy books. Linear algebra and Calculus III have been incredible. I’m able to dissect problems and understand their context in ways like never before.

As an example, consider the problem of tangent space normal mapping. I never understood the formal concept of linear transformations and basis vectors. A matrix was just numbers to me; now it’s a familiar construct with a plethora of fascinating properties and elements (like eigenvalues and eigenvectors!). Computing the tangent, bi-tangent, and normal vectors and transforming the lights  and viewpoint into tangent space is a walk in the park now. No game development book primer is a worthy replacement for a rigorous math course.

So do yourself a favor. Learn the math! And really learn it.

Most recently, I’ve been studying the Singular Value Decomposition of a matrix, as well as it’s Psuedoinverse. These constructs are ways to break down matrices into basic and powerful elements. A great application of this concept is inverse kinematics. In my next post, I’ll explain how I solved a basic inverse kinematics chain in 2D using python, linear algebra, and calculus.

Advertisements

Project Sandbox

This project is a 3D game engine built from scratch using C++, DirectX 11, and Bullet Physics. I had some pretty specific goals with this project, although I wasn’t sure how far I wanted to take it after that. I really wanted to learn DirectX 11 and implement an advanced deferred renderer. I also wanted to design a flexible entity/component system that would support an articulate object. To test this, I built a tank out of constrained rigid bodies. The tank is fully simulated except for the treads, which are just rendered. The wheels were given a high friction coefficient so as to better approximate the treads, but the overall handling of the tank is fast and arcade-like (which is what I wanted). Below are some of the features that are included in the implementation.

Resources

The engine supports tag-based resource loading from an XML file. On initiation, the user specifies the main resource XML file, which catalogs all of the resources used by the application, along with appropriate metadata. The loader creates stubs for all of these files. The resources can also be grouped, allowing a single load/unload call for a specific resource group. Then, the resource can be requested directly from the resource manager via the tag and accessed (if it is loaded).

Entities

The entity system in Project Sandbox is inspired by the Artemis Framework. Entities are essentially just ids; the data is held  in individual components that the id maps to. An entity is allowed multiple components of a given type, and each component is given direct smart pointer references to other components that it needs. For instance, a rigid body component needs a transform to orient it in space. That transform could also be the root transform of another component. In fact, there could be multiple transforms within a given entity. For instance, the tank entity in the screenshots above has multiple rigid body components, each connected by Joint components. Those rigid body components each have a transform that they are given write access to. The model transforms for each rigid body are given read only access to their respective transforms, allowing the physics engine to edit the transform that is then used by the graphics subsystem to render the mesh.

This architecture allows the engine to elegantly handle breakable objects. For instance, if the tank were to explode, the joints could be removed from the system, and the respective parts would be allowed to bounce around. When it’s time to cleanup the object, you have only one entity to destroy. Furthermore, if you wanted to break off a chunk of an object and create a second entity, you could remove those components and add them to a new id.

To handle game logic, the user creates entity systems that match entities with certain component requirements. An event system allows message-passing communication between these entity systems.

Rendering

Project Sandbox utilizes a DirectX 11 deferred renderer with flexible material support. It currently supports cascade shadow mapping for directional lights, and a modular post processing system with high dynamic range lighting and filmic tonemapping. The demo utilizes the shading framework to implement Cook Torrance shading with normal, specular, and roughness maps.

One of the more interesting problems I overcame was rendering the treads of the tank. The treads are handled as a single instanced mesh. A parametric curve traces out the path around and between the wheels. The joint rotation delta is computed from the driver wheel and applied to the evaluation of that curve. Once a point on the curve is evaluated, the normal and tangent vectors are computed and formed into a basis for the instance. I was concerned that the compression of the joint springs would result in popping (since the lines between wheels are linear), but that hasn’t been a big problem so far. I was originally going to try and fashion splines between the wheels, but the linear version ended up looking great as is.

Physics

The engine integrates with Bullet Physics and provides a layer of abstraction over the framework. Components were crafted for joints and rigid bodies, allowing the user to easily pieces together articulate objects. The engine also handles replicating updates from the physics to component transform, and sends events for collisions, etc. The tank above is fully simulated via constraint motors. I spent a great of time tinkering with the handling of the tank, specifically looking for a fast, arcade-like feel.

I ran into an interesting problem with lockstepping the tank wheels (to approximate tread motion). Bullet Physics doesn’t have any sort of gear joint constraint. As an alternative, I connected each pair of wheels into a chain of distance constraints. There are two distance constraints per pair of wheels, one oriented 90 degrees from the other (sort of like a train). This choice of orientation was intentional. The magnitude of the force vector varies with the sine of the angle of the two wheels (i.e. if they are both oriented at 0 or 180 degrees with the constraint rooted on the boundary of each wheel, floating point inaccuracies could result in the two wheel reversing direction). Having them 90 degrees apart allows the two constraints to work together to power the rotation at a constant rate. See the image below:

Also, below is a video of the engine in early development when I was focused heavily on the physics and handling of the tank. This was before much of the rendering features were available.

And finally, here is a video of the engine in action. I threw together a test level with some models I found online, so it’s not particularly glorious looking. Most of the cool stuff is under the hood, although I personally think the tank is pretty cool. 🙂

Multithreaded Software Rasterizer

As a part of two semesters research of undergraduate research at Taylor University, I development a multithreaded, tile-based software rasterizer. The pipeline rasterizes and shades four fragments in parallel using SSE instructions, and utilizes and extensive custom written SIMD optimized math library for all vertex transformations. Features supported include custom vertex and fragment shaders written purely in C++ (thanks to some operator overloading tricks), perspective correct texture mapping, clipping and backface culling, the flexibility to select different render targets, and early Z rejection. In addition, rendering order is preserved. On a Hyper-Threaded Quad-Core Intel I7 mobile processor, the rasterizer performs a full four times faster with eight threads than with one. It utilizes SDL for frame buffer, thread, and bitmap management. In the following link, you can find the code repository and research paper.

http://code.google.com/p/msr-zbethel-tu/

Arena – iOS

As part of a mobile computing class at Taylor University, Jesse Denardo (a fellow student) and I built a 3D first-person multiplayer space shooter. It renders with OpenGL ES 1.1 and uses the built-in bluetooth socket API to handle networking. I’m particularly proud of the space background. You can’t see it in the screenshots, but the stars pulse in and out using a randomized sinusoidal function. I rendered them using point sprites. The game allows two players to connect and battle it out in the asteroid field. Also, the game uses quaternions to avoid gimbol lock for ship rotation.