Coordinate Systems, Vectors, Planes FAQ
=======================================
Version 1.4 28th December 2001
-------------------------------
This FAQ is now maintained by "andreas@(no-spam)cs.ualberta.ca".
Any additional suggestions or related questions are welcome.
Just send E-mail to the above address.
The latest copy of this FAQ can be found at the following web page:
http://www.cs.ualberta.ca/~andreas/math/vectfaq_latest.html
Feel free to distribute or copy this FAQ as you please.
Contributions
-------------
Appearance: Cleaned out some of the empty lines, made the header like the
matrfaq: Andreas Junghanns
History
-------
I (Andreas) received this FAQ from "Sylvain Carette" by email.
I tried to find "hexapod@(no-spam)netcom.com" who seemed to have maintained
this (as others) for a while, but the site at netcom.com doesn't exist anymore,
emails bounce. Since I (and colleques) wasted quite some time figuring out
what was wrong with some of the algorithms given in the earlier versions of
this document, I decided to correct it and put it back on the web.
The formerly given sites for the location of these documents do
not exist anymore:
ftp://ftp.netcom.com/pub/he/hexapod/index.html
http://www.glue.umd.edu/~rsrodger
Versions, dates and links to local copies (so you can compare):
vectfaq_1.03.html: Version 1.3 17th March 1998
vectfaq_1.04.html: Version 1.4 28th December 2001
Please refrain from asking me math questions. I am only maintaining this FAQ
and have very little knowledge about the subject. But, if you have a
question that is not answered by this FAQ and later happen to find the
answer and believe it to be relevant for this FAQ (or its readers), please
send all relevant information, hopefully in a pre-digested form, to me to
be included here. Thanks!
If you prefer to appear as "anonymous" in the contributions list, let me
know, otherwise I'll just put you down with whatever name I can gather from
your email header.
Questions
---------
COORDINATE SYSTEMS
==================
Q1. What is a coordinate system?
Q2. What is a point?
Q3. What is a origin?
Q4. What is a vector?
Q5. What is a column vector?
Q6. What is a row vector?
Q7. What is a vertex?
Q8. What are homogeneous coordinates?
Q9. What is the Euclidean coordinate system?
Q10. What is the Polar coordinate system?
Q11. How do I display Polar coordinates?
Q12. What are right-handed and left-handed coordinate systems?
Q13. Which is the best coordinate system to use?
Q14. How do rotation angles relate to coordinate systems?
Q15. What is a global coordinate system?
Q16. What is a local coordinate system?
Q17. How do I convert Euclidean to Polar coordinates?
Q18. How do I convert Polar to Euclidean coordinates?
Q19. How do I convert between rotation systems?
VECTORS
=======
Q20. How do I represent a vector using the C/C++ programming languages?
Q21. How do I calculate the length of a vector?
Q22. What is the magnitude of a vector?
Q23. What is a normalised vector?
Q24. How do I normalise a vector?
Q25. What is an unit vector?
Q26. What is a direction vector?
Q27. What is an outward normal?
Q28. What is a dot product?
Q29. How do I determine the angle between two vectors?
Q30. What is a cross product?
Q31. How do I add two vectors?
Q32. How do I subtract two vectors?
Q33. How do I scale a vector?
Q34. How do I perform linear interpolation between two vectors?
Q35. How do I perform cubic interpolation between four vectors?
PLANES
======
Q36. What is a plane equation?
Q37. How do I evaluate a point relative to a plane?
Q38. How do I find the point of intersection with a between and a plane?
Q39. How do I calculate the reflection of a vector from a plane equation?
Q40. How is the reflection of a vector equation derived?
Q41. How do I calculate the acceleration of an object on a sloping surface?
DEFORMATION PATCHES
===================
Q42. What are deformation patches?
Q43. What are linear deformation patches?
Q44. How do I perform linear deformation?
Q45. How do I implement a linear deformation system?
Q46. How do I define a cubic deformation patch?
Q47. How do I evaluate a deformation patch?
Q48. How do I implement a deformation patch system?
Q49. How can I use keyframe animation with deformation patches?
Answers
-------
COORDINATE SYSTEMS
==================
Q1. What is a coordinate system?
---------------------------------
A coordinate system is a way of defining multi-dimensional space so that
every individual point in space can be referenced uniquely.
Several types of coordinate systems exist. These include the following:
o Euclidean coordinate system
o Polar coordinate system
A coordinate system may exist in one, two, three or more dimensions.
A one dimensional coordinate system defines a set of coordinates along
a single straight line.
A two dimensional coordinate system defines a flat rectangular space.
This requires a pair of coordinates.
A three dimensional coordinate system defines a solid box. This requires
a triplet of coordinates.
A coordinate system using four or more dimensions requires some
imagination in order to be visualised. Several method exist to handle
this situation.
With four to six dimensions, the first three coordinates can be used to
define standard 3D Euclidean space. The remaining three coordinates
can be converted into a set of RGB color values. This system is used
in CAT or NMR scanners. The first three dimensions are the position of
the patients body. The fourth dimension defines the signal intensity
for an individual voxel or point in the patients body.
Q2. What is a point?
---------------------
A point is an absolute position in space. It measures the displacement
of the point along each axis or dimension of the coordinate system.
Q3. What is a origin?
----------------------
The origin is the point within the coordinate system, where the
displacement along each axis or dimension is equal to zero.
For example, with the Euclidean coordinate system, the point (0,0,0)
is the origin.
Q4. What is a vector?
----------------------
Mathematically speaking, a vector differs from a point in that it
defines the displacement between two points rather than the
physical location of an actual point in space.
A point does not define a direction, while a vector does.
However, a vector between the origin and a point in space, has exactly
the same coordinates.
Q5. What is a column vector?
------------------------------
By convention, two dimensional and three dimensional vectors are
represented as a single vertical column of numeric values ie:
| x | | x |
V = | | V = | y |
| y | | z |
Two dimensions Three dimensions
A list of vectors (eg. the geometry of a 3D model) is represented
simply by adding additional columns ie.
| x1 x2 x3 ... xN |
V = | y1 y2 y4 ... yN |
| z1 z2 z4 ... zN |
Q6. What is row vector?
------------------------
For problem-solving, a vector may be described as V = (x,y,z) during
the specification of a problem.
This is a row vector. However, row-vectors should not really be used
with any mathematical descriptions.
Q7. What is a vertex?
----------------------
A vertex is another name for a point. However, it used specifically
when referring to a group of points arranged into a geometric shape.
Q8. What are homogeneous coordinates?
--------------------------------------
Homogenous coordinates are used in order to implement perspective depth
projection operations using matrices. With ordinary matrix multiplication
it is not possible to divide columns of a matrix by the value of a
particular element ie. Dividing X and Y by Z.
Homogeneous coordinates get around this problem by defining an additional
coordinate W. When vectors are normally defined, this value is always
set to 1.0. Because, of this, it is not usually necessary to store this
value with 3D coordinates and vectors.
The use of this coordinate is the reason why all projection matrices are
4x4 in size.
When a 3D vector is multiplied with a projection matrix, the W
coordinate gets multiplied alongside XYZ. The resulting value is
then used to divide each of X,Y and Z.
A simple perspective matrix will set the value of W to Z.
Q9. What is the Euclidean coordinate system?
---------------------------------------------
Euclidean coordinates can range from 1 to N dimension. Each dimension
is always perpendicular to all the others. Two and three dimensions
are most commonly used by game systems.
In a two dimensional system, each position is defined by two coordinates
X and Y. A two-dimensional system is as follows:
+-------------------+
| |
| +Y |
| |
| o |
| | |
| | |
| | |
| | |
| ....o----o +X |
| . |
| . |
| . |
| . |
| |
+-------------------+
In a three dimensional system, an additional Z coordinate is added.
+-------------------+
| |
| +Y |
| |
| o |
| | |
| | |
| | |
| | |
| ....o----o +X |
| /. |
| / . |
| / . |
| +Z o . |
| |
+-------------------+
For example, a football field can be represented as a coordinate system.
The centre point is the origin. The X axis is the centre line, the Z
axis is the direction from one goal to another and the Y axis is the
height of the football from the ground.
The Euclidean coordinate system can also be extended into four or more
dimensions.
For example, in a flight simulator game, it may be useful to keep track
of the flight path of an aeroplane. In this case, the fourth dimension
actually defines time.
Q10. What is the Polar coordinate system?
-----------------------------------------
The Polar coordinate system differs from the Euclidean coordinate system
in that each point in space is defined in terms of its position and
distance from a sphere with unit radius.
The centre of the sphere is the origin . The first two coordinates
define longitude and latitude on the sphere. In effect they wrap a two
dimensional coordinate system onto the surface of the sphere.
The third coordinate defines the distance of the point from the centre
of the sphere.
Each point defines a triplet of values (latitude, longitude and height).
Latitude ranges from +90 to -90. Longitude ranges from -180 to +180, and
height range from 0 to infinity. Height can be negative.
ie. ( +90, --, +r ) defines the North Pole.
( -90, --, -r ) defines the South Pole.
( 0, 0, r ) is a point on the equator.
Q11. How do I display Polar coordinates?
----------------------------------------
Longitude and Latitude can be displayed as floating point values or
as degrees, minutes and seconds (and even arc-seconds).
These angles are represented in the format
o
dd mm' ss"
where dd ranges from -180 to 180,
mm ranges from 0 to 59,
and ss ranges from 0 to 59.
dd defines the integer number of degrees, while mm and ss take the
fractional part and scale it into two other integers ie:
----------------------------------
frac = modf( angle, &dd ) * 3600.0
ss = frac % 60
mm = frac - ss
----------------------------------
Q12. What are right-handed and left-handed coordinate systems?
---------------------------------------------------------------
When working with coordinates in the Euclidean coordinate system
there are two possible ways of arranging the three XYZ coordinate
axii.
One way is to have the positive Z-axis point outwards of the screen.
This is referred to as the "right-handed coordinate system" and is
the system preferred by mathematicians.
The more negative a coordinate is, the further back into the screen it
appears. Coordinates with positive values are behind the observer.
Alternatively, the positive Z-axis can be made to point into the
screen. This is referred to as the "left-handed coordinate system".
This is opposite to the right-handed coordinate system. The more
positive a coordinate is, the further back into the screen it appears.
Coordinates with positive values are behind the observer.
Left-handed coordinate system Right-handed coordinate system
+-----------------------------+ +------------------------------+
| | | |
| +Y | | +Y |
| ^ | | ^ |
| | +Z | | | |
| | -o | | | . |
| | /| | | | . |
| | / | | | . |
| | / | | | . |
| |/ | | |. |
| .......o-------> +X | | .......o-------> +X |
| .. | | /. |
| . . | | / . |
| . . | | / . |
| . . | | |/ . |
| . . | | o- . |
| . | | . |
| . | | +Z . |
| | | |
+-----------------------------+ +------------------------------+
If the direction of the Y-axis is reversed, then whichever coordinate
system is currently in use becomes the direct opposite.
OpenGl and XGL use the right-handed coordinate system. Direct3D uses
the left-handed coordinate system.
The terms "left-handed" and "right-handed" are
derived from the way you can use your thumb, index and middle fingers
to model the
selected coordinate systems.
If you point the index finger of your right hand in the direction of
the Z-axis, then your right thumb points in the direction of the Y-axis
and your right middle finger points in the direction of the X-axis.
If the direction of the Z-axis is reversed (ie. pointing into the
screen) then this is defined as a "left-handed" coordinate system.
This is because your left thumb now points in the direction of the
Y-axis and your left middle finger nows points in the direction of
the X-axis.
Q13. Which is the best coordinate system to use?
------------------------------------------------
In practical use, there is no particular advantage that either the
left-handed or right-hand coordinatee systems has over the other.
The main reason for choosing one system over the other is purely
a matter of convenience.
Such reasons might include maintaining compatability with the
underlying 3D API or geographical coordinate system. For example
OpenGL uses a right-handed coordinate system, while Direct 3D uses
a left-handed coordinate system.
For an aircraft simulator, it is convenient to "map" the geographical
longitude with the X-axis, geographical latitude with the Y-axis and
height (or depth) with the Z-axis. When combined together, all three
coordinate axii form the right-handed coordinate system, albeit rotated
-90 degrees in the X-axis.
Right-handed coordinate system
for aircraft simulator
+------------------------------+
| |
| +Z |
| ^ +Y |
| | -o |
| | /| |
| | / |
| | / |
| | / |
| |/ |
| .......o-------> +X |
| .. |
| . . |
| . . |
| . . |
| . . |
| . |
| . |
| |
+------------------------------+
In the case of a submarine simulator, the Z-axis actually has polarity
reversed, so that positive values of Z represents increasing depth,
while the X and Y still represent longitude and latitude respectively.
Thus, all three coordinate axii form the left-handed coordinate system,
albeit rotated +90 degrees in the X-axis.
Left-handed coordinate system
for submarine simulator
+-----------------------------+
| |
| . |
| . +Y |
| . -o |
| . /| |
| . / |
| . / |
| ./ |
| .......o-------> +X |
| .| |
| . | |
| . | |
| . | |
| . | |
| | |
| V |
| +Z |
| |
+-----------------------------+
For the aircraft simulator, converting coordinates to OpenGL is simply
a matter of performing a +90 degree rotation in the X-axis.
Likewise, for the submatine simulator, the conversion to OpeGL is
simply a matter of performing a -90 degree rotation in the X-axis.
Q14. How do rotation angles relate to coordinate systems?
---------------------------------------------------------
By mathematical convention, a positive rotation angle generates a
clockwise rotation when looking from the origin towards the positive
end of the selected rotation axis.
Given this relationship between rotation angles and coordinate
systems, it is possible to derive the rotation matrices for each
rotation axis.
Q15. What is a global coordinate system?
----------------------------------------
Global coordinate system are used to assign the coordinates of all
points relative to a single common origin.
For example, when tracking the positions of players in a 3D maze, it
is convenient to have all players and obstacles assign coordinates
relative to a single common origin eg. The entrance/exit of the maze.
Q16. What is a local coordinate system?
---------------------------------------
Local coordinate systems are used to assign the coordinates of all
points relative to one or more origins.
For example, using the Euclidean coordinate system to animate the
movement of a multi-jointed robot arm, it is convenient to assign
each joint separate local coordinate systems.
The point of rotation of each joint actually becomes the origin of
the related geometry.
This allows for the surface geometry of each joint to be transformed
by the current position of that joint.
The coordinate system need not always Euclidean. In the case of
astronomy and tracking the positions of features on the moon or
other planets, it is necessary to give each planet its own local
polar coordinates system.
However, the position of all planets can be defined using a global
coordinate system, with the Sun being placed at the origin.
Q17. How do I convert Euclidean to Polar coordinates?
-----------------------------------------------------
With a Euclidean coordinate (x y z), the goal is to convert it into a
Polar coordinate (latitude, longitude, distance).
The conversion is as follows:
-----------------------------------------
distance = sqrt( x*x + y*y + z*z )
x /= distance;
y /= distance;
z /= distance;
xz_dist = sqrt( x*x + z*z )
latitude = atan2( xz_dist, y ) * RADIANS
longitude = atan2( x, z ) * RADIANS
-----------------------------------------
Q18. How do I convert Polar to Euclidean coordinates?
-----------------------------------------------------
With a Polar coordinate (latitude, longitude, distance), the goal is to
convert it into a Euclidean coordinate (x y z).
The conversion is as follows:
-----------------------------------------
x = cos( latitude ) . sin( longitude )
y = sin( latitude )
z = cos( latitude ) . cos( longitude )
-----------------------------------------
Q19. How do I convert between rotation systems?
-----------------------------------------------
Altogether, there are around five different ways in which a rotation
in three dimensions can be represented:
These include:
Euler angles
Matrices
Quaternions
Rotation Axis/Angle
Spherical Rotation Angles
Euler angles define each rotation as a combination of rotations in
each of the three main X, Y and Z axii. Euler angles must be converted
to matrices before any vertex transformations can be performed.
Matrices define each rotation as an 2D array of values which are
multiplied with an array of vertices. They can either be 3x3 or 4x4
in size.
Quaternions define each rotation in 4 dimension instead of three. As a
result they require four floating point values. Quaternions must be
connverted to matrices before any vertex transformation can be
performed.
Rotation Axis/Angles define each rotation as a unit vector along with
a specifiede rotation angle along that axis. Rotation Axis/Angle pairs
must be converted into Quaternions before finally being converted into
a rotation matrix.
Spherical angles define each rotation in terms of latitude/longitude
and a rotation angle. They must be converted into a rotation matrix
through the use of AxisAngle and Quaternion coordinates.
The conversion paths are as follows:
+--------------+ +--------------+ +--------------+
| Matrix |<===>| Quaternion |<===>| AxisAngle |
+--------------+ +--------------+ +--------------+
/\ /\
|| ||
\/ \/
+--------------+ +--------------+
| Euler angles | | Spherical |
+--------------+ +--------------+
A comparision of the various representations is presented below:
+--------------+------------+---------------------------------------+
| Data type | Size | Usage |
+--------------+------------+---------------------------------------+
| Euler Angles | FLOAT * 3 | Must be converted to a matrix |
| | | Gimbal lock can occur |
+--------------+------------+---------------------------------------+
| Matrix | FLOAT * 9 | Can be used directly for vertex |
| | FLOAT * 16 | transformation |
| | | 3x3 matrices can be used for rotation |
| | | and scaling only. |
| | | 4x4 matrices can be used for both |
| | | translation and perspective |
+--------------+------------+---------------------------------------+
| Quaternion | FLOAT * 4 | Must be converted to a matrix |
| | | No danger of Gimbal lock |
+--------------+------------+---------------------------------------+
| Axis Angle | FLOAT * 4 | Must be converted to a matrix through |
| | | the use of Quaternions. |
| | | No danger of Gimbal lock |
+--------------+------------+---------------------------------------+
| Spherical | FLOAT * 3 | Must be converted to a matrix through |
| | | the use of AxisAngle and Quaternion |
| | | representations. |
| | | No danger of Gimbal lock |
+--------------+------------+---------------------------------------+
VECTORS
=======
Q20. How do I represent a vector using the C/C++ programming languages?
-----------------------------------------------------------------------
The most convenient way of representing a vector using the C/C++
programming languages is through the use of a data structure:
typedef float VFLOAT;
typedef vector3_st
{
VFLOAT vx;
VFLOAT vy;
VFLOAT vz;
} VECTOR3;
or through the use of arrays:
typedef VFLOAT VECTOR3[3];
For convenience and modularity, it is always a good idea to define
labels for commonly used data types that may vary from system to system.
Thus floating point values are given the label "VFLOAT".
Q21. How do I calculate the length of a vector?
-----------------------------------------------
The length of a vector is calculated by taking the square root of
the sum of the squares of each coordinate ie.
If the vector is defined as (x,y,z) then the length of the vector is
calculated from:
----------------
/ 2 2 2
L = \/ x + y + z
Q22. What is the magnitude of a vector?
---------------------------------------
This is equivalent to the length of a vector.
Placing a pair of vertical lines around a vector indicates the
magnitude of the vector.
eg. If the variable V is used to represent a vector, then the
expression |V| indicates the magnitude of a vector.
Q23. What is a normalised vector?
---------------------------------
A normalised vector is a vector where the sum of the squares of all
coordinates is equal to one.
For example, the vector ( 2, 2, 0 ) is not normalised, while the
vectors ( 0.707, 0.707, 0.0) and ( 1.0, 0.0, 0.0 ) are normalised.
Q24. How do I normalise a vector?
---------------------------------
A vector can be normalised by calculating the magnitude or length of
the vector and dividing each coordinate by this value.
For example, consider the vector
| 3.0 |
V = | 4.0 |
| 0.0 |
The length of this vector is 5.0
|V| = 5.0
Then the value of the normalised vector is given by:
V | 3.0 | 1 | 0.6 |
--- = | 4.0 | . - = | 0.8 |
|V| | 0.0 | 5 | 0.0 |
If the vector is already normalised, then the value of |V| will be
equal to one, and after division, the vector will remain as before.
Q25. What is an unit vector?
----------------------------
A unit vector is another name for a normalised vector. The sum of the
squares of all coordinates is equal to one.
Q26. What is a direction vector?
--------------------------------
A direction vector is another name for a vector, but which is
specifically used for the purpose of determining the direction that
a polygon surface or vertex is facing.
However, direction vectors are not necessarily always normalised.
For example, a direction vector may be used to represent wind direction
of points within a landscape. The magnitude of the vector is used to
represent wind speed combined with the direction of the wind.
Q27. What is an outward normal?
-------------------------------
An outward normal is another name for a normalised vector. Similar
in purpose to a direction vector, an outward normal are used
specifically for representing the direction that a polygon surface or
vertex is facing.
Q28. What is a dot product?
---------------------------
The dot product is used to calculate the angle between two vectors.
If v1 and v2 are two normalised vectors, then the dot product is given
by the expression:
v1.v2
For a pair of three dimension vectors this expression is evaluated
using the equation:
d = v1 . v2
| x1 | | x2 |
d = | y1 | . | y2 |
| z1 | | z2 |
d = x1.x2 + y1.y2 + z1.z2
This can be represented using the C/C++ programming languages as:
d = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z
where * is the standard multiplication operation.
For efficiency, this function can represented as C #define macros or
C++ inline class functions.
Q29. How do I determine the angle between two vectors?
------------------------------------------------------
The angle between two normalised vectors can be calculated from the
mathematical expression:
cos A = v1.v2
| x1 | | x2 |
= | y1 | . | y2 |
| z1 | | z2 |
where cos is the cosine function,
A is the angle between the two vectors,
v1 is the first vector and
v2 is the second vector
The expression v1.v2 is the actual dot product
If the two vectors are not normalised, then the following expression
can be used:
v1.v2
cos A = ---------
v1 . v2
-- --
where -- is the magnitude or length of the vector.
This takes the dot product of the two vectors, and divides the result
by the product of the lengths of both vectors.
Q30. What is a cross product?
-----------------------------
The cross product between two normalised vectors is used to determine
the vector which perpendicular to both the vectors. This is expressed
as the mathematical expression:
v3 = v1 x v2
| x1 | | x2 |
v3 = | y1 | x | y2 |
| z1 | | z2 |
| y1.z2 + z1.y2 |
v3 = | z1.x2 + x1.z2 |
| x1.y2 + y1.x2 |
This can be represented using the C/C++ programming languages as:
v3.vx = v1.y * v2.z + v1.z * v2.y
v3.vy = v1.z * v2.x + v1.x * v2.z
v3.vz = v1.x * v2.y + v1.y * v2.x
For efficiency, this function can represented as C #define macros or
C++ inline class functions.
Q31. How do I add two vectors?
------------------------------
Adding two vectors together is very simple to perform. This is achieved
by adding together the individual coordinates of each vector. The
operation is defined by the following mathematical expression:
v3 = v1 + v2
| x1 | | x2 |
v3 = | y1 | + | y2 |
| z1 | | z2 |
| x1 + x2 |
v3 = | y1 + y2 |
| z1 + z2 |
This can be represented using the C/C++ programming languages as:
v3.vx = v1.vx + v2.vx
v3.vy = v1.vy + v2.vy
v3.vz = v1.vz + v2.vz
For efficiency, this function can represented as C #define macros or
C++ inline class functions.
Q32. How do I subtract two vectors?
-----------------------------------
Subtraction is performed in the same way as addition. This is achieved
by subtracting the individual coordinates of each vector. The
operation is defined by the following mathematical expression:
v3 = v1 - v2
| x1 | | x2 |
v3 = | y1 | - | y2 |
| z1 | | z2 |
| x1 - x2 |
v3 = | y1 - y2 |
| z1 - z2 |
This can be represented using the C/C++ programming languages as:
v3.vx = v1.vx - v2.vx
v3.vy = v1.vy - v2.vy
v3.vz = v1.vz - v2.vz
For efficiency, this function can represented as C #define macros or
C++ inline class functions.
Q33. How do I scale a vector?
-----------------------------
A vector can be scaled (enlarged or reduced) in a way similar to
multiplication. This is achieved by multiplying each coordinate by the
same scaling factor. The mathematical expression for this is as follows:
v2 = v1 . S
| x1 |
v3 = | y1 | . S
| z1 |
| x1.S |
v3 = | y1.S |
| z1.S |
This can be represented using the C/C++ programming languages as:
v3.vx = v1.vx * S
v3.vy = v1.vy * S
v3.vz = v1.vz * S
For efficiency, this function can represented as C #define macros or
C++ inline class functions.
Q34. How do I perform linear interpolation between two vectors?
---------------------------------------------------------------
For many 3D applications, it is sometimes necessary to perform linear
interpolation between two vectors. Such applications can include view
frustum clipping and morphing.
Linear interpolation is implemented by taking the coordinates of two
known points and scaling them in such a way as to generate a series
of points that forms a straight line between them.
This equation is sometimes referred to as a blending function. For
linear interpolation this equations is as follows:
V' = (1-t).Va + t.Vb
V' = Va + t.(Vb-Va)
The second form is more commonly used as it only requires a single
multiplication operation.
This is implemented using the following set of vector operations:
Using the C programming language:
void v3_linear( VECTOR3 *vr, VECTOR3 *va, VECTOR3 *vb, VFLOAT t )
{
v3_sub( &vtemp, vb, va );
v3_scalef( &vtemp, &vtemp, t );
v3_add( &vr, &vtemp, va );
}
Q35. How do I perform cubic interpolation between four vectors?
---------------------------------------------------------------
Given four vectors, the problem is to find a way of determining
intermediate positions specified by a parametric variable t.
This can be achieved by making use of cubic interpolation. The set
of four vectors is combined into a single geometry vector G.
Through the use of spline mathematics, this geometry vector is
converted into an interpolation matrix M.
If the geometry vector is defined as:
| x1 x2 x3 x4 |
G = | y1 y2 y3 y4 |
| z1 z2 z3 z4 |
Then multiplication by the base matrix:
| -4.5 9.0 -5.5 1.0 |
Mb = | 13.5 -22.5 9.0 0.0 |
| -13.5 18.0 -4.5 0.0 |
| 4.5 -4.5 1.0 0.0 |
will generate the 3x4 interpolation matrix Mi:
Mi = G .Mb
This can be implemented through a modified matrix-vector multiplication:
m4_multspline( m_cubic, v_geom, v_source );
Interpolation can then be performed by the use of the parametric
variable t:
R = Mi . t
|t^3|
| xr | | A B C D | |t^2|
| yr | = | E F G H | . |t |
| zr | | I J K L | |1 |
This can be implemented through a modified cubic interpolation
algorithm:
v3_cubic( vr, v_geom, t );
The resulting vector can then be used as required.
The function m4_multspline is implemented as follows:
-------------------------
void m4_multspline( MATRIX4 mat, VECTOR3 *vsrc, VECTOR3 *vdst )
{
VFLOAT tx, ty, tz;
int n;
for ( n = 0; n < 4; n++ )
{
vdst[n].vx = vsrc[0].vx * mat[n]
+ vsrc[1].vx * mat[n+4]
+ vsrc[2].vx * mat[n+8]
+ vsrc[3].vx * mat[n+12];
vdst[n].vy = vsrc[0].vy * mat[n]
+ vsrc[1].vy * mat[n+4]
+ vsrc[2].vy * mat[n+8]
+ vsrc[3].vy * mat[n+12];
vdst[n].vz = vsrc[0].vz * mat[n]
+ vsrc[1].vz * mat[n+4]
+ vsrc[2].vz * mat[n+8]
+ vsrc[3].vz * mat[n+12];
}
}
-------------------------
The function v3_cubic is implemented as follows:
-------------------------
void v3_cubic( VECTOR3 *vpos, VECTOR3 *vdst, VFLOAT t )
{
vpos -> vx = ((vdst[0].vx*t+vdst[1].vx)*t+vdst[2].vx)*t+vdst[3].vx;
vpos -> vy = ((vdst[0].vy*t+vdst[1].vy)*t+vdst[2].vy)*t+vdst[3].vy;
vpos -> vz = ((vdst[0].vz*t+vdst[1].vz)*t+vdst[2].vz)*t+vdst[3].vz;
}
-------------------------
In fact, a cubic spline surface can be generated from the combination
of these two algorithms:
-------------------------
void cubic_patch( VECTOR3 *vlist, VECTOR3 *vsurf, int hdiv, int vdiv )
{
MATRIX4 mh_geom[4];
VECTOR3 mv_geom[4], mv_interp[4];
VFLOAT du, dv;
int n, u, v;
if ( hdiv < 1 || vdiv < 1 ) /* Not enough subdivisions? */
return; /* No, so return */
for ( n = 0; n < 4; n++ ) /* Horiz. interp */
m4_multspline( m_cubic, vsurf+n*4,mh_geom[n]); /* Make I-matrix */
for ( u = 0; u <= hdiv; u++ ) /* For each column */
{
for ( n = 0; n < 4; n++ )
v3_cubic( mv_geom+n, mh_geom[n], (VFLOAT) u/hdiv );
m4_multspline( m_cubic, mv_geom, mv_interp ); /* Make I-matrix */
for ( v = 0; v <= vdiv; v++, vlist++ ) /* For each row */
v3_cubic( vlist,mv_interp,(VFLOAT) v/vdiv ); /* Save vertex */
}
}
-------------------------
PLANES
======
Q36. What is a plane equation?
------------------------------
Plane equations are widely used in the field of 3D animation to
define and manipulate polygon surfaces. Plane equations are used to
implement back face culling, view frustum culling, clipping and
collision detection.
The plane equation or "equation of the plane" is a mathematical
expression as follows:
Ax + By + Cz + D = 0
where A, B, C and D are known constants and (x,y,z) specifies any
point in three-dimensional space.
Q37. How do I evaluate a point relative to a plane?
---------------------------------------------------
The position of a point relative to a plane is determined by
evaluating the plane equation ie. Multiplying each coordinate (x,y,z)
with the associated parameters (A,B,C) and adding D.
If the evaluation of a point with the plane equation generates a
positive value then the point is said to be "in front of the plane".
If the evaluation generates a result which is negative, then the point
is said to be "behind the plane".
Otherwise, if the evaluation generates a result which is exactly
zero, then the point is said to be "on the plane".
The values of A,B and C actually define the outward normal of the
surface. As such, the sum of the squares of these values will always
add up to one ie.
2 2 2
A + B + C - 1 = 0
In fact, the evaluation of a point relative to the plane is actually
a dot product calculation.
Q38. How do I find the point of intersection with a line and a plane?
------------------------------------------------------------------------
For computer animation purpose, it is often convenient to determine
where a straight 3D line intersects a polygon surface. The polygon
surface is represented as a plane equation.
The 3D line may be specified in two possible ways:
o starting and finishing points ( Vs, Vf )
o starting point and direction vector ( Vs, Vd )
If only a starting point and a direction vector are known, then
a dummy end point is calculated by adding the direction vector to
the starting point ie:
Vf = Vs + Vd
This parameter can then be used in the algorithm defined as follows:
In the case that both starting and finishing points are known, it is
possible to determine the point of intersection by evaluating both
points relative to the plane equation and interpolating ie.
Es = P( Vs )
Ef = P( Vf )
Using these two values as weighting factors, it is possible to
interpolate between the two endpoints.
The weighting factor for the two points is evaluated as follows:
Es Ef
Ws = ----- Wf = -----
Ef-Es Ef-Es
Then the point of intersection is calculated as follows:
Vp = Ws.Vs + Wf.Vf
Q39. How do I calculate the reflection of a vector from a plane equation?
-------------------------------------------------------------------------
In order to perform calculations such as a light reflecting off a
reflective surface, it is necessary to be able to calculate the
reflection of a vector off a plane.
The plane is represented as an outward normal.
The mathematical expression for the reflection of a vector is
given by:
V' = 2N.(V.N) - V
where the known (and unknown) parameters are as follows:
N = outward normal for the plane
V = unit vector of light ray
V' = unknown unit vector of reflected light ray
Q40. How is the reflection of a vector equation derived?
--------------------------------------------------------
The reflection of a vector is visualised by the following drawing:
N
^
V | V'
|- | -|
|\ | /|
\ | /
\|/
------o-------
where:
V is the original direction vector
V' is the reflection direction vector, and
N is the outward normal of the plane
The angle between the vector V and N is given by the dot product ie.
cos(angle) = V.N
So the expression must have a component V.N within it
Then the following angles are known:
At V.N = 0, V' = -V
At V.N = 1, V' = N
At V.N = -1, V' = -N
Since V.N = 1 gives N and V.N = -1, gives -N, this indicates that the
component V.N is multiplied by N, ie.
V' = f( N.(V.N) )
where f() is the evalation function (not completely known).
However, if V.N=0 then a result of -V is given.
Therefore, there must also be a -V component ie.
V' = f( N.(V.N) - V )
But, since at V=N, V.N=1, this equation would cancel out completely.
Thus, one of the parameters must be scaled by a factor of two.
Then, the final equation is given by:
V' = 2N.(V.N) - V
This can be implemented using the vector library as follows:
----------------------
void v3_reflect( VECTOR3 *vreflect, VECTOR3 *vdir, VECTOR3 *vnormal )
{
VFLOAT angle;
VECTOR3 vtemp;
angle = v3_dot( vreflect, vnormal ) * 2;
v3_scale( &vreflect, vnormal, angle );
v3_sub( &vreflect, &vreflect, vnormal );
}
----------------------
Q41. How do I calculate the acceleration of an object on a sloping surface?
---------------------------------------------------------------------------
In the real world, when an object moves onto a sloping surface, it
experiences acceleration forces due to gravity. However, because of the
existence of the sloping surface, the acceleration will not be directly
in the direction towards the gravitational source. Examples include a
football rolling down a hill and a person sliding down a mudslide.
In a virtual 3D environment, the position of an object is represented
as a vector coordinate, the sloping surface as a plane equation and
gravity is as a direction vector.
The problem can then be defined as combining these parameters together
in order to determine the acceleration force, which is represented as a
direction vector.
The following parameters are known:
Vo = Position vector of the object
Vg = Direction vector of gravity
Vp = Outward normal of the current slope polygon
Only the following parameter is unknown:
Va = Direction vector of acceleration forces
This can be visualised as follows:
-----------------------------------------------
Vp = Outward normal of polygon
--
\ /|
\ /
\ /
\O
|\
|\\
| \\| Va = Acceleration force
| \-
V \
Vg = Gravity
-----------------------------------------------
Then the calculation is as follows:
Axis of rotation of a rolling object is given by:
Vt = Vg x Vp
Then the direction vector representing the acceleration force is
given by:
Va = Vt x Vp
This can be implemented using the 3D vector library as follows:
-------------------------------
void v3_slope( VECTOR3 *va, VECTOR3 *vr, VECTOR3 *vg, VECTOR3 *vp )
{
v3_cross( &vr, vg, vp );
v3_cross( &va, vt, vp );
}
-------------------------------
DEFORMATION PATCHES
===================
Q42. What are deformation patches?
----------------------------------
Deformation patches are a means of modifying the shape of an object
while preserving the connectivity of all the geometry. They attempt
to warp the local coordinate system of an object so that straight
lines can become curved lines and vice versa.
Applications of deformation patches includes special effects and
character animation. An inanimate object can be made to twist around,
shrink away from a threatening object and even shuffle or tip-toe
about. For a really trippy effect, a camera can be made to move
through an architectural model, while the geometry of the model is
warped using a deformation patch.
In the real world (using stop-go animation and clay), deformation of
an object can be implemented through the use of reshaping, adding or
removing clay.
However, when animating by computer, using clay is not an option.
Instead, surface are modelled using either polygons defined from
vertices or surfaces defined using spline curves and control points.
By warping the positions of these vertices and control points, it is
possible to deform the shape of the object by modifying the local
coordinate system, while still preserving the connectivity of the
geometry.
Warping or "deforming" of the geometry can be implemented using either
linear or cubic interpolation. Linear interpolation offers considerable
performance advantages over cubic interpolation, at the sacrifice of
control over the way the geometry deforms.
Q43. What are linear deformation patches?
-----------------------------------------
Linear deformation patches are a low-budget version of cubic
deformation patches. Instead of using cubic interpolation, linear
interpolation only makes use of linear interpolation of vectors.
As a result, only eight control points are required, instead of the
full complement of sixty-four. However, the control points are still
arranged in the shape of a cube.
Q44. How do I perform linear deformation?
-----------------------------------------
Once the bounding volume and control points have been defined, the
next stage is to evaluate the new coordinates of each vertex.
Each coordinate of the original object is converted into a parametric
form based on the limits of the bounding volume.
If the limits of the bounding volume are defined by:
| Xlo | | Xhi |
Min = | Ylo | and Max = | Yhi |
| Zlo | | Zhi |
Then a point P can be converted to parametric form:
| X |
P = | Y |
| Z |
Then the parameteric version of P can be calculated from:
| X - Xlo |
| --------- |
| Xhi - Xlo |
| |
| Y - Ylo |
P' = | --------- |
| Yhi - Ylo |
| |
| Z - Zlo |
| --------- |
| Zhi - Zlo |
This parametric coordinate can then be used as input to the evaluation
stage.
Because the deformation patch exists in three dimensions, this requires
interpolation through three levels of spline curves:
+---------------------------------------------------------------------+
| |
| Level 1 Level 2 Level 3 |
| |
| O------O ..O.. |
| .. .. |. |
| . . . . | . . |
| . . . . | . . . |
| . O------O P'.X | ..O.. P'.Y O P'.Z . |
| . . . . =====> | | =====> .\ =====> O |
| . . . . | | . \ . . |
| . . . . | | \. . |
| O---.--O . ..O.. | O |
| . . . . . | . |
| . . . . . | . |
| .. .. .| |
| O------O ..O.. |
| |
+---------------------------------------------------------------------+
The first level is defined from four interpolation lines, each of
which is defined from pair of control points in the X-axis.
Substituting in the X-axis parametric coordinate from P' generates
a new set of 4 control points.
These are used to generate two interpolation lines in the Y-axis.
Substituting in the Y-axis parameteric coordinate from P' generates
a new set of 2 control points.
These are used to generate a single interpolation line in the Z-axis.
Substituting in the Z-axis parametric coordinate from P' generates
a single coordinate.
This coordinate is in fact the final warped position of the point P.
Each vertex or control point of the model is processed in this manner
until all every coordinate has been processed.
Q45. How do I implement a linear deformation system?
----------------------------------------------------
Implementation of a deformation patch system requires three sets of
input parameters. These include the following:
o Model geometry
o Original bounding cube
o Deformation patch (8 control points)
The evaluation function, must then accept a set of vertex data as
input (these might even be control points of a NURBS mesh!), and
produce a modified set of vertex data as output.
For efficiency, the default ordering of the control points of the
deformation patch is X-minor, Z-major, ie. Vertices on the same
X-axis row are placed next to each other in memory ie.
| X1 X2 X1 X2 X1 X2 X1 X2 |
Mdeform = | Y1 Y1 Y2 Y2 Y1 Y1 Y2 Y2 |
| Z1 Z1 Z1 Z1 Z2 Z2 Z2 Z2 |
The first stage of linear interpolation will convert each pair of
control points into a single coordinate.
By substituting in the parametric X coordinate and evaluating, a set
of four coordinates are generated:
| Xp Xp Xp Xp |
Mdx = | Y1 Y2 Y1 Y2 |
| Z1 Z1 Z2 Z2 |
As with the first stage, the parametric Y coordinate is substituted
and evaluated. This generates a pair of coordinates.
| Xp Xp |
Mdy = | Yp Yp |
| Z1 Z2 |
Finally, these are converted into a interpolation matrix, and the
parametric Z coordinate is substituted and evaluated. This generates
a single coordinate
| Xp |
Mdz = | Yp |
| Zp |
This is the final processed coordinate.
A complete routine to perform this is as follows:
The following parameters are used:
vnum - number of vertices to be processed
vsrc - source vertex data
vdst - processed vertex data
vlimits - bounding volume for deformation patch
vdeform - control points for deformation patch (64)
------------------------------------------------------
void lpatch_evaluate( VECTOR3 *vdst, int vnum, VECTOR3 *vsrc,
VECTOR3 *vlimits, VECTOR3 *vdeform )
{
VECTOR3 v_diff, vparam, v_ymesh[4], v_zmesh[2];
int n, m;
v3_sub( &v_diff, vlimits+1, vlimits ); /* Scale for box */
for ( n = 0; n < vnum; n++ ) /* For each vertex */
{
v3_sub( &vparam, vsrc+n, vlimits ); /* Get parametric */
v3_div( &vparam, &vparam, &v_diff ); /* coordinates */
for ( m = 0; m < 4; m++ ) /* Get Y-axis mesh */
v3_linear( v_ymesh+m, vdeform+m*2, vdeform+m*2+1, vparam.vx );
for ( m = 0; m < 2; m++ ) /* Get Z-axis mesh */
v3_linear( v_zmesh+m, v_ymesh+m*2, v_ymesh+m*2+1, vparam.vy );
v3_linear( vdst+n, v_zmesh, v_zmesh+1, vparam.vz ); /* Final coord. */
}
}
------------------------------------------------------
Q46. How do I define a cubic deformation patch?
-----------------------------------------------
A cubic deformation patch is defined as a set of spline curve control
points arranged in the shape of a cube. Modification of the cubic
deformation patch is performed by repositioning groups of control points.
Since a minimum of four points are required to define a spline curve,
a cubic deformation patch requires at least sixty-four control points.
Each control point is represented as a single 3D vector.
It is also necessary to define a bounding volume which contains the
area of coordinate space which is to be deformed.
Thus, a single deformation patch can be defined from less than 70 3D
vectors or less than 1K of memory.
Q47. How do I evaluate a cubic deformation patch?
-------------------------------------------------
Once the bounding volume and control points have been defined, the
next stage is to evaluate the new coordinates of each vertex.
Each coordinate of the original object is converted into a
parametric form based on the limits of the original bounding volume.
If the limits of the bounding volume are defined by:
| Xlo | | Xhi |
Min = | Ylo | and Max = | Yhi |
| Zlo | | Zhi |
Then a point P can be converted to parametric form:
| X |
P = | Y |
| Z |
Then the parameteric version of P can be calculated from:
| X - Xlo |
| --------- |
| Xhi - Xlo |
| |
| Y - Ylo |
P' = | --------- |
| Yhi - Ylo |
| |
| Z - Zlo |
| --------- |
| Zhi - Zlo |
This parametric coordinate can then be used as input to the evaluation
stage.
Because the deformation patch exists in three dimensions, this requires
interpolation through three levels of spline curves:
+--------------------------------------------------------------------+
| |
| Level 1 Level 2 Level 3 |
| |
| o---o---o---o |
| .. . . .. |
| . o---o---o---o |
| . . . .. . o |
| . o---o---o---o |. |
| . . . .. . | o |
| . o---o---o---o o |. o . |
| . . . . |.| o \ . |
| o---o---o---o . P'.X | o |. P'.Y o P'.Z . |
| .. .. . .. . o |.| o \ . |
| . o---o---o---o . |.| o | o o |
| . . .. .. . . ===> | o |.| ===> \ ===> . |
| . o---o---o---o . o |.| o o . |
| . .. . .. .. .| o | |
| . o---o---o---o o |.| |
| . . . . .| o |
| o---o---o---o . o | |
| . .. . . . .| |
| o---o---o---o . o |
| . .. . . . |
| o---o---o---o . |
| .. . . .. |
| o---o---o---o |
| |
+--------------------------------------------------------------------+
The first level is defined from sixteen spline curves, each of which
is defined from a row of control points in the X-axis.
Substituting in the X-axis parametric coordinate from P' generates
a new set of 16 control points.
These are used to generate four spline curves in the Y-axis.
Substituting in the Y-axis parameteric coordinate from P' generates
a new set of 4 control points.
These are used to generate a single spline path in the Z-axis.
Substituting in the Z-axis parametric coordinate from P' generates
a single coordinate.
This coordinate is in fact the final warped position of the point P.
Each vertex or control point of the model is processed in this manner
until all every coordinate has been processed.
Q48. How do I implement a cubic deformation patch system?
---------------------------------------------------------
Implementation of a deformation patch system requires three sets of
input parameters. These include the following:
o Model geometry
o Original bounding cube
o Deformation patch (64 control points)
The evaluation function, must then accept a set of vertex data as
input (these might even be control points of a NURBS mesh!), and
produce a modified set of vertex data as output.
For efficiency, the default ordering of the control points of the
deformation patch is X-minor, Z-major, ie. Vertices on the same
X-axis row are placed next to each other in memory ie.
| X1 X2 X3 X4 X1 X2 X3 X4 ... X4 |
Mdeform = | Y1 Y1 Y1 Y1 Y2 Y2 Y2 Y2 ... Y4 |
| Z1 Z1 Z1 Z1 Z1 Z1 Z1 Z1 ... Z4 |
The first stage of cubic interpolation will convert each set of four
control points into a cubic interpolation matrix.
By substituting in the parametric X coordinate and evaluating, a set
of 16 coordinates are generated:
| X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 X1 |
Mdx = | Y1 Y2 Y3 Y4 Y1 Y2 Y3 Y4 Y1 Y2 Y3 Y4 Y1 Y2 Y3 Y4 |
| Z1 Z1 Z1 Z1 Z2 Z2 Z2 Z2 Z3 Z3 Z3 Z3 Z4 Z4 Z4 Z4 |
As with the first stage, the parametric Y coordinate is substituted
and evaluated. This generates a set of four coordinates:
| X1 X1 X1 X1 |
Mdy = | Y1 Y1 Y1 Y1 |
| Z1 Z2 Z3 Z4 |
Finally, these are converted into a interpolation matrix, and the
parametric Z coordinate is substituted and evaluated. This generates
a single coordinate
| X1 |
Mdz = | Y1 |
| Z1 |
This is the final processed coordinate.
A complete routine to perform this is as follows:
The following parameters are used:
vnum - number of vertices to be processed
vsrc - source vertex data
vdst - processed vertex data
vlimits - bounding volume for deformation patch
vdeform - control points for deformation patch (64)
------------------------------------------------------
typedef VECTOR3 GVECTOR3[4];
void dpatch_evaluate( VECTOR3 *vdst, int vnum, VECTOR3 *vsrc,
VECTOR3 *vlimits, VECTOR3 *vdeform )
{
GVECTOR3 m_xgeom[16], m_ygeom[4], m_zgeom;
VECTOR3 v_diff, vparam, v_ymesh[16], v_zmesh[4];
int n, m;
v3_sub( &v_diff, vlimits+1, vlimits ); /* Scale for box */
for ( m = 0; m < 16; m++ ) /* I-matrix X-axis */
m4_multspline( m_cubic, vdeform+m*4, m_xgeom[m] );
for ( n = 0; n < vnum; n++ ) /* For each vertex */
{
v3_sub( &vparam, vsrc+n, vlimits ); /* Get parametric */
v3_div( &vparam, &vparam, &v_diff ); /* coordinates */
for ( m = 0; m < 16; m++ ) /* Get Y-axis mesh */
v3_cubic( v_ymesh+m, m_xgeom[m], vparam.vx );
for ( m = 0; m < 4; m++ )
{ /* I-matrix Y axis */
m4_multspline( m_cubic, v_ymesh+m*4, m_ygeom[m] );
v3_cubic( v_zmesh+m, m_ygeom[m], vparam.vy ); /* Get Z-axis mesh */
}
m4_multspline( m_cubic, v_zmesh, m_zgeom ); /* I-matrix Z axis */
v3_cubic( vdst+n, m_zgeom, vparam.vz ); /* New coordinate */
}
}
------------------------------------------------------
Q49. How do I use keyframe animation with deformation patches?
--------------------------------------------------------------
Using the algorithm described above, it is only possible to render
a single rendered frame.
In order to implement smooth and continuous animation, it is necessary
to define more than one deformation patch.
However, defining and positioning a single deformation patch for every
keyframe is very time-consuming. The solution is to add another
dimension to the deformation patch ie. time.
For every two keyframes, it is possible to perform linear interpolation
to generate each frame between the two keyframes.
For every four keyframes, it is possible to perform cubic interpolation
to generate each frame between the four keyframes.
This allows for smooth animation along with efficient use of memory
space.