google / liquidfun

2D physics engine for games
http://google.github.io/liquidfun
4.68k stars 641 forks source link

b2PolygonShape::ComputeDistance is inaccurate #123

Open Manamongods opened 1 year ago

Manamongods commented 1 year ago

I'm pretty sure that the b2PolygonShape::ComputeDistance does not return the actual distance when it comes to corners, only distances along normals. There is a secondary check after finding the max dot product that checks distance to each point, but I don't think that check will ever do anything. I believe that the greatest dot product can at most be equal to the distance to the nearest point, but never greater than it.

The code in question:

void b2PolygonShape::ComputeDistance(const b2Transform& xf, const b2Vec2& p, float32* distance, b2Vec2* normal, int32 childIndex) const
{
    B2_NOT_USED(childIndex);

    b2Vec2 pLocal = b2MulT(xf.q, p - xf.p);
    float32 maxDistance = -FLT_MAX;
    b2Vec2 normalForMaxDistance = pLocal;

    for (int32 i = 0; i < m_count; ++i)
    {
        float32 dot = b2Dot(m_normals[i], pLocal - m_vertices[i]);
        if (dot > maxDistance)
        {
            maxDistance = dot;
            normalForMaxDistance = m_normals[i];
        }
    }

    if (maxDistance > 0)
    {
        b2Vec2 minDistance = normalForMaxDistance;
        float32 minDistance2 = maxDistance * maxDistance;
        for (int32 i = 0; i < m_count; ++i)
        {
            b2Vec2 distance = pLocal - m_vertices[i];
            float32 distance2 = distance.LengthSquared();
            if (minDistance2 > distance2)
            {
                minDistance = distance;
                minDistance2 = distance2;
            }
        }

        *distance = b2Sqrt(minDistance2);
        *normal = b2Mul(xf.q, minDistance);
        normal->Normalize();
    }
    else
    {
        *distance = maxDistance;
        *normal = b2Mul(xf.q, normalForMaxDistance);
    }
}
Manamongods commented 1 year ago

I created a pull request: https://github.com/google/liquidfun/pull/124