Hello everyone,

I know that collision detection is a frequent topic of discussion here, so I figured that this might be a good forum to present an early version of some research that I have been working on and hopefully get some early feedback. The basic idea here is to rewrite the collision test as a convolution, then use a low pass filter to discretize the geometry of the solids. These convolutions can then be evaluated and differentiated exactly using a finite Fourier summation, which leads to a new collision test / Jacobian calculation that scales with the accuracy of the solids (ie the number of coefficients is proportional to the running time and to the accuracy of the test). I believe that this technique has the potential to be much simpler than more conventional contact/geometry based collision detection schemes and could lead to a new class of solvers for approximate collision detection/rigid body dynamics. Here is a link to the early draft of the paper:


http://sal-cnc.me.wisc.edu/index.php?option=com_remository&Itemid=143&func=fileinfo&id=191


This is still an early version, but I'd definitely appreciate any and all comments. I am also curious to know what those who have more experience with developing rigid body dynamics engines may think about this approach, and what their views are on the general problem.

As for the actual idea, seems 'way out there' in terms of concept Because nearly everything is polyhedral in games (with a few spherical exceptions) in terms of collision detection, it seems like converting to frequency space with all the associated ringing problems there in would be counter intuitive...

Can you summarise the main advantages of your technique?

Cheers, Paul.

Sure! The Fourier representation proposed in the paper is formally equivalent to working with a "fuzzy voxelized" version of a solid. You can think of the collision test in the following way:


1. Take all your solid objects (for example a polyhedral mesh) and convert them to a voxelized representation.

2. For each of these voxelized objects, blur them, for example with a Gaussian filter. (This is also equivalent to offsetting the solids some amount).

3. Now when you want to check if two solids collide, you basically compute the amount of overlap volume between their two fuzzy representations; if this overlap volume is very close to 0, you say the solids don't intersect, or if it is very high you say they collide.

(Bonus) If you also want to figure out how to push the two objects apart, you can take the gradient of this overlap volume and use it to generate a normal force. It is also possible to use the same idea to generate rotational separation forces too! So you get free collision forces without having to find contact points!



Now the tricky part is basically figuring out how to make all of this reasonably fast. The way you do this is that instead of working with voxel images, you work with Fourier coefficients. It can be shown that this is in fact exactly the same thing as working with blurry voxel images; or alternatively it is equivalent to doing collision detection between offset solids. The fewer coefficients you use, the more you end up offsetting the solid/blurring the voxel map. Also, since we are using Fourier coefficients, we can compute the gradients for the collision test for free by just using some basic calculus which makes finding the Jacobian for collision forces really easy.

In terms of what kind of geometry you could use this with, it would work really well with bitmap images in a 2D game, or in a 3D version you could use precalculated voxelized geometry to approximate your meshes.

EDIT: And to address the question about ringing, this turns out to be quite fixable if you use a good blurring process. In fact, the method described in this paper provably has no ringing artifacts.

I haven't finished it yet, but so far I can't help but love this paper.

I do have some concerns though; maybe you can address them.

The biggest of these is that the functions you use to represent solids seem kind of pathological. In particular, they have zero derivative at the boundary of their support. This seems at odds with the idea of differentiating them to determine e.g. contact normals. It's precisely when you need the most information about the normals to the level sets that the gradient of the bump function stops giving you any information. Isn't this problematic?

I do have some concerns though; maybe you can address them.

The biggest of these is that the functions you use to represent solids seem kind of pathological. In particular, they have zero derivative at the boundary of their support. This seems at odds with the idea of differentiating them to determine e.g. contact normals. It's precisely when you need the most information about the normals to the level sets that the gradient of the bump function stops giving you any information. Isn't this problematic?

Thanks for reading!

To address your concerns, let me first point out two things:

1. The derivative at the boundary always exists, since it is formed from the convolution of two continuous functions.
2. Since we end up actually low pass filtering the objects, (see below), the level set defining the boundary of the configuration space obstacle turns out to be a smooth curve and so it always has a well defined tangent and normal direction (ie it will not be 0 anywhere).

Now to elaborate on this smoothing/filtering business, it is really an artifact of discretizing/downsampling the shape. In fact, from the Fourier perspective low pass filtering and downsampling are identical. As a result, low pass filtering has the nice side effect of killing off the higher order divergent frequency terms, which ends up forcing the derivative to be convergent. (At least in the sense of a Weyl derivative http://en.wikipedia.org/wiki/Weyl_differintegral ) Geometrically, this discretization/sampling has a simple interpretation as offsetting (ie Minkowski summing) the shape with a ball of finite radius. In fact, one of the fascinating consequences of this observation is that it seems to suggest that offsetting a shape or a collision test is a lossy process, which parallels downsampling in DSP!

Of course the messy part is basically figuring out how how to do the low pass filtering but at the same time keep a working collision test (since if you do this naively you will get ringing artifacts that will mess things up and result in spurious collisions). In order to make this work, I ended up resorting a sort of brute force, ugly analysis method to construct a filter, but I am fairly convinced that there is a more elegant solution. For example, I found that just smoothing out the frequency terms with a carefully scaled Gaussian appears to do a fine job of fixing the boundary discontinuities and also makes the collision test work properly, though I wasn't able to compute the tight radius or cutoff estimates for the Gaussian kernel. This nastiness is the main topic of section 5 in the paper, and is basically where I spent the bulk of the work in developing this method (probably because I wasn't clever enough to see a simpler way to get an estimate).

To be honest, I didn't read the paper really. I just kind of skimmed it and read your posts.

It's an interesting idea, but have you compared it to just approximating objects with a sphere tree? The last current gen game I worked on basically just represented each object as a collection of spheres (don't even remember if we bothered with a tree..). This is also an approximation of the actual shape, but it's trivial to scale/rotate/translate and it's very predictable and easily controlled. So I think for your work to be taken seriously, you really should make some speed comparisons to sphere tree (or any bounding volume hierarchy) collision - in 3D.

To be honest, I didn't read the paper really. I just kind of skimmed it and read your posts.

It's an interesting idea, but have you compared it to just approximating objects with a sphere tree? The last current gen game I worked on basically just represented each object as a collection of spheres (don't even remember if we bothered with a tree..). This is also an approximation of the actual shape, but it's trivial to scale/rotate/translate and it's very predictable and easily controlled. So I think for your work to be taken seriously, you really should make some speed comparisons to sphere tree (or any bounding volume hierarchy) collision - in 3D.

Well, it is not exactly the same thing as approximating your object as a sphere. It is basically like taking your object then offsetting it with a sphere. Also rotations and translations are really easy to do in this method too, (though scaling is currently more problematic). So in this way, I don't really see why it would be less predictable. But you are right, I think that adding some speed comparisons would be a good idea. Do you know of any good commercial code for doing sphere tree based collision detection?

[quote name='stevesan' timestamp='1299611141' post='4783228']
To be honest, I didn't read the paper really. I just kind of skimmed it and read your posts.

It's an interesting idea, but have you compared it to just approximating objects with a sphere tree? The last current gen game I worked on basically just represented each object as a collection of spheres (don't even remember if we bothered with a tree..). This is also an approximation of the actual shape, but it's trivial to scale/rotate/translate and it's very predictable and easily controlled. So I think for your work to be taken seriously, you really should make some speed comparisons to sphere tree (or any bounding volume hierarchy) collision - in 3D.

Well, it is not exactly the same thing as approximating your object as a sphere. It is basically like taking your object then offsetting it with a sphere. Also rotations and translations are really easy to do in this method too, (though scaling is currently more problematic). So in this way, I don't really see why it would be less predictable. But you are right, I think that adding some speed comparisons would be a good idea. Do you know of any good commercial code/benchmarks for doing sphere tree intersections of objects?

[/quote]

Not exactly the same, sure, but an approximation nonetheless. By "predictable" I mean that with a sphere-tree, there are no parameters to adjust - it seems like there's a threshold in your algorithm. With sphere-trees, the spheres either touch or they don't.

For comparisons, you should implement your own. You should understand it anyway and be able to articulate why your method is faster (if it actually is). See section 3.1 of this paper for relevant references: http://graphics.cs.cmu.edu/projects/bdtree/JamesPai_BDTree04.pdf
The particular algorithm you use isn't too relevant assuming you implement it reasonably well. If your approach is clearly faster, it should show on complex examples.

And if that is the case, consider submitting to SIGGRAPH! I'm no expert on this topic, so I can't guarantee it would get in (this method may not actually be new), but it seems novel to me.