A concept fundamental to motion in, and depiction of, two or higher dimensional universes is that of the  vector. A vector specifies both a direction and a distance travelled along that direction (eg."3 miles east"). Once we have established this concept, the position of a point in space is the vector going to the point from a specific origin point (eg."3 miles east of the church").

    Vectors are described in a given coordinate system but the vector can be said to exist independently of any coordinate system. The simplest coordinate systems are  Cartesian coordinates which describe vectors with reference to perpendicular axes conventionally refered to as X, Y (and Z) axes.


Coordinate Systems in Two Dimensions


Cartesian Coordinates
The X-component of a vector is its component in the direction of the X axis which is conventionally thought of as running from left to right across the paper (east). Its Y-component is its component in the Y direction which is conventionally ”up• the paper (north).

We write (x,y) or sometimes	æ	x	ö
	è	y	ø

for the vector with X-component x and Y-component Y. (5,2) for example is the vector described by travelling 5 units (miles, meters, lightyears or whatever) east and 2 units north.
Note that all points on the X-axis have zero Y component; for this reason, we often describe the X-axis as the y=0 line.

Polar Coordinates
The other common coordinate system for describing 2D vectors is polar coordinates. To describe a vector in this system we specify its length (sometimes called its magnitude) and its angle of deviation, measured counterclockwise, from a fixed (zero) reference direction, conventionally taken as due east to coincide with the X axis.
We write [r,f] for the vector having length r and inscribing an angle f with y=0. Since we can describe any vector in both Cartesian and polar coordinates it is useful to be able to convert between the two formats. It is traditional to use q for the angle in much of the literature, but we will use f here since this seques better with the traditional use of q and f in 3D spherical polar coordinates.

[r,f]	=	(rcosf,rsinf)
(x,y)	=	[ Ö (x2+y2),f(x,y)]
Where
f(x,y)	=	tan-1(y/x)	if x>0
		p- tan-1(-y/x)	if x<0
		p/2	if x=0 y>0
		-p/2	if x=0, y<0
		Arbitary	if x=y=0.

Both systems have their advantages. It is very easy to rotate a vector by an angle f' if it is expressed in polar coordinates for the result is just [r,f+_polang']; whereas in Cartesian coordinates it is (xcosf'-_y sinf',x sinf'+_y cosf').
On the other hand it is much harder to add vectors if they are expressed in polar coordinates. In Cartesian Coordinates we simply add the corresponding components [  3 east and 5 north plus 1 east and -3 north (ie. 3 south) equals 4 east and 2 north ]. Formally, we have:

(x1,y1)	+	(x2,y2)	=	(x1+x2,y1+y2)
[r1,f1]	+	[r2,f2]	=	[r, sin-1(r2 sin(f2-f1)/r)+f1]

where  r = Ö(r₁²+r₂²-2r₁r₂ cos(f₁-f₂)).
This latter expression involves 5 multiplications, 1 division, 1 square root, and 3 trigonometric operartions (5M+1D+1Ö+3T). Converting both vectors into Cartesian coordinates, adding them directly, and then converting back involves 6M+1D+Ö+5T and is therefore slower by 1M+2T.

    Rather than writing all our vectors as (x,y) or [r,f] we use bold letters to refer to vectors to distinguish them from "normal numbers" or scalers and so avoid having to express them in a particular coordinate system. In the presence of Cartesian axes we write r₁ for the X component of a vector r, and r₂ for its Y component. We often write r for the magnitude (length) of the vetor r.

Coordinate Systems in Three Dimensions
  Cartesian coordinates can be readily extended to cover three dimensions by adding a third "Z" axis perpendicular to the X and Y axes. This may be thought of as coming "up out of" the paper. Three dimensional Cartesian vectors behave very much the same as two dimensional ones. It is conventional to ensure that the X,Y, and Z axes form a right handed triad (which means that if you were to place your right hand at the origin and point your first finger along the X axis and your second along the Y axis your thumb would point down the Z axis) although a left handed set is more intuitive when considering cameras.
Cartesian coordinates are the favourite for 3D game programmers and many games, such as Elite, use them exclusively.

    There are two other common coordinate systems for three space.

   Cylindrical polar coordinates
P  Cylindrical polar coordinates replace the Cartesian X and Y coordinates by their polar equivalents but retains the Z component. Cylindrical polar coordinates are most useful in cases where one axis in the games 3D universe is somehow different from the other two. One example of this is Battlezone, involving a tank travelling over a flat landscape. The X and Y coordinates are used to specify position on the landscape and the Z coordinate gives its height above the landscape. If the origin of the coordinate system is kept as the player‘s tank and the "zero direction" of the polar coordinates is say, north on the landscape, it becomes very easy to check player visibility of objects (is the objects f within a given deviation from the player‘s viewing angle?).
 We will write a vector  expressed in this format as [s,f,z).

Spherical polar coordinates
     

     Spherical polar coordinates specify the length of the vector with a scalar r and its direction by means of two angles: f as for cylindrical polar coordinates, and f, the angle between the vector and the Z axis.

    Spherical polar coordinates can be used to advantage in 3D games particularly when defining orientations (see below). One advantage they possess is that only one of the three parameters, r, needs to handle the "size" of the game volume. If our game universe is set in a cube having side length 2³² then a general point requires 12 bytes (three four- byte words) to specify in a Cartesian format. The same point can be specified, albeit highly inaccurately for large r, with just eight bytes in spherical polars (four bytes for r, two each for f and f).

    We can convert between these three principle 3D coordinate systems using:

[f,q,r]	=	(rsinqcosf,rsinqsinf,rcosq)	=	[rsinq , f , rcosq)
(x,y,z)	=	[ tan-1(y/x) ,  cos-1(z/ Ö (x2+y2+z2) , Ö (x2+y2+z2)]	=	[ Ö (x2+y2) ,  tan-1(y/x) , z)
[s,f,z)	=	[f , Ö (s2+z2) ,  cos-1(z/ Ö (s2+z2)]	=	(scosf , ssinf , z)

Scaled Cartesian coordinates
Scaled Cartesian Coordinates represent a vector r as a vector r~ of magnitude <1 and a magnitude r so that r = rr~. Typically, r would be a four-byte integer or one-byte exponent and r~ be comprised of three two-byte words. We will use the notation <r,x,y,z> for such a representation. If we choose r so that r~ is a unit vector then since x,y, and z will all have magnitude <1 we can find angles a,b, and g such that x=cosa,y=cosb,z=cosg. We will use the notation <r,a,b,g) for this  directed cosine representation.

Added square Cartesian Coordinates
Added Square Cartesians represent a vector with four values (x,y,z,S> where S=x²+y²+z².

Vector Operations
    3D games involve a lot of manipulation of vectors so we will consider their mathematical properties in some detail even though many good books are available on the subject (eg.Vector Analysis and Cartesian Tensors by D.E.Bourne and P.C.Kendall (Van Nostrand Reinhold)).
Before we embark on a discussion of vector algebra, we will establish some terminology.
A vector is  normal or  normalised if it has unit magnitude, ie. its length is one.
Two vectors are said to be  orthogonal if their directions subtend an angle of p/2 (90^o). We require the scalar product defined below to define this rigourously. A set of vectors is  orthonormal if all the vectors are normalised and any two of them are orthogonal.

    We have already seen how to add two vectors together. We can multiply a vector by a scaler by multiplying each Cartesian component of the vector by that scaler and this means that if we write i,j,k for the orthonormal vectors (1,0,0),(0,1,0) and (0,0,1) respectively  we can think of (x,y,z) as xi+yj+zk. Is it possible to "multiply" two vectors together? There are in fact several vector "products":

Dot Product
    The  scalar product (aka  dot product,  commutative inner product ) of two vectors is the product of the lengths of the vectors and the cosine of the angle between them.
    We write r₁.r₂ = r₁r₂ cosf where f is the subtended angle between r₁ and r₂.

    In 2D we calculate dot products using:

(x1,y1).(x2,y2)	=	x1x2 + y1y2
[r1,f1].[r2,f2]	=	r1r2cos(f1-f2).

In 3D we have:

(x1,y1,z1).(x2,y2,z2)	=	x1x2 + y1y2 + z1z2
[r1,f1,z1).[r2,f2,z2)	=	r1r2cos(f1-f2) + z1z2
[r1,f1,q1].[r2,f2,q2]	=	r1r2(sin{f1sinf2cos(q1-q2)+cosf1cos{f2)
<r1,x1,y1,z1>.<r2,x2,y2,z2>	=	r1r2(x1x2 + y1y2 + z1z2)
<r1,a1,b1,g1).<r2,a2,b2,g2)	=	r1r2(cos(a1+a2)+cos(a1-a2)+cos(b1+b2)+cos(b1-b2)+cos(g1+g2)+cos(g1-g2)

Note that here scaled Cartesian coordinates have an advantage over unscaled ones in that fewer "wide" multiplications are required to calculate a scalar product. This is also true of vector products (see below).

    The scalar product has the following properties:

• If two vectors are orthogonal (f=90^o) their dot product is zero.
  
• For any vector r, r.r = r²cos0 = r², the square of the length of r. (We write r² as shorthand for r.r).
  
• i.i = j.j = k.k = 1 ; i.j = j.k = k.i = 0.
  
• For any vectors a,b, and c:
  a.(b+c) = a.b + a.c
  a.b = b.a
  
• In matrix notatation, r.s = r^Ts.
  

    The dot product may be used to find the the component of a vector r in a given direction n (r.n/n) or to find the angle between two vectors (cos­1(r₁.r₂/(r₁r₂)).


Cross Product
    The  vector product (aka  cross product) of two vectors is itself a vector having as its magnitude the product of the lengths of the two vectors times the sine of the angle between them; and a direction perpendicular to both. Since there are infact two such directions for a given vector pair r₁,r₂ (one the opposite of the other) we choose the one that makes r₁,r₂,r₁×r₂ a right- handed triad. This definition requires three dimensions, we cannot take vector products of 2D vectors without going into 3D.
For 3D vectors (x₁,y₁,z₁)×(x₂,y₂,z₂)=(y₁z₂-y₂z₁, x₂z₁-x₁z₂, x₁y₂-x₂y₁).
The vector product has the following properties:

• If two vectors are parallel (f=0 or p) their vector product is 0 (a vector having zero length)).
  
• i×i = j×j = k×k = 0 ; i×j = k ; j×k = i ; k×i = j
• For any vectors a,b,c, and d:
  a×(b+c) = a×b + a×c
  a×b = -b×a
  a×(b×c) = (a.c)b - (a.b)c
  (a×b)×c = ((a.c)I - ac^T)b where I is the identity matrix. (This is very useful in collision mechanics).
  a×b×c×d = 0 (since if a×(b×c) ¹ 0 then d must be a linear combination of a,b, and c)  

• For any vectors a,b, and c:
  aºb = a(b^T) (3×1 by 1×3 matrix multiply)
   bºa = (aºb)^T
  (aºb)c = (b.c)a

    Also of interest is the  skewed matrix vector product defined by aÄb = a^TbI - ab^T
    The skewed matrix vector product has the following properties:

• For any vectors a,b, and c:
  (aÄb) = (bÄa)^T
  (aÄb)c = (a×c)×b

    The  triple scalar product of three vectors is [a,b,c]=a.(b×c) and corresponds to the volume of the parallelepiped defined by a,b and c. It is equal to the determinent of the 3x3 matrix (a,b,c).

    The  triple vector product of three vectors is a×(b×c).

Curvature and Tortion
Perhaps surprisingly, any continuos 3D curve r=(x(_t),y(_t),z(_t)) may be specified with just two scalar functions r(_t), t(_t) together with a position r(0) and an orientation matrix. We define the  arc length s(_t) = ò₀^_tÖ(x'(u)² + y'(u)² + z'(u)²) du and rexpress r(_t) as r(s). Letting ' denote d/ds we have that
    |r'(s)| = 1 and we accordingly call r'(s) the  unit tangent.
    |r"(s)| is known as the  curvature of r(s).
    r(s) = 1/|r"(s)| is known as the  radius of curvature of r(s). Note that some authors use r to denote curvature.
    n(s)=r(s)r"(s) is known as the  unit principle normal of r(s) at s.
    b(s)=r(s)r'(s)×r"(s) is the  unit binormal of r(s) at s.
    |b'(s)|= 1/t(s) , known as the  tortion of r(s).
    (r',n,b) form an orthonormal vector triad known as the  moving trihedral.
    It can easily be shown that b'(s)=-n/t(s) and that t(s) = 1/(r'(s).(r"(s)×r"'(s))).

     Frenet's Formula states that

d/ds(r',n,b)	=	(r',n,b)	æ	0	-1/r	0	ö
			ç	1/r	0	-1/t	÷
			è	0	1/t	0	ø

Next : Approximating Polar Functions