MetaVoxel

Since my last post, I started working on a new game project with a friend, Steven Barnett. It’s called MetaVoxel, and it’s a puzzle game involving a deeply recursive world.  What does that mean? Well, that’s a very good question. While initially tossing around ideas for the game, we decided it would be cool if the player could shrink to fit into a part of the world. In doing so, they would discover a deeper world within. The player can move in and out of these worlds to solve puzzles and discover new sub-worlds. Sure, it doesn’t make much sense, but who cares? We think it’s a cool idea. Here’s a concept painting by the illustrious and talented Steven:

At any rate, we’ve been hard at work on our new project, and we’re making a ton of progress. We’ve built a game editor for creating levels and crafting puzzles. We’re excited to show more, so in short order we’ll have a development blog online to show off our progress!

Advertisements

Simulating an Inverse Kinematics Chain

Inverse kinematics is a fun application of linear algebra and calculus that is extremely relevant in computer animation. Given a rigged skeleton, inverse kinematics can solve the joint angles (or similar parameters for other types of joints) necessary to minimize the distance between the end effector (i.e. joint at the end of the chain) and target. Solving this system essentially boils down to the following system of equations:

\vec{e}=J\vec{\Delta\theta}

where \vec{e} is called the “error vector,” and describes the velocity of the end effector necessary to converge on the target; \Delta\vec{\theta} is the vector of joint angle velocities that will result in the correct end effector velocity (this is the unknown part), and the Jacobian matrix J, that encodes the change of basis from joint angle space to Cartesian coordinate space for the partial derivatives. Alternatively, you can view this as a transformation matrix that takes the rate of change of the joint angles and relates it to the rate of change of the Cartesian coordinates of the end effector joint.

It is common to have more columns than rows in a system like this (especially in a chain), because the there will be few end effectors and many joints. Because the matrix is not invertible, our next best thing is the Moore-Penrose psuedoinverse which gives a least-squares solution to the problem. This is desirable because there are many cases where the chain cannot converge on the target, so we want the best possible attempt. The results in the following equation:

\Delta\vec{\theta}=J^T(JJ^T)^{-1}\vec{e}

This form of the psuedoinverse assumes that you have full row rank in your matrix J, otherwise JJ^T will be singular an non-invertible. This presents a problem because there do exist singularities in certain joint configurations. A common solution to this problem is to damp this matrix by a small factor to ensure invertibility. This method is called the Damped Least Squares method, and the requires only a simple change to the previous equation:

\Delta\vec{\theta}=J^T(JJ^T + \lambda I)^{-1}\vec{e}

Here, \lambda is just an arbitrarily chosen constant that keeps the matrix from every going singular. The bigger the constant, the less realistic the motion near singular configurations. On the other hand, a higher constant results in more numerical stability in the equations. The demo I wrote allows you to set an arbitrary \lambda value.

I also implemented two other solvers, a Jacobian Transpose solver and a Cyclic-Coordinate Decent solver. The former cheats by using the transpose of the Jacobian to solve the system rather than the psuedoinverse. It’s a simple solution but results in a lot of jittery motion and isn’t very realistic. CCD essentially loops through each joint multiple times and orients the child chain in the direction of the target. With enough iterations, this converges on a solution, but it only works in situations where joints are 1DOF. It is quite simple to understand and there are several articles online that explain it well.

Finally, the demo is written in Python using the pyglet library. User interactions is almost exclusively through a console interface (activated with ~). Included in the zip is a text file with the syntax for these commands.

Source Archive

For a more in-depth introduction to this topic, I found this paper extremely helpful.

Some Thoughts on Software Design

NOTE: This was taken from my blog on gamedev.net. I’m migrating things over slowly.

Software Engineering as I understand it involves the concept of software design. Anyone can program, and I would even venture to say that programming is the easy part. Good software design is where things get hairy. I consider myself a seasoned programmer, but a somewhat fledgling Software Engineer–a state that I think is fairly commonplace among academic or hobbyist developers. Bad habits done out ignorance can carry over into the industry and wreak havoc on bigger projects. I too am struggling when it comes to designing and implementing larger systems (like a game engine), although I am learning a lot. Though I am still inexperienced, I thought I might share some of my realizations so far. If you consider yourself a seasoned software engineer, feel free to comment/correct as you see fit.

Formulate Requirements

First of all, trying to design a system without knowing the requirements will drive you insane if you are expecting any semblance of quality in your architecture. I know this because I’ve tried. My previous attempt at creating a game engine went down in flaming glory because the end result wasn’t as flexible and usable as I had hoped. Before you write a single line of code, I implore you, write a design document for your project. Describe what the system needs to do in detail. Why is this so important? Without this step, you’re essentially flying blind. You will re-factor your code three times as often, bloat your code base including features you don’t need; and if you’re like me, you’ll agonize over finding the Right Way to do it–except you won’t, because you don’t know what you need.

Case in point: in my first engine, I rewrote my resource manager four times. Not a simple re-factor mind you; a complete rewrite. I included features like loading from a separate thread, which is a great feature, except that I didn’t really need it. I just thought it was cool and that every engine should use it. Granted, I learned a lot about what I did need during those four rewrites, but I would have been better off starting with the essentials and refactoring from there. I went into it without fleshing out how the end product would use the system; as a result, my design suffered from code bloat.

Build a (Good) Foundation

I’ve heard differing opinions on this, so take it with a grain of salt. I see a two specific mistakes that neophyte developers make (including myself) when they are just starting a big project. Either they try to sketch out the entire system (a large one, mind you) on paper, in detail, including every major class and how they’ll interact with other classes; or they don’t attempt to design anything and just start coding. The latter is just pure laziness in my opinion–the chances of designing a good system with that strategy are akin to winning the lottery (unless you’re John Carmack). The former, however, is just as destructive. From my experience, trying to build exclusive from the top down is paralyzing. You scrap design after design trying to find the perfect one (hint: it doesn’t exist).

As with all things in life, good design comes with moderation. Begin with your requirements and write some hypothetical sample code of how you will use the system. One good way I’ve found is to write a bogus program (or part of one) in pseudo code, testing out various interfaces and ideas. At the same time, begin building the foundation for your system. If it’s a game, start with the basics, like a basic map loader. Just get something working.

Break Down Work into Manageable Chunks

As you build the components of your system, not only will the next step become more clear, but so will the requirements. You’ll realize something you need but couldn’t have known early on in the process. This allows you to refine your requirements as well as your code. By starting simple, you will save time refactoring and gain momentum and efficiency. I see many developers who attempt to write hundreds of lines of code without ever compiling it. They proceed to spend hours trying to get it to even compile, and then twice as many working out the bugs. This is not good practice; a better method is to utilize unit testing. This is the process of writing small chunks of code and then rigorously testing it before moving on to another component. This gives you confidence in the components of your system as you build on them, and boosts your morale as you see small parts working independently. Furthermore, it simplifies bug fixing since you can focus on one part of the system exclusively.

Pick an Achievable Goal and Stick to It

This is probably the most important point. Avoid the pain and suffering of trying to design the perfect system for any product. It won’t happen. Always know your requirements and design for that only. This is especially true if you are trying something new. I don’t personally know how the guys at Epic designed Unreal 3 or their story, but I would imagine they built it up using the good parts of their games. Not only that, but the guys developing Unreal Engine 4 are probably the same ones who built the previous three engines (at least the lead developers). In short, defer your amazing do-it-all project for when you actually know what you’re doing (I say this to myself as well). Most of us started out wanting to develop the best MMO on the planet; we quickly realized this was foolish. However, some of us are repeating that foolishness on a smaller scale. We’re trying to build something we have little experience with, and make it better than everything else out there. That’s just my opinion.

How does this apply to me? Well, a lot. I’m trying to trim down my grandiose plans to something manageable. For instance, what are my goals? I’ve spoken about those in recent blog entries. If you go back to my first blog, you’ll find that I’ve trimmed it down a bit since then. I may trim it down even more. As a humble hobbyist with only 10 or so hours a week to devote to doing what I love, this has to be the way it is. It’s just reality.

Anyway, I hope this was helpful. Again, it’s just my opinion, and I’d love to hear your feedback if you agree or disagree. Thanks!

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.

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.