Initial commit:

PhysX 3.4.0 Update @ 21294896
APEX 1.4.0 Update @ 21275617

[CL 21300167]

1 files changed, 395 insertions, 0 deletions

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(&center.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);
+}