[ODE] solid terrain representations that are still tunnelable?

[David Black]

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 
origin(polyhedra centroid) within that quadrant. This leads to perfect 
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