|
|
|
BOUNDINGBOX COLLISION TEST 26.10.02
|
|
Almost every 3D game today uses some kind of collision test in their game engine.
For example, you want to decide if a missile has hit a character, or a character
is colliding with a wall or trip-wire. The first goal when creating a collision test is
to decide what kind of collision test to use. You need to keep a lot of things in mind
when making this choice: high frame rate, collision accuracy, terrain, etc.
I can’t tell you what kind of collision test is best for your engine, but in
this article I will explain the basics in one of the easiest collision tests to understand (less math and calculations) "The Bounding Box".
 |
The bounding box collision test is based on a simple inside/outside system that is used
in many classic 3D games.
First imagine a 2D situation, you're standing in a room and you take a piece
of chalk and draw a quad on the floor. The front-left corner you name A and you name
the other corners clock Wise B, C and D like in the picture on the left.
You move to the position of the red dot in the picture and face the AB line.
You are now inside the quad. Line AB is in front of you, BC is on your right,
DA is on your left and line CD is behind you. Let's say A,B,C and D has the given coordinates:
A(2,10), B(10,10), C(10,2) and D(2,2).
Now, to be inside the quad your position have to be:
pos.x < 10 pos.x > 2 //in x-direction.
pos.y < 10 pos.y > 2 //in y-direction.
|
The red dot is inside because it has the position (6, 4).
It is fairly easy to understand that if you move forward to the position of the blue dot (6, 12),
then line AB is behind you and "pos.y > 10".
This means that you have moved outside of the quad.
|
|
Now you have learned how you can check if a point is
inside or outside a quad in 2D, you can use the same method to test for collision.
To test collision in 3D, add a height (y value), and think of the quad as a box instead.
Then you precalculate all min/max vertex positions in x, y and z directions of all your shapes,
and store them in an array. You can use the min/max values to build bounding boxes around all your objects.
Then to test for collision, you check if a point is inside one of the bounding boxes. This method is a lot easier then to
test against a complicated object.
|
If you compare the bounding box collision test to other 3D collision tests,
you will see that it has its limitations. It’s mostly suited for "indoor environment"
and is not suited for "terrain". The bounding box collision test is not very precise
on complicated objects, since it has a box-shape. But despite of all this it is
extremely fast, and easy to use. And if you combine it with other collision tests you
might find that it can be very useful in many situations. An example is to use one test
for your "terrain" and the bounding box test for your "buildings", to speed up your 3D
engine.
|
The picture on the left symbolises your new 3D box from top-view in OpenGL, the yellow dot is the y-axis.
Notice, that OpenGL uses a negative z-axis into the screen (DirectX uses positive z-axis).
Two examples of this kind of collision tests are "2D Floor Test" and "3D Box Test".
They can both be used in 3D, and the main differense
between them is that the floor test does not use the height of the object (just like the "quad on the floor" above).
|
The Floor Test (for the "box" in the picture above with height y = 10):
Use this struct, and create an array (boxArray[1]) to store the min/max values:
struct tBoundingBox
{
tVector3 max;
tVector3 min;
};
tBoundingBox boxArray[1];
|
Calculate and store the min/max values:
boxArray[1].min.x = 2;
boxArray[1].max.x = 10;
boxArray[1].min.z = -10;
boxArray[1].max.z = -2;
|
Create a test to see if you are inside or outside:
pos.x < boxArray[1].max.x pos.x > boxArray[1].min.x
pos.z < boxArray[1].max.z pos.z > boxArray[1].min.z
|
The Box test (for the "box" in the picture above with height y = 10):
Use this struct, and create an array (boxArray[1]) to store the min/max values:
struct tBoundingBox
{
tVector3 max;
tVector3 min;
};
tBoundingBox boxArray[1];
|
Calculate and store the min/max values:
boxArray[1].min.x = 2;
boxArray[1].max.x = 10;
boxArray[1].min.y = 0;
boxArray[1].max.y = 10;
boxArray[1].min.z = -10;
boxArray[1].max.z = -2;
|
Create a test to see if you are inside or outside:
pos.x < boxArray[1].max.x pos.x > boxArray[1].min.x
pos.y < boxArray[1].max.y pos.x > boxArray[1].min.y
pos.z < boxArray[1].max.z pos.z > boxArray[1].min.z
|
Regards.
Ronny André Reierstad
|
|
|
