diff options
| author | git perforce import user <a@b> | 2016-10-25 12:29:14 -0600 |
|---|---|---|
| committer | Sheikh Dawood Abdul Ajees <Sheikh Dawood Abdul Ajees> | 2016-10-25 18:56:37 -0500 |
| commit | 3dfe2108cfab31ba3ee5527e217d0d8e99a51162 (patch) | |
| tree | fa6485c169e50d7415a651bf838f5bcd0fd3bfbd /PhysX_3.4/Source/GeomUtils/src/sweep | |
| download | physx-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')
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 |