Tuesday, December 21, 2010

A Graphics Programmer's Toolbox, part 1 (Vectors)

Everyone needs to know the basic tools of their art. I thought I'd like to share with you my equivalents of a screwdriver, a hammer and maybe a saw, some of the everyday tools of a graphics programmer.

Vectors

A vector is just a fancy word for a point in space. So in 2d, a vector is just a co-ordinate pair (x, y). In 3d it's (x, y, z) and in 4d it's (x, y, z, w). A mental image of four dimensions is not important here - don't even try.

Some vectors are given a special name. The vector in the middle of the space, the zero-vector, is called the origin. In 3d, that's (0, 0, 0). The vector to the right, (1, 0, 0), is called i. The up-vector, (0, 1, 0) is j. The remaining vector, (0, 0, 1), is named k and it's the backwards-vector.

Sum, Difference and Multiplication

These points, or vectors, can be added and subtracted. Adding a vector to another is just summing the coordinates of the vectors; if a = (X, Y) and b = (x, y), then a + b = (X+x, Y+y). Subtracting is done in a similar way, a - b = (X-x, Y-y). Multi-dimensional calculation is not really that much more complicated. It's basically just the same, but doing the operations to all co-ordinates, instead of just one.

Sum and difference are easy, but with multiple components (co-ordinates) there are many kind of vectors multiplications with different meanings. Complicated? I didn't say anything; not yet.

Multiplying by a scalar just multiplies the distance of the point with respect to the origin. This scalar is just a fancy name for a real number; you might have noticed mathematicians love fancy words. So in other words, if a = (x, y, z) and r is a real number, then a*r = (x*r, y*r, z*r). If r is negative, you can see that the point will also be mirrored with respect to the origin.

The componentwise product works the same way as sum and addition, but it's a bit rarer in the mathematical context. It's very useful in computer graphics though, mostly in lighting calculations. This product is denoted with , and if a = (R, G, B, A) and b = (r, g, b, a), then ab = (R*r, G*g, B*b, A*a). Mathematicians call this product the Hadamard product (Jacques Hadamard, 1865 to 1963). Componentwise product is fine too.

There are also at least two more very useful products.

Dot and Cross Product

The dot product is the screwdriver of the toolbox. This product is written with the symbol •, and it's the sum of the components' products; if a = (X, Y, Z) and b = (x, y, z), then ab = X*x + Y*y + Z*z. Notice that the result is a scalar, or a real number. The usefulness of this product comes mainly from the fact that if a and b are both unit-length (X2 + Y2 + Z2 = 12), then, denoting the angle between b and a with α, it holds that ab = cos α. Generally, if a and b are not necessarily of unit length, then ab / |a||b| = cos α, where |v| denotes the length of a vector.

In 3d there's the cross product. Its main purpose is outputting a vector that's orthogonal to two given vectors, i.e. getting their normal vector. It can also be used to calculate the sine of the angle between two vectors. A funny fact is that a cross product only exists in 3 and 7 dimensions. The formula for cross product is pretty symmetric; if a = (X, Y, Z) and b = (x, y, z), then a × b = (Yz - Zy, Zx - Xz, Xy - Yx). Notice that this product is a bit special in that a × b = - b × a, so you can't just switch the order mindlessly. It is also true, like stated before, that a × b is orthogonal to both a and b. In mathematical notation, (a × b) • a = 0 and (a × b) • b = 0. For the direction of the cross product vector there's the right-hand rule, well described in this wiki article.

Continuing soon...
It's a known fact that once you open a Wikipedia page, you just can't stop reading. I'll set here a trap for you and I bet you can't oppose it:
Euclidean vector
Unit vector
The Gram-Schmidt algorithm

I'm planning to continue with matrices, bases, coordinate transforms, quaternions and such. If you'd like to suggest a topic or ask a question, please comment! :)

1. HI!

Very cool to see other developers using JS in games as well. I have been working with it for a long while.

Have you considered using an existing library for maths?
http://sylvester.jcoglan.com/

Also, I would like to discuss some v8 stuff if you don't mind? Feel free to email me : fuzzyspoon at gmail.com

FuzzYspo0N
http://blog.centrc.net

2. So it's doable after all!

I have postponed the scripting language decision since I'm not yet sure which one I should implement support for. Last time I checked V8 didn't seem nice enough to me. Maybe I missed some seemingly trivial thing, like a hidden cache of superfluous documentation, or then I just had bad luck or wanted too clean code ;)

I'm not sure if JS is the easiest language to learn for our map and scripting guys though, with mostly some C++ or Java experience. At the moment I'm thinking of Lua, or maybe Python.

3. All of the languages have many exceptional qualities and of course it boils down to your needs as a team.

But, as with many, the v8 docs are simple and uninformative. The crucial breakdown of how v8 works though, can easily be understood by studying those using it extremely effectively. Take http://nodejs.org for example. They now have a huge user base, all of which use v8 to write plugins. This has led to many blog posts, many helper libraries and many many already made extensions to the platform itself.

With that in mind, here is an example
Mit licence, 100% mappable and simple to implement. It also implements the module system which is really easy to extend your game with modules dynamically at runtime. This makes it hugely more flexible than manually binding stuff at compile time, while the trend for server side and module extensions to v8 is incredibly unlikely to go away any time soon.

Have a look at one of the examples, Node has similar simpler code structures. This is from the UUID class, in the llv8call library.

MODULE()
{
CLASS();
BIND_CM("create", _create);
BIND_CM("createRandom", _createRandom);
BIND_CM("createTime", _createTime);
BIND_CM("fromString", _fromString);
BIND_CM("compare", _compare);
BIND_IM("toString", _toString);
INTERNALCOUNT(1);
EXPORT_CLASS("UUID");
}
ENDMODULE

I hardly find this kind of code messy :)
Of course, there are other developers all around using all the other tools with just such examples, i think it comes down to the strengths of the team, and where they fit best.

The reasons i chose javascript?
1) Its a race war. Everyone wants to be faster. This means improvements all the time
2) Emergent technology, such as node, make the extensive work in all areas grow massively
3) There is a library for everything imaginable. As javascript and browsers are nothing new - this makes for easy pickings. AI Pathfinding? Done (fast, too). QuadTrees? Done. Things like that, box2d physics? Available in javascript too.
4) Strong developers behind the tech that are on the fringe of the development all the time. Constant updates to the v8 svn leave performance, fixes, platform support ALL the time.

Theres many more, im sure.
You may also be interested in libraries like http://mootools.net which offer full OOP programming in javascript, as well as many benefits and additions to the toolsets that can run in server side (or embedded javascript) runtimes.

Ecma script is 11 years old, and widely supported. Javascript being the most widely used extension of this standard is a good thing. Tools like javascript debuggers evolved due to the web world, fully usable and bindable to v8 - of course ;)

I hope that your choice speeds up your development though, and gives you as flexible platform as i am enjoying in my 2d engine :)