Monday, August 20, 2012

3D Math Primer for Graphics and Game Development, 2nd Edition

I've picked up a copy of 3D Math Primer on Graphics and Game Development recently and have been slowly going through it.  It's been around 15 years since I took Linear Algebra, or had to do any real matrix or vector based math, so the brain cells are slowly being re-initialized.  Heh.  Hopefully, this turns into a series of posts to share as I relearn things cruising through the book.

Here's what I've covered so far.

Chapter 1 deals with coordinate systems and concepts.  I was always fairly decent at trig so this went by really quick.  Chapter 2 gets into vectors and discusses the importance of the dot and cross products.  I remember learning and using these in school, but their application in game development terms wasn't obvious to me.  There are a couple of really good exercises that hit home the importance of these two operations.

One of the exercises describes an NPC in a game at a point p, that has a forward vector v.  Given this, and a point x, how can you use a dot product for determining whether or not the point x is in front or behind the NPC?

There are a couple of things to know about the dot product.  First, it gives you a scalar.  Big whoop.  How can this be used?  Well, the sign of the scalar gives you an indication of the relative direction / angle between one vector and another.  If the dot product is positive, then the angle between them is between 0 and 90 degrees.  If the dot product is 0, then the vectors are orthogonal (ie. at right angles).  If the dot product is < 0, then the angle between the vectors is greater than 90 degrees (and less than 180).

So, given a NPC location of p, we can calculate a vector x-p that gives us a vector describing the relative position of point x from point p.  If we know the facing of the character (vector v at point p), then we can take the dot product between v and x-p and know the relative positioning.

Recall that the dot product yields a scalar, defined as:

a dot  b =
(ax*bx + ay*by + az*bz).

Given this, we can determine if point x is in front-of or behind the NPC:

If vx*(xx-px)+vy*(xy-py)+vz*(xz-pz) > 0, it's in front.  If it's < 0, is behind.  If it's == 0, then it's to the side of the NPC.


Using the magnitudes of the related vectors and the relation: cos theta = a dot b / (||a|| * ||b||), we can further determine the angle between the two vectors.

Another cool exercise from the book details the practical application of the cross-product.  If the NPC above navigates from point p to point q and then to point r in the x-z plane (using left hand orientation), how can we use a cross-product to determine if the NPC should turn clockwise or counter-clockwise at point q in order to reach r?

Recall that the cross-product yields a new vector, defined as:
a x b =
[ax ay az] x [bx by bz] =
[ay*bz-az*by -(ax*bz-az*bx) ax*by-bx*by]

Here, it helps to know that the cross-product for a couple of vectors yields another vector that is orthogonal to the other two vectors.  This vector gives a magnitude that is proportional to the area of the parallelogram area formed by the vector sides.  We can look at the direction of the vector to clue us in to whether the orientation from one vector to another is clockwise or counter-clockwise.  If the angle from a to b is less than 180 degrees, the resulting vector will point up (left-hand rule orientation) on the orientation is considered clockwise.  If the angle from a to b is greater than 180 degrees (ie.  from b to a is less then 180 degrees), the orientation is considered counter-clockwise and the resulting vector will point down.

In the NPC case above, it's pretty straightforward to calculate the cross-product.  Doing this results in a single vector that either points in the +y direction, or the -y direction. Using this info, we can easily determine which way to rotate the NPC at the point q.  The NPC could actually rotate either way and still reach the same position.  The cross-product ends up giving you the shortest direction to rotate through.

Cool x2!

No comments:

Post a Comment