| Basic 3D Math |
Introduction
Before reading this section I highly recommended that you read the Win95GPE article on basic 2D math, since that section lays a lot of the ground work for understanding the information in this article. This section contains some of the basic high-school math needed to understand the equations and graphics primitives used in 3D computer graphics. As you will see, 3D math is often just a simple extension of the same techniques used for 2D math.
Here's a secret tip for anyone who has a hard time understanding 3D math: think of it as simply another programming language! I had a very difficult time understanding it all when I first started learning it years ago, but once I started looking at it like this it suddenly became a lot easier. Start by learning the basic techniques and then select, rearrange and apply them to the problems you need to solve.
Definition of a 3D Point
A point is similar to it's 2D counterpart, we simply add an extra component, Z, for the 3rd axis:
Points are now represented with 3 numbers: <x,y,z>. This particular method of representing 3D space is the "left-handed" coordinate system, which I use throughout this entire article . In the left-handed system the x axis increases going to the right, the y axis increases going up, and the z axis increases going into the page/screen. The right-handed system is the same but with the z-axis pointing in the opposite direction.
Distance Between Two 3D Points
The distance between two points <Ax,Ay,Az> and <Bx,By,Bz> can be found by again using the pythagorus theorem:
dx = Ax-Bx
dy = Ay-By
dz = Az-Bz
distance = sqrt(dx*dx + dy*dy + dz*dz)
Definition of a 3D Vector
Like it's 2D counterpart, a vector can be thought of in two ways: either a point at <x,y,z> or a line going from the origin <0,0,0> to the point <x,y,z>.
3D Vector addition and subtraction is virtually identical to the 2D case. You can add a 3D vector <vx,vy,vz> to a 3D point <x,y,z> to get the new point <x',y',z'> like so:
x' = x + vx
y' = y + vy
z' = z + vz
Vectors themselves can be added by adding each of their components, or they can be multiplied (scaled) by multiplying each component by some constant k (where k <> 0). Scaling a vector by 2 (say) will still cause the vector to point in the same direction, but it will now be twice as long. Of course you can also divide the vector by k (where k <> 0) to get a similar result.
To calculate the length of a vector we simply calculate the distance between the origin and the point at <x,y,z> :
length = | <x,y,z> - <0,0,0> |
= sqrt( (x-0)*(x-0) + (y-0)*(y-0) + (z-0)*(z-0) )
= sqrt(x*x + y*y + z*z)
Often in 3D computer graphics you need to convert a vector to a unit vector, ie a vector that points in the same direction but has a length of 1. This is done by simply dividing each component by the length:
Let <x,y,z> be our vector, length = sqrt(x*x + y*y + z*z)
Unit vector = <x,y,z> = | x , y , z |
length | length length length |
( where length = |<x,y,z>|)
Note that if the vector is already a unit vector then the length will be 1, and the new values will be the same as the old.
Definition of a Line
As in 2D, we can represent a line by it's endpoints (P1 and P2) or by the parametric equation:
P = P1 + k * (P2-P1)
where k is some scalar value between 0 and 1.
The Dot Product
The dot product between two vectors <Ax,Ay,Az> and <Bx,By,Bz> is calculated like so:
A * B = Ax*Bx + Ay*By + Az*Bz
If A and B are unit vectors then the dot product is the cosine of the angle between them, so the angle itself can be calculated by taking the inverse cosine of the dot product:
theta = invcos (A * B)
Fortunately you'll often only need the cosine of the angle between 2 vectors and not the angle itself, so the expensive step of calculating the inverse cosine can be skipped.
Definition of a Plane
A plane is an infinately wide flat polygon-type surface. A plane can be defined by a normal <nx,ny,nz> and a scalar value k. The normal can be thought of as representing the direction that the surface of the plane is facing, ie it's a directional vector at a right angle to the plane:
We can imagine the normal as describing an infinately long line stretching off to infinity in either direction, and that a plane can slide up and down along this line. In the plane equation the value k specifies where exactly on this line the plane sits.
The equation for the plane uses the dot product:
<x,y,z> * <nx,ny,nz> = k
All points <x,y,z> that actually lie on the plane itself will satisfy this equation. This gives us a convenient method for determining which side of a plane any given point <x,y,z> is:
<x,y,z> * <nx,ny,nz> = k Point is in plane
<x,y,z> * <nx,ny,nz> > k Point is on one side of plane
<x,y,z> * <nx,ny,nz> < k Point is on other side of plane
The vector <nx,ny,nz> and scalar k are unique to every plane (I'll show a way of calculating them below). These equations are helpful in performing back-face culling. Substitute the view point into the equation, if the value comes out less than k then you know that you are facing the "back" side of the polygon and thus don't need to draw it.
The Cross Product
If you have 2 vectors then the cross product will return a vector which is perpendicular (ie at a right angle) to both of them. The cross product between two vectors <Ax,Ay,Az> and <Bx,By,Bz> is:
A x B = <Ay*Bz - Az*By, Az*Bx - Ax*Bz, Ax*By - Ay*Bx>
Note that while the dot product returns a single scalar value, the cross product returns a vector.
Taking the cross-product between the x axis <1,0,0> and y axis <0,1,0> gives us:
<1,0,0> x <0,1,0> = <0*0 - 0*1, 0*1 - 1*0, 1*1 - 0*0>
= <0,0,1>
which is of course the z axis and is indeed perpendicular to both vectors.
Calculating a Plane from 3 Points
To calculate a plane from 3 given points we first calculate the normal. If we imagine the 3 points form three edges in the plane then we can take two of the edges and calculate the cross-product between them. The resulting directional vector will be the normal, and then we can plug any of the 3 known points into the plane equation to solve for k. For points p1,p2 and p3 we get:
normal = (p1-p2) x (p3-p2)
k = normal * p1
Note that it is extremely important to keep track of which direction your points are stored in. Let's take 3 points stored in clockwise direction in the x/y plane:
The normal to the plane these 3 points define is:
normal = (p1-p2) x (p3-p2)
= (0,-1,0) x (1,-1,0)
= <(-1)*0 - 0*(-1), 0*1 - 0*0, 0*(-1) - (-1)*1>
= <0,0,1>
ie the z axis. If we were to store the points counter-clockwise the normal calculated would be <0,0,-1>, which is still the z axis but in the "opposite" direction. It's important to keep track of these things since we often need plane equations to be correct in order to determine which side of a polygon an object (such as the view point) is on.
3D Rotation
In the Win95GPE article on basic 2D math we saw how a 2D point <x,y> can be rotated around the origin <0,0>. In 3D this is the same as rotating the point around the z axis (the z value remains the same). We can slightly modify this basic equation to get rotation around all three axis:
Rotatation about the x axis:
x' = x
y' = (cos é * y) - (sin é * z)
z' = (sin é * y) + (cos é * z)
Rotation about the y axis:
x' = (cos é * x) + (sin é * z)
y' = y
z' = -(sin é * x) + (cos é * z)
Rotation about the z axis:
x' = (cos é * x) - (sin é * y)
y' = (sin é * x) + (cos é * y)
z' = z
Rotating a point around an arbitrary axis is a tad complex, so I'll discuss how to do this in the article on matrices (since they're an ideal tool for performing these types of rotations). It's fairly easy to expand the steps in that article for "regular" 3D math.
Intersections
In this section I'll show how to calculate intersections between various objects. This is particularly handy for things like collision detection.
Intersection Between a Line and a Plane
This occurs at the point which satisfies both the line and the plane equations.
Line equation: p = org + u * dir (1)
Plane equation: p * normal - k = 0. (2)
Substituting (1) into (2) and rearranging we get:
(org + u * dir) * normal - k = 0
ie u * dir * normal = k - org * normal
ie u = (k - org * normal) / (dir * normal)
If (d * normal) = 0 then the line runs parrallel to the plane and no intersection occurs. The exact point at which intersection does occurr can be found by plugging u back into the line equation in (1).
Intersection Between a Line and a Sphere
This occurrs at the point which satisfies both the line and the sphere equations.
Line equation: p = org + u * dir (1)
Sphere equation: |p - origin| = radius (2)
Substituting (1) into (2) we get:
|(org + u * dir) - origin| = radius
ie (org + u * dir - origin)^2 = radius^2
Which can be rearranged into the following form:
u^2 * dir^2 + u * 2 * dir * (org-origin) + (org-origin)^2
This is a quadratic equation in u which can thus be solved with the following formula:
u = -B +/- sqrt(B^2 - 4AC) 2A
where A = dir^2
B = 2 * dir * (org-origin)
C = ((org-origin)^2 - radius^2)
Note that dir^2 means dir*dir, ie the dot product of dir with itself. The same applies to org-origin in C. dir * (org-origin) in B is also a dot product.
To get the actual points of intersection you plug the 2 resulting u values into the line equation.
If A=0 then the line does not intersect the sphere. If sqrt(B^2-4AC)=0 then the line is tangent to the surface of the sphere and there is only one point of intersection at u=-B/2A.
Intersection Between Three Planes
In order to find the point <x,y,z> of intersection between three planes (p*n1-k1=0, p*n2-k2=0 and p*n3-k3=0) we can use matrices (in particular read the section on solving simultaneous equations). If we place all three equations into a matrix then we can see that the following rule will apply:
| n1.x n1.y n1.z -k1 | |x| |0|
| n2.x n2.y n2.z -k2 | X |y| = |0|
| n3.x n3.y n3.z -k3 | |z| |0|
| 0 0 0 1 | |1| |1|
By rearranging this equation we can solve for <x,y,z> :
-1
|x| | n1.x n1.y n1.z -k1 | |0|
|y| = | n2.x n2.y n2.z -k2 | X |0|
|z| | n3.x n3.y n3.z -k3 | |0|
|1| | 0 0 0 1 | |1|
Thus if we calculate the inverse of the matrix then the 4th collumn will contain the point of intersection. (If the matrix has no inverse then at least two of the planes are parrallel and there is no point of intersection).
Note that because of the constant terms we could instead use a 3x3 matrix for a more optimised solution:
|x| | n1.x n1.y n1.z | |k1|
|y| = | n2.x n2.y n2.z | X |k2|
|z| | n3.x n3.y n3.z | |k3|
Intersection Between Two Planes
The line (p=org+u*dir) of intersection between two planes (p*n1-k1=0 and p*n2-k2=0) is perpendicular to each plane's normal, ie:
dir = n1 x n2
What we can now do is assume there is a third plane perpendicular to both planes, ie one which has a normal of dir. All that remains is to find the k value for this plane and then find the point of intersection between all three planes, as shown in the previous section. For simplicity we can assume this third k value to be 0 and use the resulting point as our org value:
|org.x| | n1.x n1.y n1.z 0 | |k1|
|org.y| = | n2.x n2.y n2.z 0 | X |k2|
|org.z| | dir.x dir.y dir.z 0 | |0 |
| 1 | | 0 0 0 1 | |1 |
Copyright (c) 1997 Mark Feldman (pcgpe@oocities.com) - All Rights Reserved
This article is part of The Win95 Game Programmer's Encyclopedia
Please retain this footer if you distribute this file.
