Back to General and Gameplay Programming

best collision detection algo

HalcyonX · 2005-08-26T23:10:41

Im working on collision detection for my game, and need some advice. I looked into a bunch of different collision detecion algorithms, and finally decided to be ambitious and use GJK. But now that i looked more into it, im not sure if its the best choice for my requirements. So GJK is really fast for just detecting collisions. But I need the colliding objects to physically respond to the collision. For this, i need to know exactly which polygon hit where on which polygon. But it seems that calculating the point of collision requires explicitly finding the whole CSO, which would take n^2 time to find the verticies, and then even more time to build the hull. So now im not sure. Given these requirements, would GJK still be the best choice in terms of speed? Thanks. EDIT: Oh, another thing i need to find is the penetration depth in the direction of the 2 object's relative velocity. If i do build the hull of the whole CSO, i can find this fairly easily.. i think? Alternatively, if i use another algo, i could do a binary search through space. Please take this into consideration when answering my questions above. Thanks.

General and Gameplay Programming Programming

Started by HalcyonX August 12, 2005 06:05 PM

18 comments, last by SimmerD 18 years, 7 months ago

Zakwayda

2,389

August 15, 2005 02:05 AM

Quote:mmm ic. So if i dont use GJK, what alternatives would you suggest for the accurate test of body parts after the bounding volumes test?

If you can stick with static tests only for individual body parts, I'd use capsules, as the static capsule/capsule test (including penetration info) is quite easy to implement. Capsule/triangle (for intersection with the world) is a little harder, but not too difficult.

If swept is required, OBBs would be a good choice. The static and swept OBB tests can both be done with the separating axis theorem, although it's a little more complicated than the capsule test.

Cylinders are difficult, so I'd avoid them. The only other practical option I can think of at the moment would be a set of spheres.

'Hope that helps.

HalcyonX

130

Author

August 15, 2005 10:17 PM

Mmmm thanks, ic. What if i wanted more details about the collision? A friend volunteered to do collision response, and is asking for my collision detection functions to find which features (polygons, verticies, etc.) are colliding. How would you suggest doing this?

Zakwayda

2,389

August 16, 2005 12:33 PM

Typically collision response is based on either:

1. Penetration depth and distance (for static intersection)
2. Contact point(s) and normal (for swept intersection)

You might ask your friend what he or she needs the per-polygon intersection info for. Resolving collisions on a per-polygon level can be difficult (especially if the meshes are not convex) and is often unnecessary. If it turns out you really do need collision detection at the triangle level, that's a whole other area. At that point you'll be getting into bounding volume hierarchies and triangle-triangle intersection.

I'd ask your friend exactly what he or she has in mind for collision response, and between the two of you try to determine the minimum requirements for coldet feedback. Again, when it comes to collision detection it's wise to keep things as simple as possible.

HalcyonX

130

Author

August 17, 2005 09:08 PM

What he wants is the contact points and normal to do sort of a physics simulation. Isnt that the same as finding which features are colliding though? How can you find the normal if you dont know which polygon it is?

Zakwayda

2,389

August 17, 2005 09:30 PM

Quote:What he wants is the contact points and normal to do sort of a physics simulation. Isnt that the same as finding which features are colliding though? How can you find the normal if you dont know which polygon it is?

Hey,

I can't speak authoritatively on this, but I'll tell you what I think. If this were my game, I wouldn't do per-triangle collision detection; based on what you've said about the game (RPG characters and environment), it just doesn't seem like it would be practical or worth the effort.

I would do static tests wherever possible, and swept tests where necessary (like for projectiles). For static collisions, I'd resolve the penetration and then use the normal and contact info to drive the physics simulation. I'd approximate my objects with capsules and spheres; static capsule/capsule, capsule/sphere, capsule/triangle, and sphere/triangle tests are all very practical and fairly straightforward to implement.

Anyway, this is all 100% IMHO. If you're convinced per-poly is the way to go, you should do it. But my guess is that it would end up causing more problems than it solved.

HalcyonX

130

Author

August 17, 2005 09:49 PM

Quote:
I would do static tests wherever possible, and swept tests where necessary (like for projectiles). For static collisions, I'd resolve the penetration and then use the normal and contact info to drive the physics simulation. I'd approximate my objects with capsules and spheres; static capsule/capsule, capsule/sphere, capsule/triangle, and sphere/triangle tests are all very practical and fairly straightforward to implement.

Yea i get what you are saying, but what i dont understand is how do you get the normal and contact info without doing tri-tri tests?

EDIT:
oh.. you're saying to approximate the normals and contact points with the capsules and spheres?

Zakwayda

2,389

August 17, 2005 10:45 PM

Quote:oh.. you're saying to approximate the normals and contact points with the capsules and spheres?

Pretty much. Most intersection tests (including the ones I'm suggesting) can return a contact normal, and a contact point (for swept) or penetration depth (for static).

Now obviously the capsules or spheres or whatever are approximations of the underlying mesh, and so the contact information will be an approximation of the actual contact. However, in collision detection 'approximate' is often perfectly acceptable.

SimmerD

1,210

August 18, 2005 01:01 AM

I agree with jyk. That's what I'm implementing for my action/rpg. Of course, our hand-to-hand combat is a bit more abstract that what you are talking about.

I just got the capsule code integrated a few minutes ago. I changed from ellipsoids, b/c ellipsoid vs ellipsoid is hard, but capsule to capsule is easy.

I also am not doing swept tests. Right now I am limiting the speed of objects based on their radius to prevent tunnelling, but what I will change in the next few days is to make it so that if an object moves more than its 0.9 * its radius, then its movement is broken into a series of equal moves until the timestep is used, or it collides ( I treat all collisions as happening at the end of the timestep ).

Game Development Journal

HalcyonX

130

Author

August 18, 2005 01:55 AM

mmm ic. Alright, ill give that a go then. So now, how do you calculate the capsule? Does it have to be defined somehow with the model by the artist? Or is there some good way to calculate it?

SimmerD

1,210

August 26, 2005 11:10 PM

I rely on the models having their longest side in model space along the model space Y axis.

This way I can fit the capsule to fit inside their model space bounding box.

Game Development Journal

best collision detection algo

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

best collision detection algo

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines