if N is a normal of convex A, and a a point on that face. If b is a point of convex B.

bool FrontFacing(const CConvex& ConvexA, const CConvex& Convex B){    for(int i = 0; i < ConvexA.GetNumFaces(); i ++)    {        Vector a = ConvexA.GetFace(i).GetVertex(0);        Vector n = ConvexA.GetFace(i).GetNormal();            for(int j = 0; j < ConvexB.GetNumVertices(); j ++)        {             Vector b = ConvexB.GetVertex(j);             Vector ab = b - a;                 if (ab.Dot(n) > 0.0f)                  return false;        }    }    return true;}

and then you do

if (FrontFacing(A, B) || FrontFacing(B, A))    return false;// test edge edge collisions//...//...//...

it''s not very fast, nor efficient, and will give you false positives unless you also tests the planes defined by the cross products of edges, but it''s a start. This can be bad for very sharp convex hulls. A GJK algo would be certainly much better.

To simplify the separation axis theorem for convex polyhedras, you can consider only two types of possible collisions. points vs faces, and edges versus edges. all other cases are derived from those two generic cases (edge vs face, face vs face, edge versus point...).

so basically, what you have to do for each faces, find the closest point on the other polygon to that face, and see if it is back facing. That can save some time. Instead of doing the test for each points against the face, pick a point on the convex object, and using the connectivity between points, follow the edge from one point to another to find the point that would be the closest to the face. Since the object is convex, you are bound to find a minimum point towards the face on the other object. if that point is front facing the face, then no collision. This point is called a support point along the face normal. That''s also the basis for the GJK algorithm.

for edges against edges, it''s a lot more tricky. the simplest solution would be, to cross product every edges of convexA against every edges of convexB, and see if the projection of ConvexA and ConvexB along the normal defined by the cross product of the two edges overlap or not. But that''s obviously impractical.

I never tried this, but I would think finding the closest point from an edge, and taking the interconnected edges from that point, and building planes by crossing the edges together would be more practical. although, it''s still very slow.

another method tries to find the closest features on the two convex polyhedras, and caching the closest features, you can quickly test two moving convex polyhedras against each others, taking advantage of the space-time coherence (the objects won''t move much relative to each other between physics frames).

I-collide uses that method, I think, and it''s a popular way of testing two convex objects. You need to store connectivity info for each polyhedras (like a list of neighbouring points for each vertex), but that''s not a big deal.

there is a library developed by Gino Van Der Gergen, called SOLID, which implements the GJK stuff. It''s free and the source code is available.

http://www.win.tue.nl/~gino/solid/


also, for non convex polyhedras, you have a variety of methods, build octrees, a voxel map, split the non convex objects into convex parts, ...

for example
http://www.dh.aist.go.jp/~kawachi/ncmd.html

I used to have a demo of a GJK-like collison detection on convex hulls, but I seemed to have lost it.

Anyway, it should not be too hard to implement, the tricky part is to find the penetration depth (i.e. the embedded points of contacts) when the GJK fails (intersection detected), as there is no easy way to solve that case. But that''s if you allow penetrations to occur.

You would think it should be easy, as easy as when the object do not intersect, but it''s not, for some weird reason (after all, it''s like finding geometrically the point on a convex curve the closest to the origin, when the origin is inside the curve). look for enhanced GJK, which gives pointers on how to solve this.

quote:Original post by robert_s
Ok. Thank you very much Olii for help.
But I'll have to ask you again about this stuff to be sure that I understood you 100%.

So you suggesting to ignore those two methods described on gamasutra's site ie. searching for a separating plane using an edge from a convex hull A and a point from convex B.

What you're saying is to select a face in A and select a face in B and in that face (poly) from B search for the nearest point to face A. Am I right? Once the nearest point is found in current face in convex B then perform test if the point is on positive side of the current plane in convex A or not. Once this test is finished then I select the next face in B and search for nearest point to the face in A. I keep selecting faces in B and searching for nearest points in B. Then when there is no more faces to test in B I select another face in A and run those test again through all faces in B searching for nearest points in each face in B. Is this what you meant?

not quite.

1) Select a face on A (called FA).

2) Select a point on B (called PB).

3) Calculate the distance of PB to FA.

5) Get the neighbours of PB (called PB[0], PB[1], PB[2], ...).

6) let min = dist(PB, FA);

7) for (each neighbours PB[j])

8) if (dist(PB[j], FA) < min) { min = dist(PB[j], FA); PB = PB[j]; }

9) end loop

10) if (dist(PB, FA) == min) // we have a minimum
11). if (min > 0) return false; // the minimum point is front facing, Face A is the separation plane, PB is the closest point.
12). else goto 1). // test a new face on A.

10) goto 3) // continue the search


[edited by - oliii on April 14, 2004 5:05:01 AM]

[edited by - oliii on April 14, 2004 5:05:31 AM]

quote:Original post by robert_s
Now, the method you desribed,

which point do you consider to be the nearest point to the plane? B1 or B3. I know B3 is below the plane but in terms of numbers B3 is smallest. If B2 is nearest then how do you filter B3 so it desnt tell you that tere is a collision? If B3 is the smallest then this point is not front facing which would mean its a collision. But its not true. Sorry if I still have got you as I should

B3 will be the closest point.

using the loop above, start with B1.

neighbours are B2, B3, B4.

PB = B1

3)
min = d = dist(PB, FA)

dist(B2, FA) = d2, and (d2 > min)
dist(B3, FA) = d3, and (d3 < min), so min = d3, PB = B3;
dist(B4, FA) = d4, and (d4 > min)

(d != min), go to 3)


3)
PB = B3

neighbours are B1, B2, B4.

min = d = dist(PB, FA)

dist(B1, FA) = d1, and (d1 > min)
dist(B2, FA) = d2, and (d2 > min)
dist(B4, FA) = d4, and (d4 > min)

(d == min),
so P3 is the closest point from face FA.
(d < 0) so that plane is inconclusive, get the next face on Convex A and start again.

obviously caching data would help, to avoid testing the same vertices again and again (B1 B2, B4 have already been tested, no need to test them again at all, for that face).

this stuff works better for complex hulls, obviously. For a tetrahedron, you might as well test all the vertices. As soon as you found a vertex back facing the plane, go to 1). If no vertex back face the plane, you have a separation plane.

eventually, you could find that no face has a closest point front-facing the plane, so in that case, you need to test with edges as well, or you''ll get false positives.

For edges, it''s practically the same thing, except you need to find the closest point to that edge. Once you found it, build planes with edges attached to that point and the edge you are testing, and see if the projections of the convex hulls overlap along the plane normal or not.

this isn''t the best algo in the world, by a mile. it''s painfully slow. But walking along the convex object has it''s use, and is used by GJK and I-Collide to find support vertices. So good to keep.