Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I have a lot of complex objects in a scene and I'm looking for an efficient way to find which object a fired bullet hits, and to find the hit coordinates.
It would be best if there was a lightweight library to do this.
It seems that PhysX can do this, but I didn't find a way except to give every face in every mesh a PhysX system, and that seems to become a bottleneck.
PhysX can pre-process your collision meshes into it's own optimised collision structures (probably a series of convex meshes). The process is called cooking, and it is described in a blog here: http://actuated.wordpress.com/2010/06/26/mesh-collision-in-physx/
So I guess that your initial attempt is to iterate through all meshes in your scene, for each mesh, check all triangles if they intersect, right? The brute-force way.
I'm not sure if there's a lightweight library for you to solve your problem, but the problem is quite a large discussing area.
I would suggest using a bounding-volume structure, such as a KD-Tree used in 3 dimensions. Christer Ericsson suggests an implementation in his book "Realtime Collision Detection" which is cache-friendly and memory efficient. I've implemented his suggestion in a project and indeed it did turn out very well. The task of creating a KD-tree together with splitting your meshes into well-balanced tree's is covered in depth by Ingo Wald (http://www.sci.utah.edu/~wald/Publications/index.html). I suggest you read up on there. The Surface Area Heurestic (SAH) is considered (one of?) the best algorithms for KD-splitting, Ingo Wald covers it in one of his publications (http://www.sci.utah.edu/~wald/PhD/index.html).
There are a variety of freeware KD-tree's out there, I haven't really looked into kdtree at google-code (http://code.google.com/p/kdtree/) but it looks pretty decent. There's some interesting tutorials (http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en) that you can read.
Good luck!
I just once stuck with some collision testing like this and the answer was to pack object near each other into groups, then check a simple sphere collision test for every group and if the bullet hits a specific group then check if it realy hits acual object(now using faces) it may still take some time but is far more optimized than a standard face collision checking. and you can make some groups of groups and so on to speedup your collision testing even more.
I really can recommend the OpenDynamics, an open source physics library, with loads of examples and its pretty straightforward. It also works easily with plain old C.
As far as I can remember, OpenDynamics supports some kind of mesh loading. Otherwise, you have to create the faces for the physics themselves.
There are other nice free physics engines I have looked through (did not try them yet):
There are also some pyhsics engine for 2D only: Box2D and chipmunk I tried and are great also.
