diff options
Diffstat (limited to 'PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionTriangleBox.cpp')
| -rw-r--r-- | PhysX_3.4/Source/GeomUtils/src/intersection/GuIntersectionTriangleBox.cpp | 395 |
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(¢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); +} |