# [ODE] solid terrain representations that are still tunnelable?

David Black dblack at fastmail.fm
Thu Feb 24 15:45:53 MST 2005

```Hi,

>Hi,
>
>I'm going to be implementing a convex-convex collider in the near future.
>
>I use the SAT for box-box collision. When the boxes overlap, I use the axis
>with minimum penetration to determine the contact manifold. If the axis is
>edge-edge, it's just a single contact point. If it's a face axis, I use that
>face as a reference polygon, then determine the incident face on the other
>box. I clip the incident face against the reference face using
>Sutherland-Hodgeman clipping. This algorithm yields up to 8 contact points.
>
>
I tried a method similar to this initially, however generating the
manifold in this way does not always generate the most sensible manifold.

Consider a pair of cubes which sit one on top of the other. due to
numerical inaccuracies the closest axis could be any of the top face
normal, bottom face normal or an edge-edge cross product(eg an x-z plane
edge crossed with a y-x plane edge). You could make sure that you prefer
a face-face axis when generating the manifold.  But then you run into
problems for degenerate situations...

Imagine one of the cubes is translated along the x-axis so that a pair
of edges coincide. For this situation the contact manifold should be a
line and I want the normal to be
Normalize(Cross(edgeA.LeftFace.Normal,edgeA.RightFace.Normal)). But with
the above method the normal could be that of either of the edge faces
and might perhaps oscillate between the two... not good for my contact
solver.

Instead what I do to correctly handle degenerate situations is each time
I encounter a contact to attach it to a data structure for each face,
which stores a list of all contact points involving that face. eg there
is a list of face-point, edge-edge, edge-point vertex-edge etc.

Then later on I determine the best normal to use for the contact set by
scanning the data structure for each face. If there are a set of
contacts which cross the face, eg two edge-edge contacts on non
neighboring edges then the correct contact normal is that faces normal.
Also use that faces normal if there are any internal point contacts.

Next if I cant find a face normal to use I look for a  pair of contacts
which form a line manifold(ie two contacts which are on the same edge or
an end vertex).

Finally I conclude that it must be a single point manifold(eg
vertex-vertex, vertex-edge etc) and generate an appropriate normal.

OK, I know all this sounds like a complicated way of doing things, but
it does handle all the degenerate cases in a consistent manner and it is
quite fast if you use a sensible data structure to link the contact
points into.

>I'm thinking of doing something similar for convex-convex. The trick is to
>determine the minimum penetration axis quickly. Perhaps the axis could be
>cached. Then the next step could start with that axis and somehow "walk" the
>nearby axes to determine the minimum.
>
>Are you doing something like this, or is it pure brute force?
>
>

Well I do cache the last separating axis if the polyhedra were disjoint.
This allows a nice early out for disjoint polyhedra.

Another trick is to randomly re-order your faces and edges, this leads
to a nice spread of test axis, hopefully producing a separating axis
more quickly(the faces may initially be ordered so that  lots of similar
axis are grouped together).

However if they are in contact I cannot early out since I need to check
all axis(faces/edges) for contact points...

What I do for the inner loop, to determine the maximum point along an
axis is to pre-compute a hash table for each polyhedra based on possible
axis. Then when finding the maximal point, I compute the hash of the
axis and lookup a maximal vertex in the hash table. Given this vertex I
attempt to find a closer vertex from the vertices connected by edges. If
I cannot find a closer one then I know this vertex is  the maximal point
along the axis.

For the hash function, I just have an 8 entry hash table based on the
signs of the axis(each entry is an octant). The vertex pointers stored
in the hash table are the ones which are furthest from the
results for cubes(ie the first guess is the correct one) which is a nice
benefit, since they are very common in my levels.

I have considered using more complex hashing functions, but my current
geometry does not really warrant it...

I have also seen a BSP tree used to find the maximal vertex along an
axis, however I think this is probably overkill for the numbers of edges
in my level geometry. (plus somewhat more complicated).

David
```