Quaternions

Quaternions are an interesting bit of mathematics.  You can read the Wikipedia article if you really want to understand what they're all about (or, attempt to understand, depending how mathematically inclined you are), but I jut want to talk a bit about using them in games.

Note:  this is only dealing with unit quaternions (i.e. length of 1).  In a more generalized case, they can be of any length, but for purposes of expressing rotations in games, they should only be unit length. 

Transformations

When dealing with geometry transformations, we generally need to worry about three things:

• Translation (change in position)
• Rotation (change in orientation)
• Scale (change in size)

In games, we often use a 4x4 affine transformation matrix, as this is very efficient for most hardware to work with.  You can combine translation, rotation and scale into a single matrix.  You can also store this as a 4x3 matrix, as the last row is always (0, 0, 0, 1).

Even better, if you have multiple transformations you want to apply, you just multiply all of the matrices together and get a single matrix that does all of them at once.  This happens a lot in character animation, where the finger is positioned relative to the hand, the hand is relative to the wrist, the wrist is relative to the elbow, the elbow is relative to the shoulder, and so on.

Quaternions are another way of specifying the rotation.  Note that it is only rotation, so if you want to store scale and translation, you need to store those separately.  This is still very space-efficient.  Even using four-component vectors for each, it's still the same size as a 4x3 matrix.  If you don't need scale, it's 4x2.

Notation

There is a lot written about quaternions, but I find a lot of the articles to be pretty confusing.  When talking about programming, a quaternion and vector are essentially identical from a data storage point of view.

I put a quaternion into an (x, y, z, w) vector like this:

x = axis.x * sin(angle/2)
y = axis.y * sin(angle/2)
z = axis.z * sin(angle/2)
w = cos(angle/2)

where 'axis' is the (unit) vector you want to rotate around, and 'angle' is the angle to rotate.

What I find most confusing is people putting the 'cos(angle/2)' component in the first component of the quaternion/vector.  Mathematically there's nothing wrong with this, as long as you're consistent.

In Real Life, this causes a lot of confusion when you want to multiply a vector that has been stored as (x, y, z, w) with a quaternion that has been stored (w, x, y, z), so don't store it that way.  It's worse when articles have labeled the components (q0, q1, q2, q3) and it's not at all obvious what has been stored where.

Inspection

The way quaternions store data, it's possible to get some intuitive understanding of the rotation it represents by inspecting the values.

From the axis/angle assignment above, if angle=0, you get:
(sin(0), sin(0), sin(0), cos(0)) =
(0, 0, 0, 1)

Which is the identity quaternion rotation - if you see (0, 0, 0, 1), there is no rotation. 

For any other rotation, the (x, y, z) components will be some non-zero scale of the rotation axis, so inspecting the (x, y, z) components will give you some idea what axis it's rotating around.

If you remember your trigonometry, the amount of rotation should be obvious too:

• w = 1 = cos(0/2) means angle=0
• w = 0.7071 = 1/sqrt(2) = cos((pi/2)/2) means angle=pi/2, or a quarter turn
• w = 0 = cos(pi/2) means angle=pi, or a half turn

Operations

Quaternion multiplication is completely unintuitive, :
q0 * q1 =
( q0.w*q1.x + q0.x*q1.w + q0.y*q1.z - q0.z*q1.y,
  q0.w*q1.y - q0.x*q1.z + q0.y*q1.w + q0.z*q1.x,
  q0.w*q1.z + q0.x*q1.y - q0.y*q1.x + q0.z*q1.w,
  q0.w*q1.w - q0.x*q1.x - q0.y*q1.y - q0.z*q1.z )

Rotating a vector (v = (x, y, z, 0)) by a quaternion (q) is fairly straightforward:


v' = inverse(q) * v * q

The inverse of the quaternion (x, y, z, w) is (-x, -y, -z, w).


Even if you are storing scale and translation, this is fairly easy:

• scale = (sx, sy, sz) 
• rotation = (qx, qy, qz, qw)
• translation = (tx, ty, tz)
• scale_inverse = (1/sx, 1/sy, 1/sz)
• rotation_inverse = (-qx, -qy, -qz, qw)
• translation_inverse = rotate(rotation_inverse, scale_inverse * (-tx, -ty, -tz))

Compare with the inverse of an arbitrary 4x4 matrix and you'll understand how much more straightforward this is.

Final thoughts

There are a lot of situations where using quaternions can be very helpful - particularly if you need to take the inverse of a transform very frequently.  Having your transforms broken out into separate scale / rotation / translation components can also be very beneficial, depending on how you're animating these values.

This doesn't mean quaternion rotations should be used everywhere - matrix transformations are certainly sufficient.  You will almost certainly need a matrix for rendering, and converting back and forth between quaternions and matrices is not trivial.

Random Blog Day

On my mind recently:

I watched @Jonathan_Blow live-coding on twitch.tv - he has been working on his own language, and it's nice to watch someone else have mind-bending code generation problems for a change.  :)

I have a lot of interest in game development languages, though I have primarily focused on scripting, as opposed to an entire game development language.  It's probably a little vague as to which category some things should drop into. 

Conceptually, I like to think of scripting as writing custom code for individual game objects.  This doesn't make it strictly game-specific, but it probably tends to be.  Ultimately, it lets you glue all of the bits of the game engine together into something new.  Also, having some syntactic control can let you specify certain this more easily.  For instance, I have special notation to convert musical beat/measure values into actual time values, and ways to specify timing, sequencing and interpolation.  It could be done in C, but the point is to make it easier to read and write than make it possible.

Engine coding is a fairly different beast.  First, you probably have to talk to third party libraries, even if that's just DirectX, OpenGL, basic operating system, etc.  So, you're probably stuck at some point with whatever language those are written in.  For simpler games you can get away with a higher level language, but for maximum performance and compatability, you're still looking at C/C++.

One interesting idea is to have a sort of pre-compiler that spits out C/C++ code.  I've seen similar things done before, to varying degrees of success.  This is pretty much guaranteed to degrade the already dubious quality of debuggers and debugging, but it's a way to add language features that are otherwise hard to get.  For instance, pre-hashed strings.

-----


In other news, the new World of Warcraft expansion Warlords of Draenor is out.  It is good. :)  They have done a lot of work scripting out quests, and there are a lot of places with a huge number of NPCs wandering around, which helps to bring the world to life a lot more than I remember seeing before.  Some of the battles are truly epic.

You have your own garrison now, which is a pretty cool idea, although we'll have to see how some of the features play out.  Since everyone is doing stuff in their own garrison, you don't see other people as much.  As a hardcore solo player, it doesn't affect me much, just feels a bit weird for an MMO. 

You can also build buildings to give you access to the various professions, including ones you haven't taken on yourself.  On one hand, this seems like a good idea, as it gives you access to some of the crafting you otherwise wouldn't have.  On the other, you can't have all of the buildings at once, and you probably want the ones you do have the professions for, so your choices are kind of limited.


-----

That's all for now - sorry I haven't been posting recently.  Too much going on, not enough stuff that makes good blog posts.  :)

Python Injection

Today's fun stupid code is written in Python.

I have found a few times recently where it was handy to either replace or inject code in specific C++ files, or even level files.  I have done this sort of thing in AWK in the past, but AWK is, well, awkward.

The basic pattern looks like this:

import tempfile

src = "yourfile.txt"

with tempfile.TemporaryFile("w+") as out:
 with open(src, "rU") as f:
  for line in f:
   if line.find('REPLACE ME') != -1:
    out.write('REPLACE WITH')
   else:
    out.write(line)
 
 #Beginning of temp file
 out.seek(0)
 
 #Copy temp file over source
 with open(src, "w") as f:
  for line in out:
   f.write(line)

This just opens a temporary file, scans every line of the source file and writes it to the temporary file, with possible modifications.  Then it jumps back to the beginning of the temporary file and overwrites the source file with the temporary file.

It's probably a good idea to have whatever you're modifying backed up somewhere

It may be easier to just read the entire file into a list of strings and write that back out, but now you know how to use temporary files.  :)

What you do at the 'REPLACE ME' line is up to you - check for a specific sub-string, or exact line.  Similarly for the 'REPLACE WITH' line - replace the line with generated code, insert a new line of code and put the 'REPLACE ME' marker back in as a comment, etc.
I have one version of this that copies a component template .h and .cpp file, replaces 'XXXXX' in the new files with the new component name, and injects the component registration code into the game initialization function.  Creating a new component used to be a chore, now it's easy!

refptr

I come across this programming pattern every once in a while:

1. In an object's constructor, allocate some data
2. When copying the object, copy the pointer to the allocated data, rather than duplicate all of the data
3. Delete the data in the object's destructor

Of course, this ends in disaster, because the first of these objects that gets destroyed deletes the data, leaving all of the others holding an invalid pointer.

Some types of smart pointer let you pass "ownership" of the data when copying an object by only letting one object hold the pointer at a time, but this is very limiting.  (auto_ptr)

An alternative is to have a smart pointer that holds the "master" allocation, and all others get a regular copy of the pointer.  This works, but doesn't really fix the above problem where there is no obvious master allocation.

One of the best generic solutions I have seen is to have an intermediate reference counting class that all of the objects point to, instead of having them point directly at the data.  This causes an extra level of indirection when you want to dereference a pointer, but it solves the above problem without any manager classes, ownership passing, etc.  (shared_ptr)

So, something like this:

template <typename T>
class refptrsentinel
{
 template <typename U> friend class refptr;

 refptrsentinel(T *obj) : ptr(obj), count(1) { }
 ~refptrsentinel() { delete ptr; }

 void acquire() { ++count; }
 void release() { if(--count == 0) delete this; }

 T *ptr;
 int count;
};

template <typename T>
class refptr
{
public:
 refptr() : sentinel(NULL) { }
 refptr(const refptr &rhs) { sentinel = rhs.sentinel; if(sentinel) sentinel->acquire(); }
 refptr(T *obj) { sentinel = obj ? new refptrsentinel<T>(obj) : NULL; }
 ~refptr() { if(sentinel) sentinel->release(); }

 refptr &operator =(const refptr &rhs)
 {
  if(sentinel)
   sentinel->release();
  sentinel = rhs.sentinel;
  if(sentinel)
   sentinel->acquire();
  return SELF;
 }

 operator bool() const { return sentinel != NULL; }
 bool operator !() const { return sentinel == NULL; }

 T &operator *() const { return sentinel->ptr; }
 T *operator ->() const { return sentinel->ptr; }

private:
 refptrsentinel<T> *sentinel;
};

Light 'em up

It's lighting week.

First off, Blender's new Cycles render engine is pretty spiffy.  Path tracing just makes lighting look so nice.  Plus it's more or less interactive, as it can do a very low-res pass fairly quickly as you're moving the camera around.

Even better, Blender 2.7 added texture baking, so all of that yummy lighting goodness can be used to make lightmaps and such.

So far, the pipeline to convert a Blender shader graph into a GPU vertex/fragment shader has worked really well.  Obviously there are some limitations - path tracing and triangle rasterization are just completely different ways of doing things - but I can build up a complex set of materials and more or less get the same thing in the game.

Here's a ship in Blender:

And in-engine:

Not exactly the same, but similar.  It looks a little washed out, some of that is the bloom effect not present in the render.

This is using lighting based on the skybox - spherical harmonics for diffuse, plus a biased mip map sample to get a blurred / rough specular reflection.  It looks pretty nice in motion.  The emissive materials help as well.

Self-illumination and ambient occlusion maps would help a bit.  It may also be worth generating point/directional lights for hot spots in the skybox to give some added definition to the normal maps.

Some day we'll be doing real-time path tracing (or something similar), and it's going to be awesome.  :)

Points of note:

• Using the shader instruction texCUBEbias(...) to  choose a "blurred" mip level was not working properly.  The documentation on this instruction is pretty vague, but I kept getting really strange results.  texCUBElod(...) seems to do what I want.
• The auto-generated mip maps for the cube map definitely have seams at lower resolutions.  This seems a little tricky to fix, I may just live with it for now.
• Using D3DXSHProjectCubeMap(...) to generate the spherical harmonic coefficients was not working as expected - it looks like x and y are both negated?  Anyway, negating coefficients where the sign differences don't cancel out gives light coming from the right direction.

That's all for now, have a great week!

Getting the Message

Hello long-neglected blog viewers!

I won't get into a lengthy discussion about why I haven't posted for ages, but it sounds a lot like, "I can't post that because it's spoilers, I can't post that because it's boring, I can't post that because I'm busy working, I can't post that because I'm not at my computer, and I can't post THAT because... well, that raid's not going to heal itself now, is it?"

The short version: Game is still in progress. Engine is kind of nice. Music is coming along. Level design is not there yet, but making definite progress. I want to show stuff, but greyblock art is maybe not a good first impression, so I'm working on some prettying up.

Short-ish term goal:  Get a single level together for design and engine testing.

So, let's talk code.

typedef void (*Fn)(const string &);
typedef VSTACK<Fn> FnList;
typedef MAP<string, FnList> StringFnMap;

class cMessageHandler
{
 FnMap mFnMap;

public:
 void Register(const string &name, Fn fn)
 {
  mFnMap[name].push_back_resize(fn);
 }

 void Unregister(const string &name, Fn fn)
 {
  mFnMap[name].find_erase(fn);
 }

 void Call(const string &name, const string &s)
 {
  FnList &f = mFnMap[name];
  for(FnList::ITER it = f.begin(), end = f.end(); it != end; ++it)
  {
   (*it)(s);
  }
 }
};

Basically, it's just a list of functions listening to a particular message ID (string), and a function to broadcast a message (string) to each of them.  It's using my own containers, but you could use std::vector and std::map easily enough instead.

I also have a version that handles member functions - you just need to store the "this" pointer and a redirect function for each class, similar to a delegate.

This makes it pretty easy to send messages or triggers between components from data - there's no need to create a message ID or bind to specific functions in each class.  Instead of writing a bunch of custom code for each class to bind it to other components, they just need to send or listen to the same message name.

My project has a "game" library, which has many generic game components in it.  It is not supposed to have any game-specific code or logic in it to make it easier to re-use in a new project.  This was causing some problems connecting generic components to game-specific components, but this system lets me hook them up in data without the game library knowing anything about the game-specific stuff.

Initially I found this system kind of worrying, mostly because it involves so many strings.  It's the old-school hacker mentality, where individual bytes and cycles were of vital importance.  Well, you still probably need to be a little gentle with it - it's for events that happen only occasionally. Overall, I think it's worth being able to easily bind events from data.

So, yes, still working on things.  :)  I will try to update more often, not sure of the frequency yet!

Announcing iColorTool

Base Metal Games has its first app!

iColorTool is an iOS color identification / video processing app to help those with color blindness.



The first mode, color identification, takes the average color from the center of the camera view and tries to match it to the nearest color in a set of known colors.

There are multiple video processing modes.  The simulation modes can help those with normal color vision understand how the world appears to those with color blindness.  The error and color channel modes can help those with color blindness see color information that they might be missing.

In the next few days, I'll try to post a few thoughts on the app development experience!

Back Into the Fray

Today was back into coding land a little bit.

Mostly it has just been cleaning up the way I'm managing the UI for characters.  Since I actually have proper game assets now (yay) I discovered that the way I was handling multiple facial expressions to be a bit lacking.

This also led to some changes to the component system, allowing me to "include" an external text file for individual component definitions.  This was prompted by not wanting to duplicate the layout for the UI into every level file.

So, between those things, and the inevitable bugs from taking everything apart and putting it back together again, the day is pretty much done.

I have also clearly not been practicing the guitar enough.  I seem to practice in one or two week stretches and get back to the point where my hand doesn't feel like it's going to fall off after playing power chords for 20 minutes... and then promptly take a month off from playing and go back to square one again.

Back to it then...

The Blog That Time Forgot

My last post was Dec. 19?

Christmas season is obviously not my most productive time of year.  That's not to say I haven't been working (although there was a lot of World of Warcraft going on), but the hours have been kind of weird.

Since the last update, I have mostly been doing stuff that doesn't blog well.  Some UI stuff, editor stuff, story stuff, and level stuff.  Blogging about those would be boring, boring, spoilers, and boring spoilers, respectively.

Or maybe you're really into greyblocked spaceship placement.  This is for you guys:

Probably the most interesting thing was the addition of free-flight mode.  Up to this point, the levels have essentially been built on a rail - the user can move around inside the camera's view, but the camera is on a fixed animation path.  I had been planning on doing this for ages but was too focused on other things to get around to it.

So far it feels really good.  I'm still trying to figure out the camera angle.  It feels really good to have the camera down low, but then it's way too obvious that the whole world is built on a 2D plane.  If you pull the camera up, you can't see far enough ahead of the ship.  I'm sure I'll work something out.

Next up is a bit more enemy AI, and probably a little more level editor UI stuff.  I did manage to get parts of the UI back from the Profound State of Brokenness that I somehow put it into a couple months ago.  Even Perforce history couldn't rescue me from that one.  There were way too many "Why doesn't this work?  How did this used to work?  HOW DID THIS EVER WORK????" moments.