Sign in to follow this  
SSmith

Collision methods?

Recommended Posts

This is my first post on gamedev, so excuse me if this is in the wrong forum.
I've been a lurker for a while, but I've only just decided to sign up. I've been learning OpenGL for the past few weeks, and I've got a rather basic, but good, knowledge of the API for the most part.

Obviously you can guess where this is going, I'm working on a voxel-based terrain engine (similar to Minecraft or Infiniminer, but more of a Real Time Strategy game concept instead of FPS). So far I've managed to achieve quite a few personal feats, for example I've managed to get the engine rendering 3.3 million cubes at around 200fps (obviously this is without complex AI or physics, just basic rendering right now).

But this is where I hit a wall, I've done quite a bit of research into many collision methods, but I need a fast system, so I looked into AABB's and OBB's. For now I'm sticking with the AABB concept, as I just want the most basic of hit detection to be working, so I can continue with the more fun parts of development. I have created a BoundingBox class that detects intersections, so I'm half of the way there. [b]But heres where the problem is[/b], what do I do after detecting an intersection?

For example, I've got an entity (we'll call this creature01), the entities AI tells it to move forward. So it's velocity.z is set to +0.1f , and it moves forward that amount. During this 'movement', I loop through all the tiles in the terrain, and I detect a collision with the bocks below, and to the front. Now what? If I've got a collision with the ground below (which could be any number of blocks in length, depending on how long the entity is) and a collision in it's path, how do I stop it from: 1. Falling through the ground, and 2. Moving through the tile in front?

This is where most documents on Bounding Box's seem to end, or become overly complex and begin to just use Mathematical notation (I'm not exactly [b]brilliant[/b] at understanding most of the equations I read).

Thank you for reading my post!
- Steve

Share this post


Link to post
Share on other sites
When you compute if its intersecting anything, you should be able to calculate how much the objects overlap. Once you know how much they overlap in the X, Y, and Z directions, you can simply move the character by that much in each dimension, so that that way the character would no longer be intersecting with that object.

That's just a simple outline of a simple method. There are additional complexities I'm skipping. Usually a physics engine will do this solving step a few times in a row, because moving the object so it isn't colliding with one object could very will move the character so that it is now colliding with another object. So looping through this solving process a few times will usually give a good approximation of where the character should be moved to so it isn't colliding with anything anymore.

I'd go into more detail and give you some links, but I'm writing this on a phone...

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1317495358' post='4868041']
When you compute if its intersecting anything, you should be able to calculate how much the objects overlap. Once you know how much they overlap in the X, Y, and Z directions, you can simply move the character by that much in each dimension, so that that way the character would no longer be intersecting with that object.

That's just a simple outline of a simple method. There are additional complexities I'm skipping. Usually a physics engine will do this solving step a few times in a row, because moving the object so it isn't colliding with one object could very will move the character so that it is now colliding with another object. So looping through this solving process a few times will usually give a good approximation of where the character should be moved to so it isn't colliding with anything anymore.

I'd go into more detail and give you some links, but I'm writing this on a phone...
[/quote]

Hi Cornstalks,
Thanks for your reply. Yeah, I kinda understand what you're talking about, but how would I check which face of the tile the entity is colliding with? For example, if I detected an intersection on the X axis, that also means the entity would technically be intersecting on the Z, too. So the resulting collision would be a little off :/

As for the looping part, that seems to be a good way of doing it, although I'm guessing that could be optimised by just only checking collisions with tiles in close proximity to the entity.

And if you do have some links, I'd be very happy to read them, I'm trying to find everything I can on the subject!!

- Steve

Share this post


Link to post
Share on other sites
How do you check if two AABBs are intersecting? Can you post the code for the collision test? If its anything like it should be, it should be easy to get how much to move the object.

And yes, you're right, there's no sense in checking against objects that are very far away. There's a few methods for determining which objects are near by, though they can be quite complex.

Edit: I'll try and post some links and more detailed posts and links once I get off this phone and onto a computer.

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1317511160' post='4868111']
How do you check if two AABBs are intersecting? Can you post the code for the collision test? If its anything like it should be, it should be easy to get how much to move the object.

And yes, you're right, there's no sense in checking against objects that are very far away. There's a few methods for determining which objects are near by, though they can be quite complex.

Edit: I'll try and post some links and more detailed posts and links once I get off this phone and onto a computer.
[/quote]

Hi, at the moment I'm using a simple check I found from a page on the internet (I was using a custom one, but this one is much faster):

[code]public boolean checkCollision(BoundingBox boundingBox1, BoundingBox boundingBox2) {
if(boundingBox1.min.x > boundingBox2.max.x) return false;
if(boundingBox1.min.y > boundingBox2.max.y) return false;
if(boundingBox1.min.z > boundingBox2.max.z) return false;
if(boundingBox1.max.x < boundingBox2.min.x) return false;
if(boundingBox1.max.y < boundingBox2.min.y) return false;
if(boundingBox1.max.z < boundingBox2.min.z) return false;
return true;
}[/code]


I've also got a self-written 'get intersect amount' method which does [b]seem[/b] to work, but I'm not exactly sure how I'm supposed to actually use it effectively (without a rather inefficient and buggy algorithm which doesn't actually fit in with the general concept of AABB's), heres that method:

[code]public float AABBIntersectAmount(BoundingBox newPos, BoundingBox collisionObject, IntersectType dimension) {
if (dimension == IntersectType.Intersect_X)
if (newPos.centre.x > collisionObject.centre.x)
return newPos.min.x - collisionObject.max.x;
else
return -(collisionObject.min.x - newPos.max.x);
if (dimension == IntersectType.Intersect_Y)
if (newPos.centre.y > collisionObject.centre.y)
return newPos.min.y - collisionObject.max.y;
else
return -(collisionObject.min.y - newPos.max.y);
if (dimension == IntersectType.Intersect_Z)
if (newPos.centre.z > collisionObject.centre.z)
return newPos.min.z - collisionObject.max.z;
else
return -(collisionObject.min.z - newPos.max.z);
return 0;
}[/code]


(NewPos being the position of the player, and collisionObject being the BoundingBox of a tile, dimension is just an enum which can either be X, Y or Z).

- Steve

Share this post


Link to post
Share on other sites
Does anyone know of any methods which actually fit in with the general concept of AABB's? At the moment the method I have above is really not very good, and I'd rather actually learn how AABB's should be done.

- Steve

Share this post


Link to post
Share on other sites
Hi, sorry I've been away for a bit. Yeah, your code is what I thought it would be like.

Your main problem is that if two AABBs are intersecting, you want to move them by the smallest amount possible so they are no longer intersecting. So if I were you, I would use your AABBIntersectAmount function to determine which axis, X, Y, or Z, has the least amount of overlap. Here's an example:

[code]//box1 and box2 are colliding
float x = AABBIntersectAmount(box1, box2, IntersectType.Intersect_X);
float y = AABBIntersectAmount(box1, box2, IntersectType.Intersect_Y);
float z = AABBIntersectAmount(box1, box2, IntersectType.Intersect_Z);

// Take the magnitude of each one
float absX = std::abs(x);
float absY = std::abs(y);
float absZ = std::abs(z);

if (absX < absY && absX < absZ)
{
// We're going to add a small amount to the nudge because of floating point errors.
// For example, if we only applied exactly x, the boxes may still be overlapping
// by some very small amount because of floating point approximations. By adding a
// very small amount, it should help us to overcome the inacuracies of floating point
// numbers. If we do not add a small epsilon, the boxes may "jitter."
float epsilon = 0.001f;
if (x < 0)
{
// If x is negative, we want the epsilon to be negative too.
epsilon = -epsilon
}

// If the x-overlap is the smallest, we can nudge each box by x / 2 so they aren't overlapping
// We do x / 2 because we're nudging both boxes. If we were only nudging one box, we would nudge
// it by x.
box1.centre.x += (x / 2) + epsilon;
box2.centre.x -= (x / 2) + epsilon;
}
else if (absY < absX && absY < absZ)
{
float epsilon = 0.001f;
if (y < 0)
{
epsilon = -epsilon
}

box1.centre.y += (y / 2) + epsilon;
box2.centre.y -= (y / 2) + epsilon;
}
else
{
float epsilon = 0.001f;
if (y < 0)
{
epsilon = -epsilon
}
box1.centre.z+= (z / 2) + epsilon;
box2.centre.z -= (z / 2) + epsilon;
}[/code]

Please remember that the code above has not been tested and isn't guaranteed.

Some gold mine websites:
[url="http://www.metanetsoftware.com/technique/tutorialA.html"]N Tutorial A[/url]
[url="http://www.metanetsoftware.com/technique/tutorialB.html"]N Tutorial B[/url]
[url="http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/"]Speculative Contacts[/url]
[url="http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/"]Collsion detection for dummies[/url]
[url="http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/"]Physics engines for dummies[/url]


Don't worry, to get your AABBs working, you don't have to go through and read all of those links. But I thought I'd give them to you because they're incredibly helpful and interesting. While yes, they're 2D based, the concepts they present can be extended to 3D. Edited by Cornstalks

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1317585659' post='4868358']
Hi, sorry I've been away for a bit. Yeah, your code is what I thought it would be like.

Your main problem is that if two AABBs are intersecting, you want to move them by the smallest amount possible so they are no longer intersecting. So if I were you, I would use your AABBIntersectAmount function to determine which axis, X, Y, or Z, has the least amount of overlap. Here's an example:

[code]//box1 and box2 are colliding
float x = AABBIntersectAmount(box1, box2, IntersectType.Intersect_X);
float y = AABBIntersectAmount(box1, box2, IntersectType.Intersect_Y);
float z = AABBIntersectAmount(box1, box2, IntersectType.Intersect_Z);

// Take the magnitude of each one
float absX = std::abs(x);
float absY = std::abs(y);
float absZ = std::abs(z);

if (absX < absY && absX < absZ)
{
// We're going to add a small amount to the nudge because of floating point errors.
// For example, if we only applied exactly x, the boxes may still be overlapping
// by some very small amount because of floating point approximations. By adding a
// very small amount, it should help us to overcome the inacuracies of floating point
// numbers. If we do not add a small epsilon, the boxes may "jitter."
float epsilon = 0.001f;
if (x < 0)
{
// If x is negative, we want the epsilon to be negative too.
epsilon = -epsilon
}

// If the x-overlap is the smallest, we can nudge each box by x / 2 so they aren't overlapping
// We do x / 2 because we're nudging both boxes. If we were only nudging one box, we would nudge
// it by x.
box1.centre.x += (x / 2) + epsilon;
box2.center.x += (x / 2) + epsilon;
}
else if (absY < absX && absY < absZ)
{
float epsilon = 0.001f;
if (y < 0)
{
epsilon = -epsilon
}

box1.centre.y += (y / 2) + epsilon;
box2.center.y += (y / 2) + epsilon;
}
else
{
float epsilon = 0.001f;
if (y < 0)
{
epsilon = -epsilon
}
box1.centre.z+= (z / 2) + epsilon;
box2.center.z += (z / 2) + epsilon;
}[/code]

Please remember that the code above has not been tested and isn't guaranteed.

Some gold mine websites:
[url="http://www.metanetsoftware.com/technique/tutorialA.html"]N Tutorial A[/url]
[url="http://www.metanetsoftware.com/technique/tutorialB.html"]N Tutorial B[/url]
[url="http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/"]Speculative Contacts[/url]
[url="http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/"]Collsion detection for dummies[/url]
[url="http://www.wildbunny.co.uk/blog/2011/04/06/physics-engines-for-dummies/"]Physics engines for dummies[/url]


Don't worry, to get your AABBs working, you don't have to go through and read all of those links. But I thought I'd give them to you because they're incredibly helpful and interesting. While yes, they're 2D based, the concepts they present can be extended to 3D.
[/quote]

Thanks for the links AND code! Yeah, I'll have to read through them, I've taken a look at the N tutorials previously and they did seem to give a good overview but I was too tired to consider modifying them to be 3D. Also, when you use this line of code:

[code][color=#1C2837][font=CourierNew, monospace][size=2][color=#000000]box1[/color][color=#666600].[/color][color=#000000]centre[/color][color=#666600].[/color][color=#000000]x [/color][color=#666600]+=[/color][color=#000000] [/color][color=#666600]([/color][color=#000000]x [/color][color=#666600]/[/color][color=#000000] [/color][color=#006666]2[/color][color=#666600])[/color][color=#000000] [/color][color=#666600]+[/color][color=#000000] epsilon[/color][color=#666600];[/color][/size][/font][/color]
[font=CourierNew, monospace][size=2] box2[color=#666600].[/color][color=#000000]center[/color][color=#666600].[/color][color=#000000]x [/color][color=#666600]+=[/color][color=#000000] [/color][color=#666600]([/color][color=#000000]x [/color][color=#666600]/[/color][color=#000000] [/color][color=#006666]2[/color][color=#666600])[/color][color=#000000] [/color][color=#666600]+[/color][color=#000000] epsilon[/color][color=#666600];[/color][/size][/font][/code]


Would this be used to, for example, provide a more 'realistic' collision between two entities? E.g. If one entity collides with another, they both 'bounce' off one another?

Thank you for taking the time to help!
- Steve

Share this post


Link to post
Share on other sites
Are you referring to the epsilon or to how both box1 and box2 get their positions modified? I'll respond to both. It's not for a "bounce" effect. "Bounce" is handled in the physics engine via [url="http://en.wikipedia.org/wiki/Coefficient_of_restitution"]restitution[/url], something that this simple example doesn't handle. But I think you're on the right track.


I add the epsilon because of [url="http://download.oracle.com/docs/cd/E19957-01/806-3568/ncg_goldberg.html"]floating point rounding error[/url] ([url="http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.16"]and this is the tl;dr version[/url]). Here's a small example. Let's say box1 and box2 are overlapping by a value of 3 units on the x-axis. Simple enough, if we just shift each of them by 1.5 (1.5 + 1.5 = 3), they should not be overlapping anymore. So if we did box1.center.x += 1.5 and box2.center.x += 1.5, they should no longer be overlapping. But what about floating point rounding error? If we were to run the collision detection test again, we may find that they're still intersecting! It's possible the computer had to slightly round things, and now the overlap is some very small amount (example: 0.00001102...). So by adding an additional epsilon to our displacement, we should be able to compensate for any rounding errors that the computer has to make. I used the name epsilon because that's often the greek letter used to represent the amount of an approximation's error. Really, the epsilon shouldn't be noticed by the player. If it is, it's too big. It should just be there to help the computer overcome it's limitations with floating point numbers.

Now the reason that I added 1 / 2 of x (or y, or z, depending on which one was largest) to each of box1 and box2 is because usually when two things collide, they both move. Making them each move 1 / 2 of the necessary correction amount should allow the character to interact with things. That is, if he hits a box, then both he and the box will have their positions adjusted, causing both of them to move. However, you may want to just add the full value of x (or y, or z, depending on which is largest) to only one of the AABBs. For example, what if you have a large container that you want to be immovable and the character hits it? You only want the character's position to be affected, not the containers! So you would change the code to make it so only the character's position is affected, and you wouldn't touch the container's position values. But only adding 1 / 2 of the necessary displacement to the character's position would only move him 1 / 2 as far as he needed to move, so in this case you would add the full value.

Hopefully that makes things a little clearer.

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1317593889' post='4868407']
Are you referring to the epsilon or to how both box1 and box2 get their positions modified? I'll respond to both. It's not for a "bounce" effect. "Bounce" is handled in the physics engine via [url="http://en.wikipedia.org/wiki/Coefficient_of_restitution"]restitution[/url], something that this simple example doesn't handle. But I think you're on the right track.


I add the epsilon because of [url="http://download.oracle.com/docs/cd/E19957-01/806-3568/ncg_goldberg.html"]floating point rounding error[/url] ([url="http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.16"]and this is the tl;dr version[/url]). Here's a small example. Let's say box1 and box2 are overlapping by a value of 3 units on the x-axis. Simple enough, if we just shift each of them by 1.5 (1.5 + 1.5 = 3), they should not be overlapping anymore. So if we did box1.center.x += 1.5 and box2.center.x += 1.5, they should no longer be overlapping. But what about floating point rounding error? If we were to run the collision detection test again, we may find that they're still intersecting! It's possible the computer had to slightly round things, and now the overlap is some very small amount (example: 0.00001102...). So by adding an additional epsilon to our displacement, we should be able to compensate for any rounding errors that the computer has to make. I used the name epsilon because that's often the greek letter used to represent the amount of an approximation's error. Really, the epsilon shouldn't be noticed by the player. If it is, it's too big. It should just be there to help the computer overcome it's limitations with floating point numbers.

Now the reason that I added 1 / 2 of x (or y, or z, depending on which one was largest) to each of box1 and box2 is because usually when two things collide, they both move. Making them each move 1 / 2 of the necessary correction amount should allow the character to interact with things. That is, if he hits a box, then both he and the box will have their positions adjusted, causing both of them to move. However, you may want to just add the full value of x (or y, or z, depending on which is largest) to only one of the AABBs. For example, what if you have a large container that you want to be immovable and the character hits it? You only want the character's position to be affected, not the containers! So you would change the code to make it so only the character's position is affected, and you wouldn't touch the container's position values. But only adding 1 / 2 of the necessary displacement to the character's position would only move him 1 / 2 as far as he needed to move, so in this case you would add the full value.

Hopefully that makes things a little clearer.
[/quote]

That has cleared everything up [b]A LOT[/b], I'm glad you also included that description on Epsilon, because I think that's something I've actually encountered previously, and I didn't think to fix it in such a way.

And yes, by 'bounce' I just meant both moving instead of a single box, although I will have a look at restitution, because that will probably come in handy later!

Thanks for all the help, especially the links! I've got a lot of reading to do!!! Everything is much, much clearer now!

- Steve

Share this post


Link to post
Share on other sites
I just realized a big bug in my code example (aside from spelling it "centre" and "center"). Box1 should be += and box2 should be -= (or maybe its the other way around). I'll edit the post and correct it.

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