Collision detection on Jiggle
Author
Does Jiggle implement GJK algorithm?
At this point I don't understand GJK at all, but I think that is similar to jiggle approach.
Jiggle precalculate convex distances in a in a voxel structure.
Whatever, Do you think that Jiggle collision detection is efficient?
Perhaps Jiggle doesn't have GJK algorithm, but have a nice algorithm, fast and simple.
Author
You can get jiggle at: http://www.rowlhouse.co.uk/jiggle/
It's a physics engine, that implements an impulsive method for collisions and constraint resolution.
It has a pretty collision algorithm for convex, that consist on calculate a 3d voxel grid of that convex, and for each voxel it calculates the distance and the normal from the convex. For voxels in convex distances are negative, and for voxels out of the boundary of it are positive.
It calculates collision distance in a discret way, like GJK. I'm wrong?
It's a physics engine, that implements an impulsive method for collisions and constraint resolution.
It has a pretty collision algorithm for convex, that consist on calculate a 3d voxel grid of that convex, and for each voxel it calculates the distance and the normal from the convex. For voxels in convex distances are negative, and for voxels out of the boundary of it are positive.
It calculates collision distance in a discret way, like GJK. I'm wrong?
I really dont know, but the Jiggle paper reads "Nonconvex", GJK works with the Minkouski sum of 2 convex shapes, no voxels, so I doubt Jiggle implements GJK, it's a different approach as far as I can tell.
The "Jiggle" demo implements signed distance maps like those explained in the paper it is based on. Basically each collision object is voxelized and each voxel is assigned a distance+normal to the nearest surface (-ve when the center of the voxel is in the interior of the shape, +ve when the center of the voxel is on the exterior of the shape).
For collision detection between 2 objects, you simply map the vertices of ObjectA into the distance map of ObjectB (and vice versa), interpolating similar to bi-linear texture filtering for more accuracy - this gives you a penetration depth and normal for each vertex (you can compute the contact point using the center position of the voxel + [distance * normal])
It's pretty simple to implement (you can compile the object distance maps offline) - the downside is it can use lots of memory depending upon the size of your object and the resolution of the distance map (memory usage is Width*Height*Length*BytesPerVoxel). The big advantage is that distance maps can be used for any type of collision mesh - convex or non-convex. I think Novadex implements them, but it calls them P-Maps.
I hope this helps,
Steve.
[Edited by - sbroumley on July 5, 2005 1:41:28 AM]
For collision detection between 2 objects, you simply map the vertices of ObjectA into the distance map of ObjectB (and vice versa), interpolating similar to bi-linear texture filtering for more accuracy - this gives you a penetration depth and normal for each vertex (you can compute the contact point using the center position of the voxel + [distance * normal])
It's pretty simple to implement (you can compile the object distance maps offline) - the downside is it can use lots of memory depending upon the size of your object and the resolution of the distance map (memory usage is Width*Height*Length*BytesPerVoxel). The big advantage is that distance maps can be used for any type of collision mesh - convex or non-convex. I think Novadex implements them, but it calls them P-Maps.
I hope this helps,
Steve.
[Edited by - sbroumley on July 5, 2005 1:41:28 AM]
Interesting, I didn't know Mr.Rowl had implemented this method in Jiggle. When I first read that paper I was wondering if it would gives acceptable results for game like meshes where you often have a very uneven distribution in polygons. My feeling was that it would be very good for dense imperfect/natural meshes but ill-suited for lowpoly/clean architectural models with sharp edges. I'm off downloading Jiggle one more time [wink].
My experience with it is that it's not that great. It uses up a lot of memory, is quite slow (at least, when compared to using primitives like cubes/spheres), and you get visible artifacts because of the way you have to sample object to extract points from them. Also, since the penetration depth/direction is done based on local properties of the mesh, it will often return results that are inappropriate for the object as a whole (can result in sticky contacts). You also have to sample a large number of points, and this in turn generates a large number of contacts when you have object overlaps - either a problem for the solver, or a problem for your contact reduction code.
One of the major speedups between jiggle and jiglib was dropping this scheme and using primitives - not only is the collision detection faster, but also the contacts generated are "cleaner" which makes life a lot easier for the physics code. I agree with b34r's comments.
I'm sure it could be improved though. One thing that would help would be the ability to cast a ray through the voxel grid - would be useful for both detection with edges (rather than splitting edges up into discrete points) and swept tests. Also, "instancing" would improve memory usage by allowing you to share the voxel grid between identical (or scaled etc) models. A scheme that mixed primitives and this voxel method (for a few awkward shapes) would probably work well too.
One of the major speedups between jiggle and jiglib was dropping this scheme and using primitives - not only is the collision detection faster, but also the contacts generated are "cleaner" which makes life a lot easier for the physics code. I agree with b34r's comments.
I'm sure it could be improved though. One thing that would help would be the ability to cast a ray through the voxel grid - would be useful for both detection with edges (rather than splitting edges up into discrete points) and swept tests. Also, "instancing" would improve memory usage by allowing you to share the voxel grid between identical (or scaled etc) models. A scheme that mixed primitives and this voxel method (for a few awkward shapes) would probably work well too.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
