[ODE] solid terrain representations that are still tunnelable?

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

```Hi,

>
>... 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"*
http://www.amazon.co.uk/exec/obidos/ASIN/155860801X/qid%3D1109161026/026-0609826-2377207

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

David
```