• Advertisement
Sign in to follow this  

Collision detection

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Hannesnisula
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?


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Hannesnisula
I'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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Hannesnisula
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!


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.

Share this post


Link to post
Share on other sites
Quote:

If you just check for the extended AABB you could get false positives on certain situations such as when moving diagonally.


you can help this with a tiered collision detection system. Like once you figure out where you would "collide" you could break the object down into smaller volumes for more accurate collision detection.

You could go all the way down to per triangle collision with a tiered system. though it gets slower if you get close to something or actually hit it.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement