Vectors and Orientation

Date: 05/29/2003 at 01:15:18
From: John
Subject: Rotating a vector

Hey,

I am trying to write a game involving spaceships, and I have been 
coming across trouble regarding how to find relative positions. My 
ships are rectangular prisms and to check for the impact of a 
projectile (modeled as a point) I want to normalize a vector from the 
center of the ship to the projectile so that new vector's components 
give the x,y,z coordinates of the projectile relative to the ship 
(which can be rotated about all three axes) with the ship sitting 
along the axes (i.e. the sides of the ships are all normal or 
perpendicular to the axes). This will allow for easy hit detection.  

In addition, to find weapon facings I was hoping I could use a 
similar method to get a unit vector in the absolute direction of a 
weapon that is offset from the center of the ship, where the weapon's 
current direction is measured against the ship. And to make things 
easier for me to think about, I made the y-axis forward and the z-axis 
up, with theta measured against the y, clockwise positive, phi 
measured from y, but going to the z-axis, and a third angle I called 
eta to model the rotation of the ship about its y-axis.

The example:

A ship that naturally faces in the +y direction is rotated 45 degrees 
(clockwise in the XY plane), 45 degrees up (from the XY plane) and 
rotated about its central axis (i.e. about the vector representing the 
ship). A projectile is at (1, 2, 3). What is the position of the 
projectile relative to an unrotated ship? Also, if a gun is on the 
ship at (1,1,0) relative to the unrotated ship, and facing at -45 
degrees theta and 45 degrees phi, what is its facing in the absolute 
system?

Date: 06/03/2003 at 10:44:27
From: Doctor Tom
Subject: Re: Rotating a vector

Hi John,

Your question can have many answers, and the one that you use depends 
on how you're keeping track of the data in the program.

Let me tell you how I would do it. If this won't work for you, write 
back and we'll try to come up with a better way.

Assume you have a world coordinate system and that you know where 
everything is in that system with an x, y and z coordinate.

You also need to know the velocity in this system that will be a 
vector (vx, vy, vz). If your spaceship is at (x, y, z) and has 
velocity (vx, vy, vz) then after traveling for a short time t, its new 
position will be (x + t(vx), y + t(vy), z + t(vz)). Obviously, as the 
game goes on, the velocity can change in size and direction, but for 
each time step, you can assume that the velocity is constant through 
that tiny time step.

It may be that you need to take multiple small steps between each 
redisplay - it depends on the relative speeds of things. For example, 
if the projectiles are really fast, at one display time they might be 
on one side of a ship and on the next display time they may have 
completely passed through, so just checking for a collision before and 
after may miss the collision. This just depends on relative speeds, 
but if there's any chance of this happening, be sure to write your 
code so that you can do the calculations for multiple steps per 
display cycle.

For projectiles, a position and velocity is sufficient to describe
their state. For ships, you also have to keep orientation in mind.  
Usually the vector along the axis of the ship will be aligned with the 
velocity, but even if that were always the case, you still need to 
keep track of the "up" direction. In other words, if the pilot is 
facing in the direction of the velocity vector, his "up" direction 
could be at any angle perpendicular to this.

The usual way to keep track of orientation is with a little reference 
frame: three perpendicular normalized vectors. One vector points 
"forward," another perpendicular to that points "up" and there is a 
third, perpendicular to both, that points sideways.

As the spaceship flies along, the directions of the reference frame 
change. For example, if the pilot turns right, the "up" vector 
continues to point in the same direction, but the "forward" and 
"sideways" vectors change. If the pilot "pulls back on the stick" to 
climb, then the sideways vector stays the same, but the "forward" and 
"up" vectors change, et cetera.

To calculate these rotations of the reference frame, all you need to 
do is rotations about the three axes with standard rotation matrices.  
These can be applied to each of the three vectors "forward," "up," and 
"sideways" to get new versions of all three.

There will be roundoff error when you do this a whole bunch of times, 
so from time to time you'll need to renormalize.  Here's how to do 
that:  Make all the forward vectors have length 1 by dividing each 
component by its length.  Take the vector cross product of this vector 
with the sideways vector to get a new "up" vector guaranteed 
perpendicular to the "forward" vector. Normalize this new "up" vector.  
Finally, calculate a new sideways vector by taking the negative cross 
product of the new forward and up vectors. Now you will have a set of 
three vectors, all mutually perpendicular, and all of length one, so 
you'll have a new normalized frame.

If you put the three vectors "up," "forward," and "right" together to 
form a 3x3 matrix, this is exactly the matrix that will convert the 
reference frame of a ship in "standard position" with forward in the x 
direction, up in the y direction and sideways in the z direction to 
the current orientation.  To get the current orientation back to the 
standard position, you simply need to invert this matrix and multiply 
your points by the inverted version. Luckily, inversion of these 
normalized matrices is trivial - just transpose the matrix (exchange 
rows and columns).

So, suppose you have a ship at (x, y, z) and it has a frame of (fx, 
fy, fz) (forward), (ux, uy, uz) (up), and (sx, sy, sz) (sideways) all 
normalized and mutually perpendicular. The matrix:

( fx fy fz )
( ux uy uz)
( sx sy sz )

will transform points to the ship's coordinate system, so the 
transpose:

( fx ux sx )
( fy uy sy )
( fz uz sz )

will do the inverse operation.

Now, suppose you have a projectile at (px, py, pz).

First, translate the center of the ship and the projectile so that the 
center of the ship is at (0, 0, 0) by subtracting (x, y, z) from the 
projectile's coordinates: (px-x, py-y, pz-z).

Multiply that translated projectile's coordinates by the transposed 
matrix above. This will give the location of the projectile in ship's 
coordinates. Now see if the projectile is inside the ship: to be 
inside, its x-coordinate must be between the ship's minimum and 
maximum x-coordinates, et cetera.

This may seem messy, but it's the easiest way I know.

There may be minor errors in what I have just typed. As you code it 
up, test it with easy-to-check examples, say with the ship aligned 
with the axes, with the ship turned 90 degrees in some direction, with 
the ship rotated 45 degrees, and maybe one or two more.

You can find additional details in books on computer graphics.

Finally, I have written a couple of papers on matrices and 
transformations aimed at bright high-school kids that you might find 
helpful. Go to:

   Mathematical Circles Topics
   http://www.geometer.org/mathcircles 

and look at the PDF files:

   Homogeneous Coordinates for Computer Graphics
   http://www.geometer.org/mathcircles/cghomogen.pdf 

   Introduction to Matrices
   http://www.geometer.org/mathcircles/Matrices.pdf 

Good luck!  I'm sure you'll learn a lot.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/