Found bug in Gu::sweepSphereVSTri

[bleston]

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]

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

[bleston]

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

Thanks