Page 1 of 1

Support Mapping Function for Triangles with MPR

Posted: Wed Mar 13, 2013 3:46 pm
by jason.ngai
Hello Folks,

I am currently implementing a physics engine for a game project, modelling after XenoCollide by Gary Snethen. (Games Programming Gems 7)

I have a simple question with regards to support mapping function for triangles in 3D space.

Currently, this is what I have:

- Suppose the Triangle stores an array of 3 vertices.

Code: Select all

void Triangle::GetSupportPoint(Vector3& point, const Vector3& normal)
{
    f32 maxDist = FLT_MIN;
    s32 maxIndex = -1;

    for (s32 i = 0; i < 3; ++i)
    {
        f32 result = vertices_[i].Dot(normal);
        if (result > maxDist)
        {
             maxIndex = i;
             maxDist = result;
        }
    }
    return vertices_[maxIndex];
}
I have tested this against a working box collider. (working on box-box etc.)

If I lay the triangle on the XZ plane, and have my camera looking down -Y at the triangle, it seems okay.
But in actual fact, if I were to look at it on the XY plane, there seem to be a "tetrahedron effect" on the triangle. It registers a false positive on the +Y side of the plane that slopes upwards until it converges above the centroid. Also, the contact normal were going +Y but sloped towards the outer vertex for some reason.

I believe my derivation is wrong.

I seek you professional people's advice if there's any way that I can do to "flatten" the collision area.

Thanks!
Jason

Re: Support Mapping Function for Triangles with MPR

Posted: Thu Mar 14, 2013 3:38 pm
by jason.ngai
Hello again,

**Edit 15th March 2013**
**Added a case for when the 2 centers are perfectly on-line to the origin ray.

I have found a solution that seems to work:

Code: Select all

        Vector3 Triangle::GetSupportPoint(const Vector3& normal) const
        {
            f32 maxDist = FLT_MIN;
            s32 maxIndex = -1;

            Sphere sphere(EPSILON); //Sphere collider

            for (s32 i = 0; i < 3; ++i)
            {
                f32 result = vertices_[i].Dot(normal);
                if (result > maxDist)
                {
                    maxIndex = i;
                    maxDist = result;
                }
            }
            
            // Slap an epsilon value against the normal of the triangle plane as "volume"
            // So that MPR may terminate before it tries to construct the tetrahedron
            Vector3 point = sphere.GetSupportPoint(normal);

            // EDIT: Singularity when 2 centers are perfectly on-line to the normal from the origin
            if (maxDist > EPSILON)
                point += vertices_[maxIndex]; // Standard cases
            else
                point += (vertices_[0] + vertices_[1] + vertices_[2])/3; // Returns centroid instead

            return point;
        }
Basically, the main issues here is this:
Unlike rectangles, triangles does not come in a standard form, i.e., obtuse, acute, etc.
I attach a tiny value to the depth of the plane so that MPR could terminate earlier, allowing the triangle to behave as it should in 2D space.

The result I have achieved seems okay visually, I have yet to stress test it.

If anyone could verify or offer a better suggestion, please let us know!

Regards,
Jason

Re: Support Mapping Function for Triangles with MPR

Posted: Tue Apr 30, 2013 11:00 am
by mikeshafer
What is MPR? I use a triangle support function for GJK collision. You shouldn't need to do anything special for your triangle mapping function for GJK. There are degenerate cases (i.e. your triangle is a line or your tetrahedron is a triangle), but you can handle them pretty easily. Let me know if you've got it all figured out.

Mike