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/intersection | |
| 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/intersection')
18 files changed, 2367 insertions, 0 deletions
diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionBoxBox.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionBoxBox.cpp new file mode 100644 index 00000000..19c8c1d0 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionBoxBox.cpp @@ -0,0 +1,139 @@ +// 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 "GuIntersectionBoxBox.h" + +using namespace physx; + +bool Gu::intersectOBBOBB(const PxVec3& e0, const PxVec3& c0, const PxMat33& r0, const PxVec3& e1, const PxVec3& c1, const PxMat33& r1, bool full_test) +{ + // Translation, in parent frame + const PxVec3 v = c1 - c0; + // Translation, in A's frame + const PxVec3 T(v.dot(r0[0]), v.dot(r0[1]), v.dot(r0[2])); + + // B's basis with respect to A's local frame + PxReal R[3][3]; + PxReal FR[3][3]; + PxReal ra, rb, t; + + // Calculate rotation matrix + for(PxU32 i=0;i<3;i++) + { + for(PxU32 k=0;k<3;k++) + { + R[i][k] = r0[i].dot(r1[k]); + FR[i][k] = 1e-6f + PxAbs(R[i][k]); // Precompute fabs matrix + } + } + + // A's basis vectors + for(PxU32 i=0;i<3;i++) + { + ra = e0[i]; + + rb = e1[0]*FR[i][0] + e1[1]*FR[i][1] + e1[2]*FR[i][2]; + + t = PxAbs(T[i]); + + if(t > ra + rb) return false; + } + + // B's basis vectors + for(PxU32 k=0;k<3;k++) + { + ra = e0[0]*FR[0][k] + e0[1]*FR[1][k] + e0[2]*FR[2][k]; + + rb = e1[k]; + + t = PxAbs(T[0]*R[0][k] + T[1]*R[1][k] + T[2]*R[2][k]); + + if( t > ra + rb ) return false; + } + + if(full_test) + { + //9 cross products + + //L = A0 x B0 + ra = e0[1]*FR[2][0] + e0[2]*FR[1][0]; + rb = e1[1]*FR[0][2] + e1[2]*FR[0][1]; + t = PxAbs(T[2]*R[1][0] - T[1]*R[2][0]); + if(t > ra + rb) return false; + + //L = A0 x B1 + ra = e0[1]*FR[2][1] + e0[2]*FR[1][1]; + rb = e1[0]*FR[0][2] + e1[2]*FR[0][0]; + t = PxAbs(T[2]*R[1][1] - T[1]*R[2][1]); + if(t > ra + rb) return false; + + //L = A0 x B2 + ra = e0[1]*FR[2][2] + e0[2]*FR[1][2]; + rb = e1[0]*FR[0][1] + e1[1]*FR[0][0]; + t = PxAbs(T[2]*R[1][2] - T[1]*R[2][2]); + if(t > ra + rb) return false; + + //L = A1 x B0 + ra = e0[0]*FR[2][0] + e0[2]*FR[0][0]; + rb = e1[1]*FR[1][2] + e1[2]*FR[1][1]; + t = PxAbs(T[0]*R[2][0] - T[2]*R[0][0]); + if(t > ra + rb) return false; + + //L = A1 x B1 + ra = e0[0]*FR[2][1] + e0[2]*FR[0][1]; + rb = e1[0]*FR[1][2] + e1[2]*FR[1][0]; + t = PxAbs(T[0]*R[2][1] - T[2]*R[0][1]); + if(t > ra + rb) return false; + + //L = A1 x B2 + ra = e0[0]*FR[2][2] + e0[2]*FR[0][2]; + rb = e1[0]*FR[1][1] + e1[1]*FR[1][0]; + t = PxAbs(T[0]*R[2][2] - T[2]*R[0][2]); + if(t > ra + rb) return false; + + //L = A2 x B0 + ra = e0[0]*FR[1][0] + e0[1]*FR[0][0]; + rb = e1[1]*FR[2][2] + e1[2]*FR[2][1]; + t = PxAbs(T[1]*R[0][0] - T[0]*R[1][0]); + if(t > ra + rb) return false; + + //L = A2 x B1 + ra = e0[0]*FR[1][1] + e0[1]*FR[0][1]; + rb = e1[0] *FR[2][2] + e1[2]*FR[2][0]; + t = PxAbs(T[1]*R[0][1] - T[0]*R[1][1]); + if(t > ra + rb) return false; + + //L = A2 x B2 + ra = e0[0]*FR[1][2] + e0[1]*FR[0][2]; + rb = e1[0]*FR[2][1] + e1[1]*FR[2][0]; + t = PxAbs(T[1]*R[0][2] - T[0]*R[1][2]); + if(t > ra + rb) return false; + } + return true; +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionCapsuleTriangle.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionCapsuleTriangle.cpp new file mode 100644 index 00000000..6451405c --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionCapsuleTriangle.cpp @@ -0,0 +1,61 @@ +// 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 "GuIntersectionCapsuleTriangle.h" +#include "GuDistancePointSegment.h" + +using namespace physx; +using namespace Gu; + +bool Gu::intersectCapsuleTriangle(const PxVec3& N, const PxVec3& p0, const PxVec3& p1, const PxVec3& p2, const Gu::Capsule& capsule, const CapsuleTriangleOverlapData& params) +{ + PX_ASSERT(capsule.p0!=capsule.p1); + + { + const PxReal d2 = distancePointSegmentSquaredInternal(capsule.p0, params.mCapsuleDir, p0); + if(d2<=capsule.radius*capsule.radius) + return true; + } + +// const PxVec3 N = (p0 - p1).cross(p0 - p2); + + if(!testAxis(p0, p1, p2, capsule, N)) + return false; + + if(!testAxis(p0, p1, p2, capsule, computeEdgeAxis(p0, p1 - p0, capsule.p0, params.mCapsuleDir, params.mBDotB, params.mOneOverBDotB))) + return false; + + if(!testAxis(p0, p1, p2, capsule, computeEdgeAxis(p1, p2 - p1, capsule.p0, params.mCapsuleDir, params.mBDotB, params.mOneOverBDotB))) + return false; + + if(!testAxis(p0, p1, p2, capsule, computeEdgeAxis(p2, p0 - p2, capsule.p0, params.mCapsuleDir, params.mBDotB, params.mOneOverBDotB))) + return false; + + return true; +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionCapsuleTriangle.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionCapsuleTriangle.h new file mode 100644 index 00000000..1e327360 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionCapsuleTriangle.h @@ -0,0 +1,137 @@ +// 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_INTERSECTION_CAPSULE_TRIANGLE_H +#define GU_INTERSECTION_CAPSULE_TRIANGLE_H + +#include "CmPhysXCommon.h" +#include "GuCapsule.h" +#include "PsUtilities.h" + +namespace physx +{ +namespace Gu +{ + // PT: precomputed data for capsule-triangle test. Useful when testing the same capsule vs several triangles. + struct CapsuleTriangleOverlapData + { + PxVec3 mCapsuleDir; + float mBDotB; + float mOneOverBDotB; + + void init(const Capsule& capsule) + { + const PxVec3 dir = capsule.p1 - capsule.p0; + const float BDotB = dir.dot(dir); + mCapsuleDir = dir; + mBDotB = BDotB; + mOneOverBDotB = BDotB!=0.0f ? 1.0f/BDotB : 0.0f; + } + }; + + // PT: tests if projections of capsule & triangle overlap on given axis + PX_FORCE_INLINE PxU32 testAxis(const PxVec3& p0, const PxVec3& p1, const PxVec3& p2, const Capsule& capsule, const PxVec3& axis) + { + // Project capsule + float min0 = capsule.p0.dot(axis); + float max0 = capsule.p1.dot(axis); + if(min0>max0) + Ps::swap(min0, max0); + const float MR = axis.magnitude()*capsule.radius; + min0 -= MR; + max0 += MR; + + // Project triangle + float min1, max1; + { + min1 = max1 = p0.dot(axis); + float dp = p1.dot(axis); + if(dp<min1) min1 = dp; + if(dp>max1) max1 = dp; + dp = p2.dot(axis); + if(dp<min1) min1 = dp; + if(dp>max1) max1 = dp; + } + + // Test projections + if(max0<min1 || max1<min0) + return 0; + + return 1; + } + + // PT: computes shortest vector going from capsule axis to triangle edge + PX_FORCE_INLINE PxVec3 computeEdgeAxis( const PxVec3& p, const PxVec3& a, + const PxVec3& q, const PxVec3& b, + float BDotB, float oneOverBDotB) + { + const PxVec3 T = q - p; + const float ADotA = a.dot(a); + const float ADotB = a.dot(b); + const float ADotT = a.dot(T); + const float BDotT = b.dot(T); + + const float denom = ADotA*BDotB - ADotB*ADotB; + + float t = denom!=0.0f ? (ADotT*BDotB - BDotT*ADotB) / denom : 0.0f; + t = PxClamp(t, 0.0f, 1.0f); + + float u = (t*ADotB - BDotT) * oneOverBDotB; + + if(u<0.0f) + { + u = 0.0f; + t = ADotT / ADotA; + t = PxClamp(t, 0.0f, 1.0f); + } + else if(u>1.0f) + { + u = 1.0f; + t = (ADotB + ADotT) / ADotA; + t = PxClamp(t, 0.0f, 1.0f); + } + return T + b*u - a*t; + } + + /** + * Checks if a capsule intersects a triangle. + * + * \param normal [in] triangle normal (orientation does not matter) + * \param p0 [in] triangle's first point + * \param p1 [in] triangle's second point + * \param p2 [in] triangle's third point + * \param capsule [in] capsule + * \param params [in] precomputed capsule params + * \return true if capsule overlaps triangle + */ + bool intersectCapsuleTriangle(const PxVec3& normal, const PxVec3& p0, const PxVec3& p1, const PxVec3& p2, const Gu::Capsule& capsule, const CapsuleTriangleOverlapData& params); +} +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionEdgeEdge.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionEdgeEdge.cpp new file mode 100644 index 00000000..3f828ba5 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionEdgeEdge.cpp @@ -0,0 +1,84 @@ +// 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 "GuIntersectionEdgeEdge.h" +#include "PsMathUtils.h" +#include "CmPhysXCommon.h" + +using namespace physx; + +bool Gu::intersectEdgeEdge(const PxVec3& p1, const PxVec3& p2, const PxVec3& dir, const PxVec3& p3, const PxVec3& p4, PxReal& dist, PxVec3& ip) +{ + const PxVec3 v1 = p2 - p1; + + // Build plane P based on edge (p1, p2) and direction (dir) + PxPlane plane; + plane.n = v1.cross(dir); + plane.d = -(plane.n.dot(p1)); + + // 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); + PxReal temp = d3 * plane.distance(p4); + if(temp>0.0f) return false; + + // if colliding edge (p3,p4) and plane are parallel return no collision + PxVec3 v2 = p4 - p3; + + temp = plane.n.dot(v2); + if(temp==0.0f) return false; // ### epsilon would be better + + // compute intersection point of plane and colliding edge (p3,p4) + ip = p3-v2*(d3/temp); + + // find largest 2D plane projection + PxU32 i,j; + Ps::closestAxis(plane.n, i, j); + + // 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]))/(v1[i]*dir[j]-v1[j]*dir[i]); + 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 + temp = (p1.x-ip.x)*(p2.x-ip.x)+(p1.y-ip.y)*(p2.y-ip.y)+(p1.z-ip.z)*(p2.z-ip.z); + if(temp<1e-3f) return true; // collision found + + return false; // no collision +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionEdgeEdge.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionEdgeEdge.h new file mode 100644 index 00000000..ccff0f35 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionEdgeEdge.h @@ -0,0 +1,52 @@ +// 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_INTERSECTION_EDGE_EDGE_H +#define GU_INTERSECTION_EDGE_EDGE_H + +#include "PxPhysXCommonConfig.h" +#include "CmPhysXCommon.h" + +namespace physx +{ +namespace Gu +{ + + // collide edge (p1,p2) moving in direction (dir) colliding + // width edge (p3,p4). Return true on a collision with + // collision distance (dist) and intersection point (ip) + // note: dist and ip are invalid if function returns false. + // note: ip is on (p1,p2), not (p1+dist*dir,p2+dist*dir) + PX_PHYSX_COMMON_API bool intersectEdgeEdge(const PxVec3& p1, const PxVec3& p2, const PxVec3& dir, const PxVec3& p3, const PxVec3& p4, PxReal& dist, PxVec3& ip); + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRay.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRay.h new file mode 100644 index 00000000..ce52150e --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRay.h @@ -0,0 +1,38 @@ +// 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_INTERSECTION_RAY_H +#define GU_INTERSECTION_RAY_H + +// PT: small distance between a ray origin and a potentially hit surface. Should be small enough to +// limit accuracy issues coming from large distance values, but not too close to the surface to make +// sure we don't start inside the shape. +#define GU_RAY_SURFACE_OFFSET 10.0f + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBox.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBox.cpp new file mode 100644 index 00000000..44d583f3 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBox.cpp @@ -0,0 +1,449 @@ +// 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/PxVec3.h" +#include "foundation/PxIntrinsics.h" +#include "PsFPU.h" +#include "GuIntersectionRayBox.h" +#include "GuIntersectionRayBoxSIMD.h" + +using namespace physx; + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** +* Computes a ray-AABB intersection. +* Original code by Andrew Woo, from "Graphics Gems", Academic Press, 1990 +* Optimized code by Pierre Terdiman, 2000 (~20-30% faster on my Celeron 500) +* Epsilon value added by Klaus Hartmann. (discarding it saves a few cycles only) +* +* Hence this version is faster as well as more robust than the original one. +* +* Should work provided: +* 1) the integer representation of 0.0f is 0x00000000 +* 2) the sign bit of the float is the most significant one +* +* Report bugs: [email protected] +* +* \param aabb [in] the axis-aligned bounding box +* \param origin [in] ray origin +* \param dir [in] ray direction +* \param coord [out] impact coordinates +* \return true if ray intersects AABB +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +#define RAYAABB_EPSILON 0.00001f +bool Gu::rayAABBIntersect(const PxVec3& minimum, const PxVec3& maximum, const PxVec3& origin, const PxVec3& _dir, PxVec3& coord) +{ + Ps::IntBool Inside = Ps::IntTrue; + PxVec3 MaxT(-1.0f, -1.0f, -1.0f); + const PxReal* dir = &_dir.x; + const PxU32* idir = reinterpret_cast<const PxU32*>(dir); + // Find candidate planes. + for(PxU32 i=0;i<3;i++) + { + if(origin[i] < minimum[i]) + { + coord[i] = minimum[i]; + Inside = Ps::IntFalse; + + // Calculate T distances to candidate planes + if(idir[i]) +// if(PX_IR(dir[i])) + MaxT[i] = (minimum[i] - origin[i]) / dir[i]; + } + else if(origin[i] > maximum[i]) + { + coord[i] = maximum[i]; + Inside = Ps::IntFalse; + + // Calculate T distances to candidate planes + if(idir[i]) +// if(PX_IR(dir[i])) + MaxT[i] = (maximum[i] - origin[i]) / dir[i]; + } + } + + // Ray origin inside bounding box + if(Inside) + { + coord = origin; + return true; + } + + // Get largest of the maxT's for final choice of intersection + PxU32 WhichPlane = 0; + if(MaxT[1] > MaxT[WhichPlane]) WhichPlane = 1; + if(MaxT[2] > MaxT[WhichPlane]) WhichPlane = 2; + + // Check final candidate actually inside box + const PxU32* tmp = reinterpret_cast<const PxU32*>(&MaxT[WhichPlane]); + if((*tmp)&PX_SIGN_BITMASK) +// if(PX_IR(MaxT[WhichPlane])&PX_SIGN_BITMASK) + return false; + + for(PxU32 i=0;i<3;i++) + { + if(i!=WhichPlane) + { + coord[i] = origin[i] + MaxT[WhichPlane] * dir[i]; +#ifdef RAYAABB_EPSILON + if(coord[i] < minimum[i] - RAYAABB_EPSILON || coord[i] > maximum[i] + RAYAABB_EPSILON) +#else + if(coord[i] < minimum[i] || coord[i] > maximum[i]) +#endif + return false; + } + } + return true; // ray hits box +} + + + +/** +* Computes a ray-AABB intersection. +* Original code by Andrew Woo, from "Graphics Gems", Academic Press, 1990 +* Optimized code by Pierre Terdiman, 2000 (~20-30% faster on my Celeron 500) +* Epsilon value added by Klaus Hartmann. (discarding it saves a few cycles only) +* Return of intersected face code and parameter by Adam! Also modified behavior for ray starts inside AABB. 2004 :-p +* +* Hence this version is faster as well as more robust than the original one. +* +* Should work provided: +* 1) the integer representation of 0.0f is 0x00000000 +* 2) the sign bit of the float is the most significant one +* +* Report bugs: [email protected] +* +* \param minimum [in] the smaller corner of the bounding box +* \param maximum [in] the larger corner of the bounding box +* \param origin [in] ray origin +* \param _dir [in] ray direction +* \param coord [out] impact coordinates +* \param t [out] t such that coord = origin + dir * t +* \return false if ray does not intersect AABB, or ray origin is inside AABB. Else: + 1 + coordinate index of box axis that was hit + + Note: sign bit that determines if the minimum (0) or maximum (1) of the axis was hit is equal to sign(coord[returnVal-1]). +*/ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +PxU32 Gu::rayAABBIntersect2(const PxVec3& minimum, const PxVec3& maximum, const PxVec3& origin, const PxVec3& _dir, PxVec3& coord, PxReal & t) +{ + Ps::IntBool Inside = Ps::IntTrue; + PxVec3 MaxT(-1.0f, -1.0f, -1.0f); + const PxReal* dir = &_dir.x; + const PxU32* idir = reinterpret_cast<const PxU32*>(dir); + // Find candidate planes. + for(PxU32 i=0;i<3;i++) + { + if(origin[i] < minimum[i]) + { + coord[i] = minimum[i]; + Inside = Ps::IntFalse; + + // Calculate T distances to candidate planes + if(idir[i]) +// if(PX_IR(dir[i])) + MaxT[i] = (minimum[i] - origin[i]) / dir[i]; + } + else if(origin[i] > maximum[i]) + { + coord[i] = maximum[i]; + Inside = Ps::IntFalse; + + // Calculate T distances to candidate planes + if(idir[i]) +// if(PX_IR(dir[i])) + MaxT[i] = (maximum[i] - origin[i]) / dir[i]; + } + } + + // Ray origin inside bounding box + if(Inside) + { + coord = origin; + t = 0; + return 1; + } + + // Get largest of the maxT's for final choice of intersection + PxU32 WhichPlane = 0; + if(MaxT[1] > MaxT[WhichPlane]) WhichPlane = 1; + if(MaxT[2] > MaxT[WhichPlane]) WhichPlane = 2; + + // Check final candidate actually inside box + const PxU32* tmp = reinterpret_cast<const PxU32*>(&MaxT[WhichPlane]); + if((*tmp)&PX_SIGN_BITMASK) +// if(PX_IR(MaxT[WhichPlane])&PX_SIGN_BITMASK) + return 0; + + for(PxU32 i=0;i<3;i++) + { + if(i!=WhichPlane) + { + coord[i] = origin[i] + MaxT[WhichPlane] * dir[i]; +#ifdef RAYAABB_EPSILON + if(coord[i] < minimum[i] - RAYAABB_EPSILON || coord[i] > maximum[i] + RAYAABB_EPSILON) return 0; +#else + if(coord[i] < minimum[i] || coord[i] > maximum[i]) return 0; +#endif + } + } + t = MaxT[WhichPlane]; + return 1 + WhichPlane; // ray hits box +} + +// Collide ray defined by ray origin (ro) and ray direction (rd) +// with the bounding box. Returns -1 on no collision and the face index +// for first intersection if a collision is found together with +// the distance to the collision points (tnear and tfar) + +// ptchernev: +// Should we use an enum, or should we keep the anonymous ints? +// Should we increment the return code by one (return 0 for non intersection)? + +int Gu::intersectRayAABB(const PxVec3& minimum, const PxVec3& maximum, const PxVec3& ro, const PxVec3& rd, float& tnear, float& tfar) +{ + // Refactor + int ret=-1; + + tnear = -PX_MAX_F32; + tfar = PX_MAX_F32; + // PT: why did we change the initial epsilon value? + #define LOCAL_EPSILON PX_EPS_F32 + //#define LOCAL_EPSILON 0.0001f + + for(unsigned int a=0;a<3;a++) + { + if(rd[a]>-LOCAL_EPSILON && rd[a]<LOCAL_EPSILON) + { + if(ro[a]<minimum[a] || ro[a]>maximum[a]) + return -1; + } + else + { + const PxReal OneOverDir = 1.0f / rd[a]; + PxReal t1 = (minimum[a]-ro[a]) * OneOverDir; + PxReal t2 = (maximum[a]-ro[a]) * OneOverDir; + + unsigned int b = a; + if(t1>t2) + { + PxReal t=t1; + t1=t2; + t2=t; + b += 3; + } + + if(t1>tnear) + { + tnear = t1; + ret = int(b); + } + if(t2<tfar) + tfar=t2; + if(tnear>tfar || tfar<LOCAL_EPSILON) + return -1; + } + } + + if(tnear>tfar || tfar<LOCAL_EPSILON) + return -1; + + return ret; +} + +// PT: specialized version where oneOverDir is available +int Gu::intersectRayAABB(const PxVec3& minimum, const PxVec3& maximum, const PxVec3& ro, const PxVec3& rd, const PxVec3& oneOverDir, float& tnear, float& tfar) +{ + // PT: why did we change the initial epsilon value? + #define LOCAL_EPSILON PX_EPS_F32 + //#define LOCAL_EPSILON 0.0001f + + if(physx::intrinsics::abs(rd.x)<LOCAL_EPSILON) +// if(rd.x>-LOCAL_EPSILON && rd.x<LOCAL_EPSILON) + if(ro.x<minimum.x || ro.x>maximum.x) + return -1; + if(physx::intrinsics::abs(rd.y)<LOCAL_EPSILON) +// if(rd.y>-LOCAL_EPSILON && rd.y<LOCAL_EPSILON) + if(ro.y<minimum.y || ro.y>maximum.y) + return -1; + if(physx::intrinsics::abs(rd.z)<LOCAL_EPSILON) +// if(rd.z>-LOCAL_EPSILON && rd.z<LOCAL_EPSILON) + if(ro.z<minimum.z || ro.z>maximum.z) + 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(t1x>tnear) // PT: no need to test for the first value + { + tnear = t1x; + ret = bx; + } +// tfar = PxMin(tfar, t2x); + tfar = t2x; // PT: no need to test for the first value + + if(t1y>tnear) + { + tnear = t1y; + ret = by; + } + tfar = PxMin(tfar, t2y); + + if(t1z>tnear) + { + tnear = t1z; + ret = bz; + } + tfar = PxMin(tfar, t2z); + + if(tnear>tfar || tfar<LOCAL_EPSILON) + return -1; + + return ret; +} + +bool Gu::intersectRayAABB2( + const PxVec3& minimum, const PxVec3& maximum, const PxVec3& ro, const PxVec3& rd, float maxDist, float& tnear, float& tfar) +{ + PX_ASSERT(maximum.x-minimum.x >= GU_MIN_AABB_EXTENT*0.5f); + PX_ASSERT(maximum.y-minimum.y >= GU_MIN_AABB_EXTENT*0.5f); + PX_ASSERT(maximum.z-minimum.z >= GU_MIN_AABB_EXTENT*0.5f); + // not using vector math due to vector to integer pipeline penalties. TODO: verify that it's indeed faster + namespace i = physx::intrinsics; + + // P+tD=a; t=(a-P)/D + // t=(a - p.x)*1/d.x = a/d.x +(- p.x/d.x) + const PxF32 dEpsilon = 1e-9f; + // using recipFast fails height field unit tests case where a ray cast from y=10000 to 0 gets clipped to 0.27 in y + PxF32 invDx = i::recip(i::selectMax(i::abs(rd.x), dEpsilon) * i::sign(rd.x)); +#ifdef RAYAABB_EPSILON + PxF32 tx0 = (minimum.x - RAYAABB_EPSILON - ro.x) * invDx; + PxF32 tx1 = (maximum.x + RAYAABB_EPSILON - ro.x) * invDx; +#else + PxF32 tx0 = (minimum.x - ro.x) * invDx; + PxF32 tx1 = (maximum.x - ro.x) * invDx; +#endif + PxF32 txMin = i::selectMin(tx0, tx1); + PxF32 txMax = i::selectMax(tx0, tx1); + + PxF32 invDy = i::recip(i::selectMax(i::abs(rd.y), dEpsilon) * i::sign(rd.y)); +#ifdef RAYAABB_EPSILON + PxF32 ty0 = (minimum.y - RAYAABB_EPSILON - ro.y) * invDy; + PxF32 ty1 = (maximum.y + RAYAABB_EPSILON - ro.y) * invDy; +#else + PxF32 ty0 = (minimum.y - ro.y) * invDy; + PxF32 ty1 = (maximum.y - ro.y) * invDy; +#endif + PxF32 tyMin = i::selectMin(ty0, ty1); + PxF32 tyMax = i::selectMax(ty0, ty1); + + PxF32 invDz = i::recip(i::selectMax(i::abs(rd.z), dEpsilon) * i::sign(rd.z)); +#ifdef RAYAABB_EPSILON + PxF32 tz0 = (minimum.z - RAYAABB_EPSILON - ro.z) * invDz; + PxF32 tz1 = (maximum.z + RAYAABB_EPSILON - ro.z) * invDz; +#else + PxF32 tz0 = (minimum.z - ro.z) * invDz; + PxF32 tz1 = (maximum.z - ro.z) * invDz; +#endif + PxF32 tzMin = i::selectMin(tz0, tz1); + PxF32 tzMax = i::selectMax(tz0, tz1); + + PxF32 maxOfNears = i::selectMax(i::selectMax(txMin, tyMin), tzMin); + PxF32 minOfFars = i::selectMin(i::selectMin(txMax, tyMax), tzMax); + + tnear = i::selectMax(maxOfNears, 0.0f); + tfar = i::selectMin(minOfFars, maxDist); + + return (tnear<tfar); +} + +bool Gu::intersectRayAABB2(const Ps::aos::Vec3VArg minimum, const Ps::aos::Vec3VArg maximum, + const Ps::aos::Vec3VArg ro, const Ps::aos::Vec3VArg rd, const Ps::aos::FloatVArg maxDist, + Ps::aos::FloatV& tnear, Ps::aos::FloatV& tfar) +{ + using namespace Ps::aos; + const FloatV zero = FZero(); + const Vec3V eps = V3Load(1e-9f); + const Vec3V absRD = V3Max(V3Abs(rd), eps); + const Vec3V signRD = V3Sign(rd); + const Vec3V rdV = V3Mul(absRD, signRD); + const Vec3V rdVRecip = V3Recip(rdV); + const Vec3V _min = V3Mul(V3Sub(minimum, ro), rdVRecip); + const Vec3V _max = V3Mul(V3Sub(maximum, ro), rdVRecip); + const Vec3V min = V3Min(_max, _min); + const Vec3V max = V3Max(_max, _min); + const FloatV maxOfNears = FMax(V3GetX(min), FMax(V3GetY(min), V3GetZ(min))); + const FloatV minOfFars = FMin(V3GetX(max), FMin(V3GetY(max), V3GetZ(max))); + + tnear = FMax(maxOfNears, zero); + tfar = FMin(minOfFars, maxDist); + //tfar = FAdd(FMin(minOfFars, maxDist), V3GetX(eps)); // AP: + epsilon because a test vs empty box should return true + + return FAllGrtr(tfar, tnear) != 0; +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBox.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBox.h new file mode 100644 index 00000000..edfece5c --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBox.h @@ -0,0 +1,91 @@ +// 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_INTERSECTION_RAY_BOX_H +#define GU_INTERSECTION_RAY_BOX_H + +#include "foundation/PxIntrinsics.h" +#include "PxPhysXCommonConfig.h" +#include "CmPhysXCommon.h" + +namespace physx +{ +namespace Gu +{ + + bool rayAABBIntersect(const PxVec3& minimum, const PxVec3& maximum, const PxVec3& origin, const PxVec3& _dir, PxVec3& coord); + PxU32 rayAABBIntersect2(const PxVec3& minimum, const PxVec3& maximum, const PxVec3& origin, const PxVec3& _dir, PxVec3& coord, PxReal & t); + + // Collide ray defined by ray origin (rayOrigin) and ray direction (rayDirection) + // with the bounding box. Returns -1 on no collision and the face index + // for first intersection if a collision is found together with + // the distance to the collision points (tnear and tfar) + // + // ptchernev: + // Even though the above is the original comment by Pierre I am quite confident + // that the tnear and tfar parameters are parameters along rayDirection of the + // intersection points: + // + // ip0 = rayOrigin + (rayDirection * tnear) + // ip1 = rayOrigin + (rayDirection * tfar) + // + // The return code is: + // -1 no intersection + // 0 the ray first hits the plane at aabbMin.x + // 1 the ray first hits the plane at aabbMin.y + // 2 the ray first hits the plane at aabbMin.z + // 3 the ray first hits the plane at aabbMax.x + // 4 the ray first hits the plane at aabbMax.y + // 5 the ray first hits the plane at aabbMax.z + // + // The return code will be -1 if the RAY does not intersect the AABB. + // The tnear and tfar values will give the parameters of the intersection + // points between the INFINITE LINE and the AABB. + int PX_PHYSX_COMMON_API intersectRayAABB( const PxVec3& minimum, const PxVec3& maximum, + const PxVec3& rayOrigin, const PxVec3& rayDirection, + float& tnear, float& tfar); + + // Faster version when one-over-dir is available + int intersectRayAABB( const PxVec3& minimum, const PxVec3& maximum, + const PxVec3& rayOrigin, const PxVec3& rayDirection, const PxVec3& invDirection, + float& tnear, float& tfar); + + // minimum extent length required for intersectRayAABB2 to return true for a zero-extent box + // this can happen when inflating the raycast by a 2-d square + #define GU_MIN_AABB_EXTENT 1e-3f + + // a much faster version that doesn't return face codes + bool PX_PHYSX_COMMON_API intersectRayAABB2( + const PxVec3& minimum, const PxVec3& maximum, const PxVec3& ro, const PxVec3& rd, float maxDist, float& tnear, float& tfar); + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBoxSIMD.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBoxSIMD.h new file mode 100644 index 00000000..51f01dd7 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayBoxSIMD.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_INTERSECTION_RAY_BOX_SIMD_H +#define GU_INTERSECTION_RAY_BOX_SIMD_H + +#include "foundation/PxIntrinsics.h" +#include "PxPhysXCommonConfig.h" +#include "CmPhysXCommon.h" +#include "PsVecMath.h" + +namespace physx +{ +namespace Gu +{ + bool PX_PHYSX_COMMON_API intersectRayAABB2( const Ps::aos::Vec3VArg minimum, const Ps::aos::Vec3VArg maximum, + const Ps::aos::Vec3VArg ro, const Ps::aos::Vec3VArg rd, const Ps::aos::FloatVArg maxDist, + Ps::aos::FloatV& tnear, Ps::aos::FloatV& tfar); + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayCapsule.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayCapsule.cpp new file mode 100644 index 00000000..bde848bd --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayCapsule.cpp @@ -0,0 +1,245 @@ +// 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 "GuIntersectionRayCapsule.h" +#include "GuIntersectionRaySphere.h" + +using namespace physx; + +// PT: ray-capsule intersection code, originally from the old Magic Software library. +PxU32 Gu::intersectRayCapsuleInternal(const PxVec3& origin, const PxVec3& dir, const PxVec3& p0, const PxVec3& p1, float radius, PxReal s[2]) +{ + // set up quadratic Q(t) = a*t^2 + 2*b*t + c + PxVec3 kW = p1 - p0; + const float fWLength = kW.magnitude(); + if(fWLength!=0.0f) + kW /= fWLength; + + // PT: if the capsule is in fact a sphere, switch back to dedicated sphere code. + // This is not just an optimization, the rest of the code fails otherwise. + if(fWLength<=1e-6f) + { + const float d0 = (origin - p0).magnitudeSquared(); + const float d1 = (origin - p1).magnitudeSquared(); + const float approxLength = (PxMax(d0, d1) + radius)*2.0f; + return PxU32(Gu::intersectRaySphere(origin, dir, approxLength, p0, radius, s[0])); + } + + // generate orthonormal basis + PxVec3 kU(0.0f); + + if (fWLength > 0.0f) + { + PxReal fInvLength; + if ( PxAbs(kW.x) >= PxAbs(kW.y) ) + { + // W.x or W.z is the largest magnitude component, swap them + fInvLength = PxRecipSqrt(kW.x*kW.x + kW.z*kW.z); + kU.x = -kW.z*fInvLength; + kU.y = 0.0f; + kU.z = kW.x*fInvLength; + } + else + { + // W.y or W.z is the largest magnitude component, swap them + fInvLength = PxRecipSqrt(kW.y*kW.y + kW.z*kW.z); + kU.x = 0.0f; + kU.y = kW.z*fInvLength; + kU.z = -kW.y*fInvLength; + } + } + + PxVec3 kV = kW.cross(kU); + kV.normalize(); // PT: fixed november, 24, 2004. This is a bug in Magic. + + // compute intersection + + PxVec3 kD(kU.dot(dir), kV.dot(dir), kW.dot(dir)); + const float fDLength = kD.magnitude(); + const float fInvDLength = fDLength!=0.0f ? 1.0f/fDLength : 0.0f; + kD *= fInvDLength; + + const PxVec3 kDiff = origin - p0; + const PxVec3 kP(kU.dot(kDiff), kV.dot(kDiff), kW.dot(kDiff)); + const PxReal fRadiusSqr = radius*radius; + + // Is the velocity parallel to the capsule direction? (or zero) + if ( PxAbs(kD.z) >= 1.0f - PX_EPS_REAL || fDLength < PX_EPS_REAL ) + { + const float fAxisDir = dir.dot(kW); + + const PxReal fDiscr = fRadiusSqr - kP.x*kP.x - kP.y*kP.y; + if ( fAxisDir < 0 && fDiscr >= 0.0f ) + { + // Velocity anti-parallel to the capsule direction + const PxReal fRoot = PxSqrt(fDiscr); + s[0] = (kP.z + fRoot)*fInvDLength; + s[1] = -(fWLength - kP.z + fRoot)*fInvDLength; + return 2; + } + else if ( fAxisDir > 0 && fDiscr >= 0.0f ) + { + // Velocity parallel to the capsule direction + const PxReal fRoot = PxSqrt(fDiscr); + s[0] = -(kP.z + fRoot)*fInvDLength; + s[1] = (fWLength - kP.z + fRoot)*fInvDLength; + return 2; + } + else + { + // sphere heading wrong direction, or no velocity at all + return 0; + } + } + + // test intersection with infinite cylinder + PxReal fA = kD.x*kD.x + kD.y*kD.y; + PxReal fB = kP.x*kD.x + kP.y*kD.y; + PxReal fC = kP.x*kP.x + kP.y*kP.y - fRadiusSqr; + PxReal fDiscr = fB*fB - fA*fC; + if ( fDiscr < 0.0f ) + { + // line does not intersect infinite cylinder + return 0; + } + + PxU32 iQuantity = 0; + + if ( fDiscr > 0.0f ) + { + // line intersects infinite cylinder in two places + const PxReal fRoot = PxSqrt(fDiscr); + const PxReal fInv = 1.0f/fA; + PxReal fT = (-fB - fRoot)*fInv; + PxReal fTmp = kP.z + fT*kD.z; + const float epsilon = 1e-3f; // PT: see TA35174 + if ( fTmp >= -epsilon && fTmp <= fWLength+epsilon ) + s[iQuantity++] = fT*fInvDLength; + + fT = (-fB + fRoot)*fInv; + fTmp = kP.z + fT*kD.z; + if ( fTmp >= -epsilon && fTmp <= fWLength+epsilon ) + s[iQuantity++] = fT*fInvDLength; + + if ( iQuantity == 2 ) + { + // line intersects capsule wall in two places + return 2; + } + } + else + { + // line is tangent to infinite cylinder + const PxReal fT = -fB/fA; + const PxReal fTmp = kP.z + fT*kD.z; + if ( 0.0f <= fTmp && fTmp <= fWLength ) + { + s[0] = fT*fInvDLength; + return 1; + } + } + + // test intersection with bottom hemisphere + // fA = 1 + fB += kP.z*kD.z; + fC += kP.z*kP.z; + fDiscr = fB*fB - fC; + if ( fDiscr > 0.0f ) + { + const PxReal fRoot = PxSqrt(fDiscr); + PxReal fT = -fB - fRoot; + PxReal fTmp = kP.z + fT*kD.z; + if ( fTmp <= 0.0f ) + { + s[iQuantity++] = fT*fInvDLength; + if ( iQuantity == 2 ) + return 2; + } + + fT = -fB + fRoot; + fTmp = kP.z + fT*kD.z; + if ( fTmp <= 0.0f ) + { + s[iQuantity++] = fT*fInvDLength; + if ( iQuantity == 2 ) + return 2; + } + } + else if ( fDiscr == 0.0f ) + { + const PxReal fT = -fB; + const PxReal fTmp = kP.z + fT*kD.z; + if ( fTmp <= 0.0f ) + { + s[iQuantity++] = fT*fInvDLength; + if ( iQuantity == 2 ) + return 2; + } + } + + // test intersection with top hemisphere + // fA = 1 + fB -= kD.z*fWLength; + fC += fWLength*(fWLength - 2.0f*kP.z); + + fDiscr = fB*fB - fC; + if ( fDiscr > 0.0f ) + { + const PxReal fRoot = PxSqrt(fDiscr); + PxReal fT = -fB - fRoot; + PxReal fTmp = kP.z + fT*kD.z; + if ( fTmp >= fWLength ) + { + s[iQuantity++] = fT*fInvDLength; + if ( iQuantity == 2 ) + return 2; + } + + fT = -fB + fRoot; + fTmp = kP.z + fT*kD.z; + if ( fTmp >= fWLength ) + { + s[iQuantity++] = fT*fInvDLength; + if ( iQuantity == 2 ) + return 2; + } + } + else if ( fDiscr == 0.0f ) + { + const PxReal fT = -fB; + const PxReal fTmp = kP.z + fT*kD.z; + if ( fTmp >= fWLength ) + { + s[iQuantity++] = fT*fInvDLength; + if ( iQuantity == 2 ) + return 2; + } + } + return iQuantity; +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayCapsule.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayCapsule.h new file mode 100644 index 00000000..93df2702 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayCapsule.h @@ -0,0 +1,93 @@ +// 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_INTERSECTION_RAY_CAPSULE_H +#define GU_INTERSECTION_RAY_CAPSULE_H + +#include "CmPhysXCommon.h" +#include "GuCapsule.h" +#include "GuDistancePointSegment.h" +#include "GuIntersectionRay.h" + +namespace physx +{ +namespace Gu +{ + PxU32 intersectRayCapsuleInternal(const PxVec3& origin, const PxVec3& dir, const PxVec3& p0, const PxVec3& p1, float radius, PxReal s[2]); + + PX_FORCE_INLINE bool intersectRayCapsule(const PxVec3& origin, const PxVec3& dir, const PxVec3& p0, const PxVec3& p1, float radius, PxReal& t) + { + // PT: move ray origin close to capsule, to solve accuracy issues. + // We compute the distance D between the ray origin and the capsule's segment. + // Then E = D - radius = distance between the ray origin and the capsule. + // We can move the origin freely along 'dir' up to E units before touching the capsule. + PxReal l = distancePointSegmentSquaredInternal(p0, p1 - p0, origin); + l = PxSqrt(l) - radius; + + // PT: if this becomes negative or null, the ray starts inside the capsule and we can early exit + if(l<=0.0f) + { + t = 0.0f; + return true; + } + + // PT: we remove an arbitrary GU_RAY_SURFACE_OFFSET units to E, to make sure we don't go close to the surface. + // If we're moving in the direction of the capsule, the origin is now about GU_RAY_SURFACE_OFFSET units from it. + // If we're moving away from the capsule, the ray won't hit the capsule anyway. + // If l is smaller than GU_RAY_SURFACE_OFFSET we're close enough, accuracy is good, there is nothing to do. + if(l>GU_RAY_SURFACE_OFFSET) + l -= GU_RAY_SURFACE_OFFSET; + else + l = 0.0f; + + // PT: move origin closer to capsule and do the raycast + PxReal s[2]; + const PxU32 nbHits = Gu::intersectRayCapsuleInternal(origin + l*dir, dir, p0, p1, radius, s); + if(!nbHits) + return false; + + // PT: keep closest hit only + if(nbHits == 1) + t = s[0]; + else + t = (s[0] < s[1]) ? s[0] : s[1]; + + // PT: fix distance (smaller than expected after moving ray close to capsule) + t += l; + return true; + } + + PX_FORCE_INLINE bool intersectRayCapsule(const PxVec3& origin, const PxVec3& dir, const Gu::Capsule& capsule, PxReal& t) + { + return Gu::intersectRayCapsule(origin, dir, capsule.p0, capsule.p1, capsule.radius, t); + } +} +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayPlane.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayPlane.h new file mode 100644 index 00000000..b28c0658 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayPlane.h @@ -0,0 +1,58 @@ +// 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_INTERSECTION_RAY_PLANE_H +#define GU_INTERSECTION_RAY_PLANE_H + +#include "foundation/PxPlane.h" + +namespace physx +{ +namespace Gu +{ + // Returns true if line and plane are not parallel + PX_INLINE bool intersectRayPlane(const PxVec3& orig, const PxVec3& dir, const PxPlane& plane, float& distanceAlongLine, PxVec3* pointOnPlane = NULL) + { + const float dn = dir.dot(plane.n); + if(-1E-7f < dn && dn < 1E-7f) + return false; // parallel + + distanceAlongLine = -plane.distance(orig)/dn; + + if(pointOnPlane) + *pointOnPlane = orig + distanceAlongLine * dir; + + return true; + } + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRaySphere.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRaySphere.cpp new file mode 100644 index 00000000..66b1f08f --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRaySphere.cpp @@ -0,0 +1,105 @@ +// 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/PxVec3.h" +#include "GuIntersectionRaySphere.h" +#include "GuIntersectionRay.h" + +using namespace physx; + +// Based on GD Mag code, but now works correctly when origin is inside the sphere. +// This version has limited accuracy. +bool Gu::intersectRaySphereBasic(const PxVec3& origin, const PxVec3& dir, PxReal length, const PxVec3& center, PxReal radius, PxReal& dist, PxVec3* hit_pos) +{ + // get the offset vector + const PxVec3 offset = center - origin; + + // get the distance along the ray to the center point of the sphere + const PxReal ray_dist = dir.dot(offset); + + // get the squared distances + const PxReal off2 = offset.dot(offset); + const PxReal rad_2 = radius * radius; + if(off2 <= rad_2) + { + // we're in the sphere + if(hit_pos) + *hit_pos = origin; + dist = 0.0f; + return true; + } + + if(ray_dist <= 0 || (ray_dist - length) > radius) + { + // moving away from object or too far away + return false; + } + + // find hit distance squared + const PxReal d = rad_2 - (off2 - ray_dist * ray_dist); + if(d<0.0f) + { + // ray passes by sphere without hitting + return false; + } + + // get the distance along the ray + dist = ray_dist - PxSqrt(d); + if(dist > length) + { + // hit point beyond length + return false; + } + + // sort out the details + if(hit_pos) + *hit_pos = origin + dir * dist; + return true; +} + +// PT: modified version calls the previous function, but moves the ray origin closer to the sphere. The test accuracy is +// greatly improved as a result. This is an idea proposed on the GD-Algorithms list by Eddie Edwards. +// See: http://www.codercorner.com/blog/?p=321 +bool Gu::intersectRaySphere(const PxVec3& origin, const PxVec3& dir, PxReal length, const PxVec3& center, PxReal radius, PxReal& dist, PxVec3* hit_pos) +{ + const PxVec3 x = origin - center; + PxReal l = PxSqrt(x.dot(x)) - radius - GU_RAY_SURFACE_OFFSET; + +// if(l<0.0f) +// l=0.0f; + l = physx::intrinsics::selectMax(l, 0.0f); + + bool status = intersectRaySphereBasic(origin + l*dir, dir, length - l, center, radius, dist, hit_pos); + if(status) + { +// dist += l/length; + dist += l; + } + return status; +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRaySphere.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRaySphere.h new file mode 100644 index 00000000..6c4244f3 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRaySphere.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_INTERSECTION_RAY_SPHERE_H +#define GU_INTERSECTION_RAY_SPHERE_H + +#include "CmPhysXCommon.h" + +namespace physx +{ +namespace Gu +{ + // PT: basic version, limited accuracy, might fail for long rays vs small spheres + bool intersectRaySphereBasic(const PxVec3& origin, const PxVec3& dir, PxReal length, const PxVec3& center, PxReal radius, PxReal& dist, PxVec3* hit_pos = NULL); + + // PT: version with improved accuracy + bool intersectRaySphere(const PxVec3& origin, const PxVec3& dir, PxReal length, const PxVec3& center, PxReal radius, PxReal& dist, PxVec3* hit_pos = NULL); + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayTriangle.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayTriangle.h new file mode 100644 index 00000000..3a8d22b6 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionRayTriangle.h @@ -0,0 +1,179 @@ +// 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_INTERSECTION_RAY_TRIANGLE_H +#define GU_INTERSECTION_RAY_TRIANGLE_H + +#include "foundation/PxVec3.h" +#include "PxPhysXCommonConfig.h" +#include "CmPhysXCommon.h" + +namespace physx +{ + +namespace Gu +{ + // PT: this is used for backface culling. It existed in Moller's original code already. Basically this is only to avoid dividing by zero. + // This should not depend on what units are used, and neither should it depend on the size of triangles. A large triangle with the same + // orientation as a small triangle should be backface culled the same way. A triangle whose orientation does not change should not suddenly + // become culled or visible when we scale it. + // + // An absolute epsilon is fine here. The computation will work fine for small triangles, and large triangles will simply make 'det' larger, + // more and more inaccurate, but it won't suddenly make it negative. + // + // Using FLT_EPSILON^2 ensures that triangles whose edges are smaller than FLT_EPSILON long are rejected. This epsilon makes the code work + // for very small triangles, while still preventing divisions by too small values. + #define GU_CULLING_EPSILON_RAY_TRIANGLE FLT_EPSILON*FLT_EPSILON + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** + * Computes a ray-triangle intersection test. + * From Tomas Moeller's "Fast Minimum Storage Ray-Triangle Intersection" + * Could be optimized and cut into 2 methods (culled or not). Should make a batch one too to avoid the call overhead, or make it inline. + * + * \param orig [in] ray origin + * \param dir [in] ray direction + * \param vert0 [in] triangle vertex + * \param vert1 [in] triangle vertex + * \param vert2 [in] triangle vertex + * \param at [out] distance + * \param au [out] impact barycentric coordinate + * \param av [out] impact barycentric coordinate + * \param cull [in] true to use backface culling + * \param enlarge [in] enlarge triangle by specified epsilon in UV space to avoid false near-edge rejections + * \return true on overlap + * \note u, v and t will remain unchanged if false is returned. + */ + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + PX_FORCE_INLINE bool intersectRayTriangle( const PxVec3& orig, const PxVec3& dir, + const PxVec3& vert0, const PxVec3& vert1, const PxVec3& vert2, + PxReal& at, PxReal& au, PxReal& av, + bool cull, float enlarge=0.0f) + { + // 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); // error ~ |v2-v0| + + // If determinant is near zero, ray lies in plane of triangle + const PxReal det = edge1.dot(pvec); // error ~ |v2-v0|*|v1-v0| + + if(cull) + { + if(det<GU_CULLING_EPSILON_RAY_TRIANGLE) + return false; + + // Calculate distance from vert0 to ray origin + const PxVec3 tvec = orig - vert0; + + // Calculate U parameter and test bounds + const PxReal u = tvec.dot(pvec); + + const PxReal enlargeCoeff = enlarge*det; + const PxReal uvlimit = -enlargeCoeff; + const PxReal uvlimit2 = det + enlargeCoeff; + + if(u<uvlimit || u>uvlimit2) + return false; + + // Prepare to test V parameter + const PxVec3 qvec = tvec.cross(edge1); + + // Calculate V parameter and test bounds + const PxReal v = dir.dot(qvec); + if(v<uvlimit || (u+v)>uvlimit2) + return false; + + // Calculate t, scale parameters, ray intersects triangle + const PxReal t = edge2.dot(qvec); + + const PxReal inv_det = 1.0f / det; + at = t*inv_det; + au = u*inv_det; + av = v*inv_det; + } + else + { + // the non-culling branch + if(PxAbs(det)<GU_CULLING_EPSILON_RAY_TRIANGLE) + return false; + + const PxReal inv_det = 1.0f / det; + + // Calculate distance from vert0 to ray origin + const PxVec3 tvec = orig - vert0; // error ~ |orig-v0| + + // Calculate U parameter and test bounds + const PxReal u = tvec.dot(pvec) * inv_det; + if(u<-enlarge || u>1.0f+enlarge) + return false; + + // prepare to test V parameter + const PxVec3 qvec = tvec.cross(edge1); + + // Calculate V parameter and test bounds + const PxReal v = dir.dot(qvec) * inv_det; + if(v<-enlarge || (u+v)>1.0f+enlarge) + return false; + + // Calculate t, ray intersects triangle + const PxReal t = edge2.dot(qvec) * inv_det; + + at = t; + au = u; + av = v; + } + return true; + } + + /* \note u, v and t will remain unchanged if false is returned. */ + PX_FORCE_INLINE bool intersectRayTriangleCulling( const PxVec3& orig, const PxVec3& dir, + const PxVec3& vert0, const PxVec3& vert1, const PxVec3& vert2, + PxReal& t, PxReal& u, PxReal& v, + float enlarge=0.0f) + { + return intersectRayTriangle(orig, dir, vert0, vert1, vert2, t, u, v, true, enlarge); + } + + /* \note u, v and t will remain unchanged if false is returned. */ + PX_FORCE_INLINE bool intersectRayTriangleNoCulling( const PxVec3& orig, const PxVec3& dir, + const PxVec3& vert0, const PxVec3& vert1, const PxVec3& vert2, + PxReal& t, PxReal& u, PxReal& v, + float enlarge=0.0f) + { + return intersectRayTriangle(orig, dir, vert0, vert1, vert2, t, u, v, false, enlarge); + } + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionSphereBox.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionSphereBox.cpp new file mode 100644 index 00000000..bb5e5769 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionSphereBox.cpp @@ -0,0 +1,88 @@ +// 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 "GuIntersectionSphereBox.h" +#include "GuSphere.h" +#include "GuBox.h" + +using namespace physx; + +bool Gu::intersectSphereBox(const Sphere& sphere, const Box& box) +{ + const PxVec3 delta = sphere.center - box.center; + PxVec3 dRot = box.rot.transformTranspose(delta); //transform delta into OBB body coords. (use method call!) + + //check if delta is outside AABB - and clip the vector to the AABB. + bool outside = false; + + if(dRot.x < -box.extents.x) + { + outside = true; + dRot.x = -box.extents.x; + } + else if(dRot.x > box.extents.x) + { + outside = true; + dRot.x = box.extents.x; + } + + if(dRot.y < -box.extents.y) + { + outside = true; + dRot.y = -box.extents.y; + } + else if(dRot.y > box.extents.y) + { + outside = true; + dRot.y = box.extents.y; + } + + if(dRot.z < -box.extents.z) + { + outside = true; + dRot.z = -box.extents.z; + } + else if(dRot.z > box.extents.z) + { + outside = true; + dRot.z = box.extents.z; + } + + if(outside) //if clipping was done, sphere center is outside of box. + { + const PxVec3 clippedDelta = box.rot.transform(dRot); //get clipped delta back in world coords. + + const PxVec3 clippedVec = delta - clippedDelta; //what we clipped away. + const PxReal lenSquared = clippedVec.magnitudeSquared(); + const PxReal radius = sphere.radius; + if(lenSquared > radius * radius) // PT: objects are defined as closed, so we return 'true' in case of equality + return false; //disjoint + } + return true; +} diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionSphereBox.h b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionSphereBox.h new file mode 100644 index 00000000..b8864473 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionSphereBox.h @@ -0,0 +1,54 @@ +// 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_INTERSECTION_SPHERE_BOX_H +#define GU_INTERSECTION_SPHERE_BOX_H + +namespace physx +{ +namespace Gu +{ + class Sphere; + class Box; + + /** + Checks if a sphere intersects a box. Based on: Jim Arvo, A Simple Method for Box-Sphere Intersection Testing, Graphics Gems, pp. 247-250. + + \param sphere [in] sphere + \param box [in] box + + \return true if sphere overlaps box (or exactly touches it) + */ + bool intersectSphereBox(const Gu::Sphere& sphere, const Gu::Box& box); + +} // namespace Gu + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionTriangleBox.cpp b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionTriangleBox.cpp new file mode 100644 index 00000000..9d3fbed3 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionTriangleBox.cpp @@ -0,0 +1,395 @@ +// 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 "GuIntersectionTriangleBox.h" +#include "CmMatrix34.h" +#include "PsVecMath.h" +#include "GuBox.h" +#include "GuSIMDHelpers.h" + +using namespace physx; + +/********************************************************/ +/* AABB-triangle overlap test code */ +/* by Tomas Akenine-M?r */ +/* Function: int triBoxOverlap(float boxcenter[3], */ +/* float boxhalfsize[3],float triverts[3][3]); */ +/* History: */ +/* 2001-03-05: released the code in its first version */ +/* 2001-06-18: changed the order of the tests, faster */ +/* */ +/* Acknowledgement: Many thanks to Pierre Terdiman for */ +/* suggestions and discussions on how to optimize code. */ +/* Thanks to David Hunt for finding a ">="-bug! */ +/********************************************************/ + +#define CROSS(dest,v1,v2) \ + dest.x=v1.y*v2.z-v1.z*v2.y; \ + dest.y=v1.z*v2.x-v1.x*v2.z; \ + dest.z=v1.x*v2.y-v1.y*v2.x; + +#define DOT(v1,v2) (v1.x*v2.x+v1.y*v2.y+v1.z*v2.z) + +#define FINDMINMAX(x0, x1, x2, minimum, maximum) \ + minimum = physx::intrinsics::selectMin(x0, x1); \ + maximum = physx::intrinsics::selectMax(x0, x1); \ + minimum = physx::intrinsics::selectMin(minimum, x2); \ + maximum = physx::intrinsics::selectMax(maximum, x2); + +static PX_FORCE_INLINE Ps::IntBool planeBoxOverlap(const PxVec3& normal, PxReal d, const PxVec3& maxbox) +{ + PxVec3 vmin,vmax; + + if (normal.x>0.0f) + { + vmin.x = -maxbox.x; + vmax.x = maxbox.x; + } + else + { + vmin.x = maxbox.x; + vmax.x = -maxbox.x; + } + + if (normal.y>0.0f) + { + vmin.y = -maxbox.y; + vmax.y = maxbox.y; + } + else + { + vmin.y = maxbox.y; + vmax.y = -maxbox.y; + } + + if (normal.z>0.0f) + { + vmin.z = -maxbox.z; + vmax.z = maxbox.z; + } + else + { + vmin.z = maxbox.z; + vmax.z = -maxbox.z; + } + + if( normal.dot(vmin) + d > 0.0f) return Ps::IntFalse; + if( normal.dot(vmax) + d >= 0.0f) return Ps::IntTrue; + return Ps::IntFalse; +} + +/*======================== X-tests ========================*/ +#define AXISTEST_X01(a, b, fa, fb) \ + p0 = a*v0.y - b*v0.z; \ + p2 = a*v2.y - b*v2.z; \ + minimum = physx::intrinsics::selectMin(p0, p2); \ + maximum = physx::intrinsics::selectMax(p0, p2); \ + rad = fa * extents.y + fb * extents.z; \ + if(minimum>rad || maximum<-rad) return Ps::IntFalse; + +#define AXISTEST_X2(a, b, fa, fb) \ + p0 = a*v0.y - b*v0.z; \ + p1 = a*v1.y - b*v1.z; \ + minimum = physx::intrinsics::selectMin(p0, p1); \ + maximum = physx::intrinsics::selectMax(p0, p1); \ + rad = fa * extents.y + fb * extents.z; \ + if(minimum>rad || maximum<-rad) return Ps::IntFalse; + +/*======================== Y-tests ========================*/ +#define AXISTEST_Y02(a, b, fa, fb) \ + p0 = -a*v0.x + b*v0.z; \ + p2 = -a*v2.x + b*v2.z; \ + minimum = physx::intrinsics::selectMin(p0, p2); \ + maximum = physx::intrinsics::selectMax(p0, p2); \ + rad = fa * extents.x + fb * extents.z; \ + if(minimum>rad || maximum<-rad) return Ps::IntFalse; + +#define AXISTEST_Y1(a, b, fa, fb) \ + p0 = -a*v0.x + b*v0.z; \ + p1 = -a*v1.x + b*v1.z; \ + minimum = physx::intrinsics::selectMin(p0, p1); \ + maximum = physx::intrinsics::selectMax(p0, p1); \ + rad = fa * extents.x + fb * extents.z; \ + if(minimum>rad || maximum<-rad) return Ps::IntFalse; + +/*======================== Z-tests ========================*/ +#define AXISTEST_Z12(a, b, fa, fb) \ + p1 = a*v1.x - b*v1.y; \ + p2 = a*v2.x - b*v2.y; \ + minimum = physx::intrinsics::selectMin(p1, p2); \ + maximum = physx::intrinsics::selectMax(p1, p2); \ + rad = fa * extents.x + fb * extents.y; \ + if(minimum>rad || maximum<-rad) return Ps::IntFalse; + +#define AXISTEST_Z0(a, b, fa, fb) \ + p0 = a*v0.x - b*v0.y; \ + p1 = a*v1.x - b*v1.y; \ + minimum = physx::intrinsics::selectMin(p0, p1); \ + maximum = physx::intrinsics::selectMax(p0, p1); \ + rad = fa * extents.x + fb * extents.y; \ + if(minimum>rad || maximum<-rad) return Ps::IntFalse; + +Ps::IntBool Gu::intersectTriangleBox_ReferenceCode(const PxVec3& boxcenter, const PxVec3& extents, const PxVec3& tp0, const PxVec3& tp1, const PxVec3& tp2) +{ + /* use separating axis theorem to test overlap between triangle and box */ + /* need to test for overlap in these directions: */ + /* 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */ + /* we do not even need to test these) */ + /* 2) normal of the triangle */ + /* 3) crossproduct(edge from tri, {x,y,z}-directin) */ + /* this gives 3x3=9 more tests */ + + // This is the fastest branch on Sun - move everything so that the boxcenter is in (0,0,0) + const PxVec3 v0 = tp0 - boxcenter; + const PxVec3 v1 = tp1 - boxcenter; + const PxVec3 v2 = tp2 - boxcenter; + + // compute triangle edges + const PxVec3 e0 = v1 - v0; // tri edge 0 + const PxVec3 e1 = v2 - v1; // tri edge 1 + const PxVec3 e2 = v0 - v2; // tri edge 2 + + float minimum,maximum,rad,p0,p1,p2; + + // Bullet 3: test the 9 tests first (this was faster) + float fex = PxAbs(e0.x); + float fey = PxAbs(e0.y); + float fez = PxAbs(e0.z); + AXISTEST_X01(e0.z, e0.y, fez, fey); + AXISTEST_Y02(e0.z, e0.x, fez, fex); + AXISTEST_Z12(e0.y, e0.x, fey, fex); + + fex = PxAbs(e1.x); + fey = PxAbs(e1.y); + fez = PxAbs(e1.z); + AXISTEST_X01(e1.z, e1.y, fez, fey); + AXISTEST_Y02(e1.z, e1.x, fez, fex); + AXISTEST_Z0(e1.y, e1.x, fey, fex); + + fex = PxAbs(e2.x); + fey = PxAbs(e2.y); + fez = PxAbs(e2.z); + AXISTEST_X2(e2.z, e2.y, fez, fey); + AXISTEST_Y1(e2.z, e2.x, fez, fex); + AXISTEST_Z12(e2.y, e2.x, fey, fex); + + // Bullet 1: + // first test overlap in the {x,y,z}-directions + // find minimum, maximum of the triangle each direction, and test for overlap in + // that direction -- this is equivalent to testing a minimal AABB around + // the triangle against the AABB + + // test in X-direction + FINDMINMAX(v0.x, v1.x, v2.x, minimum, maximum); + if(minimum>extents.x || maximum<-extents.x) return Ps::IntFalse; + + // test in Y-direction + FINDMINMAX(v0.y, v1.y, v2.y, minimum, maximum); + if(minimum>extents.y || maximum<-extents.y) return Ps::IntFalse; + + // test in Z-direction + FINDMINMAX(v0.z, v1.z, v2.z, minimum, maximum); + if(minimum>extents.z || maximum<-extents.z) return Ps::IntFalse; + + // Bullet 2: + // test if the box intersects the plane of the triangle + // compute plane equation of triangle: normal*x+d=0 + PxVec3 normal; + CROSS(normal,e0,e1); + const float d=-DOT(normal,v0); // plane eq: normal.x+d=0 + if(!planeBoxOverlap(normal, d, extents)) return Ps::IntFalse; + + return Ps::IntTrue; // box and triangle overlaps +} + +#undef CROSS +#undef DOT +#undef FINDMINMAX +#undef AXISTEST_X01 +#undef AXISTEST_X2 +#undef AXISTEST_Y02 +#undef AXISTEST_Y1 +#undef AXISTEST_Z12 +#undef AXISTEST_Z0 + + + +using namespace Ps::aos; + +static PX_FORCE_INLINE int testClassIIIAxes(const Vec4V& e0V, const Vec4V v0V, const Vec4V v1V, const Vec4V v2V, const PxVec3& extents) +{ + const Vec4V e0XZY_V = V4PermYZXW(e0V); + + const Vec4V v0XZY_V = V4PermYZXW(v0V); + const Vec4V p0V = V4NegMulSub(v0XZY_V, e0V, V4Mul(v0V, e0XZY_V)); + + const Vec4V v1XZY_V = V4PermYZXW(v1V); + const Vec4V p1V = V4NegMulSub(v1XZY_V, e0V, V4Mul(v1V, e0XZY_V)); + + const Vec4V v2XZY_V = V4PermYZXW(v2V); + const Vec4V p2V = V4NegMulSub(v2XZY_V, e0V, V4Mul(v2V, e0XZY_V)); + + Vec4V minV = V4Min(p0V, p1V); + minV = V4Min(minV, p2V); + + const Vec4V extentsV = V4LoadU(&extents.x); + const Vec4V fe0ZYX_V = V4Abs(e0V); + + const Vec4V fe0XZY_V = V4PermYZXW(fe0ZYX_V); + const Vec4V extentsXZY_V = V4PermYZXW(extentsV); + Vec4V radV = V4MulAdd(extentsV, fe0XZY_V, V4Mul(extentsXZY_V, fe0ZYX_V)); + + if(V4AnyGrtr3(minV, radV)) + return 0; + + Vec4V maxV = V4Max(p0V, p1V); + maxV = V4Max(maxV, p2V); + + radV = V4Sub(V4Zero(), radV); + + if(V4AnyGrtr3(radV, maxV)) + return 0; + return 1; +} + +static const VecU32V signV = U4LoadXYZW(0x80000000, 0x80000000, 0x80000000, 0x80000000); + +static PX_FORCE_INLINE Ps::IntBool intersectTriangleBoxInternal(const Vec4V v0V, const Vec4V v1V, const Vec4V v2V, const PxVec3& extents) +{ + // Test box axes + { + Vec4V extentsV = V4LoadU(&extents.x); + + { + const Vec4V cV = V4Abs(v0V); + if(V4AllGrtrOrEq3(extentsV, cV)) + return 1; + } + + Vec4V minV = V4Min(v0V, v1V); + minV = V4Min(minV, v2V); + + if(V4AnyGrtr3(minV, extentsV)) + return 0; + + Vec4V maxV = V4Max(v0V, v1V); + maxV = V4Max(maxV, v2V); + extentsV = V4Sub(V4Zero(), extentsV); + + if(V4AnyGrtr3(extentsV, maxV)) + return 0; + } + + // Test if the box intersects the plane of the triangle + const Vec4V e0V = V4Sub(v1V, v0V); + const Vec4V e1V = V4Sub(v2V, v1V); + { + const Vec4V normalV = V4Cross(e0V, e1V); + const Vec4V dV = Vec4V_From_FloatV(V4Dot3(normalV, v0V)); + + const Vec4V extentsV = V4LoadU(&extents.x); + VecU32V normalSignsV = V4U32and(VecU32V_ReinterpretFrom_Vec4V(normalV), signV); + const Vec4V maxV = Vec4V_ReinterpretFrom_VecU32V(V4U32or(VecU32V_ReinterpretFrom_Vec4V(extentsV), normalSignsV)); + + Vec4V tmpV = Vec4V_From_FloatV(V4Dot3(normalV, maxV)); + if(V4AnyGrtr3(dV, tmpV)) + return 0; + + normalSignsV = V4U32xor(normalSignsV, signV); + const Vec4V minV = Vec4V_ReinterpretFrom_VecU32V(V4U32or(VecU32V_ReinterpretFrom_Vec4V(extentsV), normalSignsV)); + + tmpV = Vec4V_From_FloatV(V4Dot3(normalV, minV)); + if(V4AnyGrtr3(tmpV, dV)) + return 0; + } + + // Edge-edge tests + { + if(!testClassIIIAxes(e0V, v0V, v1V, v2V, extents)) + return 0; + if(!testClassIIIAxes(e1V, v0V, v1V, v2V, extents)) + return 0; + const Vec4V e2V = V4Sub(v0V, v2V); + if(!testClassIIIAxes(e2V, v0V, v1V, v2V, extents)) + return 0; + } + return 1; +} + +// PT: a SIMD version of Tomas Moller's triangle-box SAT code +Ps::IntBool Gu::intersectTriangleBox_Unsafe(const PxVec3& center, const PxVec3& extents, const PxVec3& p0, const PxVec3& p1, const PxVec3& p2) +{ + // Move everything so that the boxcenter is in (0,0,0) + const Vec4V BoxCenterV = V4LoadU(¢er.x); + const Vec4V v0V = V4Sub(V4LoadU(&p0.x), BoxCenterV); + const Vec4V v1V = V4Sub(V4LoadU(&p1.x), BoxCenterV); + const Vec4V v2V = V4Sub(V4LoadU(&p2.x), BoxCenterV); + + return intersectTriangleBoxInternal(v0V, v1V, v2V, extents); +} + +Ps::IntBool Gu::intersectTriangleBox(const BoxPadded& box, const PxVec3& p0_, const PxVec3& p1_, const PxVec3& p2_) +{ + // PT: TODO: SIMDify this part + + // Vec3p ensures we can safely V4LoadU the data + const Vec3p p0 = box.rotateInv(p0_ - box.center); + const Vec3p p1 = box.rotateInv(p1_ - box.center); + const Vec3p p2 = box.rotateInv(p2_ - box.center); + + const Vec4V v0V = V4LoadU(&p0.x); + const Vec4V v1V = V4LoadU(&p1.x); + const Vec4V v2V = V4LoadU(&p2.x); + + return intersectTriangleBoxInternal(v0V, v1V, v2V, box.extents); +} + +static PX_FORCE_INLINE Vec4V multiply3x3V(const Vec4V p, const PxMat33& mat) +{ + const FloatV xxxV = V4GetX(p); + const FloatV yyyV = V4GetY(p); + const FloatV zzzV = V4GetZ(p); + + Vec4V ResV = V4Scale(V4LoadU(&mat.column0.x), xxxV); + ResV = V4Add(ResV, V4Scale(V4LoadU(&mat.column1.x), yyyV)); + ResV = V4Add(ResV, V4Scale(V4LoadU(&mat.column2.x), zzzV)); + return ResV; +} + +// PT: warning: all params must be safe to V4LoadU +Ps::IntBool intersectTriangleBoxBV4(const PxVec3& p0, const PxVec3& p1, const PxVec3& p2, + const PxMat33& rotModelToBox, const PxVec3& transModelToBox, const PxVec3& extents) +{ + const Vec4V transModelToBoxV = V4LoadU(&transModelToBox.x); + const Vec4V v0V = V4Add(multiply3x3V(V4LoadU(&p0.x), rotModelToBox), transModelToBoxV); + const Vec4V v1V = V4Add(multiply3x3V(V4LoadU(&p1.x), rotModelToBox), transModelToBoxV); + const Vec4V v2V = V4Add(multiply3x3V(V4LoadU(&p2.x), rotModelToBox), transModelToBoxV); + + return intersectTriangleBoxInternal(v0V, v1V, v2V, extents); +} |