I need to efficiently detect collisions between two objects made up of voxels. I don't know a lot about pixel perfect collision detection but I would think you could extrapolate some of the techniques into another dimension. The only other major difference being that the objects can rotate arbitrarily relative to each other. The only thing I can think of is doing some binary space partitioning or octree on each object, but the problem is that the objects are dynamic so that is a lot of data to recalculate when things change, and that will get pretty complicated with the objects rotating relative to each other.

Any tips? tricks? I found a couple research articles about it but they don't seem to be publicly viewable without paying.

If they're ACM or IEEE I could get the articles for you.

What you're describing sounds damn complex. How many voxel objects would be colliding at any one time? Any simplifying assumptions you can make about your voxel objects?

Maybe you could use an R*-tree to store chunks of voxels, and then you'd only have to do the comparison between the voxels closest to each other.

_________________
Whatever the mind can conceive and believe, it can achieve

Probably 8 objects tops. But they can be multi-segmented and can collide internally. So I am gonna say probably in the ballpark of 64 objects, and around 150,000 * 8 voxels total.

I don't think the articles were ACM or IEEE but thanks for the offer.

This is the kind of problem that CUDA would be great for. Should be very amenable to parallelisation.

I don't understand how the voxel objects can collide internally? Does that mean they're not static? I'm imagining a kind of Lego construct. Or is it that the various objects are created from static voxel objects that are hinged together at various joints?

Maybe you could use an existing physics engine to create a bunch of bounding boxes around your voxels. At the simplest level, you could just create a 3D grid pattern around each one. Then when the boxes from different objects collide, do an n³ collision check at the voxel level, where n is hopefully small.

I tried to draw something in Paint but it didn't look like anything

_________________
Whatever the mind can conceive and believe, it can achieve

Yeah, the objects have moving parts (joints/hinges etc.) The objects themselves are also destructible.

Unfortunately, CUDA isn't really an option. I want it to run on the Xbox360.

I am looking at a similar problem and have found an ACM article which may be relevant.
I would much appreciate some help in accessing it, and Struan may find it useful too.
Here is the link: http://portal.acm.org/citation.cfm?id=514231

Create an account and send me a PM Scog.

_________________
Whatever the mind can conceive and believe, it can achieve

The only thing that comes to mind for me is the naive n*m check. The next best thing I can think of is to approximate its shape with a set of bounding shapes at the cost of some accuracy.

In case your voxel objects are 'filled', to cut down on the n*m complexity you could only check the voxels that make up the outer shell of your object. This would fail to detect when one object is completely inside another object though.

_________________
Heard in #gpwiki: <wzl> is there some serious grammar fail in your line or am i just too intelligent for your logic