[edited by - CGameProgrammer on June 18, 2003 3:00:10 AM]
Collision libraries that don't need trees
Author
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]
[edited by - CGameProgrammer on June 18, 2003 3:00:10 AM]
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
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
Author
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
