Sign in to follow this  
leoptimus

Collision detection on Jiggle

Recommended Posts

leoptimus    106
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
leoptimus    106
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
Kwizatz    1392
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
sbroumley    283
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
b34r    365
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
MrRowl    2490
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
oliii    2196
octrees take a lot of space. What you'll end up, at the bottom of the tree, will be the voxel map anyway. But they could accelerate the col det part.

Share this post


Link to post
Share on other sites
Eelco    301
Quote:
Original post by oliii
octrees take a lot of space. What you'll end up, at the bottom of the tree, will be the voxel map anyway. But they could accelerate the col det part.


eh?

they would decelerate the coldet part, as now its no longer a simple array lookup but tree traversal is needed.

however, space requirements will go down drasticly, with a much improved ability to provide detail where its needed, on sharp edges for instance. with an octree space requirements will be more or less proportional to surface area rather than volume.

Share this post


Link to post
Share on other sites
MrRowl    2490
To be honest, I'm not sure how you'd use an octree in this situation - could be either for:

1. Storing the voxels (bad idea, makes interpolation/lookup difficult)

2. Storing the "features" - i.e. collision points. This sort-of makes sense, but you need a way of intersecting the octree cells (AABB) with the voxels - and that's going to be slow (maybe), unless

3. Store the voxels AND the features in an octree. I don't think so...

Share this post


Link to post
Share on other sites
Eelco    301
Quote:
Original post by MrRowl
To be honest, I'm not sure how you'd use an octree in this situation - could be either for:

1. Storing the voxels (bad idea, makes interpolation/lookup difficult)


so just because its difficult its a bad idea? i think youre being a little quick here.

interpolation should be quite doable. mutiple coherent lookups will take more or less the same path through the tree, so the interpolation takes almost no extra time at all.

on top of that one single tree lookup isnt prohibitively much more expensive than an array lookup i think.

in any case it is bound to make a huge difference in memory consumption.

Share this post


Link to post
Share on other sites
leoptimus    106
Octrees are just maded for arrange objects in a space. In jiggle, there are no objects, just an uniform distribution of voxels that have distances, like a heightmap.
So is more simple to test intersections on a cubic matrix, than on a hierarchy structure.

And yes, I'm wrong about GJK. Just I don't understant well that paper,so Anybody knows where I can find more information about GJK?

Share this post


Link to post
Share on other sites
oliii    2196
the only part that bugs me in the GJK is the Johnson's distance computation and simplex reduction. And also the MTD computation a little bit (gotta work onm that a bit). Short of buying Gino's book, looking into his SOLID code seems a good idea. It's relatively clean.

Share this post


Link to post
Share on other sites
Eelco    301
Quote:
Original post by leoptimus
Octrees are just maded for arrange objects in a space.


you are wrong.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Maybe Eelco came up with a breakthrough in Octree traversal.
Hey Eelco can you post your thoughts on how to go about it.

Share this post


Link to post
Share on other sites
Eelco    301
Quote:
Original post by Anonymous Poster
Maybe Eelco came up with a breakthrough in Octree traversal.
Hey Eelco can you post your thoughts on how to go about it.


its hardly a breakthrough.

just assign to each leaf in the octree the same properties as you would to the regular grid, and there you go.

you dont really need to traverse it in a raytracing sense, just traverse it downwards in one location in order to find the stored properties for a given xyz coord.

nothing special, but the memory saved compared to a regular grid is easily orders of magnitude for a typical object.

Share this post


Link to post
Share on other sites
Kwizatz    1392
Quote:
Original post by leoptimus
Aah! SOLID eh? Why I didn't check it before?
Thanks Oliii


There is a catch with SOLID you should be aware of, it is GPL, so you can only use it on GPL projects, or pay for a commercial license (2000 euros per single game), furthermore, seems like versions above 3.5 will not be Open Source at all.

However, there is FreeSOLID, which is Solid 2.0, it's LGPL, so you can make commercial apps with it, it doesn't have the latest features, and there is a bug on the code that returns the contact depth, but it does implement the GJK algorithm properly.

I kind of took over the SourceForge Project about 2 years ago, but being that back then the whole thing was way over my head, there hasn't been much improvement (I took over just so I could modify the building process in order to generate shared objects and dll's and be able to use it as the LGPL intended).

So anyway, all this rant is to say that patches for FreeSOLID are very welcome [smile].

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this