Sign in to follow this  
azjerei

Bounding Box collisions

Recommended Posts

I am having problems trying to solve how to calculate bounding boxes and collision using them. Should I simply, when I load a model, calculate the x-most, y-most, z-most, x-least, y-least and z-least vertices so I can build a bounding box around it? And then, how do I check for intersection between two or more bounding boxes?

Share this post


Link to post
Share on other sites
hi,

Building AABB:
Yep pretty much as you say, you'll have to loop through all the vertices and track the min and max extents in each axis. One thing to be very careful of is ensuring you correctly set up your initial min/max values. I used to use a maxfloat value when initialising, but this is not a great idea, and its far better IMHO to use the first vertex for the min and max extents.
You then loop through the rest of the vertices comparing each axis to the min and max stored for that axis. Obviously you can eventually add the boundingbox data to the model data or store it in a database avoiding the costly recalculation everytime the game runs.

Intersection/overlap:
Well an overlap function of two AABB is dead simple, just draw it out in 2D and you'll see you can test the min of one box against the max of the other in each axis in turn to determine if it is outside/inside.

It gets slightly more complex when you've got dynamic AABB's as you'll need to check aginst the path of the AABB. Check out this gamasutra feature (you'll have to register but its free and DEFINITELY worth it)
http://www.gamasutra.com/features/19991018/Gomez_1.htm

Hope this helps.

Share this post


Link to post
Share on other sites
Cool, definately something to help me out while I get this working. All new to this sort of thing, so it should be interesting to get it working. Have managed to make simple collision using three vectors (up/down, left/right and front/back) but it's not that accurate.

Though, just got an idea... I wonder if it would be bad to hardcode a collision box for characters.. hmm.

Thanks!

Share this post


Link to post
Share on other sites
hardcode a bbox for an object. then create a character from objects.

bbox should be a invisible part of an object, yes?

Share this post


Link to post
Share on other sites
A bbox would be six numbers indicating the min-/max-x, min-/max-y and min-/max-z, and then you simply cross-reference them to overlapping bboxes from the environment.

The problem that I am having, theoretically since I have not begun coding yet due to it, is how to discern if the collision is happening behind or in front of you.

If I collide in front of me, it is easy to just limit movement fowards, but if I turn around, the code would still limit movement forwards, thus making me stuck where I am...

Share this post


Link to post
Share on other sites
Well first off you'll need a basic AABB overlap test, as described above this is very simple. This will give you a quick and simple test for determing if an AABB is ever embeded as no AABB should ever overlap. If this happens then there is a fault in the collision code (usually becuase of precision issues that are hard to avoid, but can be worked around)

Next up you'll need to implement the swept AABB test in that gamasutra article. As u0 and u1 are normalised time, a value < 0 would mean a collision behind the AABB (although I can't see this ever being the case unless you're already embeded), a value > 1 means the collision happens some time after the current movement. Any value between 0-1 is valid. In addiiton u0 indicates the time of the initial collision, and u1 the time when the collision ends. You can then simply use the current velocity * time value to get the collision position.

In terms of storage I prefer to use minVector and maxVector (each a vector type obviously) instead of 6 values as its so much easier to deal with (if you've got a maths lib for vectors)



p.s. I'd recommened doing a search on collision detection in this forum and read up on it. There is lots of useful information even if not directly related to AABB vs AABB collision. Things like backing up from the collision point to avoid getting embeded, using an elipson value instead of checking if values are < or > 0, looping through the collision system to resolve multiple collisions and allow for sliding etc.

Share this post


Link to post
Share on other sites
ok basic collision theory.

1. Find the AABB of the moving object - AABB should be local to the object. Then by adding the objects world position to the AABB min/max vectors you'll get the AABB in world space.

2. Determine the 'mega' AABB which is the AABB of the object swept along the path of the object. In other words determine the world coord of the bounding box at the objects starting point, do the same for where it should end (position+velocity) then determine the AABB that encompasses both these AABB's, usually with a little bit added of good measure (enlarged).

3. Loop through you'll world collision geometry (AABB) and determine which are within the mega AABB to produce a 'Potential Collision Set' (PCS). This is done via the simple overlap test and results in a list of AABB's that 'might' be in collision with the object as it moves.

4. Now loop through the PCS and perfrom the swept AABB test on each. If a collsiion is found (0 < u0 < 1.0) then store the collision information (time, side hit, side normal etc). For each consecutive collision found during the loop, compare its time to the stored collision time. If it is less then update the collision information to this AABB. In this way you'll find the first collision between the object AABB and the world AABB.

5. Implement your repsonce behaviour - collide and stop, collide and slide, collide and bounce etc.

that should get you started. As I said, it would be well worth you're tme reading or searching through this forum and check up on previous posts to learn more.

Share this post


Link to post
Share on other sites
nah, don't give up.

It sounds to me like this is possibly your first venture into such collision systems, in which case it is going to be a bit of an upward struggle. There is much information to learn, maths to understand and the like.

However even if you feel its not worth bothering implementing this, do scan through this forum and read up as much as you can about collision detection and responce. You may not understand everything that is discussed and have hundreds of questions, but I often find the experience of reaing and digesting other threads on the issue will over time sink in.

This is important as I often find something that is initially confusing or beyond my current level of understand will start to click into place when re-reading the threads or after implemnting a collsiion system. The more you try the greater your understanding will become, until eventually you'll wonder why you thought it was difficult in the first place.

If its all too overwhelming at the moment, I'd suggest implementing one of the ellipsoid/polygon collsiion sytsems from either Paul nettles ( http://www.fluidstudios.com/ ) or Telemachos version ( http://www.peroxide.dk/papers/collision/collision.pdf ) Its more than you need, but you'll learn the essentails about collision detection.

Share this post


Link to post
Share on other sites
Quote:
Original post by noisecrime
This is important as I often find something that is initially confusing or beyond my current level of understand will start to click into place when re-reading the threads or after implemnting a collsiion system. The more you try the greater your understanding will become, until eventually you'll wonder why you thought it was difficult in the first place.


YES! Absolutely, noisecrime is correct. Stick with this and you'll be able to solve more difficult problems in the future!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this