🔒 Locked

Distance to collision in AABB world

Started by SpectreNectar May 3, 2012 at 7:38 PM 0 replies 2.8k views

Original Post

May 3, 2012 at 7:38 PM

I'm trying to write a function for my game that returns the distance to the nearest collision along a direction. It is fed the following data:

Vector3D origin (Point to start search from)
Vector3D volume (Halfwidths)
Vector3D direction (Direction to check)

The function iterates over a list of "Areas" that are really just axis aligned boundary boxes and attempts to return a distance in the form of a double.

But now I've gone and stirred myself blind on it and need some help. The approach that first came to my mind was to project the boxes to the direction, and when I realized that wouldn't work I thought I'd store the normals of the iterated boundary boxes somewhere instead and then do a separating axis test, like what is common in 2D.
But then it seems I'd be needing an oriented bounding box test. Is that really necessary? I mean considering the boxes are all aligned.

I'd like to know what the correct way to do this would be? Thank you.

slayemin

1,913

slayemin

May 5, 2012 at 12:36 PM

It'd probably be easier to help you correctly if you gave some context on why you need to find the nearest collision along a direction.

I'm going to assume that you're using this to create a coarse and granualar collision detection check. The coarse check would be to perform a distance calculation (somewhat cheap, even with a square root in there). The granular check would be more expensive because you may have many AABB's to check.

My idea is to use a bounding sphere. The center of the sphere is at the center of your cube volume and the sphere radius is the distance to a corner (so that you cover your farthest point). Now you have two or more bounding spheres and the orientation of your AABB doesn't matter. The calculating distance between the bounding spheres is pretty easy: Just measure the distance between the centers and add both their radiuses to the distance. Loop through every collidable object in your game and store the one with the shortest distance.

It'll be an ugly O(n*n) loop though, so if you start to get a lot of objects and slowdown, watch out.


 foreach(CollidableObject obj1 in CollidableObjects)
 {
 float shortestDistance = infinity;
 foreach(CollidableObject obj2 in CollidableObjects)
 {
 if(obj1 == obj2) //self reference check
 continue;
 
 float Dist = MeasureDistance(obj1, obj2); //<--your function to measure distance
 
 if(Dist < shortestDistance)
 {
 shortestDistance = Dist;
 obj1.NearestObject = obj2;
 } 
 }
 
 }

If you do start having a lot of collidable objects in your game and its causing performance problems, look into quad trees(2D) or oct trees(3D).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.