[ODE] solid terrain representations that are still tunnelable?

David Black dblack at fastmail.fm
Wed Feb 23 12:20:17 MST 2005


>... as for convex solids, though, that would of course be preferable.
>Is there a convex bounding hull collider available for ODE I'm just
>unaware of, or did you roll your own?  (and assuming you did, is it
>either available somewhere, or do you have any particularly good
>recommendations for reading material on them)
I should probably make it clear that I am not using ODE at all. As far 
as I am aware there is no convex convex polyhedron collider available 
for it :-(

However there are a lot of papers/code available on the internet for 
computing the distance between convex solids, unfortunatly most of them 
do not cover generating contact high quality contact manifolds/normals.

Some notable examples:

* VClip (uses a algorithm based on voronoi regions, ie planes 
perpendicular to polygons).
* Solid (GJK algorithm)
* Seperating axis (look at www.magic-software.com for an example)

My first implimentation was based on the VClip algorithm, which can be 
made to perform very well. However it was a large amount of very 
unpleasant code and there is a big scope for bugs and unpleasant edge 
cases(causing infinite loops within the collider). I eventually got sick 
of trying to deal with all the edge casses in a clean manner, so dropped it.

I am now using something based on the seperating axis theorom, which is 
much more of a brute force algorithm. As far as performance SAT can be 
made fast for disjoint polygons, but is not so good for polyhedra in 
contact (generally n^2, in practice, for the number of edges). Which is 
workable for polyhedra with a sensible number of edges, since the inner 
loop is very fast.

As for generating the contact manifold, there is much less material 
available. I could describe the algorithm I use if anyone is interested, 
but it is mainly just fiddly code dealing with the combinations of 
polyhedra features.

As for books I have "Game Physics" by David H Eberly, Which is quite 
good though seems a bit too focused on maths and a little brief on 
implimenting a practical physics system. But it does have quite a good 
discussion of implimenting a SAT collider, and some info on generating 
the contact manifolds.

There are a couple of other books, which look good, but I have not been 
able to afford yet. eg

*Real-Time Collision Detection*
http://realtimecollisiondetection.net/ and
"*Collision Detection in Interactive 3D Environments"* 

Both appear to have good coverage of convex-convex collision detection.


More information about the ODE mailing list