3D Programming - Weekly : 3d Math Questions

This week I'll go over some 3D math that might be used in game programming. I'll start by presenting a question, then a possible answer. In the code examples I use the math classes from the other articles on this page.( See building blocks ) The questions aren't meant to be advanced; they'll be easy for experienced 3d programmers. I tried setting up a situation where they apply to real world game programming, which I think is a good thing to do, but may make the questions seem more complicated than they are.

Direction Matching

Question:

You want a player to trigger an event only when he's facing a certain direction. One way to do this is to compare orientation vectors. Write a function of the form:

bool VecAngleTest( float MaxAngle, CVec3 V1, CVec3 V2 )

that returns true if the angle in degrees between V1 and V2 is less than or equal to MaxAngle.

Answer:

We want to find the angle between V1 and V2, which I'll call Angle. V1 dot V2 = cosine(Angle), if the vectors are normalized. So Angle = arccosine(V1 dot V2), and will be 0-180 degrees. Note that C/C++ uses radians for its trig functions, so we must convert to degrees. If you're sure the function will only be passed normalized vectors, you can skip the normalization step.

const float PI = 3.14159265f;
const float RAD_TO_DEG = 180.0f / PI;

bool VecAngleTest( float MaxAngle, CVec3 V1, CVec3 V2 )
{
V1.Normalize();
V2.Normalize();
float Angle = acosf( V1.Dot( V2 ) ) * RAD_TO_DEG;
return ( Angle <= MaxAngle );
}

Converting a triangle to plane

Question:

You want to create a plane used for clipping from 3 points in the world, specifically two points and an origin. ( Perhaps as part of creating a complete clipping frustum. )

Write a function to convert a triangle represented by three 3D points (P1, P2, P3) to an infinite plane, represented by a Normal Vector, and Distance from the origin.

Anwser:

To compute the plane normal, we can use the cross product with 2 edge vectors of the triangle to get an orthogonal vector. Note that there are two normals possible when converting from a triangle, which are the same except they face opposite directions. They are usually distinguished by defining the verts in clockwise or counter-clockwise order. To compute Distance we can use any point on the plane, and compute the distance along the normal to the origin using the dot product.

void ConvertTriToPlane( CVec3 P1, CVec3 P2, CVec3 P3, CVec3& Normal, float& Distance )
{
Normal = (P2-P1).CrossProduct(P3-P1);
Normal.Normalize();
Distance = -Normal.Dot( P1 );
}

Bounding Box to Sphere

Question:

In your program you perform many intersection tests with objects that are often spaced far apart, so you decide to optimize by adding an initial bounding sphere test before testing the oriented bounding boxes. Your oriented bounding box is represented by center point CP, 3x3 rotation matrix Rot, and extent vector Ext( that contains the max x,y,z values of the box. ) Write a function that will use sphere intersection to test if it's possible that 2 bounding boxes intersect.

Anwser:

To define a sphere we just need the centerpoint and a radius. We already have the center point, and rotation doesn't matter, so we can just ignore Rot. We can get the radius by taking the magnitude of the extent, which is the furthest distance from center possible. Note that it's unlikely this will be the minimal bounding sphere for the actual 3d model. Since this is an optimization, I use magnitude squared to avoid the sqrt needed to compute magnitude. I didn't precompute the max extents because I wanted to show everything in one function.

bool BoxSpheresOverlap( const CBBox& B1, const CBBox& B2 )
{
float DistanceSq = (B1.CP - B2.CP).MagSquared();
float R1 = B1.Ext.Magnitude(); // These should be precomputed.
float R2 = B2.Ext.Magnitude();
float RadiiSq = (R1 + R2) * (R1 + R2);
return ( RadiiSq > DistanceSq );
}

To speed up an intersection test for boxes that usually overlap greatly, you could create a bounding sphere where radius is the minimal extent, which is min( Ext.x, Ext.y, Ext.z ) and return a quick true if they overlap. Whether an optimization will be useful depends greatly on what the common cases are.