search

NVIDIAGameWorks / PhysX

NVIDIA PhysX SDK
Other
3.11k stars 793 forks source link

Found bug in Gu::sweepSphereVSTri #597

Open bleston opened 1 year ago

bleston commented 1 year ago

I found a bug in function Gu::sweepSphereVSTri. In some case, it will miss collision.

Below code show the bug. The capsule should hit the triangle at point hitPos. But PxGeometryQuery::sweep do not find the hit.

void testSweepSphereTriangle()
{
    const PxVec3 vertices[3] = { {7.33294010f, 79.6109009f, -26.9337997f}, {7.61456013f, 80.2574005f, -27.3008995f }, {7.33294010f, 80.2574005f, -26.9337997f} };
    const PxU32 indices[3] = { 0, 1, 2 };

    static float radius = 0.265350759f;
    static float halfHeight = 0.340350509f;

    const PxVec3 startPoint{ 7.74110079f,80.8543167f,-27.2595482f };
    const PxQuat rot{ 0.f, 0.f,0.707106829f,0.707106829f };
    const PxVec3 unitDir{ -0.929564953f,  -0.0281119142f,  0.367584974f };
    const PxReal distance{ 0.149537891f };

    const PxVec3 hitPos{ 7.59219694f, 80.2574005f, -27.2717476f };
    const PxReal hitDistance{ 0.0944127962f };

    const PxVec3 p0 = hitPos - unitDir * hitDistance;

    const physx::PxTransform pose0{ startPoint, rot};
    const physx::PxTransform poseTri{ PxIdentity };

    PxHitFlags hitFlags{ physx::PxHitFlag::eDEFAULT | physx::PxHitFlag::eMESH_BOTH_SIDES | physx::PxHitFlag::eASSUME_NO_INITIAL_OVERLAP };

    PxTriangleMeshDesc meshDesc;
    meshDesc.points.count = 3;
    meshDesc.points.data = vertices;
    meshDesc.points.stride = sizeof(PxVec3);
    meshDesc.triangles.count = 1;
    meshDesc.triangles.data = indices;
    meshDesc.triangles.stride = 3 * sizeof(PxU32);
    PxCookingParams params = gCooking->getParams();

    PxTriangleMesh* triMesh = NULL;
    triMesh = gCooking->createTriangleMesh(meshDesc, gPhysics->getPhysicsInsertionCallback());

    PxTriangleMeshGeometry triGeom{ triMesh };
    PxCapsuleGeometry capsuleGeom{ radius, halfHeight };

    bool isInitOverlap = PxGeometryQuery::overlap(capsuleGeom, pose0, triGeom, poseTri);
    printf("isInitOverlap = %d.\n", isInitOverlap);

    physx::PxSweepHit hit;
    PxU32 hitCount = PxGeometryQuery::sweep(unitDir, distance, capsuleGeom, pose0, triGeom, poseTri, hit, hitFlags);
    printf("\nSweep capsule hitCount = %d.\n", hitCount);
    if (hitCount > 0)
    {
        printf("hit position is (%f, %f, %f).\n", hit.position.x, hit.position.y, hit.position.z);
        printf("hit normal is (%f, %f, %f).\n", hit.normal.x, hit.normal.y, hit.normal.z);
        printf("hit distance is %f.\n", hit.distance);
    }

    PxTransform pose1{ startPoint + unitDir * distance, rot };
    bool isResultOverlap = PxGeometryQuery::overlap(capsuleGeom, pose1, triGeom, poseTri);
    printf("\nisResultOverlap = %d.\n", isResultOverlap);

    PxReal p0ToCapsule = PxGeometryQuery::pointDistance(p0, capsuleGeom, pose0);
    printf("\np0(%f, %f, %f) %s capsule\n", p0.x, p0.y, p0.z, (p0ToCapsule <= 0.f) ? "is in" : "is not in");
    physx::PxRaycastHit rayHits[1];
    hitCount = PxGeometryQuery::raycast(p0, unitDir, triGeom, poseTri, distance, hitFlags, 1, rayHits);
    printf("raycast p0 hitCount = %d.\n", hitCount);
    if (hitCount > 0)
    {
        printf("raycast hit position is (%f, %f, %f).\n", rayHits[0].position.x, rayHits[0].position.y, rayHits[0].position.z);
        printf("raycast hit normal is (%f, %f, %f).\n", rayHits[0].normal.x, rayHits[0].normal.y, rayHits[0].normal.z);
        printf("raycast hit distance is %f.\n", rayHits[0].distance);
    }

    triMesh->release();
}

I found the bug is in function Gu::sweepSphereVSTri. It says as below:

    //
    // Let's do some art!
    //
    // The triangle gets divided into the following areas (based on the barycentric coordinates (u,v)):
    //
    //               \   A0    /
    //                 \      /
    //                   \   /
    //                     \/ 0
    //            A02      *      A01
    //   u /              /   \          \ v
    //    *              /      \         *
    //                  /         \                     .
    //               2 /            \ 1
    //          ------*--------------*-------
    //               /                 \                .
    //        A2    /        A12         \   A1
    //
    //
    // Based on the area where the computed triangle plane intersection point lies in, a different sweep test will be applied.
    //
    // A) A01, A02, A12  : Test sphere against the corresponding edge
    // B) A0, A1, A2     : Test sphere against the corresponding vertex
    //
    // Unfortunately, B) does not work for long, thin triangles. Hence there is some extra code which does a conservative check and
    // switches to edge tests if necessary.
    //

When test sphere against vertex, this function only test with sphere. This may miss contact. In this case, both edge should be tested.

Below patch can fix this problem.

 .../geomutils/src/sweep/GuSweepSphereTriangle.cpp  | 59 +++++++++++++---------
 1 file changed, 35 insertions(+), 24 deletions(-)

diff --git a/physx/source/geomutils/src/sweep/GuSweepSphereTriangle.cpp b/physx/source/geomutils/src/sweep/GuSweepSphereTriangle.cpp
index a8e8d9b9..3470aaaa 100644
--- a/physx/source/geomutils/src/sweep/GuSweepSphereTriangle.cpp
+++ b/physx/source/geomutils/src/sweep/GuSweepSphereTriangle.cpp
@@ -86,7 +86,7 @@ static PX_FORCE_INLINE PxU32 rayTriSpecial(const PxVec3& orig, const PxVec3& dir
 // Returns true if sphere can be tested against triangle vertex, false if edge test should be performed
 //
 // Uses a conservative approach to work for "sliver triangles" (long & thin) as well.
-static PX_FORCE_INLINE bool edgeOrVertexTest(const PxVec3& planeIntersectPoint, const PxVec3* PX_RESTRICT tri, PxU32 vertIntersectCandidate, PxU32 vert0, PxU32 vert1, PxU32& secondEdgeVert)
+static PX_FORCE_INLINE bool oneOrTwoEdgeTest(const PxVec3& planeIntersectPoint, const PxVec3* PX_RESTRICT tri, PxU32 vertIntersectCandidate, PxU32 vert0, PxU32 vert1, PxU32& secondEdgeVert)
 {
    {
        const PxVec3 edge0 = tri[vertIntersectCandidate] - tri[vert0];
@@ -116,15 +116,26 @@ static PX_FORCE_INLINE bool edgeOrVertexTest(const PxVec3& planeIntersectPoint,
    return true;
 }

-static PX_FORCE_INLINE bool testRayVsSphereOrCapsule(PxReal& impactDistance, bool testSphere, const PxVec3& center, PxReal radius, const PxVec3& dir, const PxVec3* PX_RESTRICT verts, PxU32 e0, PxU32 e1)
+static PX_FORCE_INLINE bool testRayVsOneOrTwoCapsule(PxReal& impactDistance, bool testBothEdge, const PxVec3& center, PxReal radius, const PxVec3& dir, const PxVec3* PX_RESTRICT verts, PxU32 e0, PxU32 e1)
 {
-   if(testSphere)
+   if(testBothEdge)
    {
        PxReal t;
-       if(intersectRaySphere(center, dir, PX_MAX_F32, verts[e0], radius, t))
+       if (intersectRayCapsule(center, dir, verts[e0], verts[(e0+1) % 3], radius, t))
        {
-           impactDistance = t;
-           return true;
+           if (t >= 0.0f/* && t<MinDist*/)
+           {
+               impactDistance = t;
+               return true;
+           }
+       }
+       else if (intersectRayCapsule(center, dir, verts[e0], verts[(e0 + 2) % 3], radius, t))
+       {
+           if (t >= 0.0f/* && t<MinDist*/)
+           {
+               impactDistance = t;
+               return true;
+           }
        }
    }
    else
@@ -214,7 +225,7 @@ bool Gu::sweepSphereVSTri(const PxVec3* PX_RESTRICT triVerts, const PxVec3& norm
    // switches to edge tests if necessary.
    //

-   bool TestSphere;
+   bool TestBothEdge;
    PxU32 e0,e1;
    if(u<0.0f)
    {
@@ -223,19 +234,19 @@ bool Gu::sweepSphereVSTri(const PxVec3* PX_RESTRICT triVerts, const PxVec3& norm
            // 0 or 0-1 or 0-2
            e0 = 0;
            const PxVec3 intersectPoint = INTERSECT_POINT;
-           TestSphere = edgeOrVertexTest(intersectPoint, triVerts, 0, 1, 2, e1);
+           TestBothEdge = oneOrTwoEdgeTest(intersectPoint, triVerts, 0, 1, 2, e1);
        }
        else if(u+v>1.0f)
        {
            // 2 or 2-0 or 2-1
            e0 = 2;
            const PxVec3 intersectPoint = INTERSECT_POINT;
-           TestSphere = edgeOrVertexTest(intersectPoint, triVerts, 2, 0, 1, e1);
+           TestBothEdge = oneOrTwoEdgeTest(intersectPoint, triVerts, 2, 0, 1, e1);
        }
        else
        {
            // 0-2
-           TestSphere = false;
+           TestBothEdge = false;
            e0 = 0;
            e1 = 2;
        }
@@ -249,12 +260,12 @@ bool Gu::sweepSphereVSTri(const PxVec3* PX_RESTRICT triVerts, const PxVec3& norm
                // 1 or 1-0 or 1-2
                e0 = 1;
                const PxVec3 intersectPoint = INTERSECT_POINT;
-               TestSphere = edgeOrVertexTest(intersectPoint, triVerts, 1, 0, 2, e1);
+               TestBothEdge = oneOrTwoEdgeTest(intersectPoint, triVerts, 1, 0, 2, e1);
            }
            else
            {
                // 0-1
-               TestSphere = false;
+               TestBothEdge = false;
                e0 = 0;
                e1 = 1;
            }
@@ -263,12 +274,12 @@ bool Gu::sweepSphereVSTri(const PxVec3* PX_RESTRICT triVerts, const PxVec3& norm
        {
            PX_ASSERT(u+v>=1.0f);   // Else hit triangle
            // 1-2
-           TestSphere = false;
+           TestBothEdge = false;
            e0 = 1;
            e1 = 2;
        }
    }
-   return testRayVsSphereOrCapsule(impactDistance, TestSphere, center, radius, dir, triVerts, e0, e1);
+   return testRayVsOneOrTwoCapsule(impactDistance, TestBothEdge, center, radius, dir, triVerts, e0, e1);
 }

 bool Gu::sweepSphereTriangles( PxU32 nbTris, const PxTriangle* PX_RESTRICT triangles,                          // Triangle data
@@ -451,7 +462,7 @@ bool Gu::sweepSphereVSQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& no
    #define INTERSECT_POINT_Q (quadVerts[1]*u) + (quadVerts[2]*v) + (quadVerts[0] * (1.0f-u-v))

    Ps::swap(u,v);
-   bool TestSphere;
+   bool TestBothEdge;
    PxU32 e0,e1;
    if(u<0.0f)
    {
@@ -460,19 +471,19 @@ bool Gu::sweepSphereVSQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& no
            // 0 or 0-1 or 0-2
            e0 = 0;
            const PxVec3 intersectPoint = INTERSECT_POINT_Q;
-           TestSphere = edgeOrVertexTest(intersectPoint, quadVerts, 0, 1, 2, e1);
+           TestBothEdge = oneOrTwoEdgeTest(intersectPoint, quadVerts, 0, 1, 2, e1);
        }
        else if(v>1.0f)
        {
            // 1 or 1-0 or 1-3
            e0 = 1;
            const PxVec3 intersectPoint = INTERSECT_POINT_Q;
-           TestSphere = edgeOrVertexTest(intersectPoint, quadVerts, 1, 0, 3, e1);
+           TestBothEdge = oneOrTwoEdgeTest(intersectPoint, quadVerts, 1, 0, 3, e1);
        }
        else
        {
            // 0-1
-           TestSphere = false;
+           TestBothEdge = false;
            e0 = 0;
            e1 = 1;
        }
@@ -484,19 +495,19 @@ bool Gu::sweepSphereVSQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& no
            // 2 or 2-0 or 2-3
            e0 = 2;
            const PxVec3 intersectPoint = INTERSECT_POINT_Q;
-           TestSphere = edgeOrVertexTest(intersectPoint, quadVerts, 2, 0, 3, e1);
+           TestBothEdge = oneOrTwoEdgeTest(intersectPoint, quadVerts, 2, 0, 3, e1);
        }
        else if(v>1.0f)
        {
            // 3 or 3-1 or 3-2
            e0 = 3;
            const PxVec3 intersectPoint = INTERSECT_POINT_Q;
-           TestSphere = edgeOrVertexTest(intersectPoint, quadVerts, 3, 1, 2, e1);
+           TestBothEdge = oneOrTwoEdgeTest(intersectPoint, quadVerts, 3, 1, 2, e1);
        }
        else
        {
            // 2-3
-           TestSphere = false;
+           TestBothEdge = false;
            e0 = 2;
            e1 = 3;
        }
@@ -506,7 +517,7 @@ bool Gu::sweepSphereVSQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& no
        if(v<0.0f)
        {
            // 0-2
-           TestSphere = false;
+           TestBothEdge = false;
            e0 = 0;
            e1 = 2;
        }
@@ -514,11 +525,11 @@ bool Gu::sweepSphereVSQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& no
        {
            PX_ASSERT(v>=1.0f); // Else hit quad
            // 1-3
-           TestSphere = false;
+           TestBothEdge = false;
            e0 = 1;
            e1 = 3;
        }
    }
-   return testRayVsSphereOrCapsule(impactDistance, TestSphere, center, radius, dir, quadVerts, e0, e1);
+   return testRayVsOneOrTwoCapsule(impactDistance, TestBothEdge, center, radius, dir, quadVerts, e0, e1);
 }
Pierre-Terdiman commented 1 year ago

Thank you, yes, I think this is a duplicate of https://github.com/NVIDIAGameWorks/PhysX/issues/501

bleston commented 1 year ago

Thank you, yes, I think this is a duplicate of #501

Thanks