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 | ø |
[r,f] | = | (rcosf,rsinf) | |
(x,y) | = | [ Ö (x^{2}+y^{2}),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. |
(x_{1},y_{1}) | + | (x_{2},y_{2}) | = | (x_{1}+x_{2},y_{1}+y_{2}) |
[r_{1},f_{1}] | + | [r_{2},f_{2}] | = | [r, sin^{-1}(r_{2} sin(f_{2}-f_{1})/r)+f_{1}] |
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_{1} for the X component of
a vector r, and r_{2} 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^{32} 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/ Ö (x^{2}+y^{2}+z^{2}) , Ö (x^{2}+y^{2}+z^{2})] | = | [ Ö (x^{2}+y^{2}) , tan^{-1}(y/x) , z) |
[s,f,z) | = | [f , Ö (s^{2}+z^{2}) , cos^{-1}(z/ Ö (s^{2}+z^{2})] | = | (scosf , ssinf , z) |
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_{1}.r_{2} = r_{1}r_{2} cosf
where f is the subtended angle between r_{1} and r_{2}.
In 2D we calculate dot products using:
(x_{1},y_{1}).(x_{2},y_{2}) | = | x_{1}x_{2} + y_{1}y_{2} |
[r_{1},f_{1}].[r_{2},f_{2}] | = | r_{1}r_{2}cos(f_{1}-f_{2}). |
(x_{1},y_{1},z_{1}).(x_{2},y_{2},z_{2}) | = | x_{1}x_{2} + y_{1}y_{2} + z_{1}z_{2} |
[r_{1},f_{1},z_{1}).[r_{2},f_{2},z_{2}) | = | r_{1}r_{2}cos(f_{1}-f_{2}) + z_{1}z_{2} |
[r_{1},f_{1},q_{1}].[r_{2},f_{2},q_{2}] | = | r_{1}r_{2}(sin{f_{1}sinf_{2}cos(q_{1}-q_{2})+cosf_{1}cos{f_{2}) |
<r_{1},x_{1},y_{1},z_{1}>.<r_{2},x_{2},y_{2},z_{2}> | = | r_{1}r_{2}(x_{1}x_{2} + y_{1}y_{2} + z_{1}z_{2}) |
<r_{1},a_{1},b_{1},g_{1}).<r_{2},a_{2},b_{2},g_{2}) | = | r_{1}r_{2}(cos(a_{1}+a_{2})+cos(a_{1}-a_{2})+cos(b_{1}+b_{2})+cos(b_{1}-b_{2})+cos(g_{1}+g_{2})+cos(g_{1}-g_{2}) |
The scalar product has the following properties:
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
(cos1(r_{1}.r_{2}/(r_{1}r_{2})).
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_{1},r_{2} (one
the opposite of the other) we choose the one that makes
r_{1},r_{2},r_{1}×r_{2} 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_{1},y_{1},z_{1})×(x_{2},y_{2},z_{2})=(y_{1}z_{2}-y_{2}z_{1}, x_{2}z_{1}-x_{1}z_{2}, x_{1}y_{2}-x_{2}y_{1}).
The vector product has the following properties:
Also of interest is the skewed matrix vector product defined by
aÄb = a^{T}bI - ab^{T}
The skewed matrix vector product has the following properties:
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) =
ò_{0}^{_t}Ö(x'(u)^{2} + y'(u)^{2} + z'(u)^{2}) 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 | ø |