# Collision detection

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

## Recommended Posts

I know how to check rays against planes etc but I want to know how to check for collisions the fastest way. If I have a bounding box and it represents my character in-game and I want to get into my house and I wanna check if I hit the wall I will need several rays checking from the bounding box on several positions, no? Then I'd have to use loads of loads of rays and calculations just for my character so my character's head or something wont just get through the wall.

##### Share on other sites
If you haven't yet read this then it may help:
http://www.harveycartel.org/metanet/tutorials/tutorialA.html

You may have to extend it to 3D but the basic principles for quick collision detection are there

##### Share on other sites
It's not really the same thing as walking through a door. Let's say there are 4 boxes that makes up the doors borders and the door is open. How to make a "safe" check as fast as possible? To make sure it'll always work I'd have to make loads of rays checking all the 4 boxes, no?

##### Share on other sites
Good way to check for collision is a sphere swept line, or something like it.

basicly take your bounding volume at its current and previous positions and create a collision volume based on that. Then check collision with possible collision volumes in the branch of your octree your currently in if you have one.

collision detection is the easy part IMHO.

##### Share on other sites
Quote:
 Original post by HannesnisulaIt's not really the same thing as walking through a door. Let's say there are 4 boxes that makes up the doors borders and the door is open. How to make a "safe" check as fast as possible? To make sure it'll always work I'd have to make loads of rays checking all the 4 boxes, no?

Not really.

You have to make a test for each side of the boxes, to determine which boxes to check you should have some sort of method to cull them out, like an Octree or BSP Tree.

What you do is offset the ray for each box side plane in relation to the box min/max, it goes something like this (taken from here):

    vector offset;            for (int j = 0; j < 3; j++)            {                if (plane->normal[j] < 0)                    offset[j] = traceMaxs[j];                else                    offset[j] = traceMins[j];            }            startDistance = (inputStart[0] + offset[0]) * plane->normal[0] +                            (inputStart[1] + offset[1]) * plane->normal[1] +                            (inputStart[2] + offset[2]) * plane->normal[2] -                            plane->distance;            endDistance = (inputEnd[0] + offset[0]) * plane->normal[0] +                          (inputEnd[1] + offset[1]) * plane->normal[1] +                          (inputEnd[2] + offset[2]) * plane->normal[2] -                          plane->distance;

startDistance and endDistance hold float values for the distance from the current plane being tested to the start point and the end point, if they have different sign, you have a collision.

To get the delta for the collision use this:

float delta = (startDistance - EPSILON) / (startDistance - endDistance);

where EPSILON is a tiny number used to avoid floating point errors (Quake defines it as 0.03125f).

Edit: since you're not using a BSP, you should probably test that the intersection between the plane and the ray is inside the box polygon.

##### Share on other sites
I'm really confused. Are there any open-source "easy" collision detection engine or something I could take a look at?

##### Share on other sites
Why are you all talking about rays? There is none involved.
You have an axis-aligned box at point A. Then you ask to know whether that axis-aligned box can go to point B without colliding into anything.

That's easy, just make a new axis-aligned box that covers the whole path from A to B.
Then test whether that axis-aligned box collides with any of the geometry.

The same thing can be done with spheres: the path from a position to another will however then be a bullet.
Now if you work with oriented boxes, that's more complicated.

##### Share on other sites
Quote:
 Original post by HannesnisulaI'm really confused. Are there any open-source "easy" collision detection engine or something I could take a look at?

Sorry, its a complicated thing to explain, I know.

As for collision detection libraries, Bullet, OPCODE, D-COLLIDE, GIMPACT come to mind.

You can also look for Separating Axis Theorem on Google, collision detection is sadly not trivial though.

##### Share on other sites
I could find out (if I don't know already) how to check stuff, but I want to know what to check. The separating axis test is no problem (this far). But I've been thinking of making a new box around the present and "next" position of the boxes for an object and then check that for collisions. I want to know if that's one of the fastest ways to check collisions.

Thanks for all the help this far!

##### Share on other sites
Quote:
 Original post by HannesnisulaI could find out (if I don't know already) how to check stuff, but I want to know what to check. The separating axis test is no problem (this far). But I've been thinking of making a new box around the present and "next" position of the boxes for an object and then check that for collisions. I want to know if that's one of the fastest ways to check collisions.Thanks for all the help this far!

It is good for broad phase collision detection, but after that check you should do narrow phase collision detection against the objects that the bigger box partially or completely contains. If you just check for the extended AABB you could get false positives on certain situations such as when moving diagonally.

• ### What is your GameDev Story?

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

• 13
• 12
• 15
• 11
• 12
• ### Forum Statistics

• Total Topics
634153
• Total Posts
3015844
×