Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Several years ago, i made a fast collision detection for 2D, it was just checking a bullets front-pixel's color to check if it were to hit something. Lets say the target rgb color is (124,200,255) then it just checks for that color. After the collision detection, it paints the target with appropriate picture. So, collision detection is made in background without drawing but then painted and drawed.

How can i do this in 3D? Because, a vertex is not just exist like a 2D picture's pixel. I looked at some java3D and other programs and understood that 3D world is made of objects. Not just pictures. Is there a program that truly fills the world with vertices ? But it could be needing terabytes of ram even more.

Do you know an easy way to interpolate the color of a vertex in java3D or similar program?

Note: for a rgb color-identifier, i can make 255*255*255 different 2D objects in background.

share|improve this question
I don't think you actually want to do that, you should look up Space Partitioning up instead –  Mr. Beast Sep 1 '12 at 11:50
Like dividing space into cubes? –  huseyin tugrul buyukisik Sep 1 '12 at 12:14
add comment

1 Answer

up vote 2 down vote accepted

You have correctly understood your problem. Your clever trick for 2D collision detection is (usually) impractical in 3D precisely because a sufficiently precise voxel array is generally too much data to be keeping in memory or updating per-frame.

(One exception is explicitly voxel-based games, where you're paying that cost anyway, but I'll assume you're not doing that.)

Here's how 3D collision detection is typically implemented. I'll start with the simplest thing that can work and then refine it.

You have a collection — a data structure — holding all of the ‘physical’ objects in your game. Each frame, for every object in this collection, go through every other object in this collection, and call a routine which knows how to check these two objects for collisions. (For example, a slow bullet might be treated as a point — no volume of its own — and simply test whether that point is within the other object.)

This works, but since it iterates over all pairs of objects, it takes O(n²) time.

The first thing to do is to avoid wasting time on checking distant objects. To do this, you need some sort of spatial indexing in your collection of objects. One such data structure is an octree, which recursively partitions space into segments which eventually contain only a few objects. I won't include the details here, but in order to do any sort of spatial indexing, you will generally need to have routines which compute the axis-aligned bounding boxes of your objects — this is just a rough approximation of the space your object takes up. Once you have a spatial index structure, you can check only pairs of objects which are known to be in the same vicinity.

This algorithm is going to be (sloppily considering) something like O(nm² log n), where n is the total number of objects and m is the maximum number of objects all in one pile in one spot.

The second thing to do is avoid wasteful collision tests. (This is mainly applicable if you have lots of stationary objects that can never collide, but which are not treated as a special unique “this is the level geometry” object.) Instead of having a single collection of all physical objects, have (at least) two: one which stores all the moving objects, and one which stores all the stationary objects. Do the same pair-checking (using the spatially indexed collection) for the moving objects, and then check the moving objects against the stationary objects. In this way, you do not waste time checking adjacent stationary objects against each other.

Sound like a lot of work? Sure. The good news is, you don't need to write all that, unless you have a very special use case. Just use a physics library (or “engine”) in your code which will provide all of this for you. (Physics libraries also provide response to collision — bouncing off, falling down, etc. — but you can usually use the collision component without the dynamics component, or vice versa, if it is not suited for your game.)

share|improve this answer
Yes, i used spatial indexing once in a molecular-dynamics system but it was static. I havent used dynamic version. –  huseyin tugrul buyukisik Sep 1 '12 at 16:03
add comment

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.