1

I am developing a 3D Game Engine as a project. I would like to use space partitioning algorithms for each triangle/polygon in my scene to efficiently detect collisions. I just want to know (before I start programming the specifics) how fast is a typical space partitioning algorithm in modern computer games? I have dynamical objects so I am thinking that I might have to repartition my scene every frame. Is that possible and still achieve a reasonable frame rate? It would be very much appreciated if the answer could include data (e.g. the FPS, number of polygons, etc.). If that is too much trouble, just tell me if it is plausible to repartition every frame.

Any help would be appreciated.

Improve this question
2
  • I would suggest that you take a look at kinetic data structures. They might help you to avoid repartion the scene each time. Commented Jul 31, 2012 at 7:15
  • Take a look at quadtree/octree trees (en.wikipedia.org/wiki/Quadtree, en.wikipedia.org/wiki/Octree). Moving an object then means removing it from the tree, and inserting it again. If you only want to check for collisions between one dynamic and many fixed objects, then you probably don't even need to store the dynamic object in the tree, just use the tree to check for collisions) Commented Jul 31, 2012 at 11:13

1 Answer 1

Reset to default
4

I would first suggest reading the chapter on Broad-Phase Collision Detection with CUDA. It goes into comparison of different broad phase collision algorithms. Your performance depends on a few key variables. The first variable is whether or not your algorithm is implemented using GPU acceleration. The previously cited article contains some benchmarks on framerate vs. number of objects. At the very least it should give you a good idea of what is achievable.

If you don’t plan on GPU acceleration, sweep and prune is one of the easiest to implement. I don’t know the exact figures, but it performs well when there are few objects and your objects don’t vary too much between frames. In this situation, you have O(n) performance. This is a good one to start with as a baseline, because it is trivial to implement.

If you are really getting serious, I recommend the book Real-Time Collision Detection. I used this one when doing research on collision detection methods. It was a great resource.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.