Jump to content
  • Advertisement
Sign in to follow this  
leoptimus

Collision detection on Jiggle

This topic is 4881 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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?



Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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].

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!