Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question

migrated from May 20 '11 at 14:55

This question came from our site for professional and enthusiast programmers.

up vote 4 down vote accepted

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:

share|improve this answer

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 ( 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 (

There are a variety of freeware KD-tree's out there, I haven't really looked into kdtree at google-code ( but it looks pretty decent. There's some interesting tutorials ( that you can read.

Good luck!

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.