Public Group

# Collision methods?

This topic is 2669 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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. But heres where the problem is, 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 brilliant at understanding most of the equations I read).

Thank you for reading my post!
- Steve

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

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

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

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; }

I've also got a self-written 'get intersect amount' method which does seem 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:

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; }

(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 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 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:

//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; }

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

Some gold mine websites:
N Tutorial A
N Tutorial B
Speculative Contacts
Collsion detection for dummies
Physics engines for dummies

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 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:

//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; }

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

Some gold mine websites:
N Tutorial A
N Tutorial B
Speculative Contacts
Collsion detection for dummies
Physics engines for dummies

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.

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:

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

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 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 restitution, something that this simple example doesn't handle. But I think you're on the right track.

I add the epsilon because of floating point rounding error (and this is the tl;dr version). 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 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 restitution, something that this simple example doesn't handle. But I think you're on the right track.

I add the epsilon because of floating point rounding error (and this is the tl;dr version). 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.

That has cleared everything up A LOT, 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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 11
• 9
• 9
• 42
• ### Forum Statistics

• Total Topics
634131
• Total Posts
3015715
×