Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

CGameProgrammer

Collision libraries that don't need trees

This topic is 5477 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'm goint to use ODE for physics/collision but for collision with triangle meshes you need something else to generate contact points. I was looking at RAPID and OPCODE but they both use tree heirarchies to sort geometry. This is useless to me. I already sort geometry very efficiently; RAM usage is minimal and it's very fast as well. I just want to plug in the vertex data and collide'em. Is there a library someone has written to do this? ~CGameProgrammer( ); [edited by - CGameProgrammer on June 18, 2003 3:00:10 AM]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
these libraries use trees to store geometry because they are very efficient when used to determine which pairs of triangles can potentially intersect. once the potentially intersecting pairs are found, an intersection algorithm like the moller-trumbore ray-triangle algorithm (or some faster but more memory hungry alternative) is used to find if the potentially intersecting triangles do actually intersect (and find contact points)

so, if you have a very good spatial partitioning scheme you should be able to find the intersecting pairs yourself and run the tri-tri intersection algos on them to find contact points. however the brunt of the work in any collision detection system is to actually trim down all the polys in a scene to a few pairs which on which the longer intersection tests can be run quickly. if your scheme doesnt use trees it probably won''t let you find pairs quickly enough or will find too many pairs that don''t actually intersect to be practical. but if it can, just use a standard tri-tri intersection algorithm on your pairs to generate contact points, and feed those to ODE.

james

Share this post


Link to post
Share on other sites
Thanks for the reply. The reason I didn't want trees was that they'd have to be built and deleted at runtime since the world is far too large to hold trees for everything, and building trees is slow. I group geometry in equally spaced chunks of around 170 cubic feet, and then for each mesh I do a distance-squared check with its overall bounding sphere and then a distance-squared check with the [precalculated] bounding sphere of each triangle. Only when it's likely I'm colliding with a triangle do I do collision with it. Of course this means I do a linear loop through all triangles (if the first sphere test passes) whereas a tree could let me skip stuff, but it's the fact that the trees would need to be rebuilt often that prevents me from wanting to use them.

I guess I'll just be coding my own contact-point code and will try feeding the points to ODE. I found this page which is very helpful. Hopefully things will be fine. But I'm surprised there's no simple collision library -- the problem with finding contact points is you need the geometry to already be intersecting, as opposed to moving an entity only as far as it can go. That's what I do now, with sphere-triangle collision, but there are some errors and it's only sphere-triangle.

EDIT: The reason that's a problem is something can very easily move from a point in front of an object to a point behind it, in one frame. Never will it be intersecting the object so the collision code won't catch that.

~CGameProgrammer( );



[edited by - CGameProgrammer on June 20, 2003 6:35:33 AM]

Share this post


Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!