Quaternions are an Extension of Complex Numbers

May 13, 2009

Quaternions are two things: an extension of the complex numbers and a handy way of representing rotations in computer graphics.  I’m only covering the first one here.  This actually wasn’t covered at GDC, probably because you don’t actually have to understand quaternions to look up the algorithms for using them. I like being complete.

i2 = -1

i is the square root of negative one. They teach that in algebra 1 (or maybe it’s algebra 2). Complex numbers are numbers that have i in them; they look like a + bi, as if i were a variable. (3i) * (4i) = 12i2 = -12.

Quaternions are complex numbers except that they have 3 magic letters instead of 1; the familiar i, as well as j and k. Imaginative, I know.

In quaternions i isn’t the square root of negative one. It’s a square root of negative one. So are j and k.

i2 = j2 = k2 = -1

There are a couple more rules for Quats, but really not that many:

 

  1. ij = k
  2. ji = -k
  3. jk = i
  4. kj = -i
  5. ki = j
  6. ik = -j

 
 
Notice that ij != ji. Multiplication is not commutative (in fact it’s anti-commutative; ab = -ba. These rules are enough to multiply two quats, via one big distribution:


(a1 + b1i + c1j + d1k) (a2 + b2i + c2j + d2k)

= a1(a2 + b2i + c2j + d2k)
+ b1i(a2 + b2i + c2j + d2k)
+ c1j(a2 + b2i + c2j + d2k)
+ d1j(a2 + b2i + c2j + d2k)

= a1a2 + a1b2i + a1c2j + a1d2k
+ b1a2i + b1b2i2 + b1c2ij + b1d2ik
+ c1a2j + c1b2ji + c1c2j2 + c1d2jk
+ d1a2k + d1b2ki + d1c2kj + d1d2k2

= a1a2 + a1b2i + a1c2j + a1d2k
+ b1a2i - b1b2 + b1c2k - b1d2j
+ c1a2j - c1b2k - c1c2 + c1d2i
+ d1a2k + d1b2j - d1c2i - d1d2

= (a1a2 - b1b2 - c1c2 - d1d2)
+ (a1b2 + b1a2 + c1d2 - d1c2)i
+ (a1c2 - b1d2+ c1a2 + d1b2)j
+ (a1d2 + b1c2 - c1b2 + d1a2)k


Beziers

April 13, 2009

Beziers are easy-to-define curves. Since one of their applications is in computer graphics, they were covered at GDC 09 by Squirrel Eiserloh. Squirrel, by the way, gives a great presentation, and I’m cribbing a lot from the approach his presentation used. (Here‘s a presentation on interpolating position, but it’s not the one Squirrel used at GDC).

This article covers the just the beginning of Squirrel’s talk. I will probably cover more of it later. (In this article, I don’t even tell you what a Spline is!)

Linear Beziers

All Bezier curves can be thought of as ways of describing the motion of a virtual pen as it travels from one point to another. In its simplest form, the path from the start point to the endpoint is a straight line. To describe a point moving along a line, you take a weighted average of the two endpoints.

In the beginning, time 0, the pen is at the start point, [x1, y1]. At time 1, it’s at the end, or [x2, y2]. At time 0.5, at the midpoint: [(0.5)x1 + (0.5)x2, (0.5)y1 + (0.5)y2]. To find where you are at any other time t between 0 and 1:

[(1-t)x1 + (t)x2, (1-t)y1 + (t)y2]

linear-spline1

As t moves from 0 to 1, the pen’s position moves from the starting point to the endpoint. This sliding weighted averaging is yet another example of linear interpolation, which was almost the title of this article.

Quadratic Beziers

This step contains the critical idea, which lets you build higher-order Beziers out of smaller ones. The technique for drawing quadratic Beziers is to is linearly interpolate between a starting point and an endpoint, just as above, except that this time the start point and the endpoint are moving. They have their own start points and endpoints, and use linear interpolation as above.

quadratic-spline-1

As you can see here, the start point ends at the same place the end point begins.

Let’s call the start point [xa, ya] and the end point [xb, yb]. Then the path the pen follows is this:

[(1-t)xa + (t)xb, (1-t)ya + (t)yb]

Since the start point and the end point are moving themselves, xa (and the rest of those) are variable, not constant. Their movement is described in terms of their start points and endpoints, [x1, y1], [x2, y2], and [x3, y3].
quadratic-spline-2

[xa, ya] = [(1-t)x1 + (t)x2, (1-t)y1 + (t)y2]
[xb, yb] = [(1-t)x2 + (t)x3, (1-t)y2 + (t)y3]

The the position of the pen at time t comes from substituting these:
[(1-t)((1-t)x1 + (t)x2) + (t)((1-t)x2 + (t)x3),

(1-t)((1-t)y1 + (t)y2) + (t)((1-t)y2 + (t)y3)]

=[(1-t)2x1 + 2(t)(1-t)x2 + t2x3,

(1-t)2y1 + 2(t)(1-t)y2 + t2y3]

bezier_2_big
quadratic-spline-3

Cubic Beziers and beyond

The key idea was taking two Beziers, in this case linear, and interpolating between them to create a meta-Bezier, in this case a quadratic Bezier. You can use this idea to make a Bezier out of four points instead of three, by making a quadratic Bezier out of the first three points, then another quadratic out of the last three, and interpolating between those two to get a cubic Bezier. This is the most common kind of Bezier in computer graphics. Here’s the math, sans motivation:

[(1-t)3x1 + 3(t)(1-t)2x2 + 3(t)2(1-t)x3 + t3x4,

(1-t)3y1 + 3(t)(1-t)2y2 + 3(t)2(1-t)y3 + t3y4]

This image stolen from wikipedia

This image stolen from wikipedia

 


fuzzyEvery GDC article I write has the goal of helping us do a better job at IMVU. Since I want my articles to be relevant to a wider audience, I’m separating out the IMVU tie-ins. What follows is the IMVU-centric section of this post, which won’t be relevant to everyone. For the rest of you, please enjoy the fuzzy kitten.

 

How can we use this at IMVU? Since most of our art is user-generated, it’s the content creators, not us, who would want to learn about splines if they wanted to incorporate moving parts. I expect that they already have tools that handle this kind of math for them. But there’s another use – the particle system. Beziers – and later, splines – provide a simple, intuitive way to let users define curves. Just place and drag around the control points, and the particles know how to curve from the beginning to the end. There might be a good way to expose Bezier controls to content creators to help them define particles in their furniture or clothes.


Affine Transformations

April 6, 2009

This post is part of a series in which I try to explain everything I learned at GDC ’09. In it, I over Jim Van Verth‘s talk on affine transformations. I had hoped to get this post done a week ago, but I wasn’t confident in my understanding of the subject matter, so I took some time to research it independently. So, caveat lector: although I’m a math guy, I’m not a 3D graphics expert. I linked to the references I used at the end of this article, and I encourage you to take a look at some of them. However, the fact that I learned this recently could be a good thing; it’s always easier to teach things you just learned. People who’ve known a thing for years have totally internalized it and don’t know what it was like to hear it for the first time.

What is an affine transformation?

It’s a way of changing the size, shape, and/or position of an object in a 2D or 3D scene. Affine transforms are not the only kinds of transforms; they have some special properties.

  • If three points were on a line before an affine transform, they will still be collinear after it.
  • The same holds true for four points on a plane.
  • If two lines were parallel before an affine transform, they will be afterwards.

An affine transformation is a function that takes a vector or point and returns another vector or point. To transform an entire shape, just apply it to all the vectors and points in the shape.

I struggled with deciding when to introduce equations in this article. I decided to put them at the end, so that I can motivate them with concepts first. The trade-off is that it’s going to sound a little weird when I talk about composing transforms, because I’ll have to split it between the two sections. Luckily, they’re both pretty short..

Why use affine transforms?

Objects in a 3D scene are stored in memory somewhere with their own local coordinate system. To be in the right relative positions when the scene is rendered, they need to be moved, rotated, and sometimes scaled.

What kinds of affine transformations are there?

Translations, rotations, scales, reflections, and shears. All but shears are easy to imagine and describe, which is convenient because shears are “the bad one” that usually only happen by accident.

  • A translation move objects around without rotating them or changing their sizes. It’s a rigid body transform, meaning it could be performed on a rigid object, like a brick, in the real world.
  • A scale increase or decrease the size of objects. It can just make an object bigger, or stretch it in just one direction, or any combination of those. It’s not a rigid body transform, because you can’t stretch bricks.
  • A rotation does just what you’d think; rotates an object. It’s a rigid body transform. It only rotates objects around the origin; to rotate objects around other points, you have to first translate the object, rotate it, then translate it back. I’ll go into that later.
  • A reflection is a mirror-image. It swaps left and right or up and down. It’s not a rigid body transform. Another way to think of it is as a negative scale; it’s what you’d get if you squash something down to zero and stretch it back out again in the other direction.
  • A shear is a non-uniform translation. When you apply one to an object, the effect is visually similar to slanting. It’s not a rigid body transform. You rarely want these in computer graphics.

How do you compose them?

By applying one and then applying the next. There are only two things to say about composing before looking at the math. First is that order matters; for example, if you’re applying a scale and a rotation both, and you apply them in the wrong order, you can end up with a shear. Second, composing transforms is the tool that lets you rotate around a point other than the origin. You do this by translating until that point is the origin, applying the desired rotation, and then applying the inverse of the original translation.

How does the math work?

Affine transforms can be represented in more than one way. I’m only going to show the one I think is easiest.  In fact, the method I present is not the standard, as many readers have pointed out.  I only picked it to make this material as approachable as possible, which will make learning the other methods easier later.  For more on this, see the Van Verth presentation and the wikipedia page in the references.  That said, here’s how an affine transform’s function looks to mathematicians:

T(x) = Ax + y

x is the point you’re transforming, represented as a column vector. A and y define the affine transform; A is a matrix and y is another column vector. Here’s what that looks like in 3 dimensions:

example-affine-transform

In this example, I filled in all the numbers in the matrix A and the vector y at random. Intelligently generated transforms have a specific form for each type.

 

 

 

Translating an object by a units along the x axis, b units along the y axis, and c units along the z axis:

example-translation1

Scaling a an image by a factor of a in the x direction, a factor of b in the y direction, and a factor of c in the z direction:

example-scale

Rotating an image theta degrees around the x axis:

example-x-axis-rotation1

Rotating an image theta degrees around the y axis:

example-y-axis-rotation

Rotating an image theta degrees around the z axis:

example-z-axis-rotation

Reflecting an image across the x axis:

example-x-axis-reflection

Reflecting an image across the y axis:

example-y-axis-reflection

Reflecting an image across the z axis:

example-z-axis-reflection

How do you compose them? (with math!)

Same answer as before: apply one, then apply the other. And, as above, order matters. Let’s take a look at one. Suppose I want to apply two transforms: Ax + y and then Bx + z. It would look like this:

B(Ax + y) + z

Let’s compose a scale that increases an object’s size by a factor of 2:
scale-by-2

and a rotation by 90 degrees about the z axis:
z-axis-90-rotation

Here’s the composition:
composition-step-1

composition-step-2

composition-step-3

composition-step-4

References

 


_cute_kittenEvery GDC article I write has the goal of helping us do a better job at IMVU. Since I want my articles to be relevant to a wider audience, I’m separating out the IMVU tie-ins. What follows is the IMVU-centric section of this post, which won’t be relevant to everyone. For the rest of you, please enjoy the fuzzy kitten.

 

 

 

At IMVU, we’ve already got this pretty well licked. 3D rendering is our core product! Maybe we could get me involved in it, though, now that I’ve spent all this time studying it. Affine transforms are not nearly all there is to 3D rendering, though, so maybe we should wait until I finish studying and writing about the rest of the math involved. Also, I’m not the only programmer we have who is not a 3D graphics guru, so we could simply use this article as education.


Restrictions Fuel Creativity, And That’s Why Stealth Games Were Invented

March 29, 2009
GDC 2009 Keynote

GDC 2009 Keynote

The keynote at GDC was called ‘Making the Impossible Possible’.  It was delivered by Hideo Kojima, who designed the Metal Gear games, and describe the process by which he overcame seemingly-impossible obstacles to reach his game-creation goals.  He was a great speaker, and I thoroughly enjoyed the keynote.  The general take-away was that you must sometimes substitute new similar goals that are just as good, and that you have to be creative.  I might write another GDC post about the keynote which summarizes it directly, but that’s not what this post is.  Instead, I want to talk about a different takeaway I got from Kojima, which is that restrictions fuel creativity.  I’ll tie this back into Metal Gear and the keynote in a minute, but first I want to tell you more about what I mean.

Humans intuit answers to problems, but not to too-difficult ones.  You can intuit answers to simple algebra but not to simultaneous equations.  You’re not as good as chessmasters because they simply don’t see the bad moves, and only have to intuit which of the good ones are best. You’re not brute forcing; you’re doing magic that lets you simply see straight to the answer.  But, when there are lots of possible answers, it can be harder to intuit any of them.  Here’s a little experiment:

  • Quick, think of five objects.  Go.  Done? How about now?  Okay, now try the next one.
  • Quick, try to think of five red objects.  Go.
  • Okay, now try to think of five red foods.

The idea of this exercise was supposed to be that the added restrictions feel like clues, and actually make the question easier to answer.  Some early readers of this article tell me otherwise, so I guess you’ll have to take my word for it.  If you find that this makes me less believable, don’t worry!  The point I’m currently making isn’t central to the article.  But, wouldn’t it be easier if you had half the answers crossed out in a multiple-choice test?  Anyway, I intended to show that intuition is aided when you have more clues.  That’s how creativity works.

The next, more central point is that these kinds of restrictions can do more than help you find solutions; they can also help you find better, more creative solutions.  Here’s another experiment to ilustrate that point:

  • Imagine a blue thing.
  • Imagine a large blue thing.
  • Imagine a large blue thing made of wood.
  • Imagine an ugly large blue thing made of wood with three legs.

Any ugly large blue thing made of wood with three legs is still a blue thing, so you could have just started there.  But, you didn’t.  As you went down the list, your answers were forced to become more and more creative as restrictions were added.  As Mark Rosewater said in his column on developing Magic: The Gathering:

Suppose I locked a talented writer in a room. Once a week, I force him to write a short story. On the odd weeks, I let him write whatever he wants. On the even weeks, I give him a topic he has to write about. Will he be more creative on the odd or the even weeks? Research shows that the even weeks far outstrip the odd weeks.

Why? Because the even weeks force the writer’s mind to new areas of thought. Perhaps the writer would never think to write a story about a trapeze artist, but tell him he has to write about the circus and the writer heads down pathways he’s never tapped. In fact, experienced writers understand this phenomenon and thus build restrictions for themselves.

images-1This is where I tie restrictions back into Kojima’s keynote address.  The setting: 1984.  The second Rambo movie is a huge success, and to capitalize, Hideo Kojima is asked to design a combat game for the famicom, which is the Japanese NES.  That’s a broad solution space, and he might have come up with a very generic game.  Fortunately (!), a combat game was very hard to do on the available hardware.  The machine could only display 8 sprites per line, and in shooty a combat game, you’d need the player, some bad guys, and bullets.  That would quickly become too many sprites, which made a combat game impossible.  So, now he had a more restricted goal: make a combat game where there were no bullets.  Brainstorming here forced more creativity from Mr. Kojima:

  • What about a game where nobody ever shoots?  Every conflict ends with someone pointing their gun at someone else, and one of them giving up.  No, that would be lame.  There’s no action.
  • What about a game about escaping?  You have to run away and never be seen, and as soon as you’re spotted you lose.  Then there’s action, but no shooting.  No, that’s a very heroic main character.
  • What about a game about infiltrating?  You’re still running and hiding, but now going deeper into an enemy base instead of out of one.  Now you’re heroic, and it’s exciting, and there’s no shooting.

rc750j1f1This was the approach he used, and it resulted in the designing of the first Metal Gear.  That game was so creative, new, and fun that it gave birth to an entire genre.


269Every GDC article I write has the goal of helping us do a better job at IMVU.  Since I want my articles to be relevant to a wider audience, I’m separating out the IMVU tie-ins. What follows is the IMVU-centric section of this post, which won’t be relevant to everyone.  For the rest of you, please enjoy the fuzzy kitten.

How can we use this at IMVU?  Our goal is always “To Delight Customers.”  That’s a very broad goal, and can be difficult to answer.  We can try using creativity-fueling restrictions to narrow this goal, and see what new ideas pop out.  That makes brainstorming a two-step process.  First, brainstorm a wacky restriction, then brainstorm a creative solution.  I’ll improvise some right now:

  • How can we delight customers without changing anything that’s visible to them?  Maybe with performance increases?  Hmm.  Not exactly a novel idea.  Let’s try something new.
  • How can we delight customers by extending the emotion system?  Maybe by adding more moods and having them respond more dynamically to events in the 3D scene?  Hmm. There’s some thinking to do down that avenue.
  • How can we delight customers by breaking something they love?  Yikes.  That is a crazy restriction.  Well, what do they love that they shouldn’t?  Nah, I don’t want to tell them what to like.  What do they love that we could replace with something even better?  Well, they love shopping.  Maybe we could make a totally new shopping experience!  What could we make even better about shopping?  That’s a good idea, but it doesn’t qualify as breaking something they love.
  • How can we delight customers with an ugly large blue thing made of wood with three legs?  Hah!  Well, maybe there’s an answer in there somewhere.  One way to get something very large, blue, and ugly would be as a 3d product in the catalog.  Why would a creator want to make something like that?  What if we had theme weeks, where people entered new 3d products into a competition, like the outfits contest?  Hah!  Then we could be putting the creators through this very restrictions-fuel-creativity activity, and enhancing their creativity!  Very web 2.0.  I like it.

GDC 09

March 28, 2009

gdc091

My employer, IMVU, was kind enough to send me to GDC this week, on Monday, Tuesday, and Thursday.  It was the first time I’ve ever been to GDC, and it was maybe the most inspiring thing I’ve ever done.  The people and the energy there are unreal, and every day I came home overflowing with ideas and ambition.  I have to get them out.

imvulogoPart of the deal for going to GDC was that I’d share my notes with IMVU and give talks on what I learned.  Unless you work at IMVU, you don’t get to go to the talks (unless you ask very nicely), but I have permission to share my notes with a wider audience.

It will take a while, because I’m not satisfied with publishing my embarassingly unfinished notes as-is.  Instead, for each session I attended, I’m going to do some more comprehensive research.  I’ll combine my notes and memories with the GDC presentation slides and some general internet research, and write a detailed report on the subject matter.  Those will be published here, starting (and maybe finishing) this weekend.  I’ll also publish at least one general narrative that doesn’t touch on the content of the presentations but instead focuses on how the whole thing was set up and what it was like to go there.

Because the payoff of this research is to help IMVU’s team get as much as possible out of this, I’ll be relating all the subject-matter posts back to IMVU as much as I can.  This might not be relevant to you, so to make up for it I got you an image of a fuzzy kitten.

fuzzy_kitten