aboutsummaryrefslogtreecommitdiff
path: root/PhysX_3.4/Source/GeomUtils/src/sweep
diff options
context:
space:
mode:
authorgit perforce import user <a@b>2016-10-25 12:29:14 -0600
committerSheikh Dawood Abdul Ajees <Sheikh Dawood Abdul Ajees>2016-10-25 18:56:37 -0500
commit3dfe2108cfab31ba3ee5527e217d0d8e99a51162 (patch)
treefa6485c169e50d7415a651bf838f5bcd0fd3bfbd /PhysX_3.4/Source/GeomUtils/src/sweep
downloadphysx-3.4-3dfe2108cfab31ba3ee5527e217d0d8e99a51162.tar.xz
physx-3.4-3dfe2108cfab31ba3ee5527e217d0d8e99a51162.zip
Initial commit:
PhysX 3.4.0 Update @ 21294896 APEX 1.4.0 Update @ 21275617 [CL 21300167]
Diffstat (limited to 'PhysX_3.4/Source/GeomUtils/src/sweep')
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.cpp272
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.h49
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.cpp158
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.h49
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.cpp622
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.h67
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.cpp39
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.h235
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.cpp215
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.h49
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.cpp344
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.h48
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.cpp328
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.h75
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.cpp103
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.h50
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.cpp116
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.h46
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.cpp521
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.h156
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.cpp223
-rw-r--r--PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.h338
22 files changed, 4103 insertions, 0 deletions
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.cpp
new file mode 100644
index 00000000..86b8100a
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.cpp
@@ -0,0 +1,272 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepBoxBox.h"
+#include "GuBox.h"
+#include "GuIntersectionBoxBox.h"
+#include "GuIntersectionRayBox.h"
+#include "GuIntersectionEdgeEdge.h"
+#include "GuSweepSharedTests.h"
+#include "CmMatrix34.h"
+#include "GuSweepTriangleUtils.h"
+#include "GuInternal.h"
+
+using namespace physx;
+using namespace Gu;
+using namespace Cm;
+
+namespace
+{
+// PT: TODO: get rid of this copy
+static const PxReal gFatBoxEdgeCoeff = 0.01f;
+
+// PT: TODO: get rid of this copy
+static const PxVec3 gNearPlaneNormal[] =
+{
+ PxVec3(1.0f, 0.0f, 0.0f),
+ PxVec3(0.0f, 1.0f, 0.0f),
+ PxVec3(0.0f, 0.0f, 1.0f),
+ PxVec3(-1.0f, 0.0f, 0.0f),
+ PxVec3(0.0f, -1.0f, 0.0f),
+ PxVec3(0.0f, 0.0f, -1.0f)
+};
+
+#define INVSQRT2 0.707106781188f //!< 1 / sqrt(2)
+
+static PxVec3 EdgeNormals[] =
+{
+ PxVec3(0, -INVSQRT2, -INVSQRT2), // 0-1
+ PxVec3(INVSQRT2, 0, -INVSQRT2), // 1-2
+ PxVec3(0, INVSQRT2, -INVSQRT2), // 2-3
+ PxVec3(-INVSQRT2, 0, -INVSQRT2), // 3-0
+
+ PxVec3(0, INVSQRT2, INVSQRT2), // 7-6
+ PxVec3(INVSQRT2, 0, INVSQRT2), // 6-5
+ PxVec3(0, -INVSQRT2, INVSQRT2), // 5-4
+ PxVec3(-INVSQRT2, 0, INVSQRT2), // 4-7
+
+ PxVec3(INVSQRT2, -INVSQRT2, 0), // 1-5
+ PxVec3(INVSQRT2, INVSQRT2, 0), // 6-2
+ PxVec3(-INVSQRT2, INVSQRT2, 0), // 3-7
+ PxVec3(-INVSQRT2, -INVSQRT2, 0) // 4-0
+};
+
+// PT: TODO: get rid of this copy
+static const PxVec3* getBoxLocalEdgeNormals()
+{
+ return EdgeNormals;
+}
+
+/**
+Returns world edge normal
+\param edgeIndex [in] 0 <= edge index < 12
+\param worldNormal [out] edge normal in world space
+*/
+static void computeBoxWorldEdgeNormal(const Box& box, PxU32 edgeIndex, PxVec3& worldNormal)
+{
+ PX_ASSERT(edgeIndex<12);
+ worldNormal = box.rotate(getBoxLocalEdgeNormals()[edgeIndex]);
+}
+
+}
+
+// ### optimize! and refactor. And optimize for aabbs
+bool Gu::sweepBoxBox(const Box& box0, const Box& box1, const PxVec3& dir, PxReal length, PxHitFlags hitFlags, PxSweepHit& sweepHit)
+{
+ if(!(hitFlags & PxHitFlag::eASSUME_NO_INITIAL_OVERLAP))
+ {
+ // PT: test if shapes initially overlap
+ if(intersectOBBOBB(box0.extents, box0.center, box0.rot, box1.extents, box1.center, box1.rot, true))
+ {
+ sweepHit.flags = PxHitFlag::eDISTANCE|PxHitFlag::eNORMAL;
+ sweepHit.distance = 0.0f;
+ sweepHit.normal = -dir;
+ return true;
+ }
+ }
+
+ PxVec3 boxVertices0[8]; box0.computeBoxPoints(boxVertices0);
+ PxVec3 boxVertices1[8]; box1.computeBoxPoints(boxVertices1);
+
+ // float MinDist = PX_MAX_F32;
+ PxReal MinDist = length;
+ int col = -1;
+
+ // In following VF tests:
+ // - the direction is FW/BK since we project one box onto the other *and vice versa*
+ // - the normal reaction is FW/BK for the same reason
+
+ // Vertices1 against Box0
+ {
+ // We need:
+
+ // - Box0 in local space
+ const PxVec3 Min0 = -box0.extents;
+ const PxVec3 Max0 = box0.extents;
+
+ // - Vertices1 in Box0 space
+ Matrix34 worldToBox0;
+ computeWorldToBoxMatrix(worldToBox0, box0);
+
+ // - the dir in Box0 space
+ const PxVec3 localDir0 = worldToBox0.rotate(dir);
+
+ const PxVec3* boxNormals0 = gNearPlaneNormal;
+
+ for(PxU32 i=0; i<8; i++)
+ {
+ PxReal tnear, tfar;
+ const int plane = intersectRayAABB(Min0, Max0, worldToBox0.transform(boxVertices1[i]), -localDir0, tnear, tfar);
+
+ if(plane==-1 || tnear<0.0f)
+ continue;
+
+ if(tnear <= MinDist)
+ {
+ MinDist = tnear;
+ sweepHit.normal = box0.rotate(boxNormals0[plane]);
+ sweepHit.position = boxVertices1[i];
+ col = 0;
+ }
+ }
+ }
+
+ // Vertices0 against Box1
+ {
+ // We need:
+
+ // - Box1 in local space
+ const PxVec3 Min1 = -box1.extents;
+ const PxVec3 Max1 = box1.extents;
+
+ // - Vertices0 in Box1 space
+ Matrix34 worldToBox1;
+ computeWorldToBoxMatrix(worldToBox1, box1);
+
+ // - the dir in Box1 space
+ const PxVec3 localDir1 = worldToBox1.rotate(dir);
+
+ const PxVec3* boxNormals1 = gNearPlaneNormal;
+
+ for(PxU32 i=0; i<8; i++)
+ {
+ PxReal tnear, tfar;
+ const int plane = intersectRayAABB(Min1, Max1, worldToBox1.transform(boxVertices0[i]), localDir1, tnear, tfar);
+
+ if(plane==-1 || tnear<0.0f)
+ continue;
+
+ if(tnear <= MinDist)
+ {
+ MinDist = tnear;
+ sweepHit.normal = box1.rotate(-boxNormals1[plane]);
+ sweepHit.position = boxVertices0[i] + tnear * dir;
+ col = 1;
+ }
+ }
+ }
+
+ PxVec3 p1s, p2s, p3s, p4s;
+ {
+ const PxU8* PX_RESTRICT edges0 = getBoxEdges();
+ const PxU8* PX_RESTRICT edges1 = getBoxEdges();
+
+ PxVec3 edgeNormals0[12];
+ PxVec3 edgeNormals1[12];
+ for(PxU32 i=0; i<12; i++)
+ computeBoxWorldEdgeNormal(box0, i, edgeNormals0[i]);
+ for(PxU32 i=0; i<12; i++)
+ computeBoxWorldEdgeNormal(box1, i, edgeNormals1[i]);
+
+ // Loop through box edges
+ for(PxU32 i=0; i<12; i++) // 12 edges
+ {
+ if(!(edgeNormals0[i].dot(dir) >= 0.0f))
+ continue;
+
+ // Catch current box edge // ### one vertex already known using line-strips
+
+ // Make it fat ###
+ PxVec3 p1 = boxVertices0[edges0[i*2+0]];
+ PxVec3 p2 = boxVertices0[edges0[i*2+1]];
+ Ps::makeFatEdge(p1, p2, gFatBoxEdgeCoeff);
+
+ // Loop through box edges
+ for(PxU32 j=0;j<12;j++)
+ {
+ if(edgeNormals1[j].dot(dir) >= 0.0f)
+ continue;
+
+ // Orientation culling
+ // PT: this was commented for some reason, but it fixes the "stuck" bug reported by Ubi.
+ // So I put it back. We'll have to see whether it produces Bad Things in particular cases.
+ if(edgeNormals0[i].dot(edgeNormals1[j]) >= 0.0f)
+ continue;
+
+ // Catch current box edge
+
+ // Make it fat ###
+ PxVec3 p3 = boxVertices1[edges1[j*2+0]];
+ PxVec3 p4 = boxVertices1[edges1[j*2+1]];
+ Ps::makeFatEdge(p3, p4, gFatBoxEdgeCoeff);
+
+ PxReal Dist;
+ PxVec3 ip;
+ if(intersectEdgeEdge(p1, p2, dir, p3, p4, Dist, ip))
+ {
+ if(Dist<=MinDist)
+ {
+ p1s = p1;
+ p2s = p2;
+ p3s = p3;
+ p4s = p4;
+
+ sweepHit.position = ip + Dist * dir;
+
+ col = 2;
+ MinDist = Dist;
+ }
+ }
+ }
+ }
+ }
+
+ if(col==-1)
+ return false;
+
+ if(col==2)
+ {
+ computeEdgeEdgeNormal(sweepHit.normal, p1s, p2s-p1s, p3s, p4s-p3s, dir, MinDist);
+ sweepHit.normal.normalize();
+ }
+
+ sweepHit.flags = PxHitFlag::eDISTANCE|PxHitFlag::eNORMAL|PxHitFlag::ePOSITION;
+ sweepHit.distance = MinDist;
+ return true;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.h
new file mode 100644
index 00000000..a5a36016
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxBox.h
@@ -0,0 +1,49 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_BOX_BOX_H
+#define GU_SWEEP_BOX_BOX_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+#include "PxQueryReport.h"
+
+namespace physx
+{
+namespace Gu
+{
+ class Box;
+
+ bool sweepBoxBox(const Box& box0, const Box& box1, const PxVec3& dir, PxReal length, PxHitFlags hitFlags, PxSweepHit& sweepHit);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.cpp
new file mode 100644
index 00000000..408dedad
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.cpp
@@ -0,0 +1,158 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepBoxSphere.h"
+#include "GuOverlapTests.h"
+#include "GuSphere.h"
+#include "GuBoxConversion.h"
+#include "GuCapsule.h"
+#include "GuIntersectionRayCapsule.h"
+#include "GuIntersectionRayBox.h"
+#include "GuIntersectionSphereBox.h"
+#include "GuDistancePointSegment.h"
+#include "GuInternal.h"
+
+using namespace physx;
+using namespace Gu;
+using namespace Cm;
+
+namespace
+{
+// PT: TODO: get rid of this copy
+static const PxVec3 gNearPlaneNormal[] =
+{
+ PxVec3(1.0f, 0.0f, 0.0f),
+ PxVec3(0.0f, 1.0f, 0.0f),
+ PxVec3(0.0f, 0.0f, 1.0f),
+ PxVec3(-1.0f, 0.0f, 0.0f),
+ PxVec3(0.0f, -1.0f, 0.0f),
+ PxVec3(0.0f, 0.0f, -1.0f)
+};
+
+}
+
+bool Gu::sweepBoxSphere(const Box& box, PxReal sphereRadius, const PxVec3& spherePos, const PxVec3& dir, PxReal length, PxReal& min_dist, PxVec3& normal, PxHitFlags hitFlags)
+{
+ if(!(hitFlags & PxHitFlag::eASSUME_NO_INITIAL_OVERLAP))
+ {
+ // PT: test if shapes initially overlap
+ if(intersectSphereBox(Sphere(spherePos, sphereRadius), box))
+ {
+ // Overlap
+ min_dist = 0.0f;
+ normal = -dir;
+ return true;
+ }
+ }
+
+ PxVec3 boxPts[8];
+ box.computeBoxPoints(boxPts);
+ const PxU8* PX_RESTRICT edges = getBoxEdges();
+ PxReal MinDist = length;
+ bool Status = false;
+ for(PxU32 i=0; i<12; i++)
+ {
+ const PxU8 e0 = *edges++;
+ const PxU8 e1 = *edges++;
+ const Capsule capsule(boxPts[e0], boxPts[e1], sphereRadius);
+
+ PxReal t;
+ if(intersectRayCapsule(spherePos, dir, capsule, t))
+ {
+ if(t>=0.0f && t<=MinDist)
+ {
+ MinDist = t;
+
+ const PxVec3 ip = spherePos + t*dir;
+ distancePointSegmentSquared(capsule, ip, &t);
+
+ PxVec3 ip2;
+ capsule.computePoint(ip2, t);
+
+ normal = (ip2 - ip);
+ normal.normalize();
+ Status = true;
+ }
+ }
+ }
+
+ PxVec3 localPt;
+ {
+ Matrix34 M2;
+ buildMatrixFromBox(M2, box);
+
+ localPt = M2.rotateTranspose(spherePos - M2.p);
+ }
+
+ const PxVec3* boxNormals = gNearPlaneNormal;
+
+ const PxVec3 localDir = box.rotateInv(dir);
+
+ // PT: when the box exactly touches the sphere, the test for initial overlap can fail on some platforms.
+ // In this case we reach the sweep code below, which may return a slightly negative time of impact (it should be 0.0
+ // but it ends up a bit negative because of limited FPU accuracy). The epsilon ensures that we correctly detect a hit
+ // in this case.
+ const PxReal epsilon = -1e-5f;
+
+ PxReal tnear, tfar;
+
+ PxVec3 extents = box.extents;
+ extents.x += sphereRadius;
+ int plane = intersectRayAABB(-extents, extents, localPt, localDir, tnear, tfar);
+ if(plane!=-1 && tnear>=epsilon && tnear <= MinDist)
+ {
+ MinDist = PxMax(tnear, 0.0f);
+ normal = box.rotate(boxNormals[plane]);
+ Status = true;
+ }
+
+ extents = box.extents;
+ extents.y += sphereRadius;
+ plane = intersectRayAABB(-extents, extents, localPt, localDir, tnear, tfar);
+ if(plane!=-1 && tnear>=epsilon && tnear <= MinDist)
+ {
+ MinDist = PxMax(tnear, 0.0f);
+ normal = box.rotate(boxNormals[plane]);
+ Status = true;
+ }
+
+ extents = box.extents;
+ extents.z += sphereRadius;
+ plane = intersectRayAABB(-extents, extents, localPt, localDir, tnear, tfar);
+ if(plane!=-1 && tnear>=epsilon && tnear <= MinDist)
+ {
+ MinDist = PxMax(tnear, 0.0f);
+ normal = box.rotate(boxNormals[plane]);
+ Status = true;
+ }
+
+ min_dist = MinDist;
+
+ return Status;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.h
new file mode 100644
index 00000000..1fd163b9
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxSphere.h
@@ -0,0 +1,49 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_BOX_SPHERE_H
+#define GU_SWEEP_BOX_SPHERE_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+#include "PxQueryReport.h"
+
+namespace physx
+{
+namespace Gu
+{
+ class Box;
+
+ bool sweepBoxSphere(const Box& box, PxReal sphereRadius, const PxVec3& spherePos, const PxVec3& dir, PxReal length, PxReal& min_dist, PxVec3& normal, PxHitFlags hitFlags);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.cpp
new file mode 100644
index 00000000..3e13f785
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.cpp
@@ -0,0 +1,622 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "foundation/PxBounds3.h"
+#include "GuSweepBoxTriangle_FeatureBased.h"
+#include "GuIntersectionRayBox.h"
+#include "PxTriangle.h"
+#include "GuSweepTriangleUtils.h"
+#include "GuInternal.h"
+
+using namespace physx;
+using namespace Gu;
+
+#define LOCAL_EPSILON 0.00001f // PT: this value makes the 'basicAngleTest' pass. Fails because of a ray almost parallel to a triangle
+
+namespace
+{
+static const PxReal gFatTriangleCoeff = 0.02f;
+
+static const PxVec3 gNearPlaneNormal[] =
+{
+ PxVec3(1.0f, 0.0f, 0.0f),
+ PxVec3(0.0f, 1.0f, 0.0f),
+ PxVec3(0.0f, 0.0f, 1.0f),
+ PxVec3(-1.0f, 0.0f, 0.0f),
+ PxVec3(0.0f, -1.0f, 0.0f),
+ PxVec3(0.0f, 0.0f, -1.0f)
+};
+}
+
+#define INVSQRT3 0.577350269189f //!< 1 / sqrt(3)
+
+/**
+Returns vertex normals.
+\return 24 floats (8 normals)
+*/
+static const PxF32* getBoxVertexNormals()
+{
+ // 7+------+6 0 = ---
+ // /| /| 1 = +--
+ // / | / | 2 = ++-
+ // / 4+---/--+5 3 = -+-
+ // 3+------+2 / y z 4 = --+
+ // | / | / | / 5 = +-+
+ // |/ |/ |/ 6 = +++
+ // 0+------+1 *---x 7 = -++
+
+ static PxF32 VertexNormals[] =
+ {
+ -INVSQRT3, -INVSQRT3, -INVSQRT3,
+ INVSQRT3, -INVSQRT3, -INVSQRT3,
+ INVSQRT3, INVSQRT3, -INVSQRT3,
+ -INVSQRT3, INVSQRT3, -INVSQRT3,
+ -INVSQRT3, -INVSQRT3, INVSQRT3,
+ INVSQRT3, -INVSQRT3, INVSQRT3,
+ INVSQRT3, INVSQRT3, INVSQRT3,
+ -INVSQRT3, INVSQRT3, INVSQRT3
+ };
+
+ return VertexNormals;
+}
+
+static PxTriangle inflateTriangle(const PxTriangle& triangle, PxReal fat_coeff)
+{
+ PxTriangle fatTri = triangle;
+
+ // Compute triangle center
+ const PxVec3& p0 = triangle.verts[0];
+ const PxVec3& p1 = triangle.verts[1];
+ const PxVec3& p2 = triangle.verts[2];
+ const PxVec3 center = (p0 + p1 + p2)*0.333333333f;
+
+ // Don't normalize?
+ // Normalize => add a constant border, regardless of triangle size
+ // Don't => add more to big triangles
+ for(PxU32 i=0;i<3;i++)
+ {
+ const PxVec3 v = fatTri.verts[i] - center;
+ fatTri.verts[i] += v * fat_coeff;
+ }
+ return fatTri;
+}
+
+// PT: special version to fire N parallel rays against the same tri
+static PX_FORCE_INLINE Ps::IntBool rayTriPrecaCull( const PxVec3& orig, const PxVec3& dir,
+ const PxVec3& vert0, const PxVec3& edge1, const PxVec3& edge2, const PxVec3& pvec,
+ PxReal det, PxReal oneOverDet, PxReal& t)
+{
+ // Calculate distance from vert0 to ray origin
+ const PxVec3 tvec = orig - vert0;
+
+ // Calculate U parameter and test bounds
+ PxReal u = tvec.dot(pvec);
+ if((u < 0.0f) || u>det)
+ return 0;
+
+ // Prepare to test V parameter
+ const PxVec3 qvec = tvec.cross(edge1);
+
+ // Calculate V parameter and test bounds
+ PxReal v = dir.dot(qvec);
+ if((v < 0.0f) || u+v>det)
+ return 0;
+
+ // Calculate t, scale parameters, ray intersects triangle
+ t = edge2.dot(qvec);
+ t *= oneOverDet;
+ return 1;
+}
+
+static PX_FORCE_INLINE Ps::IntBool rayTriPrecaNoCull( const PxVec3& orig, const PxVec3& dir,
+ const PxVec3& vert0, const PxVec3& edge1, const PxVec3& edge2, const PxVec3& pvec,
+ PxReal /*det*/, PxReal oneOverDet, PxReal& t)
+{
+ // Calculate distance from vert0 to ray origin
+ const PxVec3 tvec = orig - vert0;
+
+ // Calculate U parameter and test bounds
+ PxReal u = (tvec.dot(pvec)) * oneOverDet;
+ if((u < 0.0f) || u>1.0f)
+ return 0;
+
+ // prepare to test V parameter
+ const PxVec3 qvec = tvec.cross(edge1);
+
+ // Calculate V parameter and test bounds
+ PxReal v = (dir.dot(qvec)) * oneOverDet;
+ if((v < 0.0f) || u+v>1.0f)
+ return 0;
+
+ // Calculate t, ray intersects triangle
+ t = (edge2.dot(qvec)) * oneOverDet;
+ return 1;
+}
+
+// PT: specialized version where oneOverDir is available
+// PT: why did we change the initial epsilon value?
+#define LOCAL_EPSILON_RAY_BOX PX_EPS_F32
+//#define LOCAL_EPSILON_RAY_BOX 0.0001f
+static PX_FORCE_INLINE int intersectRayAABB2(const PxVec3& minimum, const PxVec3& maximum,
+ const PxVec3& ro, const PxVec3& /*rd*/, const PxVec3& oneOverDir,
+ float& tnear, float& tfar,
+ bool fbx, bool fby, bool fbz)
+{
+ // PT: this unrolled loop is a lot faster on Xbox
+
+ if(fbx)
+ if(ro.x<minimum.x || ro.x>maximum.x)
+ {
+// tnear = FLT_MAX;
+ return -1;
+ }
+ if(fby)
+ if(ro.y<minimum.y || ro.y>maximum.y)
+ {
+// tnear = FLT_MAX;
+ return -1;
+ }
+ if(fbz)
+ if(ro.z<minimum.z || ro.z>maximum.z)
+ {
+// tnear = FLT_MAX;
+ return -1;
+ }
+
+ PxReal t1x = (minimum.x - ro.x) * oneOverDir.x;
+ PxReal t2x = (maximum.x - ro.x) * oneOverDir.x;
+ PxReal t1y = (minimum.y - ro.y) * oneOverDir.y;
+ PxReal t2y = (maximum.y - ro.y) * oneOverDir.y;
+ PxReal t1z = (minimum.z - ro.z) * oneOverDir.z;
+ PxReal t2z = (maximum.z - ro.z) * oneOverDir.z;
+
+ int bx;
+ int by;
+ int bz;
+
+ if(t1x>t2x)
+ {
+ PxReal t=t1x; t1x=t2x; t2x=t;
+ bx = 3;
+ }
+ else
+ {
+ bx = 0;
+ }
+
+ if(t1y>t2y)
+ {
+ PxReal t=t1y; t1y=t2y; t2y=t;
+ by = 4;
+ }
+ else
+ {
+ by = 1;
+ }
+
+ if(t1z>t2z)
+ {
+ PxReal t=t1z; t1z=t2z; t2z=t;
+ bz = 5;
+ }
+ else
+ {
+ bz = 2;
+ }
+
+ int ret;
+ if(!fbx)
+ {
+// if(t1x>tnear) // PT: no need to test for the first value
+ {
+ tnear = t1x;
+ ret = bx;
+ }
+// tfar = Px::intrinsics::selectMin(tfar, t2x);
+ tfar = t2x; // PT: no need to test for the first value
+ }
+ else
+ {
+ ret=-1;
+ tnear = -PX_MAX_F32;
+ tfar = PX_MAX_F32;
+ }
+
+ if(!fby)
+ {
+ if(t1y>tnear)
+ {
+ tnear = t1y;
+ ret = by;
+ }
+ tfar = physx::intrinsics::selectMin(tfar, t2y);
+ }
+
+ if(!fbz)
+ {
+ if(t1z>tnear)
+ {
+ tnear = t1z;
+ ret = bz;
+ }
+ tfar = physx::intrinsics::selectMin(tfar, t2z);
+ }
+
+ if(tnear>tfar || tfar<LOCAL_EPSILON_RAY_BOX)
+ return -1;
+
+ return ret;
+}
+
+// PT: force-inlining this saved 500.000 cycles in the benchmark. Ok to inline, only used once anyway.
+static PX_FORCE_INLINE bool intersectEdgeEdge3(const PxPlane& plane, const PxVec3& p1, const PxVec3& p2, const PxVec3& dir, const PxVec3& v1,
+ const PxVec3& p3, const PxVec3& p4,
+ PxReal& dist, PxVec3& ip, PxU32 i, PxU32 j, const PxReal coeff)
+{
+ // if colliding edge (p3,p4) does not cross plane return no collision
+ // same as if p3 and p4 on same side of plane return 0
+ //
+ // Derivation:
+ // d3 = d(p3, P) = (p3 | plane.n) - plane.d; Reversed sign compared to Plane::Distance() because plane.d is negated.
+ // d4 = d(p4, P) = (p4 | plane.n) - plane.d; Reversed sign compared to Plane::Distance() because plane.d is negated.
+ // if d3 and d4 have the same sign, they're on the same side of the plane => no collision
+ // We test both sides at the same time by only testing Sign(d3 * d4).
+ // ### put that in the Plane class
+ // ### also check that code in the triangle class that might be similar
+ const PxReal d3 = plane.distance(p3);
+
+ const PxReal temp = d3 * plane.distance(p4);
+ if(temp>0.0f) return false;
+
+ // if colliding edge (p3,p4) and plane are parallel return no collision
+ const PxVec3 v2 = p4 - p3;
+
+ const PxReal temp2 = plane.n.dot(v2);
+ if(temp2==0.0f) return false; // ### epsilon would be better
+
+ // compute intersection point of plane and colliding edge (p3,p4)
+ ip = p3-v2*(d3/temp2);
+
+ // compute distance of intersection from line (ip, -dir) to line (p1,p2)
+ dist = (v1[i]*(ip[j]-p1[j])-v1[j]*(ip[i]-p1[i])) * coeff;
+ if(dist<0.0f) return false;
+
+ // compute intersection point on edge (p1,p2) line
+ ip -= dist*dir;
+
+ // check if intersection point (ip) is between edge (p1,p2) vertices
+ const PxReal temp3 = (p1.x-ip.x)*(p2.x-ip.x)+(p1.y-ip.y)*(p2.y-ip.y)+(p1.z-ip.z)*(p2.z-ip.z);
+ return temp3<0.0f;
+}
+
+namespace
+{
+static const PxReal gFatBoxEdgeCoeff = 0.01f;
+#define INVSQRT2 0.707106781188f //!< 1 / sqrt(2)
+
+static const PxVec3 EdgeNormals[] =
+{
+ PxVec3(0, -INVSQRT2, -INVSQRT2), // 0-1
+ PxVec3(INVSQRT2, 0, -INVSQRT2), // 1-2
+ PxVec3(0, INVSQRT2, -INVSQRT2), // 2-3
+ PxVec3(-INVSQRT2, 0, -INVSQRT2), // 3-0
+
+ PxVec3(0, INVSQRT2, INVSQRT2), // 7-6
+ PxVec3(INVSQRT2, 0, INVSQRT2), // 6-5
+ PxVec3(0, -INVSQRT2, INVSQRT2), // 5-4
+ PxVec3(-INVSQRT2, 0, INVSQRT2), // 4-7
+
+ PxVec3(INVSQRT2, -INVSQRT2, 0), // 1-5
+ PxVec3(INVSQRT2, INVSQRT2, 0), // 6-2
+ PxVec3(-INVSQRT2, INVSQRT2, 0), // 3-7
+ PxVec3(-INVSQRT2, -INVSQRT2, 0) // 4-0
+};
+
+static const PxVec3* getBoxLocalEdgeNormals()
+{
+ return EdgeNormals;
+}
+}
+
+static PX_FORCE_INLINE void closestAxis2(const PxVec3& v, PxU32& j, PxU32& k)
+{
+ // find largest 2D plane projection
+ const PxF32 absPx = physx::intrinsics::abs(v.x);
+ const PxF32 absPy = physx::intrinsics::abs(v.y);
+ const PxF32 absPz = physx::intrinsics::abs(v.z);
+ //PxU32 m = 0; //x biggest axis
+ j = 1;
+ k = 2;
+ if( absPy > absPx && absPy > absPz)
+ {
+ //y biggest
+ j = 2;
+ k = 0;
+ //m = 1;
+ }
+ else if(absPz > absPx)
+ {
+ //z biggest
+ j = 0;
+ k = 1;
+ //m = 2;
+ }
+// return m;
+}
+
+bool Gu::sweepBoxTriangle( const PxTriangle& tri, const PxBounds3& box,
+ const PxVec3& motion, const PxVec3& oneOverMotion,
+ PxVec3& hit, PxVec3& normal, PxReal& d, bool isDoubleSided)
+{
+ // Create triangle normal
+ PxVec3 denormalizedTriNormal;
+ tri.denormalizedNormal(denormalizedTriNormal);
+
+ // Backface culling
+ const bool doBackfaceCulling = !isDoubleSided;
+ if(doBackfaceCulling && (denormalizedTriNormal.dot(motion)) >= 0.0f) // ">=" is important !
+ return false;
+
+ /////////////////////////
+
+ PxVec3 boxVertices[8];
+ computeBoxPoints(box, boxVertices);
+
+ /////////////////////////
+
+ // Make fat triangle
+ const PxTriangle fatTri = inflateTriangle(tri, gFatTriangleCoeff);
+
+ PxReal minDist = d; // Initialize with current best distance
+ int col = -1;
+
+ // Box vertices VS triangle
+ {
+ // ### cull using box-plane distance ?
+ const PxVec3 edge1 = fatTri.verts[1] - fatTri.verts[0];
+ const PxVec3 edge2 = fatTri.verts[2] - fatTri.verts[0];
+ const PxVec3 PVec = motion.cross(edge2);
+ const PxReal Det = edge1.dot(PVec);
+
+ // We can't use stamps here since we can still find a better TOI for a given vertex,
+ // even if that vertex has already been tested successfully against another triangle.
+ const PxVec3* VN = reinterpret_cast<const PxVec3*>(getBoxVertexNormals());
+
+ const PxReal oneOverDet = Det!=0.0f ? 1.0f / Det : 0.0f;
+
+ PxU32 hitIndex=0;
+ if(doBackfaceCulling)
+ {
+ if(Det>=LOCAL_EPSILON)
+ {
+ for(PxU32 i=0;i<8;i++)
+ {
+ // Orientation culling
+ if((VN[i].dot(denormalizedTriNormal) >= 0.0f)) // Can't rely on triangle normal for double-sided faces
+ continue;
+
+ // ### test this
+ // ### ok, this causes the bug in level3's v-shaped desk. Not really a real "bug", it just happens
+ // that this VF test fixes this case, so it's a bad idea to cull it. Oh, well.
+ // If we use a penetration-depth code to fixup bad cases, we can enable this culling again. (also
+ // if we find a better way to handle that desk)
+ // Discard back vertices
+// if(VN[i].dot(motion)<0.0f)
+// continue;
+
+ // Shoot a ray from vertex against triangle, in direction "motion"
+ PxReal t;
+ if(!rayTriPrecaCull(boxVertices[i], motion, fatTri.verts[0], edge1, edge2, PVec, Det, oneOverDet, t))
+ continue;
+
+ //if(t<=OffsetLength) t=0.0f;
+ // Only consider positive distances, closer than current best
+ // ### we could test that first on tri vertices & discard complete tri if it's further than current best (or equal!)
+ if(t < 0.0f || t > minDist)
+ continue;
+
+ minDist = t;
+ col = 0;
+// hit = boxVertices[i] + t * motion;
+ hitIndex = i;
+ }
+ }
+ }
+ else
+ {
+ if(Det<=-LOCAL_EPSILON || Det>=LOCAL_EPSILON)
+ {
+ for(PxU32 i=0;i<8;i++)
+ {
+ // ### test this
+ // ### ok, this causes the bug in level3's v-shaped desk. Not really a real "bug", it just happens
+ // that this VF test fixes this case, so it's a bad idea to cull it. Oh, well.
+ // If we use a penetration-depth code to fixup bad cases, we can enable this culling again. (also
+ // if we find a better way to handle that desk)
+ // Discard back vertices
+ // if(!VN[i].SameDirection(motion))
+ // continue;
+
+ // Shoot a ray from vertex against triangle, in direction "motion"
+ PxReal t;
+ if(!rayTriPrecaNoCull(boxVertices[i], motion, fatTri.verts[0], edge1, edge2, PVec, Det, oneOverDet, t))
+ continue;
+
+ //if(t<=OffsetLength) t=0.0f;
+ // Only consider positive distances, closer than current best
+ // ### we could test that first on tri vertices & discard complete tri if it's further than current best (or equal!)
+ if(t < 0.0f || t > minDist)
+ continue;
+
+ minDist = t;
+ col = 0;
+// hit = boxVertices[i] + t * motion;
+ hitIndex = i;
+ }
+ }
+ }
+
+ // Only copy this once, if needed
+ if(col==0)
+ {
+ // PT: hit point on triangle
+ hit = boxVertices[hitIndex] + minDist * motion;
+ normal = denormalizedTriNormal;
+ }
+ }
+
+ // Triangle vertices VS box
+ {
+ const PxVec3 negMotion = -motion;
+ const PxVec3 negInvMotion = -oneOverMotion;
+
+ // PT: precompute fabs-test for ray-box
+ // - doing this outside of the ray-box function gets rid of 3 fabs/fcmp per call
+ // - doing this with integer code removes the 3 remaining fabs/fcmps totally
+ // - doing this outside reduces the LHS
+ const bool b0 = physx::intrinsics::abs(negMotion.x)<LOCAL_EPSILON_RAY_BOX;
+ const bool b1 = physx::intrinsics::abs(negMotion.y)<LOCAL_EPSILON_RAY_BOX;
+ const bool b2 = physx::intrinsics::abs(negMotion.z)<LOCAL_EPSILON_RAY_BOX;
+
+ // ### have this as a param ?
+ const PxVec3& Min = box.minimum;
+ const PxVec3& Max = box.maximum;
+
+ const PxVec3* boxNormals = gNearPlaneNormal;
+
+ // ### use stamps not to shoot shared vertices multiple times
+ // ### discard non-convex verts
+ for(PxU32 i=0;i<3;i++)
+ {
+ PxReal tnear, tfar;
+ const int plane = ::intersectRayAABB2(Min, Max, tri.verts[i], negMotion, negInvMotion, tnear, tfar, b0, b1, b2);
+ PX_ASSERT(plane == intersectRayAABB(Min, Max, tri.verts[i], negMotion, tnear, tfar));
+
+ // The following works as well but we need to call "intersectRayAABB" to get a plane index compatible with BoxNormals.
+ // We could fix this by unifying the plane indices returned by the different ray-aabb functions...
+ //PxVec3 coord;
+ //PxReal t;
+ //PxU32 status = rayAABBIntersect2(Min, Max, tri.verts[i], -motion, coord, t);
+
+ // ### don't test -1 ?
+ if(plane==-1 || tnear<0.0f) continue;
+// if(tnear<0.0f) continue;
+ if(tnear <= minDist)
+ {
+ minDist = tnear; // ### warning, tnear => flips normals
+ normal = boxNormals[plane];
+ col = 1;
+
+ // PT: hit point on triangle
+ hit = tri.verts[i];
+ }
+ }
+ }
+
+ PxU32 saved_j = PX_INVALID_U32;
+ PxU32 saved_k = PX_INVALID_U32;
+ PxVec3 p1s;
+ PxVec3 v1s;
+
+ // Edge-vs-edge
+ {
+ // Loop through box edges
+ const PxU8* PX_RESTRICT edges = getBoxEdges();
+ const PxVec3* PX_RESTRICT edgeNormals = getBoxLocalEdgeNormals();
+ for(PxU32 i=0;i<12;i++) // 12 edges
+ {
+ // PT: TODO: skip this if edge is culled
+ PxVec3 p1 = boxVertices[*edges++];
+ PxVec3 p2 = boxVertices[*edges++];
+ Ps::makeFatEdge(p1, p2, gFatBoxEdgeCoeff);
+
+ if(edgeNormals[i].dot(motion) < 0.0f)
+ continue;
+
+ // While we're at it, precompute some more data for EE tests
+ const PxVec3 v1 = p2 - p1;
+
+ // Build plane P based on edge (p1, p2) and direction (dir)
+ const PxVec3 planeNormal = v1.cross(motion);
+ const PxPlane plane(planeNormal, -(planeNormal.dot(p1)));
+
+ // find largest 2D plane projection
+ PxU32 closest_i, closest_j;
+ // Ps::closestAxis(plane.normal, ii, jj);
+ closestAxis2(planeNormal, closest_i, closest_j);
+
+ const PxReal coeff = 1.0f / (v1[closest_i]*motion[closest_j] - v1[closest_j]*motion[closest_i]);
+
+ // Loop through triangle edges
+ for(PxU32 j=0; j<3; j++)
+ {
+ // Catch current triangle edge
+ // j=0 => 0-1
+ // j=1 => 1-2
+ // j=2 => 2-0
+ // => this is compatible with EdgeList
+ const PxU32 k = Ps::getNextIndex3(j);
+
+ PxReal dist;
+ PxVec3 ip;
+ if(intersectEdgeEdge3(plane, p1, p2, motion, v1, tri.verts[j], tri.verts[k], dist, ip, closest_i, closest_j, coeff))
+ {
+ if(dist<=minDist)
+ {
+ p1s = p1;
+ v1s = v1;
+ saved_j = j;
+ saved_k = k;
+
+ col = 2;
+ minDist = dist;
+
+ // PT: hit point on triangle
+ hit = ip + motion*dist;
+ }
+ }
+ }
+ }
+ }
+
+ if(col==-1)
+ return false;
+
+ if(col==2)
+ {
+ PX_ASSERT(saved_j != PX_INVALID_U32);
+ PX_ASSERT(saved_k != PX_INVALID_U32);
+ const PxVec3& p3 = tri.verts[saved_j];
+ const PxVec3& p4 = tri.verts[saved_k];
+ computeEdgeEdgeNormal(normal, p1s, v1s, p3, p4-p3, motion, minDist);
+ }
+
+ d = minDist;
+ return true;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.h
new file mode 100644
index 00000000..3bd450e8
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_FeatureBased.h
@@ -0,0 +1,67 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_BOX_TRIANGLE_FEATURE_BASED_H
+#define GU_SWEEP_BOX_TRIANGLE_FEATURE_BASED_H
+
+#include "foundation/PxVec3.h"
+#include "foundation/PxPlane.h"
+#include "CmPhysXCommon.h"
+
+namespace physx
+{
+ class PxTriangle;
+
+ namespace Gu
+ {
+ /**
+ Sweeps a box against a triangle, using a 'feature-based' approach.
+
+ This is currently only used for computing the box-sweep impact data, in a second pass,
+ after the best triangle has been identified using faster approaches (SAT/GJK).
+
+ \warning Returned impact normal is not normalized
+
+ \param tri [in] the triangle
+ \param box [in] the box
+ \param motion [in] (box) motion vector
+ \param oneOverMotion [in] precomputed inverse of motion vector
+ \param hit [out] impact point
+ \param normal [out] impact normal (warning: not normalized)
+ \param d [in/out] impact distance (please initialize with best current distance)
+ \param isDoubleSided [in] whether triangle is double-sided or not
+ \return true if an impact has been found
+ */
+ bool sweepBoxTriangle( const PxTriangle& tri, const PxBounds3& box,
+ const PxVec3& motion, const PxVec3& oneOverMotion,
+ PxVec3& hit, PxVec3& normal, PxReal& d, bool isDoubleSided=false);
+ } // namespace Gu
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.cpp
new file mode 100644
index 00000000..fd3b3ff7
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.cpp
@@ -0,0 +1,39 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepBoxTriangle_SAT.h"
+
+using namespace physx;
+using namespace Gu;
+
+// PT: SAT-based version, in box space
+int Gu::triBoxSweepTestBoxSpace(const PxTriangle& tri, const PxVec3& extents, const PxVec3& dir, const PxVec3& oneOverDir, float tmax, float& toi, bool doBackfaceCulling)
+{
+ return triBoxSweepTestBoxSpace_inlined(tri, extents, dir, oneOverDir, tmax, toi, PxU32(doBackfaceCulling));
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.h
new file mode 100644
index 00000000..c0c172f0
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepBoxTriangle_SAT.h
@@ -0,0 +1,235 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_BOX_TRIANGLE_SAT_H
+#define GU_SWEEP_BOX_TRIANGLE_SAT_H
+
+#include "GuSweepSharedTests.h"
+#include "PxTriangle.h"
+
+ #define RetType int
+ #define MTDType bool
+
+namespace physx
+{
+namespace Gu
+{
+
+// We have separation if one of those conditions is true:
+// -BoxExt > TriMax (box strictly to the right of the triangle)
+// BoxExt < TriMin (box strictly to the left of the triangle
+// <=> d0 = -BoxExt - TriMax > 0
+// d1 = BoxExt - TriMin < 0
+// Hence we have overlap if d0 <= 0 and d1 >= 0
+// overlap = (d0<=0.0f && d1>=0.0f)
+#define TEST_OVERLAP \
+ const float d0 = -BoxExt - TriMax; \
+ const float d1 = BoxExt - TriMin; \
+ const bool bIntersect = (d0<=0.0f && d1>=0.0f); \
+ bValidMTD &= bIntersect;
+
+ // PT: inlining this one is important. Returning floats looks bad but is faster on Xbox.
+ static PX_FORCE_INLINE RetType testAxis(const PxTriangle& tri, const PxVec3& extents, const PxVec3& dir, const PxVec3& axis, MTDType& bValidMTD, float& tfirst, float& tlast)
+ {
+ const float d0t = tri.verts[0].dot(axis);
+ const float d1t = tri.verts[1].dot(axis);
+ const float d2t = tri.verts[2].dot(axis);
+
+ float TriMin = PxMin(d0t, d1t);
+ float TriMax = PxMax(d0t, d1t);
+ TriMin = PxMin(TriMin, d2t);
+ TriMax = PxMax(TriMax, d2t);
+
+ ////////
+
+ const float BoxExt = PxAbs(axis.x)*extents.x + PxAbs(axis.y)*extents.y + PxAbs(axis.z)*extents.z;
+ TEST_OVERLAP
+
+ const float v = dir.dot(axis);
+ if(PxAbs(v) < 1.0E-6f)
+ return bIntersect;
+ const float oneOverV = -1.0f / v;
+
+ // float t0 = d0 * oneOverV;
+ // float t1 = d1 * oneOverV;
+ // if(t0 > t1) TSwap(t0, t1);
+ const float t0_ = d0 * oneOverV;
+ const float t1_ = d1 * oneOverV;
+ float t0 = PxMin(t0_, t1_);
+ float t1 = PxMax(t0_, t1_);
+
+ if(t0 > tlast) return false;
+ if(t1 < tfirst) return false;
+
+ // if(t1 < tlast) tlast = t1;
+ tlast = PxMin(t1, tlast);
+
+ // if(t0 > tfirst) tfirst = t0;
+ tfirst = PxMax(t0, tfirst);
+
+ return true;
+ }
+
+ template<const int XYZ>
+ static PX_FORCE_INLINE RetType testAxisXYZ(const PxTriangle& tri, const PxVec3& extents, const PxVec3& dir, float oneOverDir, MTDType& bValidMTD, float& tfirst, float& tlast)
+ {
+ const float d0t = tri.verts[0][XYZ];
+ const float d1t = tri.verts[1][XYZ];
+ const float d2t = tri.verts[2][XYZ];
+
+ float TriMin = PxMin(d0t, d1t);
+ float TriMax = PxMax(d0t, d1t);
+ TriMin = PxMin(TriMin, d2t);
+ TriMax = PxMax(TriMax, d2t);
+
+ ////////
+
+ const float BoxExt = extents[XYZ];
+ TEST_OVERLAP
+
+ const float v = dir[XYZ];
+ if(PxAbs(v) < 1.0E-6f)
+ return bIntersect;
+
+ const float oneOverV = -oneOverDir;
+
+ // float t0 = d0 * oneOverV;
+ // float t1 = d1 * oneOverV;
+ // if(t0 > t1) TSwap(t0, t1);
+ const float t0_ = d0 * oneOverV;
+ const float t1_ = d1 * oneOverV;
+ float t0 = PxMin(t0_, t1_);
+ float t1 = PxMax(t0_, t1_);
+
+ if(t0 > tlast) return false;
+ if(t1 < tfirst) return false;
+
+ // if(t1 < tlast) tlast = t1;
+ tlast = PxMin(t1, tlast);
+
+ // if(t0 > tfirst) tfirst = t0;
+ tfirst = PxMax(t0, tfirst);
+
+ return true;
+ }
+
+ PX_FORCE_INLINE int testSeparationAxes( const PxTriangle& tri, const PxVec3& extents,
+ const PxVec3& normal, const PxVec3& dir, const PxVec3& oneOverDir, float tmax, float& tcoll)
+ {
+ bool bValidMTD = true;
+ float tfirst = -FLT_MAX;
+ float tlast = FLT_MAX;
+
+ // Triangle normal
+ if(!testAxis(tri, extents, dir, normal, bValidMTD, tfirst, tlast))
+ return 0;
+
+ // Box normals
+ if(!testAxisXYZ<0>(tri, extents, dir, oneOverDir.x, bValidMTD, tfirst, tlast))
+ return 0;
+ if(!testAxisXYZ<1>(tri, extents, dir, oneOverDir.y, bValidMTD, tfirst, tlast))
+ return 0;
+ if(!testAxisXYZ<2>(tri, extents, dir, oneOverDir.z, bValidMTD, tfirst, tlast))
+ return 0;
+
+ // Edges
+ for(PxU32 i=0; i<3; i++)
+ {
+ int ip1 = int(i+1);
+ if(i>=2) ip1 = 0;
+ const PxVec3 TriEdge = tri.verts[ip1] - tri.verts[i];
+
+ {
+ const PxVec3 Sep = Ps::cross100(TriEdge);
+ if((Sep.dot(Sep))>=1.0E-6f && !testAxis(tri, extents, dir, Sep, bValidMTD, tfirst, tlast))
+ return 0;
+ }
+ {
+ const PxVec3 Sep = Ps::cross010(TriEdge);
+ if((Sep.dot(Sep))>=1.0E-6f && !testAxis(tri, extents, dir, Sep, bValidMTD, tfirst, tlast))
+ return 0;
+ }
+ {
+ const PxVec3 Sep = Ps::cross001(TriEdge);
+ if((Sep.dot(Sep))>=1.0E-6f && !testAxis(tri, extents, dir, Sep, bValidMTD, tfirst, tlast))
+ return 0;
+ }
+ }
+
+ if(tfirst > tmax || tlast < 0.0f)
+ return 0;
+
+ if(tfirst <= 0.0f)
+ {
+ if(!bValidMTD)
+ return 0;
+ tcoll = 0.0f;
+ }
+ else tcoll = tfirst;
+
+ return 1;
+ }
+
+ //! Inlined version of triBoxSweepTestBoxSpace. See that other function for comments.
+ PX_FORCE_INLINE int triBoxSweepTestBoxSpace_inlined(const PxTriangle& tri, const PxVec3& extents, const PxVec3& dir, const PxVec3& oneOverDir, float tmax, float& toi, PxU32 doBackfaceCulling)
+ {
+ // Create triangle normal
+ PxVec3 triNormal;
+ tri.denormalizedNormal(triNormal);
+
+ // Backface culling
+ if(doBackfaceCulling && (triNormal.dot(dir)) >= 0.0f) // ">=" is important !
+ return 0;
+
+ // The SAT test will properly detect initial overlaps, no need for extra tests
+ return testSeparationAxes(tri, extents, triNormal, dir, oneOverDir, tmax, toi);
+ }
+
+ /**
+ Sweeps a box against a triangle, using a 'SAT' approach (Separating Axis Theorem).
+
+ The test is performed in box-space, i.e. the box is axis-aligned and its center is (0,0,0). In other words it is
+ defined by its extents alone. The triangle must have been transformed to this "box-space" before calling the function.
+
+ \param tri [in] triangle in box-space
+ \param extents [in] box extents
+ \param dir [in] sweep direction. Does not need to be normalized.
+ \param oneOverDir [in] precomputed inverse of sweep direction
+ \param tmax [in] sweep length
+ \param toi [out] time of impact/impact distance. Does not need to be initialized before calling the function.
+ \param doBackfaceCulling [in] true to enable backface culling, false for double-sided triangles
+ \return non-zero value if an impact has been found (in which case returned 'toi' value is valid)
+ */
+ int triBoxSweepTestBoxSpace(const PxTriangle& tri, const PxVec3& extents, const PxVec3& dir, const PxVec3& oneOverDir, float tmax, float& toi, bool doBackfaceCulling);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.cpp
new file mode 100644
index 00000000..87764670
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.cpp
@@ -0,0 +1,215 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "foundation/PxBounds3.h"
+#include "foundation/PxTransform.h"
+#include "GuSweepCapsuleBox.h"
+#include "GuSweepSphereTriangle.h"
+#include "GuCapsule.h"
+#include "PxTriangle.h"
+#include "GuDistanceSegmentBox.h"
+#include "GuInternal.h"
+#include "PsAlloca.h"
+#include "GuSIMDHelpers.h"
+
+using namespace physx;
+using namespace Gu;
+
+namespace
+{
+/**
+* Returns triangles.
+* \return 36 indices (12 triangles) indexing the list returned by ComputePoints()
+*/
+static const PxU8* getBoxTriangles()
+{
+ static PxU8 Indices[] = {
+ 0,2,1, 0,3,2,
+ 1,6,5, 1,2,6,
+ 5,7,4, 5,6,7,
+ 4,3,0, 4,7,3,
+ 3,6,2, 3,7,6,
+ 5,0,1, 5,4,0
+ };
+ return Indices;
+}
+}
+
+#define OUTPUT_TRI(t, p0, p1, p2){ \
+t->verts[0] = p0; \
+t->verts[1] = p1; \
+t->verts[2] = p2; \
+t++;}
+
+#define OUTPUT_TRI2(t, p0, p1, p2, d){ \
+t->verts[0] = p0; \
+t->verts[1] = p1; \
+t->verts[2] = p2; \
+t->denormalizedNormal(denormalizedNormal); \
+if((denormalizedNormal.dot(d))>0.0f) { \
+PxVec3 Tmp = t->verts[1]; \
+t->verts[1] = t->verts[2]; \
+t->verts[2] = Tmp; \
+} \
+t++; *ids++ = i; }
+
+static PxU32 extrudeMesh( PxU32 nbTris, const PxTriangle* triangles,
+ const PxVec3& extrusionDir, PxTriangle* tris, PxU32* ids, const PxVec3& dir)
+{
+ const PxU32* base = ids;
+
+ for(PxU32 i=0; i<nbTris; i++)
+ {
+ const PxTriangle& currentTriangle = triangles[i];
+
+ // Create triangle normal
+ PxVec3 denormalizedNormal;
+ currentTriangle.denormalizedNormal(denormalizedNormal);
+
+ // Backface culling
+ const bool culled = (denormalizedNormal.dot(dir)) > 0.0f;
+ if(culled) continue;
+
+ PxVec3 p0 = currentTriangle.verts[0];
+ PxVec3 p1 = currentTriangle.verts[1];
+ PxVec3 p2 = currentTriangle.verts[2];
+
+ PxVec3 p0b = p0 + extrusionDir;
+ PxVec3 p1b = p1 + extrusionDir;
+ PxVec3 p2b = p2 + extrusionDir;
+
+ p0 -= extrusionDir;
+ p1 -= extrusionDir;
+ p2 -= extrusionDir;
+
+ if(denormalizedNormal.dot(extrusionDir) >= 0.0f) OUTPUT_TRI(tris, p0b, p1b, p2b)
+ else OUTPUT_TRI(tris, p0, p1, p2)
+ *ids++ = i;
+
+ // ### it's probably useless to extrude all the shared edges !!!!!
+ //if(CurrentFlags & TriangleCollisionFlag::eACTIVE_EDGE12)
+ {
+ OUTPUT_TRI2(tris, p1, p1b, p2b, dir)
+ OUTPUT_TRI2(tris, p1, p2b, p2, dir)
+ }
+ //if(CurrentFlags & TriangleCollisionFlag::eACTIVE_EDGE20)
+ {
+ OUTPUT_TRI2(tris, p0, p2, p2b, dir)
+ OUTPUT_TRI2(tris, p0, p2b, p0b, dir)
+ }
+ //if(CurrentFlags & TriangleCollisionFlag::eACTIVE_EDGE01)
+ {
+ OUTPUT_TRI2(tris, p0b, p1b, p1, dir)
+ OUTPUT_TRI2(tris, p0b, p1, p0, dir)
+ }
+ }
+ return PxU32(ids-base);
+}
+
+static PxU32 extrudeBox(const PxBounds3& localBox, const PxTransform* world, const PxVec3& extrusionDir, PxTriangle* tris, const PxVec3& dir)
+{
+ // Handle the box as a mesh
+
+ PxTriangle boxTris[12];
+
+ PxVec3 p[8];
+ computeBoxPoints(localBox, p);
+
+ const PxU8* PX_RESTRICT indices = getBoxTriangles();
+
+ for(PxU32 i=0; i<12; i++)
+ {
+ const PxU8 VRef0 = indices[i*3+0];
+ const PxU8 VRef1 = indices[i*3+1];
+ const PxU8 VRef2 = indices[i*3+2];
+
+ PxVec3 p0 = p[VRef0];
+ PxVec3 p1 = p[VRef1];
+ PxVec3 p2 = p[VRef2];
+ if(world)
+ {
+ p0 = world->transform(p0);
+ p1 = world->transform(p1);
+ p2 = world->transform(p2);
+ }
+
+ boxTris[i].verts[0] = p0;
+ boxTris[i].verts[1] = p1;
+ boxTris[i].verts[2] = p2;
+ }
+ PxU32 fakeIDs[12*7];
+ return extrudeMesh(12, boxTris, extrusionDir, tris, fakeIDs, dir);
+}
+
+//
+// The problem of testing a swept capsule against a box is transformed into sweeping a sphere (lying at the center
+// of the capsule) against the extruded triangles of the box. The box triangles are extruded along the
+// capsule segment axis.
+//
+bool Gu::sweepCapsuleBox(const Capsule& capsule, const PxTransform& boxWorldPose, const PxVec3& boxDim, const PxVec3& dir, PxReal length, PxVec3& hit, PxReal& min_dist, PxVec3& normal, PxHitFlags hitFlags)
+{
+ if(!(hitFlags & PxHitFlag::eASSUME_NO_INITIAL_OVERLAP))
+ {
+ // PT: test if shapes initially overlap
+ if(distanceSegmentBoxSquared(capsule.p0, capsule.p1, boxWorldPose.p, boxDim, PxMat33Padded(boxWorldPose.q)) < capsule.radius*capsule.radius)
+ {
+ min_dist = 0.0f;
+ normal = -dir;
+ return true;
+ }
+ }
+
+ // Extrusion dir = capsule segment
+ const PxVec3 extrusionDir = (capsule.p1 - capsule.p0)*0.5f;
+
+ // Extrude box
+ PxReal MinDist = length;
+ bool Status = false;
+ {
+ const PxBounds3 aabb(-boxDim, boxDim);
+
+ PX_ALLOCA(triangles, PxTriangle, 12*7);
+ const PxU32 nbTris = extrudeBox(aabb, &boxWorldPose, extrusionDir, triangles, dir);
+ PX_ASSERT(nbTris<=12*7);
+
+ // Sweep sphere vs extruded box
+ PxSweepHit h; // PT: TODO: ctor!
+ PxVec3 bestNormal;
+ if(sweepSphereTriangles(nbTris, triangles, capsule.computeCenter(), capsule.radius, dir, length, NULL, h, bestNormal, false, false, false, false))
+ {
+ hit = h.position;
+ MinDist = h.distance;
+ normal = h.normal;
+ Status = true;
+ }
+ }
+
+ min_dist = MinDist;
+ return Status;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.h
new file mode 100644
index 00000000..698e78a3
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleBox.h
@@ -0,0 +1,49 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_CAPSULE_BOX_H
+#define GU_SWEEP_CAPSULE_BOX_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+#include "PxQueryReport.h"
+
+namespace physx
+{
+namespace Gu
+{
+ class Capsule;
+
+ bool sweepCapsuleBox(const Capsule& capsule, const PxTransform& boxWorldPose, const PxVec3& boxDim, const PxVec3& dir, PxReal length, PxVec3& hit, PxReal& min_dist, PxVec3& normal, PxHitFlags hitFlags);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.cpp
new file mode 100644
index 00000000..d1f0158b
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.cpp
@@ -0,0 +1,344 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepCapsuleCapsule.h"
+#include "GuCapsule.h"
+#include "GuDistancePointSegment.h"
+#include "GuDistanceSegmentSegment.h"
+#include "GuIntersectionRayCapsule.h"
+#include "PxQueryReport.h"
+#include "PxTriangle.h"
+
+using namespace physx;
+using namespace Gu;
+
+#define LOCAL_EPSILON 0.00001f // PT: this value makes the 'basicAngleTest' pass. Fails because of a ray almost parallel to a triangle
+
+static void edgeEdgeDist(PxVec3& x, PxVec3& y, // closest points
+ const PxVec3& p, const PxVec3& a, // seg 1 origin, vector
+ const PxVec3& q, const PxVec3& b) // seg 2 origin, vector
+{
+ const PxVec3 T = q - p;
+ const PxReal ADotA = a.dot(a);
+ const PxReal BDotB = b.dot(b);
+ const PxReal ADotB = a.dot(b);
+ const PxReal ADotT = a.dot(T);
+ const PxReal BDotT = b.dot(T);
+
+ // t parameterizes ray (p, a)
+ // u parameterizes ray (q, b)
+
+ // Compute t for the closest point on ray (p, a) to ray (q, b)
+ const PxReal Denom = ADotA*BDotB - ADotB*ADotB;
+
+ PxReal t;
+ if(Denom!=0.0f)
+ {
+ t = (ADotT*BDotB - BDotT*ADotB) / Denom;
+
+ // Clamp result so t is on the segment (p, a)
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ else
+ {
+ t = 0.0f;
+ }
+
+ // find u for point on ray (q, b) closest to point at t
+ PxReal u;
+ if(BDotB!=0.0f)
+ {
+ u = (t*ADotB - BDotT) / BDotB;
+
+ // if u is on segment (q, b), t and u correspond to closest points, otherwise, clamp u, recompute and clamp t
+ if(u<0.0f)
+ {
+ u = 0.0f;
+ if(ADotA!=0.0f)
+ {
+ t = ADotT / ADotA;
+
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ else
+ {
+ t = 0.0f;
+ }
+ }
+ else if(u > 1.0f)
+ {
+ u = 1.0f;
+ if(ADotA!=0.0f)
+ {
+ t = (ADotB + ADotT) / ADotA;
+
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ else
+ {
+ t = 0.0f;
+ }
+ }
+ }
+ else
+ {
+ u = 0.0f;
+
+ if(ADotA!=0.0f)
+ {
+ t = ADotT / ADotA;
+
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ else
+ {
+ t = 0.0f;
+ }
+ }
+
+ x = p + a * t;
+ y = q + b * u;
+}
+
+static bool rayQuad(const PxVec3& orig, const PxVec3& dir, const PxVec3& vert0, const PxVec3& vert1, const PxVec3& vert2, PxReal& t, PxReal& u, PxReal& v, bool cull)
+{
+ // Find vectors for two edges sharing vert0
+ const PxVec3 edge1 = vert1 - vert0;
+ const PxVec3 edge2 = vert2 - vert0;
+
+ // Begin calculating determinant - also used to calculate U parameter
+ const PxVec3 pvec = dir.cross(edge2);
+
+ // If determinant is near zero, ray lies in plane of triangle
+ const PxReal det = edge1.dot(pvec);
+
+ if(cull)
+ {
+ if(det<LOCAL_EPSILON)
+ return false;
+
+ // Calculate distance from vert0 to ray origin
+ const PxVec3 tvec = orig - vert0;
+
+ // Calculate U parameter and test bounds
+ u = tvec.dot(pvec);
+ if(u<0.0f || u>det)
+ return false;
+
+ // Prepare to test V parameter
+ const PxVec3 qvec = tvec.cross(edge1);
+
+ // Calculate V parameter and test bounds
+ v = dir.dot(qvec);
+ if(v<0.0f || v>det)
+ return false;
+
+ // Calculate t, scale parameters, ray intersects triangle
+ t = edge2.dot(qvec);
+ const PxReal oneOverDet = 1.0f / det;
+ t *= oneOverDet;
+ u *= oneOverDet;
+ v *= oneOverDet;
+ }
+ else
+ {
+ // the non-culling branch
+ if(det>-LOCAL_EPSILON && det<LOCAL_EPSILON)
+ return false;
+ const PxReal oneOverDet = 1.0f / det;
+
+ // Calculate distance from vert0 to ray origin
+ const PxVec3 tvec = orig - vert0;
+
+ // Calculate U parameter and test bounds
+ u = (tvec.dot(pvec)) * oneOverDet;
+ if(u<0.0f || u>1.0f)
+ return false;
+
+ // prepare to test V parameter
+ const PxVec3 qvec = tvec.cross(edge1);
+
+ // Calculate V parameter and test bounds
+ v = (dir.dot(qvec)) * oneOverDet;
+ if(v<0.0f || v>1.0f)
+ return false;
+
+ // Calculate t, ray intersects triangle
+ t = (edge2.dot(qvec)) * oneOverDet;
+ }
+ return true;
+}
+
+bool Gu::sweepCapsuleCapsule(const Capsule& capsule0, const Capsule& capsule1, const PxVec3& dir, PxReal length, PxReal& min_dist, PxVec3& ip, PxVec3& normal, PxU32 inHitFlags, PxU16& outHitFlags)
+{
+ const PxReal radiusSum = capsule0.radius + capsule1.radius;
+
+ if(!(inHitFlags & PxHitFlag::eASSUME_NO_INITIAL_OVERLAP))
+ {
+ // PT: test if shapes initially overlap
+
+ // PT: It would be better not to use the same code path for spheres and capsules. The segment-segment distance
+ // function doesn't work for degenerate capsules so we need to test all combinations here anyway.
+ bool initialOverlapStatus;
+ if(capsule0.p0==capsule0.p1)
+ initialOverlapStatus = distancePointSegmentSquared(capsule1, capsule0.p0)<radiusSum*radiusSum;
+ else if(capsule1.p0==capsule1.p1)
+ initialOverlapStatus = distancePointSegmentSquared(capsule0, capsule1.p0)<radiusSum*radiusSum;
+ else
+ initialOverlapStatus = distanceSegmentSegmentSquared(capsule0, capsule1)<radiusSum*radiusSum;
+
+ if(initialOverlapStatus)
+ {
+ min_dist = 0.0f;
+ normal = -dir;
+ outHitFlags = PxHitFlag::eDISTANCE | PxHitFlag::eNORMAL;
+ return true;
+ }
+ }
+
+ // 1. Extrude capsule0 by capsule1's length
+ // 2. Inflate extruded shape by capsule1's radius
+ // 3. Raycast against resulting shape
+
+ const PxVec3 capsuleExtent1 = capsule1.p1 - capsule1.p0;
+
+ // Extrusion dir = capsule segment
+ const PxVec3 D = capsuleExtent1*0.5f;
+
+ const PxVec3 p0 = capsule0.p0 - D;
+ const PxVec3 p1 = capsule0.p1 - D;
+ const PxVec3 p0b = capsule0.p0 + D;
+ const PxVec3 p1b = capsule0.p1 + D;
+
+ PxTriangle T(p0b, p1b, p1);
+ PxVec3 Normal;
+ T.normal(Normal);
+
+ PxReal MinDist = length;
+ bool Status = false;
+
+ PxVec3 pa,pb,pc;
+ if((Normal.dot(dir)) >= 0) // Same direction
+ {
+ Normal *= radiusSum;
+ pc = p0 - Normal;
+ pa = p1 - Normal;
+ pb = p1b - Normal;
+ }
+ else
+ {
+ Normal *= radiusSum;
+ pb = p0 + Normal;
+ pa = p1 + Normal;
+ pc = p1b + Normal;
+ }
+ PxReal t, u, v;
+ const PxVec3 center = capsule1.computeCenter();
+ if(rayQuad(center, dir, pa, pb, pc, t, u, v, true) && t>=0.0f && t<MinDist)
+ {
+ MinDist = t;
+ Status = true;
+ }
+
+ // PT: optimization: if we hit one of the quad we can't possibly get a better hit, so let's skip all
+ // the remaining tests!
+ if(!Status)
+ {
+ Capsule Caps[4];
+ Caps[0] = Capsule(p0, p1, radiusSum);
+ Caps[1] = Capsule(p1, p1b, radiusSum);
+ Caps[2] = Capsule(p1b, p0b, radiusSum);
+ Caps[3] = Capsule(p0, p0b, radiusSum);
+
+ // ### a lot of ray-sphere tests could be factored out of the ray-capsule tests...
+ for(PxU32 i=0;i<4;i++)
+ {
+ PxReal w;
+ if(intersectRayCapsule(center, dir, Caps[i], w))
+ {
+ if(w>=0.0f && w<= MinDist)
+ {
+ MinDist = w;
+ Status = true;
+ }
+ }
+ }
+ }
+
+ if(Status)
+ {
+ outHitFlags = PxHitFlag::eDISTANCE;
+ if(inHitFlags & PxU32(PxHitFlag::ePOSITION|PxHitFlag::eNORMAL))
+ {
+ const PxVec3 p00 = capsule0.p0 - MinDist * dir;
+ const PxVec3 p01 = capsule0.p1 - MinDist * dir;
+// const PxVec3 p10 = capsule1.p0;// - MinDist * dir;
+// const PxVec3 p11 = capsule1.p1;// - MinDist * dir;
+
+ const PxVec3 edge0 = p01 - p00;
+ const PxVec3 edge1 = capsuleExtent1;
+
+ PxVec3 x, y;
+ edgeEdgeDist(x, y, p00, edge0, capsule1.p0, edge1);
+
+ if(inHitFlags & PxHitFlag::eNORMAL)
+ {
+ normal = (x - y);
+ const float epsilon = 0.001f;
+ if(normal.normalize()<epsilon)
+ {
+ // PT: happens when radiuses are zero
+ normal = edge1.cross(edge0);
+ if(normal.normalize()<epsilon)
+ {
+ // PT: happens when edges are parallel
+ const PxVec3 capsuleExtent0 = capsule0.p1 - capsule0.p0;
+ edgeEdgeDist(x, y, capsule0.p0, capsuleExtent0, capsule1.p0, edge1);
+ normal = (x - y);
+ normal.normalize();
+ }
+ }
+
+ outHitFlags |= PxHitFlag::eNORMAL;
+ }
+
+ if(inHitFlags & PxHitFlag::ePOSITION)
+ {
+ ip = (capsule1.radius*x + capsule0.radius*y)/(capsule0.radius+capsule1.radius);
+ outHitFlags |= PxHitFlag::ePOSITION;
+ }
+ }
+ min_dist = MinDist;
+ }
+ return Status;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.h
new file mode 100644
index 00000000..b6d6d712
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleCapsule.h
@@ -0,0 +1,48 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_CAPSULE_CAPSULE_H
+#define GU_SWEEP_CAPSULE_CAPSULE_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+
+namespace physx
+{
+namespace Gu
+{
+ class Capsule;
+
+ bool sweepCapsuleCapsule(const Capsule& capsule0, const Capsule& capsule1, const PxVec3& dir, PxReal length, PxReal& min_dist, PxVec3& ip, PxVec3& normal, PxU32 inHitFlags, PxU16& outHitFlags);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.cpp
new file mode 100644
index 00000000..82c4d1dc
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.cpp
@@ -0,0 +1,328 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepCapsuleTriangle.h"
+#include "GuIntersectionCapsuleTriangle.h"
+#include "GuDistanceSegmentTriangle.h"
+#include "GuDistanceSegmentTriangleSIMD.h"
+#include "GuIntersectionTriangleBox.h"
+#include "GuSweepSphereTriangle.h"
+#include "GuInternal.h"
+
+using namespace physx;
+using namespace Gu;
+using namespace physx::shdfnd::aos;
+
+#define COLINEARITY_EPSILON 0.00001f
+
+///////////////////////////////////////////////////////////////////////////////
+
+#define OUTPUT_TRI(pp0, pp1, pp2){ \
+ extrudedTris[nbExtrudedTris].verts[0] = pp0; \
+ extrudedTris[nbExtrudedTris].verts[1] = pp1; \
+ extrudedTris[nbExtrudedTris].verts[2] = pp2; \
+ extrudedTris[nbExtrudedTris].denormalizedNormal(extrudedTrisNormals[nbExtrudedTris]); \
+ nbExtrudedTris++;}
+
+#define OUTPUT_TRI2(p0, p1, p2, d){ \
+ PxTriangle& tri = extrudedTris[nbExtrudedTris]; \
+ tri.verts[0] = p0; \
+ tri.verts[1] = p1; \
+ tri.verts[2] = p2; \
+ PxVec3 nrm; \
+ tri.denormalizedNormal(nrm); \
+ if(nrm.dot(d)>0.0f) { \
+ PxVec3 tmp = tri.verts[1]; \
+ tri.verts[1] = tri.verts[2]; \
+ tri.verts[2] = tmp; \
+ nrm = -nrm; \
+ } \
+ extrudedTrisNormals[nbExtrudedTris] = nrm; \
+ nbExtrudedTris++; }
+
+
+bool Gu::sweepCapsuleTriangles_Precise( PxU32 nbTris, const PxTriangle* PX_RESTRICT triangles, // Triangle data
+ const Capsule& capsule, // Capsule data
+ const PxVec3& unitDir, const PxReal distance, // Ray data
+ const PxU32* PX_RESTRICT cachedIndex, // Cache data
+ PxSweepHit& hit, PxVec3& triNormalOut, // Results
+ PxHitFlags hitFlags, bool isDoubleSided, // Query modifiers
+ const BoxPadded* cullBox) // Cull data
+{
+ if(!nbTris)
+ return false;
+
+ const bool meshBothSides = hitFlags & PxHitFlag::eMESH_BOTH_SIDES;
+ const bool doBackfaceCulling = !isDoubleSided && !meshBothSides;
+ const bool anyHit = hitFlags & PxHitFlag::eMESH_ANY;
+ const bool testInitialOverlap = !(hitFlags & PxHitFlag::eASSUME_NO_INITIAL_OVERLAP);
+
+ // PT: we can fallback to sphere sweep:
+ // - if the capsule is degenerate (i.e. it's a sphere)
+ // - if the sweep direction is the same as the capsule axis, in which case we can just sweep the top or bottom sphere
+
+ const PxVec3 extrusionDir = (capsule.p0 - capsule.p1)*0.5f; // Extrusion dir = capsule segment
+ const PxReal halfHeight = extrusionDir.magnitude();
+ bool mustExtrude = halfHeight!=0.0f;
+ if(!mustExtrude)
+ {
+ // PT: capsule is a sphere. Switch to sphere path (intersectCapsuleTriangle doesn't work for degenerate capsules)
+ return sweepSphereTriangles(nbTris, triangles, capsule.p0, capsule.radius, unitDir, distance, cachedIndex, hit, triNormalOut, isDoubleSided, meshBothSides, anyHit, testInitialOverlap);
+ }
+ else
+ {
+ const PxVec3 capsuleAxis = extrusionDir/halfHeight;
+ const PxReal colinearity = PxAbs(capsuleAxis.dot(unitDir));
+ mustExtrude = (colinearity < (1.0f - COLINEARITY_EPSILON));
+ }
+
+ const PxVec3 capsuleCenter = capsule.computeCenter();
+
+ if(!mustExtrude)
+ {
+ CapsuleTriangleOverlapData params;
+ params.init(capsule);
+ // PT: unfortunately we need to do IO test with the *capsule*, even though we're in the sphere codepath. So we
+ // can't directly reuse the sphere function.
+ const PxVec3 sphereCenter = capsuleCenter + unitDir * halfHeight;
+ // PT: this is a copy of 'sweepSphereTriangles' but with a capsule IO test. Saves double backface culling....
+ {
+ PxU32 index = PX_INVALID_U32;
+ const PxU32 initIndex = getInitIndex(cachedIndex, nbTris);
+
+ PxReal curT = distance;
+ const PxReal dpc0 = sphereCenter.dot(unitDir);
+
+ PxReal bestAlignmentValue = 2.0f;
+
+ PxVec3 bestTriNormal(0.0f);
+
+ for(PxU32 ii=0; ii<nbTris; ii++) // We need i for returned triangle index
+ {
+ const PxU32 i = getTriangleIndex(ii, initIndex);
+
+ const PxTriangle& currentTri = triangles[i];
+
+ if(rejectTriangle(sphereCenter, unitDir, curT, capsule.radius, currentTri.verts, dpc0))
+ continue;
+
+ PxVec3 triNormal;
+ currentTri.denormalizedNormal(triNormal);
+
+ // Backface culling
+ if(doBackfaceCulling && (triNormal.dot(unitDir) > 0.0f))
+ continue;
+
+ if(testInitialOverlap && intersectCapsuleTriangle(triNormal, currentTri.verts[0], currentTri.verts[1], currentTri.verts[2], capsule, params))
+ return setInitialOverlapResults(hit, unitDir, i);
+
+ const PxReal magnitude = triNormal.magnitude();
+ if(magnitude==0.0f)
+ continue;
+
+ triNormal /= magnitude;
+
+ PxReal currentDistance;
+ bool unused;
+ if (!sweepSphereVSTri(currentTri.verts, triNormal, sphereCenter, capsule.radius, unitDir, currentDistance, unused, false))
+ continue;
+
+ const PxReal distEpsilon = GU_EPSILON_SAME_DISTANCE; // pick a farther hit within distEpsilon that is more opposing than the previous closest hit
+ const PxReal hitDot = computeAlignmentValue(triNormal, unitDir);
+ if (!keepTriangle(currentDistance, hitDot, curT, bestAlignmentValue, distance, distEpsilon))
+ continue;
+
+ curT = currentDistance;
+ index = i;
+ bestAlignmentValue = hitDot;
+ bestTriNormal = triNormal;
+ if(anyHit)
+ break;
+ }
+ return computeSphereTriangleImpactData(hit, triNormalOut, index, curT, sphereCenter, unitDir, bestTriNormal, triangles, isDoubleSided, meshBothSides);
+ }
+ }
+
+ // PT: extrude mesh on the fly. This is a modified copy of sweepSphereTriangles, unfortunately
+ PxTriangle extrudedTris[7];
+ PxVec3 extrudedTrisNormals[7]; // Not normalized
+
+ hit.faceIndex = PX_INVALID_U32;
+ const PxU32 initIndex = getInitIndex(cachedIndex, nbTris);
+
+ const PxReal radius = capsule.radius;
+ PxReal curT = distance;
+ const PxReal dpc0 = capsuleCenter.dot(unitDir);
+
+ // PT: we will copy the best triangle here. Using indices alone doesn't work
+ // since we extrude on-the-fly (and we don't want to re-extrude later)
+ PxTriangle bestTri;
+ PxVec3 bestTriNormal(0.0f);
+ PxReal mostOpposingHitDot = 2.0f;
+
+ CapsuleTriangleOverlapData params;
+ params.init(capsule);
+
+ for(PxU32 ii=0; ii<nbTris; ii++) // We need i for returned triangle index
+ {
+ const PxU32 i = getTriangleIndex(ii, initIndex);
+
+ const PxTriangle& currentSrcTri = triangles[i]; // PT: src tri, i.e. non-extruded
+
+///////////// PT: this part comes from "ExtrudeMesh"
+ // Create triangle normal
+ PxVec3 denormalizedNormal;
+ currentSrcTri.denormalizedNormal(denormalizedNormal);
+
+ // Backface culling
+ if(doBackfaceCulling && (denormalizedNormal.dot(unitDir) > 0.0f))
+ continue;
+
+ if(cullBox)
+ {
+ if(!intersectTriangleBox(*cullBox, currentSrcTri.verts[0], currentSrcTri.verts[1], currentSrcTri.verts[2]))
+ continue;
+ }
+
+ if(testInitialOverlap && intersectCapsuleTriangle(denormalizedNormal, currentSrcTri.verts[0], currentSrcTri.verts[1], currentSrcTri.verts[2], capsule, params))
+ return setInitialOverlapResults(hit, unitDir, i);
+
+ // Extrude mesh on the fly
+ PxU32 nbExtrudedTris=0;
+
+ const PxVec3 p0 = currentSrcTri.verts[0] - extrusionDir;
+ const PxVec3 p1 = currentSrcTri.verts[1] - extrusionDir;
+ const PxVec3 p2 = currentSrcTri.verts[2] - extrusionDir;
+
+ const PxVec3 p0b = currentSrcTri.verts[0] + extrusionDir;
+ const PxVec3 p1b = currentSrcTri.verts[1] + extrusionDir;
+ const PxVec3 p2b = currentSrcTri.verts[2] + extrusionDir;
+
+ if(denormalizedNormal.dot(extrusionDir) >= 0.0f) OUTPUT_TRI(p0b, p1b, p2b)
+ else OUTPUT_TRI(p0, p1, p2)
+
+ // ### it's probably useless to extrude all the shared edges !!!!!
+ //if(CurrentFlags & TriangleCollisionFlag::eACTIVE_EDGE12)
+ {
+ OUTPUT_TRI2(p1, p1b, p2b, unitDir)
+ OUTPUT_TRI2(p1, p2b, p2, unitDir)
+ }
+ //if(CurrentFlags & TriangleCollisionFlag::eACTIVE_EDGE20)
+ {
+ OUTPUT_TRI2(p0, p2, p2b, unitDir)
+ OUTPUT_TRI2(p0, p2b, p0b, unitDir)
+ }
+ //if(CurrentFlags & TriangleCollisionFlag::eACTIVE_EDGE01)
+ {
+ OUTPUT_TRI2(p0b, p1b, p1, unitDir)
+ OUTPUT_TRI2(p0b, p1, p0, unitDir)
+ }
+/////////////
+
+ // PT: TODO: this one is new, to fix the tweak issue. However this wasn't
+ // here before so the perf hit should be analyzed.
+ denormalizedNormal.normalize();
+ const PxReal hitDot1 = computeAlignmentValue(denormalizedNormal, unitDir);
+
+ for(PxU32 j=0;j<nbExtrudedTris;j++)
+ {
+ const PxTriangle& currentTri = extrudedTris[j];
+
+ PxVec3& triNormal = extrudedTrisNormals[j];
+ // Backface culling
+ if(doBackfaceCulling && (triNormal.dot(unitDir)) > 0.0f)
+ continue;
+
+ // PT: beware, culling is only ok on the sphere I think
+ if(rejectTriangle(capsuleCenter, unitDir, curT, radius, currentTri.verts, dpc0))
+ continue;
+
+ const PxReal magnitude = triNormal.magnitude();
+ if(magnitude==0.0f)
+ continue;
+
+ triNormal /= magnitude;
+
+ PxReal currentDistance;
+ bool unused;
+ if (!sweepSphereVSTri(currentTri.verts, triNormal, capsuleCenter, radius, unitDir, currentDistance, unused, false))
+ continue;
+
+ const PxReal distEpsilon = GU_EPSILON_SAME_DISTANCE; // pick a farther hit within distEpsilon that is more opposing than the previous closest hit
+ if (!keepTriangle(currentDistance, hitDot1, curT, mostOpposingHitDot, distance, distEpsilon))
+ continue;
+
+ curT = currentDistance;
+ hit.faceIndex = i;
+ mostOpposingHitDot = hitDot1; // arbitrary bias. works for hitDot1=-1, prevHitDot=0
+ bestTri = currentTri;
+ bestTriNormal = denormalizedNormal;
+ if(anyHit)
+ goto Exit; // PT: using goto to have one test per hit, not test per triangle ('break' doesn't work here)
+ }
+ }
+Exit:
+ if(hit.faceIndex==PX_INVALID_U32)
+ return false; // We didn't touch any triangle
+
+ hit.distance = curT;
+
+ triNormalOut = bestTriNormal;
+
+ // Compute impact data only once, using best triangle
+ computeSphereTriImpactData(hit.position, hit.normal, capsuleCenter, unitDir, hit.distance, bestTri);
+
+ // PT: by design, returned normal is opposed to the sweep direction.
+ if(shouldFlipNormal(hit.normal, meshBothSides, isDoubleSided, bestTriNormal, unitDir))
+ hit.normal = -hit.normal;
+
+ // PT: revisit this
+ if(hit.faceIndex!=PX_INVALID_U32)
+ {
+ // PT: we need to recompute a hit here because the hit between the *capsule* and the source mesh can be very
+ // different from the hit between the *sphere* and the extruded mesh.
+
+ // Touched tri
+ const PxVec3& p0 = triangles[hit.faceIndex].verts[0];
+ const PxVec3& p1 = triangles[hit.faceIndex].verts[1];
+ const PxVec3& p2 = triangles[hit.faceIndex].verts[2];
+
+ // AP: measured to be a bit faster than the scalar version
+ const PxVec3 delta = unitDir*hit.distance;
+ Vec3V pointOnSeg, pointOnTri;
+ distanceSegmentTriangleSquared(
+ V3LoadU(capsule.p0 + delta), V3LoadU(capsule.p1 + delta),
+ V3LoadU(p0), V3LoadU(p1), V3LoadU(p2),
+ pointOnSeg, pointOnTri);
+ V3StoreU(pointOnTri, hit.position);
+
+ hit.flags = PxHitFlag::eDISTANCE|PxHitFlag::eNORMAL|PxHitFlag::ePOSITION;
+ }
+ return true;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.h
new file mode 100644
index 00000000..e56d02ef
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepCapsuleTriangle.h
@@ -0,0 +1,75 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_CAPSULE_TRIANGLE_H
+#define GU_SWEEP_CAPSULE_TRIANGLE_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+#include "PxQueryReport.h"
+
+namespace physx
+{
+ class PxTriangle;
+
+namespace Gu
+{
+ class BoxPadded;
+ class Capsule;
+
+ /**
+ Sweeps a capsule against a set of triangles.
+
+ \param nbTris [in] number of triangles in input array
+ \param triangles [in] array of input triangles
+ \param capsule [in] the capsule
+ \param unitDir [in] sweep's unit direcion
+ \param distance [in] sweep's length
+ \param cachedIndex [in] cached triangle index, or NULL. Cached triangle will be tested first.
+ \param hit [out] results
+ \param triNormalOut [out] triangle normal
+ \param hitFlags [in] query modifiers
+ \param isDoubleSided [in] true if input triangles are double-sided
+ \param cullBox [in] additional/optional culling box. Triangles not intersecting the box are quickly discarded.
+ \warning if using a cullbox, make sure all triangles can be safely V4Loaded (i.e. allocate 4 more bytes after last triangle)
+ \return true if an impact has been found
+ */
+ bool sweepCapsuleTriangles_Precise( PxU32 nbTris, const PxTriangle* PX_RESTRICT triangles, // Triangle data
+ const Capsule& capsule, // Capsule data
+ const PxVec3& unitDir, const PxReal distance, // Ray data
+ const PxU32* PX_RESTRICT cachedIndex, // Cache data
+ PxSweepHit& hit, PxVec3& triNormalOut, // Results
+ PxHitFlags hitFlags, bool isDoubleSided, // Query modifiers
+ const BoxPadded* cullBox=NULL); // Cull data
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.cpp
new file mode 100644
index 00000000..498ae293
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.cpp
@@ -0,0 +1,103 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepSphereCapsule.h"
+#include "GuSphere.h"
+#include "GuCapsule.h"
+#include "GuDistancePointSegment.h"
+#include "GuSweepSphereSphere.h"
+#include "GuIntersectionRayCapsule.h"
+
+using namespace physx;
+using namespace Gu;
+
+bool Gu::sweepSphereCapsule(const Sphere& sphere, const Capsule& lss, const PxVec3& dir, PxReal length, PxReal& d, PxVec3& ip, PxVec3& nrm, PxHitFlags hitFlags)
+{
+ const PxReal radiusSum = lss.radius + sphere.radius;
+
+ if(!(hitFlags & PxHitFlag::eASSUME_NO_INITIAL_OVERLAP))
+ {
+ // PT: test if shapes initially overlap
+ if(distancePointSegmentSquared(lss.p0, lss.p1, sphere.center)<radiusSum*radiusSum)
+ {
+ d = 0.0f;
+ nrm = -dir;
+ return true;
+ }
+ }
+
+ if(lss.p0 == lss.p1)
+ {
+ // Sphere vs. sphere
+ if(sweepSphereSphere(sphere.center, sphere.radius, lss.p0, lss.radius, -dir*length, d, nrm))
+ {
+ d*=length;
+// if(hitFlags & PxHitFlag::ePOSITION) // PT: TODO
+ ip = sphere.center + nrm * sphere.radius;
+ return true;
+ }
+ return false;
+ }
+
+ // Create inflated capsule
+ Capsule Inflated(lss.p0, lss.p1, radiusSum);
+
+ // Raycast against it
+ PxReal t;
+ if(intersectRayCapsule(sphere.center, dir, Inflated, t))
+ {
+ if(t>=0.0f && t<=length)
+ {
+ d = t;
+
+// PT: TODO:
+// const Ps::IntBool needsImpactPoint = hitFlags & PxHitFlag::ePOSITION;
+// if(needsImpactPoint || hitFlags & PxHitFlag::eNORMAL)
+ {
+ // Move capsule against sphere
+ const PxVec3 tdir = t*dir;
+ Inflated.p0 -= tdir;
+ Inflated.p1 -= tdir;
+
+ // Compute closest point between moved capsule & sphere
+ distancePointSegmentSquared(Inflated, sphere.center, &t);
+ Inflated.computePoint(ip, t);
+
+ // Normal
+ nrm = (ip - sphere.center);
+ nrm.normalize();
+
+// if(needsImpactPoint) // PT: TODO
+ ip -= nrm * lss.radius;
+ }
+ return true;
+ }
+ }
+ return false;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.h
new file mode 100644
index 00000000..c8b76508
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereCapsule.h
@@ -0,0 +1,50 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_SPHERE_CAPSULE_H
+#define GU_SWEEP_SPHERE_CAPSULE_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+#include "PxQueryReport.h"
+
+namespace physx
+{
+namespace Gu
+{
+ class Sphere;
+ class Capsule;
+
+ bool sweepSphereCapsule(const Sphere& sphere, const Capsule& lss, const PxVec3& dir, PxReal length, PxReal& d, PxVec3& ip, PxVec3& nrm, PxHitFlags hitFlags);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.cpp
new file mode 100644
index 00000000..7a84750d
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.cpp
@@ -0,0 +1,116 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepSphereSphere.h"
+#include "PsUtilities.h"
+
+using namespace physx;
+using namespace Gu;
+
+// Adapted from Gamasutra (Gomez article)
+// Return true if r1 and r2 are real
+static PX_FORCE_INLINE bool quadraticFormula(const PxReal a, const PxReal b, const PxReal c, PxReal& r1, PxReal& r2)
+{
+ const PxReal q = b*b - 4*a*c;
+ if(q>=0.0f)
+ {
+ PX_ASSERT(a!=0.0f);
+ const PxReal sq = PxSqrt(q);
+ const PxReal d = 1.0f / (2.0f*a);
+ r1 = (-b + sq) * d;
+ r2 = (-b - sq) * d;
+ return true;//real roots
+ }
+ else
+ {
+ return false;//complex roots
+ }
+}
+
+static bool sphereSphereSweep( const PxReal ra, //radius of sphere A
+ const PxVec3& A0, //previous position of sphere A
+ const PxVec3& A1, //current position of sphere A
+ const PxReal rb, //radius of sphere B
+ const PxVec3& B0, //previous position of sphere B
+ const PxVec3& B1, //current position of sphere B
+ PxReal& u0, //normalized time of first collision
+ PxReal& u1 //normalized time of second collision
+ )
+{
+ const PxVec3 va = A1 - A0;
+ const PxVec3 vb = B1 - B0;
+ const PxVec3 AB = B0 - A0;
+ const PxVec3 vab = vb - va; // relative velocity (in normalized time)
+ const PxReal rab = ra + rb;
+
+ const PxReal a = vab.dot(vab); //u*u coefficient
+ const PxReal b = 2.0f*(vab.dot(AB)); //u coefficient
+
+ const PxReal c = (AB.dot(AB)) - rab*rab; //constant term
+
+ //check if they're currently overlapping
+ if(c<=0.0f || a==0.0f)
+ {
+ u0 = 0.0f;
+ u1 = 0.0f;
+ return true;
+ }
+
+ //check if they hit each other during the frame
+ if(quadraticFormula(a, b, c, u0, u1))
+ {
+ if(u0>u1)
+ Ps::swap(u0, u1);
+
+ // u0<u1
+// if(u0<0.0f || u1>1.0f) return false;
+ if(u1<0.0f || u0>1.0f) return false;
+
+ return true;
+ }
+ return false;
+}
+
+bool Gu::sweepSphereSphere(const PxVec3& center0, PxReal radius0, const PxVec3& center1, PxReal radius1, const PxVec3& motion, PxReal& d, PxVec3& nrm)
+{
+ const PxVec3 movedCenter = center1 + motion;
+
+ PxReal tmp;
+ if(!sphereSphereSweep(radius0, center0, center0, radius1, center1, movedCenter, d, tmp))
+ return false;
+
+ // Compute normal
+ // PT: if spheres initially overlap, the convention is that returned normal = -sweep direction
+ if(d==0.0f)
+ nrm = -motion;
+ else
+ nrm = (center1 + d * motion) - center0;
+ nrm.normalize();
+ return true;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.h
new file mode 100644
index 00000000..1fd7cef5
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereSphere.h
@@ -0,0 +1,46 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_SPHERE_SPHERE_H
+#define GU_SWEEP_SPHERE_SPHERE_H
+
+#include "foundation/PxVec3.h"
+#include "CmPhysXCommon.h"
+
+namespace physx
+{
+namespace Gu
+{
+ bool sweepSphereSphere(const PxVec3& center0, PxReal radius0, const PxVec3& center1, PxReal radius1, const PxVec3& motion, PxReal& d, PxVec3& nrm);
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.cpp
new file mode 100644
index 00000000..c54dac8b
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.cpp
@@ -0,0 +1,521 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "GuSweepSphereTriangle.h"
+#include "GuIntersectionRaySphere.h"
+#include "GuIntersectionRayCapsule.h"
+#include "GuIntersectionRayTriangle.h"
+#include "GuCapsule.h"
+#include "GuInternal.h"
+#include "PsUtilities.h"
+#include "GuDistancePointTriangle.h"
+
+using namespace physx;
+using namespace Gu;
+
+// PT: using GU_CULLING_EPSILON_RAY_TRIANGLE fails here, in capsule-vs-mesh's triangle extrusion, when
+// the sweep dir is almost the same as the capsule's dir (i.e. when we usually fallback to the sphere codepath).
+// I suspect det becomes so small that we lose all accuracy when dividing by det and using the result in computing
+// impact distance.
+#define LOCAL_EPSILON 0.00001f
+
+// PT: special version computing (u,v) even when the ray misses the tri. Version working on precomputed edges.
+static PX_FORCE_INLINE PxU32 rayTriSpecial(const PxVec3& orig, const PxVec3& dir, const PxVec3& vert0, const PxVec3& edge1, const PxVec3& edge2, PxReal& t, PxReal& u, PxReal& v)
+{
+ // Begin calculating determinant - also used to calculate U parameter
+ const PxVec3 pvec = dir.cross(edge2);
+
+ // If determinant is near zero, ray lies in plane of triangle
+ const PxReal det = edge1.dot(pvec);
+
+ // the non-culling branch
+// if(det>-GU_CULLING_EPSILON_RAY_TRIANGLE && det<GU_CULLING_EPSILON_RAY_TRIANGLE)
+ if(det>-LOCAL_EPSILON && det<LOCAL_EPSILON)
+ return 0;
+ const PxReal oneOverDet = 1.0f / det;
+
+ // Calculate distance from vert0 to ray origin
+ const PxVec3 tvec = orig - vert0;
+
+ // Calculate U parameter
+ u = (tvec.dot(pvec)) * oneOverDet;
+
+ // prepare to test V parameter
+ const PxVec3 qvec = tvec.cross(edge1);
+
+ // Calculate V parameter
+ v = (dir.dot(qvec)) * oneOverDet;
+
+ if(u<0.0f || u>1.0f)
+ return 1;
+ if(v<0.0f || u+v>1.0f)
+ return 1;
+
+ // Calculate t, ray intersects triangle
+ t = (edge2.dot(qvec)) * oneOverDet;
+
+ return 2;
+}
+
+// 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)
+{
+ {
+ const PxVec3 edge0 = tri[vertIntersectCandidate] - tri[vert0];
+ const PxReal edge0LengthSqr = edge0.dot(edge0);
+
+ const PxVec3 diff = planeIntersectPoint - tri[vert0];
+
+ if (edge0.dot(diff) < edge0LengthSqr) // If the squared edge length is used for comparison, the edge vector does not need to be normalized
+ {
+ secondEdgeVert = vert0;
+ return false;
+ }
+ }
+
+ {
+ const PxVec3 edge1 = tri[vertIntersectCandidate] - tri[vert1];
+ const PxReal edge1LengthSqr = edge1.dot(edge1);
+
+ const PxVec3 diff = planeIntersectPoint - tri[vert1];
+
+ if (edge1.dot(diff) < edge1LengthSqr)
+ {
+ secondEdgeVert = vert1;
+ return false;
+ }
+ }
+ 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)
+{
+ if(testSphere)
+ {
+ PxReal t;
+ if(intersectRaySphere(center, dir, PX_MAX_F32, verts[e0], radius, t))
+ {
+ impactDistance = t;
+ return true;
+ }
+ }
+ else
+ {
+ PxReal t;
+ if(intersectRayCapsule(center, dir, verts[e0], verts[e1], radius, t))
+ {
+ if(t>=0.0f/* && t<MinDist*/)
+ {
+ impactDistance = t;
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool Gu::sweepSphereVSTri(const PxVec3* PX_RESTRICT triVerts, const PxVec3& normal, const PxVec3& center, PxReal radius, const PxVec3& dir, PxReal& impactDistance, bool& directHit, bool testInitialOverlap)
+{
+ // Ok, this new version is now faster than the original code. Needs more testing though.
+
+ directHit = false;
+ const PxVec3 edge10 = triVerts[1] - triVerts[0];
+ const PxVec3 edge20 = triVerts[2] - triVerts[0];
+
+ if(testInitialOverlap) // ### brute force version that always works, but we can probably do better
+ {
+ const PxVec3 cp = closestPtPointTriangle2(center, triVerts[0], triVerts[1], triVerts[2], edge10, edge20);
+ if((cp - center).magnitudeSquared() <= radius*radius)
+ {
+ impactDistance = 0.0f;
+ return true;
+ }
+ }
+
+ #define INTERSECT_POINT (triVerts[1]*u) + (triVerts[2]*v) + (triVerts[0] * (1.0f-u-v))
+
+ PxReal u,v;
+ {
+ PxVec3 R = normal * radius;
+ if(dir.dot(R) >= 0.0f)
+ R = -R;
+
+ // The first point of the sphere to hit the triangle plane is the point of the sphere nearest to
+ // the triangle plane. Hence, we use center - (normal*radius) below.
+
+ // PT: casting against the extruded triangle in direction R is the same as casting from a ray moved by -R
+ PxReal t;
+ const PxU32 r = rayTriSpecial(center-R, dir, triVerts[0], edge10, edge20, t, u, v);
+ if(!r)
+ return false;
+ if(r==2)
+ {
+ if(t<0.0f)
+ return false;
+ impactDistance = t;
+ directHit = true;
+ return true;
+ }
+ }
+
+ //
+ // 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.
+ //
+
+ bool TestSphere;
+ PxU32 e0,e1;
+ if(u<0.0f)
+ {
+ if(v<0.0f)
+ {
+ // 0 or 0-1 or 0-2
+ e0 = 0;
+ const PxVec3 intersectPoint = INTERSECT_POINT;
+ TestSphere = edgeOrVertexTest(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);
+ }
+ else
+ {
+ // 0-2
+ TestSphere = false;
+ e0 = 0;
+ e1 = 2;
+ }
+ }
+ else
+ {
+ if(v<0.0f)
+ {
+ if(u+v>1.0f)
+ {
+ // 1 or 1-0 or 1-2
+ e0 = 1;
+ const PxVec3 intersectPoint = INTERSECT_POINT;
+ TestSphere = edgeOrVertexTest(intersectPoint, triVerts, 1, 0, 2, e1);
+ }
+ else
+ {
+ // 0-1
+ TestSphere = false;
+ e0 = 0;
+ e1 = 1;
+ }
+ }
+ else
+ {
+ PX_ASSERT(u+v>=1.0f); // Else hit triangle
+ // 1-2
+ TestSphere = false;
+ e0 = 1;
+ e1 = 2;
+ }
+ }
+ return testRayVsSphereOrCapsule(impactDistance, TestSphere, center, radius, dir, triVerts, e0, e1);
+}
+
+bool Gu::sweepSphereTriangles( PxU32 nbTris, const PxTriangle* PX_RESTRICT triangles, // Triangle data
+ const PxVec3& center, const PxReal radius, // Sphere data
+ const PxVec3& unitDir, PxReal distance, // Ray data
+ const PxU32* PX_RESTRICT cachedIndex, // Cache data
+ PxSweepHit& h, PxVec3& triNormalOut, // Results
+ bool isDoubleSided, bool meshBothSides, bool anyHit, bool testInitialOverlap) // Query modifiers
+{
+ if(!nbTris)
+ return false;
+
+ const bool doBackfaceCulling = !isDoubleSided && !meshBothSides;
+
+ PxU32 index = PX_INVALID_U32;
+ const PxU32 initIndex = getInitIndex(cachedIndex, nbTris);
+
+ PxReal curT = distance;
+ const PxReal dpc0 = center.dot(unitDir);
+
+ PxReal bestAlignmentValue = 2.0f;
+
+ PxVec3 bestTriNormal(0.0f);
+
+ for(PxU32 ii=0; ii<nbTris; ii++) // We need i for returned triangle index
+ {
+ const PxU32 i = getTriangleIndex(ii, initIndex);
+
+ const PxTriangle& currentTri = triangles[i];
+
+ if(rejectTriangle(center, unitDir, curT, radius, currentTri.verts, dpc0))
+ continue;
+
+ PxVec3 triNormal;
+ currentTri.denormalizedNormal(triNormal);
+
+ // Backface culling
+ if(doBackfaceCulling && (triNormal.dot(unitDir) > 0.0f))
+ continue;
+
+ const PxReal magnitude = triNormal.magnitude();
+ if(magnitude==0.0f)
+ continue;
+
+ triNormal /= magnitude;
+
+ PxReal currentDistance;
+ bool unused;
+ if (!sweepSphereVSTri(currentTri.verts, triNormal, center, radius, unitDir, currentDistance, unused, testInitialOverlap))
+ continue;
+
+ const PxReal distEpsilon = GU_EPSILON_SAME_DISTANCE; // pick a farther hit within distEpsilon that is more opposing than the previous closest hit
+ const PxReal hitDot = computeAlignmentValue(triNormal, unitDir);
+ if (!keepTriangle(currentDistance, hitDot, curT, bestAlignmentValue, distance, distEpsilon))
+ continue;
+
+ if(currentDistance==0.0f)
+ return setInitialOverlapResults(h, unitDir, i);
+
+ curT = currentDistance;
+ index = i;
+ bestAlignmentValue = hitDot;
+ bestTriNormal = triNormal;
+ if(anyHit)
+ break;
+ }
+ return computeSphereTriangleImpactData(h, triNormalOut, index, curT, center, unitDir, bestTriNormal, triangles, isDoubleSided, meshBothSides);
+}
+
+static PX_FORCE_INLINE PxU32 rayQuadSpecial2(const PxVec3& orig, const PxVec3& dir, const PxVec3& vert0, const PxVec3& edge1, const PxVec3& edge2, float& t, float& u, float& v)
+{
+ // Begin calculating determinant - also used to calculate U parameter
+ const PxVec3 pvec = dir.cross(edge2);
+
+ // If determinant is near zero, ray lies in plane of triangle
+ const float det = edge1.dot(pvec);
+
+ // the non-culling branch
+ if(det>-LOCAL_EPSILON && det<LOCAL_EPSILON)
+ return 0;
+ const float OneOverDet = 1.0f / det;
+
+ // Calculate distance from vert0 to ray origin
+ const PxVec3 tvec = orig - vert0;
+
+ // Calculate U parameter
+ u = tvec.dot(pvec) * OneOverDet;
+
+ // prepare to test V parameter
+ const PxVec3 qvec = tvec.cross(edge1);
+
+ // Calculate V parameter
+ v = dir.dot(qvec) * OneOverDet;
+
+ if(u<0.0f || u>1.0f)
+ return 1;
+ if(v<0.0f || v>1.0f)
+ return 1;
+
+ // Calculate t, ray intersects triangle
+ t = edge2.dot(qvec) * OneOverDet;
+
+ return 2;
+}
+
+bool Gu::sweepSphereVSQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& normal, const PxVec3& center, float radius, const PxVec3& dir, float& impactDistance)
+{
+ // Quad formed by 2 tris:
+ // p0 p1 p2
+ // p2 p1 p3 = p3 p2 p1
+ //
+ // p0___p2
+ // | /|
+ // | / |
+ // | / |
+ // |/ |
+ // p1---p3
+ //
+ // Edge10 = p1 - p0
+ // Edge20 = p2 - p0
+ // Impact point = Edge10*u + Edge20*v + p0
+ // => u is along Y, between 0.0 (p0;p2) and 1.0 (p1;p3)
+ // => v is along X, between 0.0 (p0;p1) and 1.0 (p2;p3)
+ //
+ // For the second triangle,
+ // Edge10b = p2 - p3 = -Edge10
+ // Edge20b = p1 - p3 = -Edge20
+
+ const PxVec3 Edge10 = quadVerts[1] - quadVerts[0];
+ const PxVec3 Edge20 = quadVerts[2] - quadVerts[0];
+
+ if(1) // ### brute force version that always works, but we can probably do better
+ {
+ const float r2 = radius*radius;
+ {
+ const PxVec3 Cp = closestPtPointTriangle2(center, quadVerts[0], quadVerts[1], quadVerts[2], Edge10, Edge20);
+ if((Cp - center).magnitudeSquared() <= r2)
+ {
+ impactDistance = 0.0f;
+ return true;
+ }
+ }
+ {
+ const PxVec3 Cp = closestPtPointTriangle2(center, quadVerts[3], quadVerts[2], quadVerts[1], -Edge10, -Edge20);
+ if((Cp - center).magnitudeSquared() <= r2)
+ {
+ impactDistance = 0.0f;
+ return true;
+ }
+ }
+ }
+
+ float u,v;
+ if(1)
+ {
+ PxVec3 R = normal * radius;
+ if(dir.dot(R) >= 0.0f)
+ R = -R;
+
+ // The first point of the sphere to hit the quad plane is the point of the sphere nearest to
+ // the quad plane. Hence, we use center - (normal*radius) below.
+
+ // PT: casting against the extruded quad in direction R is the same as casting from a ray moved by -R
+ float t;
+ PxU32 r = rayQuadSpecial2(center-R, dir, quadVerts[0], Edge10, Edge20, t, u, v);
+ if(!r)
+ return false;
+ if(r==2)
+ {
+ if(t<0.0f)
+ return false;
+ impactDistance = t;
+ return true;
+ }
+ }
+
+ #define INTERSECT_POINT_Q (quadVerts[1]*u) + (quadVerts[2]*v) + (quadVerts[0] * (1.0f-u-v))
+
+ Ps::swap(u,v);
+ bool TestSphere;
+ PxU32 e0,e1;
+ if(u<0.0f)
+ {
+ if(v<0.0f)
+ {
+ // 0 or 0-1 or 0-2
+ e0 = 0;
+ const PxVec3 intersectPoint = INTERSECT_POINT_Q;
+ TestSphere = edgeOrVertexTest(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);
+ }
+ else
+ {
+ // 0-1
+ TestSphere = false;
+ e0 = 0;
+ e1 = 1;
+ }
+ }
+ else if(u>1.0f)
+ {
+ if(v<0.0f)
+ {
+ // 2 or 2-0 or 2-3
+ e0 = 2;
+ const PxVec3 intersectPoint = INTERSECT_POINT_Q;
+ TestSphere = edgeOrVertexTest(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);
+ }
+ else
+ {
+ // 2-3
+ TestSphere = false;
+ e0 = 2;
+ e1 = 3;
+ }
+ }
+ else
+ {
+ if(v<0.0f)
+ {
+ // 0-2
+ TestSphere = false;
+ e0 = 0;
+ e1 = 2;
+ }
+ else
+ {
+ PX_ASSERT(v>=1.0f); // Else hit quad
+ // 1-3
+ TestSphere = false;
+ e0 = 1;
+ e1 = 3;
+ }
+ }
+ return testRayVsSphereOrCapsule(impactDistance, TestSphere, center, radius, dir, quadVerts, e0, e1);
+}
+
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.h
new file mode 100644
index 00000000..a3345e34
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepSphereTriangle.h
@@ -0,0 +1,156 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_SPHERE_TRIANGLE_H
+#define GU_SWEEP_SPHERE_TRIANGLE_H
+
+#include "GuSweepTriangleUtils.h"
+
+namespace physx
+{
+
+namespace Gu
+{
+ /**
+ Sweeps a sphere against a triangle.
+
+ All input parameters (sphere, triangle, sweep direction) must be in the same space. Sweep length is assumed to be infinite.
+
+ By default, 'testInitialOverlap' must be set to true to properly handle the case where the sphere already overlaps the triangle
+ at the start of the sweep. In such a case, returned impact distance is exactly 0.0f. If it is known ahead of time that the sphere
+ cannot overlap the triangle at t=0.0, then 'testInitialOverlap' can be set to false to skip the initial overlap test and make the
+ function run faster.
+
+ If the ray defined by the sphere's center and the unit direction directly intersects the triangle-related part of the TSS (*) (i.e.
+ the prism from the Minkowski sum of the inflated triangle) then 'directHit' is set to true. Otherwise it is set to false.
+
+ (*) For Triangle Swept Sphere, see http://gamma.cs.unc.edu/SSV/ssv.pdf for the origin of these names.
+
+ \param triVerts [in] triangle vertices
+ \param triUnitNormal [in] triangle's normalized normal
+ \param sphereCenter [in] sphere's center
+ \param sphereRadius [in] sphere's radius
+ \param unitDir [in] normalized sweep direction.
+ \param impactDistance [out] impact distance, if a hit has been found. Does not need to be initialized before calling the function.
+ \param directHit [out] true if a direct hit has been found, see comments above.
+ \param testInitialOverlap [in] true if an initial sphere-vs-triangle overlap test must be performed, see comments above.
+
+ \return true if an impact has been found (in which case returned result values are valid)
+ */
+ bool sweepSphereVSTri( const PxVec3* PX_RESTRICT triVerts, const PxVec3& triUnitNormal,// Triangle data
+ const PxVec3& sphereCenter, PxReal sphereRadius, // Sphere data
+ const PxVec3& unitDir, // Ray data
+ PxReal& impactDistance, bool& directHit, // Results
+ bool testInitialOverlap); // Query modifier
+
+ /**
+ Sweeps a sphere against a quad.
+
+ All input parameters (sphere, quad, sweep direction) must be in the same space. Sweep length is assumed to be infinite.
+
+ Quad must be formed by 2 tris like this:
+
+ p0___p2
+ | /|
+ | / |
+ | / |
+ |/ |
+ p1---p3
+
+ \param quadVerts [in] quad vertices
+ \param quadUnitNormal [in] quad's normalized normal
+ \param sphereCenter [in] sphere's center
+ \param sphereRadius [in] sphere's radius
+ \param unitDir [in] normalized sweep direction.
+ \param impactDistance [out] impact distance, if a hit has been found. Does not need to be initialized before calling the function.
+
+ \return true if an impact has been found (in which case returned result values are valid)
+ */
+ bool sweepSphereVSQuad( const PxVec3* PX_RESTRICT quadVerts, const PxVec3& quadUnitNormal, // Quad data
+ const PxVec3& sphereCenter, float sphereRadius, // Sphere data
+ const PxVec3& unitDir, // Ray data
+ float& impactDistance); // Results
+
+
+ // PT: computes proper impact data for sphere-sweep-vs-tri, after the closest tri has been found
+ PX_FORCE_INLINE bool computeSphereTriangleImpactData(PxSweepHit& h, PxVec3& triNormalOut, PxU32 index, PxReal curT,
+ const PxVec3& center, const PxVec3& unitDir, const PxVec3& bestTriNormal,
+ const PxTriangle* PX_RESTRICT triangles,
+ bool isDoubleSided, bool meshBothSides)
+ {
+ if(index==PX_INVALID_U32)
+ return false; // We didn't touch any triangle
+
+ // Compute impact data only once, using best triangle
+ PxVec3 hitPos, normal;
+ computeSphereTriImpactData(hitPos, normal, center, unitDir, curT, triangles[index]);
+
+ // PT: by design, returned normal is opposed to the sweep direction.
+ if(shouldFlipNormal(normal, meshBothSides, isDoubleSided, bestTriNormal, unitDir))
+ normal = -normal;
+
+ h.position = hitPos;
+ h.normal = normal;
+ h.distance = curT;
+ h.faceIndex = index;
+ h.flags = PxHitFlag::eDISTANCE|PxHitFlag::eNORMAL|PxHitFlag::ePOSITION;
+ triNormalOut = bestTriNormal;
+ return true;
+ }
+
+ /**
+ Sweeps a sphere against a set of triangles.
+
+ \param nbTris [in] number of triangles in input array
+ \param triangles [in] array of input triangles
+ \param center [in] sphere's center
+ \param radius [in] sphere's radius
+ \param unitDir [in] sweep's unit direcion
+ \param distance [in] sweep's length
+ \param cachedIndex [in] cached triangle index, or NULL. Cached triangle will be tested first.
+ \param hit [out] results
+ \param triNormalOut [out] triangle normal
+ \param isDoubleSided [in] true if input triangles are double-sided
+ \param meshBothSides [in] true if PxHitFlag::eMESH_BOTH_SIDES is used
+ \param anyHit [in] true if PxHitFlag::eMESH_ANY is used
+ \param testInitialOverlap [in] true if PxHitFlag::eASSUME_NO_INITIAL_OVERLAP is not used
+ \return true if an impact has been found
+ */
+ bool sweepSphereTriangles( PxU32 nbTris, const PxTriangle* PX_RESTRICT triangles, // Triangle data
+ const PxVec3& center, const PxReal radius, // Sphere data
+ const PxVec3& unitDir, PxReal distance, // Ray data
+ const PxU32* PX_RESTRICT cachedIndex, // Cache data
+ PxSweepHit& hit, PxVec3& triNormalOut, // Results
+ bool isDoubleSided, bool meshBothSides, bool anyHit, bool testInitialOverlap); // Query modifiers
+
+} // namespace Gu
+
+}
+
+#endif
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.cpp b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.cpp
new file mode 100644
index 00000000..a69ae54d
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.cpp
@@ -0,0 +1,223 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#include "foundation/PxBounds3.h"
+#include "GuSweepTriangleUtils.h"
+#include "GuDistancePointTriangle.h"
+#include "GuVecTriangle.h"
+#include "GuVecBox.h"
+#include "GuSweepBoxTriangle_FeatureBased.h"
+#include "GuInternal.h"
+#include "GuGJK.h"
+
+using namespace physx;
+using namespace Gu;
+using namespace physx::shdfnd::aos;
+
+#define GU_SAFE_DISTANCE_FOR_NORMAL_COMPUTATION 0.1f
+
+void Gu::computeSphereTriImpactData(PxVec3& hit, PxVec3& normal, const PxVec3& center, const PxVec3& dir, float t, const PxTriangle& tri)
+{
+ const PxVec3 newSphereCenter = center + dir*t;
+
+ // We need the impact point, not computed by the new code
+ PxReal u_unused, v_unused;
+ const PxVec3 localHit = closestPtPointTriangle(newSphereCenter, tri.verts[0], tri.verts[1], tri.verts[2], u_unused, v_unused);
+ PX_UNUSED(u_unused);
+ PX_UNUSED(v_unused);
+
+ // This is responsible for the cap-vs-box stuck while jumping. However it's needed to slide on box corners!
+ // PT: this one is also dubious since the sphere/capsule center can be far away from the hit point when the radius is big!
+ PxVec3 localNormal = newSphereCenter - localHit;
+ const PxReal m = localNormal.normalize();
+ if(m<1e-3f)
+ tri.normal(localNormal);
+
+ hit = localHit;
+ normal = localNormal;
+}
+
+// PT: not inlining this rarely-run function makes the benchmark ~500.000 cycles faster...
+// PT: using this version all the time makes the benchmark ~300.000 cycles slower. So we just use it as a backup.
+static bool runBackupProcedure(PxVec3& hit, PxVec3& normal, const PxVec3& localMotion, const PxVec3& boxExtents, const PxTriangle& triInBoxSpace)
+{
+ const Vec3V v0 = V3LoadU(triInBoxSpace.verts[0]);
+ const Vec3V v1 = V3LoadU(triInBoxSpace.verts[1]);
+ const Vec3V v2 = V3LoadU(triInBoxSpace.verts[2]);
+
+ const TriangleV triangleV(v0, v1, v2);
+
+ // PT: the box is in the triangle's space already
+ //BoxV boxV(V3LoadU(PxVec3(0.0f)), V3LoadU(boxExtents),
+ // V3LoadU(PxVec3(1.0f, 0.0f, 0.0f)), V3LoadU(PxVec3(0.0f, 1.0f, 0.0f)), V3LoadU(PxVec3(0.0f, 0.0f, 1.0f)));
+
+ const BoxV boxV(V3Zero(), V3LoadU(boxExtents));
+
+ Vec3V closestA;
+ Vec3V closestB;
+ Vec3V normalV;
+ FloatV distV;
+ LocalConvex<TriangleV> convexA(triangleV);
+ LocalConvex<BoxV> convexB(boxV);
+ const Vec3V initialSearchDir = V3Sub(triangleV.getCenter(), boxV.getCenter());
+ const FloatV contactDist = FMax();
+ GjkStatus status_ = gjk<LocalConvex<TriangleV>, LocalConvex<BoxV> >(convexA, convexB, initialSearchDir, contactDist, closestA, closestB, normalV, distV);
+
+ if(status_==GJK_CONTACT)
+ return false;
+
+ PxVec3 ml_closestB;
+ PxVec3 ml_normal;
+ V3StoreU(closestB, ml_closestB);
+ V3StoreU(normalV, ml_normal);
+
+ hit = ml_closestB + localMotion;
+// normal = -ml_normal;
+ if((ml_normal.dot(localMotion))>0.0f)
+ ml_normal = -ml_normal;
+ normal = ml_normal;
+ return true;
+}
+
+void Gu::computeBoxTriImpactData(PxVec3& hit, PxVec3& normal, const PxVec3& boxExtents, const PxVec3& localDir, const PxTriangle& triInBoxSpace, PxReal impactDist)
+{
+ // PT: the triangle is in "box space", i.e. the box can be seen as an AABB centered around the origin.
+
+ // PT: compute impact point/normal in a second pass. Here we simply re-sweep the box against the best triangle,
+ // using the feature-based code (which computes impact point and normal). This is not great because:
+ // - we know there's an impact so why do all tests again?
+ // - the SAT test & the feature-based tests could return different results because of FPU accuracy.
+ // The backup procedure makes sure we compute a proper answer even when the SAT and feature-based versions differ.
+ const PxBounds3 aabb(-boxExtents, boxExtents);
+
+ const PxVec3 oneOverDir(
+ localDir.x!=0.0f ? 1.0f/localDir.x : 0.0f,
+ localDir.y!=0.0f ? 1.0f/localDir.y : 0.0f,
+ localDir.z!=0.0f ? 1.0f/localDir.z : 0.0f);
+
+ // PT: TODO: this is the only place left using sweepBoxTriangle()
+ // Backface culling could be removed here since we know we want a hit no matter what. Plus, it's sometimes
+ // incorrectly culled and we hit the backup procedure for no reason. On Win32Modern for unknown reasons
+ // returned normal is sometimes (0,0,0). In these cases we also switch to the backup procedure.
+ float t = PX_MAX_F32; // PT: no need to initialize with best dist here since we want a hit no matter what
+ if(!sweepBoxTriangle(triInBoxSpace, aabb, localDir, oneOverDir, hit, normal, t) || normal.isZero())
+ {
+ // PT: move triangle close to box
+ const PxVec3 localMotion = localDir*impactDist;
+
+ const PxVec3 delta = localMotion - localDir*GU_SAFE_DISTANCE_FOR_NORMAL_COMPUTATION;
+ const PxTriangle movedTriangle(
+ triInBoxSpace.verts[0] - delta,
+ triInBoxSpace.verts[1] - delta,
+ triInBoxSpace.verts[2] - delta);
+
+ if(!runBackupProcedure(hit, normal, localMotion, boxExtents, movedTriangle))
+ {
+ // PT: if the backup procedure fails, we give up
+ hit = PxVec3(0.0f);
+ normal = -localDir;
+ }
+ }
+}
+
+// PT: copy where we know that input vectors are not zero
+static PX_FORCE_INLINE void edgeEdgeDistNoZeroVector( PxVec3& x, PxVec3& y, // closest points
+ const PxVec3& p, const PxVec3& a, // seg 1 origin, vector
+ const PxVec3& q, const PxVec3& b) // seg 2 origin, vector
+{
+ const PxVec3 T = q - p;
+ const PxReal ADotA = a.dot(a);
+ const PxReal BDotB = b.dot(b);
+ PX_ASSERT(ADotA!=0.0f);
+ PX_ASSERT(BDotB!=0.0f);
+ const PxReal ADotB = a.dot(b);
+ const PxReal ADotT = a.dot(T);
+ const PxReal BDotT = b.dot(T);
+
+ // t parameterizes ray (p, a)
+ // u parameterizes ray (q, b)
+
+ // Compute t for the closest point on ray (p, a) to ray (q, b)
+ const PxReal Denom = ADotA*BDotB - ADotB*ADotB;
+
+ PxReal t;
+ if(Denom!=0.0f)
+ {
+ t = (ADotT*BDotB - BDotT*ADotB) / Denom;
+
+ // Clamp result so t is on the segment (p, a)
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ else
+ {
+ t = 0.0f;
+ }
+
+ // find u for point on ray (q, b) closest to point at t
+ PxReal u;
+ {
+ u = (t*ADotB - BDotT) / BDotB;
+
+ // if u is on segment (q, b), t and u correspond to closest points, otherwise, clamp u, recompute and clamp t
+ if(u<0.0f)
+ {
+ u = 0.0f;
+ t = ADotT / ADotA;
+
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ else if(u > 1.0f)
+ {
+ u = 1.0f;
+ t = (ADotB + ADotT) / ADotA;
+
+ if(t<0.0f) t = 0.0f;
+ else if(t>1.0f) t = 1.0f;
+ }
+ }
+
+ x = p + a * t;
+ y = q + b * u;
+}
+
+void Gu::computeEdgeEdgeNormal(PxVec3& normal, const PxVec3& p1, const PxVec3& p2_p1, const PxVec3& p3, const PxVec3& p4_p3, const PxVec3& dir, float d)
+{
+ // PT: cross-product doesn't produce nice normals so we use an edge-edge distance function itself
+
+ // PT: move the edges "0.1" units from each other before the computation. If the edges are too far
+ // away, computed normal tend to align itself with the swept direction. If the edges are too close,
+ // closest points x and y become identical and we can't compute a proper normal.
+ const PxVec3 p1s = p1 + dir*(d-GU_SAFE_DISTANCE_FOR_NORMAL_COMPUTATION);
+
+ PxVec3 x, y;
+ edgeEdgeDistNoZeroVector(x, y, p1s, p2_p1, p3, p4_p3);
+ normal = x - y;
+}
diff --git a/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.h b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.h
new file mode 100644
index 00000000..302cd595
--- /dev/null
+++ b/PhysX_3.4/Source/GeomUtils/src/sweep/GuSweepTriangleUtils.h
@@ -0,0 +1,338 @@
+// This code contains NVIDIA Confidential Information and is disclosed to you
+// under a form of NVIDIA software license agreement provided separately to you.
+//
+// Notice
+// NVIDIA Corporation and its licensors retain all intellectual property and
+// proprietary rights in and to this software and related documentation and
+// any modifications thereto. Any use, reproduction, disclosure, or
+// distribution of this software and related documentation without an express
+// license agreement from NVIDIA Corporation is strictly prohibited.
+//
+// ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
+// NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
+// THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
+// MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
+//
+// Information and code furnished is believed to be accurate and reliable.
+// However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
+// information or for any infringement of patents or other rights of third parties that may
+// result from its use. No license is granted by implication or otherwise under any patent
+// or patent rights of NVIDIA Corporation. Details are subject to change without notice.
+// This code supersedes and replaces all information previously supplied.
+// NVIDIA Corporation products are not authorized for use as critical
+// components in life support devices or systems without express written approval of
+// NVIDIA Corporation.
+//
+// Copyright (c) 2008-2016 NVIDIA Corporation. All rights reserved.
+// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
+// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
+
+#ifndef GU_SWEEP_TRIANGLE_UTILS_H
+#define GU_SWEEP_TRIANGLE_UTILS_H
+
+#include "CmPhysXCommon.h"
+#include "GuSweepSharedTests.h"
+#include "GuInternal.h"
+#include "PxTriangle.h"
+#include "PxQueryReport.h"
+
+namespace physx
+{
+
+namespace Gu
+{
+ // PT: computes proper impact data for sphere-sweep-vs-tri, after the closest tri has been found.
+ void computeSphereTriImpactData(PxVec3& hit, PxVec3& normal, const PxVec3& center, const PxVec3& dir, float t, const PxTriangle& tri);
+
+ // PT: computes proper impact data for box-sweep-vs-tri, after the closest tri has been found.
+ void computeBoxTriImpactData(PxVec3& hit, PxVec3& normal, const PxVec3& boxExtents, const PxVec3& localDir, const PxTriangle& triInBoxSpace, PxReal impactDist);
+
+ // PT: computes impact normal between two edges. Produces better normals than just the EE cross product.
+ // This version properly computes the closest points between two colliding edges and makes a normal from these.
+ void computeEdgeEdgeNormal(PxVec3& normal, const PxVec3& p1, const PxVec3& p2_p1, const PxVec3& p3, const PxVec3& p4_p3, const PxVec3& dir, float d);
+
+ // PT: small function just to avoid duplicating the code.
+ // Returns index of first triangle we should process (when processing arrays of input triangles)
+ PX_FORCE_INLINE PxU32 getInitIndex(const PxU32* PX_RESTRICT cachedIndex, PxU32 nbTris)
+ {
+ PxU32 initIndex = 0; // PT: by default the first triangle to process is just the first one in the array
+ if(cachedIndex) // PT: but if we cached the last closest triangle from a previous call...
+ {
+ PX_ASSERT(*cachedIndex < nbTris);
+ PX_UNUSED(nbTris);
+ initIndex = *cachedIndex; // PT: ...then we should start with that one, to potentially shrink the ray as early as possible
+ }
+ return initIndex;
+ }
+
+ // PT: quick triangle rejection for sphere-based sweeps.
+ // Please refer to \\sw\physx\PhysXSDK\3.4\trunk\InternalDocumentation\GU\cullTriangle.png for details & diagram.
+ PX_FORCE_INLINE bool cullTriangle(const PxVec3* PX_RESTRICT triVerts, const PxVec3& dir, PxReal radius, PxReal t, const PxReal dpc0)
+ {
+ // PT: project triangle on axis
+ const PxReal dp0 = triVerts[0].dot(dir);
+ const PxReal dp1 = triVerts[1].dot(dir);
+ const PxReal dp2 = triVerts[2].dot(dir);
+
+ // PT: keep min value = earliest possible impact distance
+ PxReal dp = dp0;
+ dp = physx::intrinsics::selectMin(dp, dp1);
+ dp = physx::intrinsics::selectMin(dp, dp2);
+
+ // PT: make sure we keep triangles that are about as close as best current distance
+ radius += 0.001f + GU_EPSILON_SAME_DISTANCE;
+
+ // PT: if earliest possible impact distance for this triangle is already larger than
+ // sphere's current best known impact distance, we can skip the triangle
+ if(dp>dpc0 + t + radius)
+ {
+ //PX_ASSERT(resx == 0.0f);
+ return false;
+ }
+
+ // PT: if triangle is fully located before the sphere's initial position, skip it too
+ const PxReal dpc1 = dpc0 - radius;
+ if(dp0<dpc1 && dp1<dpc1 && dp2<dpc1)
+ {
+ //PX_ASSERT(resx == 0.0f);
+ return false;
+ }
+
+ //PX_ASSERT(resx != 0.0f);
+ return true;
+ }
+
+ // PT: quick quad rejection for sphere-based sweeps. Same as for triangle, adapted for one more vertex.
+ PX_FORCE_INLINE bool cullQuad(const PxVec3* PX_RESTRICT quadVerts, const PxVec3& dir, PxReal radius, PxReal t, const PxReal dpc0)
+ {
+ // PT: project quad on axis
+ const PxReal dp0 = quadVerts[0].dot(dir);
+ const PxReal dp1 = quadVerts[1].dot(dir);
+ const PxReal dp2 = quadVerts[2].dot(dir);
+ const PxReal dp3 = quadVerts[3].dot(dir);
+
+ // PT: keep min value = earliest possible impact distance
+ PxReal dp = dp0;
+ dp = physx::intrinsics::selectMin(dp, dp1);
+ dp = physx::intrinsics::selectMin(dp, dp2);
+ dp = physx::intrinsics::selectMin(dp, dp3);
+
+ // PT: make sure we keep quads that are about as close as best current distance
+ radius += 0.001f;
+
+ // PT: if earliest possible impact distance for this quad is already larger than
+ // sphere's current best known impact distance, we can skip the quad
+ if(dp>dpc0 + t + radius)
+ return false;
+
+ // PT: if quad is fully located before the sphere's initial position, skip it too
+ const float dpc1 = dpc0 - radius;
+ if(dp0<dpc1 && dp1<dpc1 && dp2<dpc1 && dp3<dpc1)
+ return false;
+
+ return true;
+ }
+
+ // PT: computes distance between a point 'point' and a segment. The segment is defined as a starting point 'p0'
+ // and a direction vector 'dir' plus a length 't'. Segment's endpoint is p0 + dir * t.
+ //
+ // point
+ // o
+ // __/|
+ // __/ / |
+ // __/ / |(B)
+ // __/ (A)/ |
+ // __/ / | dir
+ // p0 o/---------o---------------o-- -->
+ // t (t<=fT) t (t>fT)
+ // return (A)^2 return (B)^2
+ //
+ // |<-------------->|
+ // fT
+ //
+ PX_FORCE_INLINE PxReal squareDistance(const PxVec3& p0, const PxVec3& dir, PxReal t, const PxVec3& point)
+ {
+ PxVec3 diff = point - p0;
+ PxReal fT = diff.dot(dir);
+ fT = physx::intrinsics::selectMax(fT, 0.0f);
+ fT = physx::intrinsics::selectMin(fT, t);
+ diff -= fT*dir;
+ return diff.magnitudeSquared();
+ }
+
+ // PT: quick triangle culling for sphere-based sweeps
+ // Please refer to \\sw\physx\PhysXSDK\3.4\trunk\InternalDocumentation\GU\coarseCulling.png for details & diagram.
+ PX_FORCE_INLINE bool coarseCullingTri(const PxVec3& center, const PxVec3& dir, PxReal t, PxReal radius, const PxVec3* PX_RESTRICT triVerts)
+ {
+ // PT: compute center of triangle ### could be precomputed?
+ const PxVec3 triCenter = (triVerts[0] + triVerts[1] + triVerts[2]) * (1.0f/3.0f);
+
+ // PT: distance between the triangle center and the swept path (an LSS)
+ // Same as: distancePointSegmentSquared(center, center+dir*t, TriCenter);
+ PxReal d = PxSqrt(squareDistance(center, dir, t, triCenter)) - radius - 0.0001f;
+
+ if (d < 0.0f) // The triangle center lies inside the swept sphere
+ return true;
+
+ d*=d;
+
+ // PT: coarse capsule-vs-triangle overlap test ### distances could be precomputed?
+ if(1)
+ {
+ if(d <= (triCenter-triVerts[0]).magnitudeSquared())
+ return true;
+ if(d <= (triCenter-triVerts[1]).magnitudeSquared())
+ return true;
+ if(d <= (triCenter-triVerts[2]).magnitudeSquared())
+ return true;
+ }
+ else
+ {
+ const float d0 = (triCenter-triVerts[0]).magnitudeSquared();
+ const float d1 = (triCenter-triVerts[1]).magnitudeSquared();
+ const float d2 = (triCenter-triVerts[2]).magnitudeSquared();
+ float triRadius = physx::intrinsics::selectMax(d0, d1);
+ triRadius = physx::intrinsics::selectMax(triRadius, d2);
+ if(d <= triRadius)
+ return true;
+ }
+ return false;
+ }
+
+ // PT: quick quad culling for sphere-based sweeps. Same as for triangle, adapted for one more vertex.
+ PX_FORCE_INLINE bool coarseCullingQuad(const PxVec3& center, const PxVec3& dir, PxReal t, PxReal radius, const PxVec3* PX_RESTRICT quadVerts)
+ {
+ // PT: compute center of quad ### could be precomputed?
+ const PxVec3 quadCenter = (quadVerts[0] + quadVerts[1] + quadVerts[2] + quadVerts[3]) * (1.0f/4.0f);
+
+ // PT: distance between the quad center and the swept path (an LSS)
+ PxReal d = PxSqrt(squareDistance(center, dir, t, quadCenter)) - radius - 0.0001f;
+
+ if (d < 0.0f) // The quad center lies inside the swept sphere
+ return true;
+
+ d*=d;
+
+ // PT: coarse capsule-vs-quad overlap test ### distances could be precomputed?
+ if(1)
+ {
+ if(d <= (quadCenter-quadVerts[0]).magnitudeSquared())
+ return true;
+ if(d <= (quadCenter-quadVerts[1]).magnitudeSquared())
+ return true;
+ if(d <= (quadCenter-quadVerts[2]).magnitudeSquared())
+ return true;
+ if(d <= (quadCenter-quadVerts[3]).magnitudeSquared())
+ return true;
+ }
+ return false;
+ }
+
+ // PT: combined triangle culling for sphere-based sweeps
+ PX_FORCE_INLINE bool rejectTriangle(const PxVec3& center, const PxVec3& unitDir, PxReal curT, PxReal radius, const PxVec3* PX_RESTRICT triVerts, const PxReal dpc0)
+ {
+ if(!coarseCullingTri(center, unitDir, curT, radius, triVerts))
+ return true;
+ if(!cullTriangle(triVerts, unitDir, radius, curT, dpc0))
+ return true;
+ return false;
+ }
+
+ // PT: combined quad culling for sphere-based sweeps
+ PX_FORCE_INLINE bool rejectQuad(const PxVec3& center, const PxVec3& unitDir, PxReal curT, PxReal radius, const PxVec3* PX_RESTRICT quadVerts, const PxReal dpc0)
+ {
+ if(!coarseCullingQuad(center, unitDir, curT, radius, quadVerts))
+ return true;
+ if(!cullQuad(quadVerts, unitDir, radius, curT, dpc0))
+ return true;
+ return false;
+ }
+
+ PX_FORCE_INLINE bool shouldFlipNormal(const PxVec3& normal, bool meshBothSides, bool isDoubleSided, const PxVec3& triangleNormal, const PxVec3& dir)
+ {
+ // PT: this function assumes that input normal is opposed to the ray/sweep direction. This is always
+ // what we want except when we hit a single-sided back face with 'meshBothSides' enabled.
+
+ if(!meshBothSides || isDoubleSided)
+ return false;
+
+ PX_ASSERT(normal.dot(dir) <= 0.0f); // PT: if this fails, the logic below cannot be applied
+ PX_UNUSED(normal);
+ return triangleNormal.dot(dir) > 0.0f; // PT: true for back-facing hits
+ }
+
+ PX_FORCE_INLINE bool shouldFlipNormal(const PxVec3& normal, bool meshBothSides, bool isDoubleSided, const PxTriangle& triangle, const PxVec3& dir, const PxTransform* pose)
+ {
+ // PT: this function assumes that input normal is opposed to the ray/sweep direction. This is always
+ // what we want except when we hit a single-sided back face with 'meshBothSides' enabled.
+
+ if(!meshBothSides || isDoubleSided)
+ return false;
+
+ PX_ASSERT(normal.dot(dir) <= 0.0f); // PT: if this fails, the logic below cannot be applied
+ PX_UNUSED(normal);
+
+ PxVec3 triangleNormal;
+ triangle.denormalizedNormal(triangleNormal);
+
+ if(pose)
+ triangleNormal = pose->rotate(triangleNormal);
+
+ return triangleNormal.dot(dir) > 0.0f; // PT: true for back-facing hits
+ }
+
+ // PT: implements the spec for IO sweeps in a single place (to ensure consistency)
+ PX_FORCE_INLINE bool setInitialOverlapResults(PxSweepHit& hit, const PxVec3& unitDir, PxU32 faceIndex)
+ {
+ // PT: please write these fields in the order they are listed in the struct.
+ hit.faceIndex = faceIndex;
+ hit.flags = PxHitFlag::eDISTANCE|PxHitFlag::eNORMAL|PxHitFlag::eFACE_INDEX;
+ hit.normal = -unitDir;
+ hit.distance = 0.0f;
+ return true; // PT: true indicates a hit, saves some lines in calling code
+ }
+
+ PX_FORCE_INLINE void computeBoxLocalImpact( PxVec3& pos, PxVec3& normal, PxHitFlags& outFlags,
+ const Box& box, const PxVec3& localDir, const PxTriangle& triInBoxSpace,
+ const PxHitFlags inFlags, bool isDoubleSided, bool meshBothSides, PxReal impactDist)
+ {
+ if(inFlags & (PxHitFlag::eNORMAL|PxHitFlag::ePOSITION))
+ {
+ PxVec3 localPos, localNormal;
+ computeBoxTriImpactData(localPos, localNormal, box.extents, localDir, triInBoxSpace, impactDist);
+
+ if(inFlags & PxHitFlag::eNORMAL)
+ {
+ localNormal.normalize();
+
+ // PT: doing this after the 'rotate' minimizes errors when normal and dir are close to perpendicular
+ // ....but we must do it before the rotate now, because triangleNormal is in box space (and thus we
+ // need the normal with the proper orientation, in box space. We can't fix it after it's been rotated
+ // to box space.
+ // Technically this one is only here because of the EE cross product in the feature-based sweep.
+ // PT: TODO: revisit corresponding code in computeImpactData, get rid of ambiguity
+ // PT: TODO: this may not be needed anymore
+ if((localNormal.dot(localDir))>0.0f)
+ localNormal = -localNormal;
+
+ // PT: this one is to ensure the normal respects the mesh-both-sides/double-sided convention
+ if(shouldFlipNormal(localNormal, meshBothSides, isDoubleSided, triInBoxSpace, localDir, NULL))
+ localNormal = -localNormal;
+
+ normal = box.rotate(localNormal);
+ outFlags |= PxHitFlag::eNORMAL;
+ }
+
+ if(inFlags & PxHitFlag::ePOSITION)
+ {
+ pos = box.transform(localPos);
+ outFlags |= PxHitFlag::ePOSITION;
+ }
+ }
+ }
+
+} // namespace Gu
+
+}
+
+#endif