Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Distance to collision in AABB world


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
1 reply to this topic

#1 SpectreNectar   Members   -  Reputation: 105

Like
0Likes
Like

Posted 03 May 2012 - 01: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.

Sponsor:

#2 slayemin   Members   -  Reputation: 2797

Like
1Likes
Like

Posted 05 May 2012 - 06:36 AM

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).

Edited by slayemin, 05 May 2012 - 06:38 AM.

Eric Nevala

Indie Developer | Dev blog





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS