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/gjk | |
| 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/gjk')
23 files changed, 5606 insertions, 0 deletions
diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPA.cpp b/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPA.cpp new file mode 100644 index 00000000..44d0507b --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPA.cpp @@ -0,0 +1,698 @@ +// 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 "GuEPA.h" +#include "GuEPAFacet.h" +#include "GuGJKSimplex.h" +#include "CmPriorityQueue.h" +#include "PsAllocator.h" + +#define EPA_DEBUG 0 + +namespace physx +{ +namespace Gu +{ + using namespace Ps::aos; + + class ConvexV; + + struct FacetDistanceComparator + { + bool operator()(const Facet* left, const Facet* right) const + { + return *left < *right; + } + }; + + +#if PX_VC + #pragma warning(push) + #pragma warning( disable : 4324 ) // Padding was added at the end of a structure because of a __declspec(align) value. +#endif + + + class EPA + { + public: + EPA(){} + GjkStatus PenetrationDepth(const GjkConvex& a, const GjkConvex& b, const Ps::aos::Vec3V* PX_RESTRICT Q, const Ps::aos::Vec3V* PX_RESTRICT A, const Ps::aos::Vec3V* PX_RESTRICT B, const PxI32 size, Ps::aos::Vec3V& pa, Ps::aos::Vec3V& pb, Ps::aos::Vec3V& normal, Ps::aos::FloatV& penDepth, const bool takeCoreShape = false); + bool expandPoint(const GjkConvex& a, const GjkConvex& b, PxI32& numVerts, const FloatVArg lowerBound, const FloatVArg upperBound); + bool expandSegment(const GjkConvex& a, const GjkConvex& b, PxI32& numVerts, const FloatVArg lowerBound, const FloatVArg upperBound); + bool expandTriangle(PxI32& numVerts, const FloatVArg lowerBound, const FloatVArg upperBound); + + Facet* addFacet(const PxU32 i0, const PxU32 i1, const PxU32 i2, const Ps::aos::FloatVArg lower2, const Ps::aos::FloatVArg upper2); + + bool originInTetrahedron(const Ps::aos::Vec3VArg p1, const Ps::aos::Vec3VArg p2, const Ps::aos::Vec3VArg p3, const Ps::aos::Vec3VArg p4); + + Cm::InlinePriorityQueue<Facet*, MaxFacets, FacetDistanceComparator> heap; + Ps::aos::Vec3V aBuf[MaxSupportPoints]; + Ps::aos::Vec3V bBuf[MaxSupportPoints]; + Facet facetBuf[MaxFacets]; + EdgeBuffer edgeBuffer; + EPAFacetManager facetManager; + + private: + PX_NOCOPY(EPA) + }; +#if PX_VC + #pragma warning(pop) +#endif + + PX_FORCE_INLINE bool EPA::originInTetrahedron(const Ps::aos::Vec3VArg p1, const Ps::aos::Vec3VArg p2, const Ps::aos::Vec3VArg p3, const Ps::aos::Vec3VArg p4) + { + using namespace Ps::aos; + return BAllEqFFFF(PointOutsideOfPlane4(p1, p2, p3, p4)) == 1; + } + + + static PX_FORCE_INLINE void doSupport(const GjkConvex& a, const GjkConvex& b, const Ps::aos::Vec3VArg dir, Ps::aos::Vec3V& supportA, Ps::aos::Vec3V& supportB, Ps::aos::Vec3V& support) + { + const Vec3V tSupportA = a.support(V3Neg(dir)); + const Vec3V tSupportB = b.support(dir); + //avoid LHS + supportA = tSupportA; + supportB = tSupportB; + support = V3Sub(tSupportA, tSupportB); + } + + static FloatV calculatePlaneDist(const PxU32 i0, const PxU32 i1, const PxU32 i2, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf) + { + const Vec3V pa0(aBuf[i0]); + const Vec3V pa1(aBuf[i1]); + const Vec3V pa2(aBuf[i2]); + + const Vec3V pb0(bBuf[i0]); + const Vec3V pb1(bBuf[i1]); + const Vec3V pb2(bBuf[i2]); + + const Vec3V p0 = V3Sub(pa0, pb0); + const Vec3V p1 = V3Sub(pa1, pb1); + const Vec3V p2 = V3Sub(pa2, pb2); + const Vec3V v1 = V3Sub(p1, p0); + const Vec3V v2 = V3Sub(p2, p0); + const Vec3V v3 = V3Sub(p2, p1); + + const FloatV v1v1 = V3Dot(v1, v1); + const FloatV v2v2 = V3Dot(v2, v2); + const Vec3V v = V3Sel(FIsGrtr(v1v1, v2v2), v2, v1); + + const Vec3V planeNormal = V3Normalize(V3Cross(v, v3)); + return V3Dot(planeNormal, p0); + } + + + GjkStatus epaPenetration(const GjkConvex& a, const GjkConvex& b, PxU8* PX_RESTRICT aInd, PxU8* PX_RESTRICT bInd, PxU8 _size, Ps::aos::Vec3V& contactA, Ps::aos::Vec3V& contactB, Ps::aos::Vec3V& normal, Ps::aos::FloatV& penetrationDepth, const bool takeCoreShape) + { + using namespace Ps::aos; + const BoolV bTrue = BTTTT(); + const Vec3V zeroV = V3Zero(); + + PxU32 size=_size; + const FloatV minMargin = FMin(a.getMinMargin(), b.getMinMargin()); + + //ML: eps2 is the square value of an epsilon value which applied in the termination condition for two shapes overlap. EPA will terminate based on sq(v) < eps2 and indicate that two shapes are overlap. + //we calculate the eps2 based on 10% of the minimum margin of two shapes + const FloatV eps = FMul(minMargin, FLoad(0.1f)); + const FloatV eps2 = FMul(eps, eps); + + Vec3V A[4]; + Vec3V B[4]; + Vec3V Q[4]; + Vec3V v(zeroV); + BoolV bNotTerminated = bTrue; + BoolV bCon = bTrue; + FloatV sDist = FMax(); + FloatV minDist= sDist; + Vec3V supportA, supportB, support; + FloatV marginDif = FZero(); + + if(_size != 0) + { + //ML: we construct a simplex based on the gjk simplex indices + for(PxU32 i=0; i<_size; ++i) + { + supportA = a.supportPoint(aInd[i], &marginDif); + supportB = b.supportPoint(bInd[i], &marginDif); + //avoid LHS in xbox + A[i] = supportA; + B[i] = supportB; + Q[i] = V3Sub(supportA, supportB); + } + + //ML: if any of the gjk shapes is a shrunk shape, we need to recreate the simplex for the original shape to work on; otherwise, we can just skip this process + //and go to the epa code + if(!takeCoreShape) + { + v = GJKCPairDoSimplex(Q, A, B, Q[size-1], size); + sDist = V3Dot(v, v); + bNotTerminated = FIsGrtr(sDist, eps2); + } + else + { + bNotTerminated = BFFFF(); + } + } + else + { + const Vec3V _initialSearchDir = V3Sub(a.getCenter(), b.getCenter()); + v = V3Sel(FIsGrtr(V3Dot(_initialSearchDir, _initialSearchDir), FZero()), _initialSearchDir, V3UnitX()); + } + + + while(BAllEqTTTT(bNotTerminated)) + { + minDist = sDist; + //calculate the support point + //pair->doSupport(v, A[size], B[size], Q[size]); + supportA = a.support(V3Neg(v)); + supportB = b.support(v); + support = V3Sub(supportA, supportB); + A[size] = supportA; + B[size] = supportB; + Q[size++] = support; + + v = GJKCPairDoSimplex(Q, A, B, support, size); + sDist = V3Dot(v, v); + bCon = FIsGrtr(minDist, sDist); + bNotTerminated = BAnd(FIsGrtr(sDist, eps2), bCon); + } + + EPA epa; + + return epa.PenetrationDepth(a, b, Q, A, B, PxI32(size), contactA, contactB, normal, penetrationDepth, takeCoreShape); + } + + //ML: this function returns the signed distance of a point to a plane + PX_FORCE_INLINE Ps::aos::FloatV Facet::getPlaneDist(const Ps::aos::Vec3VArg p, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf) const + { + const Vec3V pa0(aBuf[m_indices[0]]); + const Vec3V pb0(bBuf[m_indices[0]]); + const Vec3V p0 = V3Sub(pa0, pb0); + + return V3Dot(m_planeNormal, V3Sub(p, p0)); + } + + //ML: This function: + // (1)calculates the distance from orign((0, 0, 0)) to a triangle plane + // (2) rejects triangle if the triangle is degenerate (two points are identical) + // (3) rejects triangle to be added into the heap if the plane distance is outside of the boundary[lower, upper] + PX_EPA_FORCE_INLINE Ps::aos::BoolV Facet::isValid2(const PxU32 i0, const PxU32 i1, const PxU32 i2, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, + const Ps::aos::FloatVArg lower, const Ps::aos::FloatVArg upper) + { + using namespace Ps::aos; + const FloatV eps = FEps(); + + const Vec3V pa0(aBuf[i0]); + const Vec3V pa1(aBuf[i1]); + const Vec3V pa2(aBuf[i2]); + + const Vec3V pb0(bBuf[i0]); + const Vec3V pb1(bBuf[i1]); + const Vec3V pb2(bBuf[i2]); + + const Vec3V p0 = V3Sub(pa0, pb0); + const Vec3V p1 = V3Sub(pa1, pb1); + const Vec3V p2 = V3Sub(pa2, pb2); + + const Vec3V v1 = V3Sub(p1, p0); + const Vec3V v2 = V3Sub(p2, p0); + const Vec3V v3 = V3Sub(p2, p1); + + const FloatV v1v1 = V3Dot(v1, v1); + const FloatV v2v2 = V3Dot(v2, v2); + + const Vec3V v = V3Sel(FIsGrtr(v1v1, v2v2), v2, v1); + const Vec3V denormalizedNormal = V3Cross(v, v3); + FloatV norValue = V3Dot(denormalizedNormal, denormalizedNormal); + //if norValue < eps, this triangle is degenerate + const BoolV con = FIsGrtr(norValue, eps); + norValue = FSel(con, norValue, FOne()); + + const Vec3V planeNormal = V3Scale(denormalizedNormal, FRsqrt(norValue)); + const FloatV planeDist = V3Dot(planeNormal, p0); + m_planeNormal = planeNormal; + + FStore(planeDist, &m_planeDist); + + return BAnd(con, BAnd(FIsGrtrOrEq(planeDist, lower), FIsGrtrOrEq(upper, planeDist))); + } + + //ML: if the triangle is valid(not degenerate and within lower and upper bound), we need to add it into the heap. Otherwise, we just return + //the triangle so that the facet can be linked to other facets in the expanded polytope. + Facet* EPA::addFacet(const PxU32 i0, const PxU32 i1, const PxU32 i2, const Ps::aos::FloatVArg lower2, const Ps::aos::FloatVArg upper2) + { + using namespace Ps::aos; + PX_ASSERT(i0 != i1 && i0 != i2 && i1 != i2); + //ML: we move the control in the calling code so we don't need to check weather we will run out of facets or not + PX_ASSERT(facetManager.getNumUsedID() < MaxFacets); + + const PxU32 facetId = facetManager.getNewID(); + Ps::prefetchLine(&facetBuf[facetId], 128); + + Facet * facet = PX_PLACEMENT_NEW(&facetBuf[facetId],Facet(i0, i1, i2)); + facet->m_FacetId = PxU8(facetId); + + const BoolV validTriangle = facet->isValid2(i0, i1, i2, aBuf, bBuf, lower2, upper2); + + if(BAllEqTTTT(validTriangle)) + { + heap.push(facet); + facet->m_inHeap = true; + } + else + { + facet->m_inHeap = false; + } + return facet; + } + + //ML: this function performs a flood fill over the boundary of the current polytope. + void Facet::silhouette(const PxU32 _index, const Ps::aos::Vec3VArg w, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, EdgeBuffer& edgeBuffer, EPAFacetManager& manager) + { + using namespace Ps::aos; + const FloatV zero = FZero(); + Edge stack[MaxFacets]; + stack[0] = Edge(this, _index); + PxI32 size = 1; + while(size--) + { + Facet* const PX_RESTRICT f = stack[size].m_facet; + const PxU32 index = stack[size].m_index; + PX_ASSERT(f->Valid()); + + if(!f->m_obsolete) + { + //ML: if the point is above the facet, the facet has an reflex edge, which will make the polytope concave. Therefore, we need to + //remove this facet and make sure the expanded polytope is convex. + const FloatV pointPlaneDist = f->getPlaneDist(w, aBuf, bBuf); + + if(FAllGrtr(zero, pointPlaneDist)) + { + //ML: facet isn't visible from w (we don't have a reflex edge), this facet will be on the boundary and part of the new polytope so that + //we will push it into our edgeBuffer + edgeBuffer.Insert(f, index); + } + else + { + //ML:facet is visible from w, therefore, we need to remove this facet from the heap and push its adjacent facets onto the stack + f->m_obsolete = true; // Facet is visible from w + const PxU32 next(incMod3(index)); + const PxU32 next2(incMod3(next)); + stack[size++] = Edge(f->m_adjFacets[next2],PxU32(f->m_adjEdges[next2])); + stack[size++] = Edge(f->m_adjFacets[next], PxU32(f->m_adjEdges[next])); + + PX_ASSERT(size <= MaxFacets); + if(!f->m_inHeap) + { + //if the facet isn't in the heap, we can release that memory + manager.deferredFreeID(f->m_FacetId); + } + } + } + } + } + + //ML: this function perform flood fill for the adjancent facet and store the boundary facet into the edgeBuffer + void Facet::silhouette(const Ps::aos::Vec3VArg w, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, EdgeBuffer& edgeBuffer, EPAFacetManager& manager) + { + m_obsolete = true; + for(PxU32 a = 0; a < 3; ++a) + { + m_adjFacets[a]->silhouette(PxU32(m_adjEdges[a]), w, aBuf, bBuf, edgeBuffer, manager); + } + } + + bool EPA::expandPoint(const GjkConvex& a, const GjkConvex& b, PxI32& numVerts, const FloatVArg lowerBound, const FloatVArg upperBound) + { + const Vec3V x = V3UnitX(); + Vec3V q0 = V3Sub(aBuf[0], bBuf[0]); + Vec3V q1; + doSupport(a, b, x, aBuf[1], bBuf[1], q1); + if (V3AllEq(q0, q1)) + return false; + return expandSegment(a, b, numVerts, lowerBound, upperBound); + } + + //ML: this function use the segement to create a triangle + bool EPA::expandSegment(const GjkConvex& a, const GjkConvex& b, PxI32& numVerts, const FloatVArg lowerBound, const FloatVArg upperBound) + { + const Vec3V q0 = V3Sub(aBuf[0], bBuf[0]); + const Vec3V q1 = V3Sub(aBuf[1], bBuf[1]); + const Vec3V v = V3Sub(q1, q0); + const Vec3V absV = V3Abs(v); + + const FloatV x = V3GetX(absV); + const FloatV y = V3GetY(absV); + const FloatV z = V3GetZ(absV); + + Vec3V axis = V3UnitX(); + const BoolV con0 = BAnd(FIsGrtr(x, y), FIsGrtr(z, y)); + if (BAllEqTTTT(con0)) + { + axis = V3UnitY(); + } + else if(FAllGrtr(x, z)) + { + axis = V3UnitZ(); + } + + const Vec3V n = V3Normalize(V3Cross(axis, v)); + Vec3V q2; + doSupport(a, b, n, aBuf[2], bBuf[2], q2); + + return expandTriangle(numVerts, lowerBound, upperBound); + } + + bool EPA::expandTriangle(PxI32& numVerts, const FloatVArg lowerBound, const FloatVArg upperBound) + { + numVerts = 3; + + Facet * PX_RESTRICT f0 = addFacet(0, 1, 2, lowerBound, upperBound); + Facet * PX_RESTRICT f1 = addFacet(1, 0, 2, lowerBound, upperBound); + + if(f0 == NULL || f1 == NULL || heap.empty()) + return false; + + f0->link(0, f1, 0); + f0->link(1, f1, 2); + f0->link(2, f1, 1); + + return true; + } + + + //ML: this function calculates contact information. If takeCoreShape flag is true, this means the two closest points will be on the core shape used in the support functions. + //For example, we treat sphere/capsule as a point/segment in the support function for GJK/EPA, so that the core shape for sphere/capsule is a point/segment. For PCM, we need + //to take the point from the core shape because this will allows us recycle the contacts more stably. For SQ sweeps, we need to take the point on the surface of the sphere/capsule + //when we calculate MTD because this is what will be reported to the user. Therefore, the takeCoreShape flag will be set to be false in SQ. + static void calculateContactInformation(const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, const Facet* facet, const GjkConvex& a, const GjkConvex& b, Vec3V& pa, Vec3V& pb, Vec3V& normal, FloatV& penDepth, const bool takeCoreShape) + { + const FloatV zero = FZero(); + Vec3V _pa, _pb; + facet->getClosestPoint(aBuf, bBuf, _pa, _pb); + //dist > 0 means two shapes are penetrated. If dist < 0(when origin isn't inside the polytope), two shapes status are unknown + const FloatV dist = facet->getPlaneDist(); + //planeNormal is pointing from B to A, however, the normal we are expecting is from A to B which match the GJK margin intersect case, therefore, + //we need to flip the normal + const Vec3V n =V3Neg(facet->getPlaneNormal()); + + if(takeCoreShape) + { + pa = _pa; + pb = _pb; + normal = n; + penDepth = FNeg(dist); + } + else + { + + const BoolV aQuadratic = a.isMarginEqRadius(); + const BoolV bQuadratic = b.isMarginEqRadius(); + + const FloatV marginA = FSel(aQuadratic, a.getMargin(), zero); + const FloatV marginB = FSel(bQuadratic, b.getMargin(), zero); + const FloatV sumMargin = FAdd(marginA, marginB); + pa = V3NegScaleSub(n, marginA, _pa); + pb = V3ScaleAdd(n, marginB, _pb); + normal = n; + penDepth = FNeg(FAdd(dist, sumMargin)); + +#if EPA_DEBUG + const Vec3V v = V3Sub(_pb, _pa); + const FloatV length = V3Length(v); + const Vec3V cn = V3ScaleInv(v, length); + const Vec3V cnn = V3Sel(FIsGrtr(dist, zero), cn, V3Neg(cn)); + //make sure planeNormal and n are pointing to the same direction + const FloatV dir = V3Dot(cnn, normal); + PX_ASSERT(FAllGrtr(dir, zero)); + //planeDist might be zero if the origin didn't include in the polytope + const FloatV dif = V3Sub(length, FAbs(penDepth)); + PX_ASSERT(FAllGrtr(FLoad(1e-5f), FAbs(dif))); +#endif + } + } + + //ML: This function returns one of three status codes: + //(1)EPA_FAIL: the algorithm failed to create a valid polytope(the origin wasn't inside the polytope) from the input simplex + //(2)EPA_CONTACT : the algorithm found the MTD amd converged successfully. + //(3)EPA_DEGENERATE: the algorithm cannot make further progress and the result is unknown. + GjkStatus EPA::PenetrationDepth(const GjkConvex& a, const GjkConvex& b, const Ps::aos::Vec3V* PX_RESTRICT /*Q*/, const Ps::aos::Vec3V* PX_RESTRICT A, const Ps::aos::Vec3V* PX_RESTRICT B, const PxI32 size, Ps::aos::Vec3V& pa, Ps::aos::Vec3V& pb, Ps::aos::Vec3V& normal, Ps::aos::FloatV& penDepth, const bool takeCoreShape) + { + + using namespace Ps::aos; + + Ps::prefetchLine(&facetBuf[0]); + Ps::prefetchLine(&facetBuf[0], 128); + + const FloatV zero = FZero(); + + const FloatV _max = FMax(); + FloatV upper_bound(_max); + FloatV lower_bound(FNeg(_max)); + + aBuf[0]=A[0]; aBuf[1]=A[1]; aBuf[2]=A[2]; aBuf[3]=A[3]; + bBuf[0]=B[0]; bBuf[1]=B[1]; bBuf[2]=B[2]; bBuf[3]=B[3]; + + PxI32 numVertsLocal = 0; + + heap.clear(); + + //if the simplex isn't a tetrahedron, we need to construct one before we can expand it + switch (size) + { + case 1: + { + // Touching contact. Yes, we have a collision and the penetration will be zero + if(!expandPoint(a, b, numVertsLocal, lower_bound, upper_bound)) + return EPA_FAIL; + break; + } + case 2: + { + // We have a line segment inside the Minkowski sum containing the + // origin. we need to construct two back to back triangles which link to each other + if(!expandSegment(a, b, numVertsLocal, lower_bound, upper_bound)) + return EPA_FAIL; + break; + } + case 3: + { + // We have a triangle inside the Minkowski sum containing + // the origin. We need to construct two back to back triangles which link to each other + if(!expandTriangle(numVertsLocal, lower_bound, upper_bound)) + return EPA_FAIL; + + break; + + } + case 4: + { + //check for input face normal. All face normals in this tetrahedron should be all pointing either inwards or outwards. If all face normals are pointing outward, we are good to go. Otherwise, we need to + //shuffle the input vertexes and make sure all face normals are pointing outward + const FloatV planeDistf0 = calculatePlaneDist(0, 1, 2, aBuf, bBuf); + + if(FAllGrtr(zero, planeDistf0)) + { + //shuffle the input vertexes + const Vec3V tempA0 = aBuf[2]; + const Vec3V tempB0 = bBuf[2]; + aBuf[2] = aBuf[1]; + bBuf[2] = bBuf[1]; + aBuf[1] = tempA0; + bBuf[1] = tempB0; + } + Facet * PX_RESTRICT f0 = addFacet(0, 1, 2, lower_bound, upper_bound); + Facet * PX_RESTRICT f1 = addFacet(0, 3, 1, lower_bound, upper_bound); + Facet * PX_RESTRICT f2 = addFacet(0, 2, 3, lower_bound, upper_bound); + Facet * PX_RESTRICT f3 = addFacet(1, 3, 2, lower_bound, upper_bound); + PX_ASSERT(f0->m_planeDist >= 0.f); + PX_ASSERT(f1->m_planeDist >= 0.f); + PX_ASSERT(f2->m_planeDist >= 0.f); + PX_ASSERT(f3->m_planeDist >= 0.f); + + if((f0==NULL) || (f1==NULL) || (f2==NULL) || (f3==NULL) || heap.empty()) + return EPA_FAIL; + + + f0->link(0, f1, 2); + f0->link(1, f3, 2); + f0->link(2, f2, 0); + f1->link(0, f2, 2); + f1->link(1, f3, 0); + f2->link(1, f3, 1); + numVertsLocal = 4; + + break; + } + } + + const FloatV eps = FEps(); + const FloatV tenPerc = FLoad(0.1f); + const FloatV minMargin = FMin(a.getMinMargin(), b.getMinMargin()); + const FloatV eps2 = FMul(minMargin, tenPerc); + + Facet* PX_RESTRICT facet = NULL; + Facet* PX_RESTRICT bestFacet = NULL; + + bool hasMoreFacets = false; + Vec3V tempa, tempb, q; + + do + { + + facetManager.processDeferredIds(); + facet = heap.pop(); //get the shortest distance triangle of origin from the list + facet->m_inHeap = false; + + if (!facet->isObsolete()) + { + bestFacet = facet; + Ps::prefetchLine(edgeBuffer.m_pEdges); + Ps::prefetchLine(edgeBuffer.m_pEdges,128); + Ps::prefetchLine(edgeBuffer.m_pEdges,256); + + const Vec3V planeNormal = facet->getPlaneNormal(); + const FloatV planeDist = facet->getPlaneDist(); + + tempa = a.support(planeNormal); + tempb = b.support(V3Neg(planeNormal)); + + q = V3Sub(tempa, tempb); + + Ps::prefetchLine(&aBuf[numVertsLocal],128); + Ps::prefetchLine(&bBuf[numVertsLocal],128); + + //calculate the distance from support point to the origin along the plane normal. Because the support point is search along + //the plane normal, which means the distance should be positive. However, if the origin isn't contained in the polytope, dist + //might be negative + const FloatV dist = V3Dot(q, planeNormal); + //update the upper bound to the minimum between exisiting upper bound and the distance if distance is positive + upper_bound = FSel(FIsGrtrOrEq(dist, zero), FMin(upper_bound, dist), upper_bound); + //lower bound is the plane distance, which will be the smallest among all the facets in the prority queue + lower_bound = planeDist; + //if the plane distance and the upper bound is within a small tolerance, which means we found the MTD + const BoolV con0 = FIsGrtrOrEq(eps2, FAbs(FSub(upper_bound, lower_bound))); + + if(BAllEqTTTT(con0)) + { + calculateContactInformation(aBuf, bBuf, facet, a, b, pa, pb, normal, penDepth, takeCoreShape); + return EPA_CONTACT; + } + + //if planeDist is the same as dist, which means the support point we get out from the Mincowsky sum is one of the point + //in the triangle facet, we should exist because we can't progress further. + const FloatV dif = FSub(dist, planeDist); + const BoolV degeneratedCondition = FIsGrtr(eps, dif); + if(BAllEqTTTT(degeneratedCondition)) + { + calculateContactInformation(aBuf, bBuf, facet, a, b, pa, pb, normal, penDepth, takeCoreShape); + return EPA_DEGENERATE; + } + + aBuf[numVertsLocal]=tempa; + bBuf[numVertsLocal]=tempb; + + const PxU32 index =PxU32(numVertsLocal++); + + // Compute the silhouette cast by the new vertex + // Note that the new vertex is on the positive side + // of the current facet, so the current facet will + // not be in the polytope. Start local search + // from this facet. + + edgeBuffer.MakeEmpty(); + + facet->silhouette(q, aBuf, bBuf, edgeBuffer, facetManager); + + if (edgeBuffer.IsEmpty()) + { + calculateContactInformation(aBuf, bBuf, facet, a, b, pa, pb, normal, penDepth, takeCoreShape); + return EPA_DEGENERATE; + } + + Edge* PX_RESTRICT edge=edgeBuffer.Get(0); + + PxU32 bufferSize=edgeBuffer.Size(); + + //check to see whether we have enough space in the facet manager to create new facets + if(bufferSize > facetManager.getNumRemainingIDs()) + { + calculateContactInformation(aBuf, bBuf, facet, a, b, pa, pb, normal, penDepth, takeCoreShape); + return EPA_DEGENERATE; + } + + Facet *firstFacet = addFacet(edge->getTarget(), edge->getSource(),index, lower_bound, upper_bound); + PX_ASSERT(firstFacet); + firstFacet->link(0, edge->getFacet(), edge->getIndex()); + + Facet * PX_RESTRICT lastFacet = firstFacet; + + bool degenerate = false; + for(PxU32 i=1; (i<bufferSize) && (!degenerate); ++i) + { + edge=edgeBuffer.Get(i); + Facet* PX_RESTRICT newFacet = addFacet(edge->getTarget(), edge->getSource(),index, lower_bound, upper_bound); + PX_ASSERT(newFacet); + const bool b0 = newFacet->link(0, edge->getFacet(), edge->getIndex()); + const bool b1 = newFacet->link(2, lastFacet, 1); + degenerate = degenerate || !b0 || !b1; + lastFacet = newFacet; + } + + if(degenerate) + { + calculateContactInformation(aBuf, bBuf, facet, a, b, pa, pb, normal, penDepth, takeCoreShape); + return EPA_DEGENERATE; + } + + firstFacet->link(2, lastFacet, 1); + } + facetManager.freeID(facet->m_FacetId); + + hasMoreFacets = (heap.size() > 0); + //after polytope expansion, we don't have a better facet to work with so that we should process the best facet + //this sometime won't produce the MTD but the result seems close enough so we accept it as contact. + //test case in BenchMark_GJKEPABoxConvex + if(hasMoreFacets && FAllGrtr( heap.top()->getPlaneDist(), upper_bound)) + { + calculateContactInformation(aBuf, bBuf, bestFacet, a, b, pa, pb, normal, penDepth, takeCoreShape); + return EPA_CONTACT; + } + } + while(hasMoreFacets && numVertsLocal != MaxSupportPoints); + + calculateContactInformation(aBuf, bBuf, facet, a, b, pa, pb, normal, penDepth, takeCoreShape); + + return EPA_DEGENERATE; + } +} + +} diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPA.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPA.h new file mode 100644 index 00000000..79f934e6 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPA.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_EPA_H +#define GU_EPA_H + +#include "GuGJKUtil.h" +#include "GuGJKType.h" + +namespace physx +{ + +namespace Gu +{ + //ML: The main entry point for EPA. + // + //This function returns one of three status codes: + //(1)EPA_FAIL: the algorithm failed to create a valid polytope(the origin wasn't inside the polytope) from the input simplex. + //(2)EPA_CONTACT : the algorithm found the MTD and converged successfully. + //(3)EPA_DEGENERATE: the algorithm cannot make further progress and the result is unknown. + + GjkStatus epaPenetration(const GjkConvex& a, const GjkConvex& b, // two convexes, in the same space + PxU8* PX_RESTRICT aInd, PxU8* PX_RESTRICT bInd, // warm start index points to create an initial simplex that EPA will work on + PxU8 _size, // count of warm-start indices + Ps::aos::Vec3V& contactA, Ps::aos::Vec3V& contactB, // a point on each body: when B is translated by normal*penetrationDepth, these are coincident + Ps::aos::Vec3V& normal, Ps::aos::FloatV& depth, // MTD normal & penetration depth + const bool takeCoreShape = false); // indicates whether we take support point from the core shape of the convexes +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPAFacet.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPAFacet.h new file mode 100644 index 00000000..5e2c6cde --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuEPAFacet.h @@ -0,0 +1,292 @@ +// 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_EPA_FACET_H +#define GU_EPA_FACET_H + +#include "CmPhysXCommon.h" +#include "PsVecMath.h" +#include "PsFPU.h" +#include "PsUtilities.h" +#include "CmIDPool.h" + +#if (defined __GNUC__ && defined _DEBUG) +#define PX_EPA_FORCE_INLINE +#else +#define PX_EPA_FORCE_INLINE PX_FORCE_INLINE +#endif + +namespace physx +{ +#define MaxEdges 32 +#define MaxFacets 64 +#define MaxSupportPoints 64 + +namespace Gu +{ + const PxU32 lookUp[3] = {1, 2, 0}; + + PX_FORCE_INLINE PxU32 incMod3(PxU32 i) { return lookUp[i]; } + + class EdgeBuffer; + class Edge; + typedef Cm::InlineDeferredIDPool<MaxFacets> EPAFacetManager; + + class Facet + { + public: + + Facet() + { + } + + PX_FORCE_INLINE Facet(const PxU32 _i0, const PxU32 _i1, const PxU32 _i2) + : m_obsolete(false), m_inHeap(false) + { + m_indices[0]= Ps::toI8(_i0); + m_indices[1]= Ps::toI8(_i1); + m_indices[2]= Ps::toI8(_i2); + + m_adjFacets[0] = m_adjFacets[1] = m_adjFacets[2] = NULL; + m_adjEdges[0] = m_adjEdges[1] = m_adjEdges[2] = -1; + } + + + PX_FORCE_INLINE void invalidate() + { + m_adjFacets[0] = m_adjFacets[1] = m_adjFacets[2] = NULL; + m_adjEdges[0] = m_adjEdges[1] = m_adjEdges[2] = -1; + } + + PX_FORCE_INLINE bool Valid() + { + return (m_adjFacets[0] != NULL) & (m_adjFacets[1] != NULL) & (m_adjFacets[2] != NULL); + } + + PX_FORCE_INLINE PxU32 operator[](const PxU32 i) const + { + return PxU32(m_indices[i]); + } + + //create ajacency information + bool link(const PxU32 edge0, Facet* PX_RESTRICT facet, const PxU32 edge1); + + PX_FORCE_INLINE bool isObsolete() const { return m_obsolete; } + + //calculate the signed distance from a point to a plane + PX_FORCE_INLINE Ps::aos::FloatV getPlaneDist(const Ps::aos::Vec3VArg p, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf) const; + + //check to see whether the triangle is a valid triangle, calculate plane normal and plane distance at the same time + PX_EPA_FORCE_INLINE Ps::aos::BoolV isValid2(const PxU32 i0, const PxU32 i1, const PxU32 i2, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, + const Ps::aos::FloatVArg lower, const Ps::aos::FloatVArg upper); + + //return the absolute value for the plane distance from origin + PX_FORCE_INLINE Ps::aos::FloatV getPlaneDist() const + { + return Ps::aos::FLoad(m_planeDist); + } + + //return the plane normal + PX_FORCE_INLINE Ps::aos::Vec3V getPlaneNormal()const + { + return m_planeNormal; + } + + //calculate the closest points for a shape pair + void getClosestPoint(const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, Ps::aos::Vec3V& closestA, Ps::aos::Vec3V& closestB) const; + + //performs a flood fill over the boundary of the current polytope. + void silhouette(const Ps::aos::Vec3VArg w, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, EdgeBuffer& edgeBuffer, EPAFacetManager& manager); + + + //m_planeDist is positive + bool operator <(const Facet& b) const + { + return m_planeDist < b.m_planeDist; + } + + //store all the boundary facets for the new polytope in the edgeBuffer and free indices when an old facet isn't part of the boundary anymore + PX_FORCE_INLINE void silhouette(const PxU32 index, const Ps::aos::Vec3VArg w, const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, EdgeBuffer& edgeBuffer, + EPAFacetManager& manager); + + Ps::aos::Vec3V m_planeNormal; //16 + PxF32 m_planeDist; //20 + + Facet* PX_RESTRICT m_adjFacets[3]; //the triangle adjacent to edge i in this triangle //32 + PxI8 m_adjEdges[3]; //the edge connected with the corresponding triangle //35 + PxI8 m_indices[3]; //the index of vertices of the triangle //38 + bool m_obsolete; //a flag to denote whether the triangle are still part of the bundeary of the new polytope //39 + bool m_inHeap; //a flag to indicate whether the triangle is in the heap //40 + PxU8 m_FacetId; //41 //73 + + }; + + + class Edge + { + public: + PX_FORCE_INLINE Edge() {} + PX_FORCE_INLINE Edge(Facet * PX_RESTRICT facet, const PxU32 index) : m_facet(facet), m_index(index) {} + PX_FORCE_INLINE Edge(const Edge& other) : m_facet(other.m_facet), m_index(other.m_index){} + + PX_FORCE_INLINE Edge& operator = (const Edge& other) + { + m_facet = other.m_facet; + m_index = other.m_index; + return *this; + } + + PX_FORCE_INLINE Facet *getFacet() const { return m_facet; } + PX_FORCE_INLINE PxU32 getIndex() const { return m_index; } + + //get out the associated start vertex index in this edge from the facet + PX_FORCE_INLINE PxU32 getSource() const + { + PX_ASSERT(m_index < 3); + return (*m_facet)[m_index]; + } + + //get out the associated end vertex index in this edge from the facet + PX_FORCE_INLINE PxU32 getTarget() const + { + PX_ASSERT(m_index < 3); + return (*m_facet)[incMod3(m_index)]; + } + + Facet* PX_RESTRICT m_facet; + PxU32 m_index; + }; + + + class EdgeBuffer + { + public: + EdgeBuffer() : m_Size(0) + { + } + + Edge* Insert(const Edge& edge) + { + PX_ASSERT(m_Size < MaxEdges); + Edge* PX_RESTRICT pEdge = &m_pEdges[m_Size++]; + *pEdge = edge; + return pEdge; + } + + Edge* Insert(Facet* PX_RESTRICT facet, const PxU32 index) + { + PX_ASSERT(m_Size < MaxEdges); + Edge* pEdge = &m_pEdges[m_Size++]; + pEdge->m_facet=facet; + pEdge->m_index=index; + return pEdge; + } + + Edge* Get(const PxU32 index) + { + PX_ASSERT(index < m_Size); + return &m_pEdges[index]; + } + + PxU32 Size() + { + return m_Size; + } + + bool IsEmpty() + { + return m_Size == 0; + } + + void MakeEmpty() + { + m_Size = 0; + } + + Edge m_pEdges[MaxEdges]; + PxU32 m_Size; + }; + + //ML: calculate MTD points for a shape pair + PX_FORCE_INLINE void Facet::getClosestPoint(const Ps::aos::Vec3V* PX_RESTRICT aBuf, const Ps::aos::Vec3V* PX_RESTRICT bBuf, Ps::aos::Vec3V& closestA, Ps::aos::Vec3V& closestB) const + { + using namespace Ps::aos; + + const Vec3V pa0(aBuf[m_indices[0]]); + const Vec3V pa1(aBuf[m_indices[1]]); + const Vec3V pa2(aBuf[m_indices[2]]); + + const Vec3V pb0(bBuf[m_indices[0]]); + const Vec3V pb1(bBuf[m_indices[1]]); + const Vec3V pb2(bBuf[m_indices[2]]); + + const Vec3V p0 = V3Sub(pa0, pb0); + const Vec3V p1 = V3Sub(pa1, pb1); + const Vec3V p2 = V3Sub(pa2, pb2); + + const Vec3V v1 = V3Sub(p1, p0); + const Vec3V v2 = V3Sub(p2, p0); + + const FloatV v1dv1 = V3Dot(v1, v1); + const FloatV v1dv2 = V3Dot(v1, v2); + const FloatV v2dv2 = V3Dot(v2, v2); + + const FloatV p0dv1 = V3Dot(p0, v1); //V3Dot(V3Sub(p0, origin), v1); + const FloatV p0dv2 = V3Dot(p0, v2); + + const FloatV det = FNegScaleSub(v1dv2, v1dv2, FMul(v1dv1, v2dv2));//FSub( FMul(v1dv1, v2dv2), FMul(v1dv2, v1dv2) ); // non-negative + const FloatV recip = FRecip(det); + + const FloatV lambda1 = FMul(FNegScaleSub(p0dv1, v2dv2, FMul(p0dv2, v1dv2)), recip); + const FloatV lambda2 = FMul(FNegScaleSub(p0dv2, v1dv1, FMul(p0dv1, v1dv2)), recip); + + const Vec3V a0 = V3Scale(V3Sub(pa1, pa0), lambda1); + const Vec3V a1 = V3Scale(V3Sub(pa2, pa0), lambda2); + const Vec3V b0 = V3Scale(V3Sub(pb1, pb0), lambda1); + const Vec3V b1 = V3Scale(V3Sub(pb2, pb0), lambda2); + closestA = V3Add(V3Add(a0, a1), pa0); + closestB = V3Add(V3Add(b0, b1), pb0); + } + + //ML: create adjacency informations for both facets + PX_FORCE_INLINE bool Facet::link(const PxU32 edge0, Facet * PX_RESTRICT facet, const PxU32 edge1) + { + m_adjFacets[edge0] = facet; + m_adjEdges[edge0] = Ps::toI8(edge1); + facet->m_adjFacets[edge1] = this; + facet->m_adjEdges[edge1] = Ps::toI8(edge0); + + return (m_indices[edge0] == facet->m_indices[incMod3(edge1)]) && (m_indices[incMod3(edge0)] == facet->m_indices[edge1]); + } + +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJK.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJK.h new file mode 100644 index 00000000..d0f1254e --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJK.h @@ -0,0 +1,219 @@ +// 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_GJK_H +#define GU_GJK_H + + +#include "GuGJKType.h" +#include "GuGJKUtil.h" +#include "GuConvexSupportTable.h" +#include "GuGJKSimplex.h" +#include "PsFPU.h" + +#define GJK_SEPERATING_AXIS_VALIDATE 0 + +namespace physx +{ +namespace Gu +{ + + class ConvexV; + +#if GJK_SEPERATING_AXIS_VALIDATE + template<typename ConvexA, typename ConvexB> + static void validateSeparatingAxis(const ConvexA& a, const ConvexB& b, const Ps::aos::Vec3VArg separatingAxis) + { + using namespace Ps::aos; + const Vec3V minV0 = a.ConvexA::support(V3Neg(separatingAxis)); + const Vec3V maxV0 = a.ConvexA::support(separatingAxis); + + const Vec3V minV1 = b.ConvexB::support(V3Neg(separatingAxis)); + const Vec3V maxV1 = b.ConvexB::support(separatingAxis); + + const FloatV min0 = V3Dot(minV0, separatingAxis); + const FloatV max0 = V3Dot(maxV0, separatingAxis); + + const FloatV min1 = V3Dot(minV1, separatingAxis); + const FloatV max1 = V3Dot(maxV1, separatingAxis); + + PX_ASSERT(FAllGrtr(min1, max0) || FAllGrtr(min0, max1)); + } +#endif + + + /* + + initialSearchDir :initial search direction in the mincowsky sum, it should be in the local space of ConvexB + closestA :it is the closest point in ConvexA in the local space of ConvexB if acceptance threshold is sufficent large. Otherwise, it will be garbage + closestB :it is the closest point in ConvexB in the local space of ConvexB if acceptance threshold is sufficent large. Otherwise, it will be garbage + normal :normal pointing from ConvexA to ConvexB in the local space of ConvexB if acceptance threshold is sufficent large. Otherwise, it will be garbage + distance :the distance of the closest points between ConvexA and ConvexB if acceptance threshold is sufficent large. Otherwise, it will be garbage + contactDist :the distance which we will generate contact information if ConvexA and ConvexB are both separated within contactDist + */ + + //*Each convex has + //* a support function + //* a margin - the amount by which we shrunk the shape for a convex or box. If the shape are sphere/capsule, margin is the radius + //* a minMargin - some percentage of margin, which is used to determine the termination condition for gjk + + //*We'll report: + //* GJK_NON_INTERSECT if the sign distance between the shapes is greater than the sum of the margins and the the contactDistance + //* GJK_CLOSE if the minimum distance between the shapes is less than the sum of the margins and the the contactDistance + //* GJK_CONTACT if the two shapes are overlapped with each other + template<typename ConvexA, typename ConvexB> + GjkStatus gjk(const ConvexA& a, const ConvexB& b, const Ps::aos::Vec3V& initialSearchDir, const Ps::aos::FloatV& contactDist, Ps::aos::Vec3V& closestA, Ps::aos::Vec3V& closestB, Ps::aos::Vec3V& normal, + Ps::aos::FloatV& distance) + { + using namespace Ps::aos; + Vec3V Q[4]; + Vec3V A[4]; + Vec3V B[4]; + + const FloatV zero = FZero(); + PxU32 size=0; + + //const Vec3V _initialSearchDir = aToB.p; + Vec3V closest = V3Sel(FIsGrtr(V3Dot(initialSearchDir, initialSearchDir), zero), initialSearchDir, V3UnitX()); + Vec3V v = V3Normalize(closest); + + // ML: eps2 is the square value of an epsilon value which applied in the termination condition for two shapes overlap. + // GJK will terminate based on sq(v) < eps and indicate that two shapes are overlapping. + // we calculate the eps based on 10% of the minimum margin of two shapes + const FloatV tenPerc = FLoad(0.1f); + const FloatV minMargin = FMin(a.getMinMargin(), b.getMinMargin()); + const FloatV eps = FMul(minMargin, tenPerc); + + // ML:epsRel is square value of 1.5% which applied to the distance of a closest point(v) to the origin. + // If |v|- v/|v|.dot(w) < epsRel*|v|, + // two shapes are clearly separated, GJK terminate and return non intersect. + // This adjusts the termination condition based on the length of v + // which avoids ill-conditioned terminations. + const FloatV epsRel = FLoad(0.000225f);//1.5%. + + FloatV dist = FMax(); + FloatV prevDist; + Vec3V prevClos, prevDir; + + const BoolV bTrue = BTTTT(); + BoolV bNotTerminated = bTrue; + BoolV bNotDegenerated = bTrue; + + //ML: we treate sphere as a point and capsule as segment in the support function, so that we need to add on radius + const BoolV aQuadratic = a.isMarginEqRadius(); + const BoolV bQuadratic = b.isMarginEqRadius(); + + const FloatV sumMargin = FAdd(FSel(aQuadratic, a.getMargin(), zero), FSel(bQuadratic, b.getMargin(), zero)); + const FloatV separatingDist = FAdd(sumMargin, contactDist); + const FloatV relDif = FSub(FOne(), epsRel); + + do + { + prevDist = dist; + prevClos = closest; + prevDir = v; + + //de-virtualize, we don't need to use a normalize direction to get the support point + //this will allow the cpu better pipeline the normalize calculation while it does the + //support map + const Vec3V supportA=a.ConvexA::support(V3Neg(closest)); + const Vec3V supportB=b.ConvexB::support(closest); + + //calculate the support point + const Vec3V support = V3Sub(supportA, supportB); + + const FloatV signDist = V3Dot(v, support); + + if(FAllGrtr(signDist, separatingDist)) + { + //ML:gjk found a separating axis for these two objects and the distance is large than the seperating distance, gjk might not converage so that + //we won't generate contact information +#if GJK_SEPERATING_AXIS_VALIDATE + validateSeparatingAxis(a, b, v); +#endif + return GJK_NON_INTERSECT; + } + + const BoolV con = BAnd(FIsGrtr(signDist, sumMargin), FIsGrtr(signDist, FMul(relDif, dist))); + + if(BAllEqTTTT(con)) + { + //ML:: gjk converage and we get the closest point information + Vec3V closA, closB; + //normal point from A to B + const Vec3V n = V3Neg(v); + getClosestPoint(Q, A, B, closest, closA, closB, size); + closestA = V3Sel(aQuadratic, V3ScaleAdd(n, a.getMargin(), closA), closA); + closestB = V3Sel(bQuadratic, V3NegScaleSub(n, b.getMargin(), closB), closB); + distance = FMax(zero, FSub(dist, sumMargin)); + normal = n;//V3Normalize(V3Neg(closest)); + return GJK_CLOSE; + } + + PX_ASSERT(size < 4); + A[size]=supportA; + B[size]=supportB; + Q[size++]=support; + + //calculate the closest point between two convex hull + closest = GJKCPairDoSimplex(Q, A, B, support, size); + + dist = V3Length(closest); + v = V3ScaleInv(closest, dist); + bNotDegenerated = FIsGrtr(prevDist, dist); + bNotTerminated = BAnd(FIsGrtr(dist, eps), bNotDegenerated); + }while(BAllEqTTTT(bNotTerminated)); + + if(BAllEqTTTT(bNotDegenerated)) + { + //GJK_CONTACT + distance = zero; + return GJK_CONTACT; + } + + //GJK degenerated, use the previous closest point + const FloatV acceptancePerc = FLoad(0.2f); + const FloatV acceptanceMargin = FMul(acceptancePerc, FMin(a.getMargin(), b.getMargin())); + const FloatV acceptanceDist = FSel(FIsGrtr(sumMargin, zero), sumMargin, acceptanceMargin); + Vec3V closA, closB; + const Vec3V n = V3Neg(prevDir);//V3Normalize(V3Neg(prevClos)); + getClosestPoint(Q, A, B, prevClos, closA, closB, size); + closestA = V3Sel(aQuadratic, V3ScaleAdd(n, a.getMargin(), closA), closA); + closestB = V3Sel(bQuadratic, V3NegScaleSub(n, b.getMargin(), closB), closB); + normal = n; + dist = FMax(zero, FSub(prevDist, sumMargin)); + distance = dist; + + return FAllGrtr(dist, acceptanceDist) ? GJK_CLOSE: GJK_CONTACT; + } +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKPenetration.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKPenetration.h new file mode 100644 index 00000000..17d26e62 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKPenetration.h @@ -0,0 +1,336 @@ +// 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_GJK_PENETRATION_H +#define GU_GJK_PENETRATION_H + + +#include "GuConvexSupportTable.h" +#include "GuGJKSimplex.h" +#include "GuVecShrunkConvexHullNoScale.h" +#include "GuVecConvexHullNoScale.h" +#include "GuGJKUtil.h" +#include "PsUtilities.h" +#include "GuGJKType.h" + +#define GJK_VALIDATE 0 + + +namespace physx +{ +namespace Gu +{ + + class ConvexV; + + + PX_FORCE_INLINE void assignWarmStartValue(PxU8* PX_RESTRICT aIndices, PxU8* PX_RESTRICT bIndices, PxU8& size_, PxI32* PX_RESTRICT aInd, PxI32* PX_RESTRICT bInd, PxU32 size ) + { + if(aIndices) + { + PX_ASSERT(bIndices); + size_ = Ps::to8(size); + for(PxU32 i=0; i<size; ++i) + { + aIndices[i] = Ps::to8(aInd[i]); + bIndices[i] = Ps::to8(bInd[i]); + } + } + } + + + PX_FORCE_INLINE void validateDuplicateVertex(const Ps::aos::Vec3V* Q, const Ps::aos::Vec3VArg support, const PxU32 size) + { + using namespace Ps::aos; + + const FloatV eps = FEps(); + //Get rid of the duplicate point + BoolV match = BFFFF(); + for(PxU32 na = 0; na < size; ++na) + { + Vec3V dif = V3Sub(Q[na], support); + match = BOr(match, FIsGrtr(eps, V3Dot(dif, dif))); + } + + //we have duplicate code + if(BAllEqTTTT(match)) + { + PX_ASSERT(0); + } + } + + + //*Each convex has + //* a support function + //* a margin - the amount by which we shrunk the shape for a convex or box. If the shape are sphere/capsule, margin is the radius + //* a minMargin - some percentage of margin, which is used to determine the termination condition for gjk + + //*We'll report: + //* GJK_NON_INTERSECT if the minimum distance between the shapes is greater than the sum of the margins and the the contactDistance + //* EPA_CONTACT if shrunk shapes overlap. We treat sphere/capsule as a point/a segment and we shrunk other shapes by 10% of margin + //* GJK_CONTACT if the algorithm converges, and the distance between the shapes is less than the sum of the margins plus the contactDistance. In this case we return the closest points found + //* GJK_DEGENERATE if the algorithm doesn't converge, we return this flag to indicate the normal and closest point we return might not be accurated + template<typename ConvexA, typename ConvexB > + PX_NOINLINE GjkStatus gjkPenetration(const ConvexA& a, const ConvexB& b, const Ps::aos::Vec3VArg initialSearchDir, const Ps::aos::FloatVArg originalContactDist, Ps::aos::Vec3V& contactA, + Ps::aos::Vec3V& contactB, Ps::aos::Vec3V& normal, Ps::aos::FloatV& penetrationDepth, PxU8* PX_RESTRICT aIndices, PxU8* PX_RESTRICT bIndices, PxU8& warmStartSize, const bool takeCoreShape) + { + using namespace Ps::aos; + + const FloatV marginA = a.getMargin(); + const FloatV marginB = b.getMargin(); + + //ML: eps is the threshold that uses to determine whether two (shrunk) shapes overlap. We calculate eps2 based on 10% of the minimum margin of two shapes + const FloatV minMargin = FMin(a.ConvexA::getMinMargin(), b.ConvexB::getMinMargin()); + const FloatV eps = FMul(minMargin, FLoad(0.1f)); + + //const FloatV eps2 = FMul(_eps2, _eps2); + //ML: epsRel2 is the square of 0.01. This is used to scale the square distance of a closest point to origin to determine whether two shrunk shapes overlap in the margin, but + //they don't overlap. + //const FloatV epsRel2 = FMax(FLoad(0.0001), eps2); + + // ML:epsRel is square value of 1.5% which applied to the distance of a closest point(v) to the origin. + // If |v|- v/|v|.dot(w) < epsRel*|v|=>(|v|*(1-epsRel) < v/|v|.dot(w)), + // two shapes are clearly separated, GJK terminate and return non intersect. + // This adjusts the termination condition based on the length of v + // which avoids ill-conditioned terminations. + const FloatV epsRel = FLoad(0.000225f);//1.5%. + const FloatV relDif = FSub(FOne(), epsRel); + + const FloatV sumOriginalMargin = FAdd(marginA, marginB); + FloatV contactDist = originalContactDist; + + FloatV dist = FMax(); + FloatV prevDist = dist; + const Vec3V zeroV = V3Zero(); + Vec3V prevClos = zeroV; + + const BoolV bTrue = BTTTT(); + BoolV bNotTerminated = bTrue; + BoolV bNotDegenerated = bTrue; + Vec3V closest; + + Vec3V Q[4]; + Vec3V A[4]; + Vec3V B[4]; + PxI32 aInd[4]; + PxI32 bInd[4]; + Vec3V supportA = zeroV, supportB = zeroV, support=zeroV; + Vec3V v; + + PxU32 size = 0;//_size; + const FloatV zero = FZero(); + FloatV marginDifA = zero; + FloatV marginDifB = zero; + FloatV maxMarginDif = zero; + + //ML: if _size!=0, which means we pass in the previous frame simplex so that we can warm-start the simplex. + //In this case, GJK will normally terminate in one iteration + if(warmStartSize != 0) + { + for(PxU32 i=0; i<warmStartSize; ++i) + { + aInd[i] = aIndices[i]; + bInd[i] = bIndices[i]; + + //de-virtualize + supportA = a.ConvexA::supportPoint(aIndices[i], &marginDifA); + supportB = b.ConvexB::supportPoint(bIndices[i], &marginDifB); + maxMarginDif = FAdd(marginDifA, marginDifB); + contactDist = FMax(contactDist, FAdd(originalContactDist, maxMarginDif)); + + support = V3Sub(supportA, supportB); + +#if GJK_VALIDATE + //ML: this is used to varify whether we will have duplicate vertices in the warm-start value. If this function get triggered, + //this means something isn't right and we need to investigate + validateDuplicateVertex(Q, support, size); +#endif + A[size] = supportA; + B[size] = supportB; + Q[size++] = support; + } + + //run simplex solver to determine whether the point is closest enough so that gjk can terminate + closest = GJKCPairDoSimplex(Q, A, B, aInd, bInd, support, size); + dist = V3Length(closest); + //sDist = V3Dot(closest, closest); + v = V3ScaleInv(closest, dist); + prevDist = dist; + prevClos = closest; + + bNotTerminated = FIsGrtr(dist, eps); + } + else + { + //const Vec3V _initialSearchDir = V3Sub(a.getCenter(), b.getCenter()); + closest = V3Sel(FIsGrtr(V3Dot(initialSearchDir, initialSearchDir), zero), initialSearchDir, V3UnitX()); + v = V3Normalize(closest); + } + + + // ML : termination condition + //(1)two (shrunk)shapes overlap. GJK will terminate based on sq(v) < eps2 and indicate that two shapes are overlapping. + //(2)two (shrunk + margin)shapes are separated. If sq(vw) > sqMargin * sq(v), which means the original objects do not intesect, GJK terminate with GJK_NON_INTERSECT. + //(3)two (shrunk) shapes don't overlap. However, they interect within margin distance. if sq(v)- vw < epsRel2*sq(v), this means the shrunk shapes interect in the margin, + // GJK terminate with GJK_CONTACT. + while(BAllEqTTTT(bNotTerminated)) + { + //prevDist, prevClos are used to store the previous iteration's closest point and the square distance from the closest point + //to origin in Mincowski space + prevDist = dist; + prevClos = closest; + + //de-virtualize + supportA = a.ConvexA::support(V3Neg(closest), aInd[size], &marginDifA); + supportB = b.ConvexB::support(closest, bInd[size], &marginDifB); + + //calculate the support point + support = V3Sub(supportA, supportB); + + //ML: because we shrink the shapes by plane shifting(box and convexhull), the distance from the "shrunk" vertices to the original vertices may be larger than contact distance. + //therefore, we need to take the largest of these 2 values into account so that we don't incorrectly declare shapes to be disjoint. If we don't do this, there is + //an inherent inconsistency between fallback SAT tests and GJK tests that may result in popping due to SAT discovering deep penetrations that were not detected by + //GJK operating on a shrunk shape. + //const FloatV maxMarginDif = FMax(a.getMarginDif(), b.getMarginDif()); + //contactDist = FMax(contactDist, maxMarginDif); + maxMarginDif = FAdd(marginDifA, marginDifB); + contactDist = FMax(contactDist, FAdd(originalContactDist, maxMarginDif)); + + const FloatV sumMargin = FAdd(sumOriginalMargin, contactDist); + + const FloatV vw = V3Dot(v, support); + if(FAllGrtr(vw, sumMargin)) + { + assignWarmStartValue(aIndices, bIndices, warmStartSize, aInd, bInd, size); + return GJK_NON_INTERSECT; + } + + //if(FAllGrtr(FMul(epsRel, dist), FSub(dist, vw))) + if(FAllGrtr(vw, FMul(dist, relDif))) + { + assignWarmStartValue(aIndices, bIndices, warmStartSize, aInd, bInd, size); + PX_ASSERT(FAllGrtr(dist, FEps())); + //const Vec3V n = V3ScaleInv(closest, dist);//normalise + normal = v; + Vec3V closA, closB; + getClosestPoint(Q, A, B, closest, closA, closB, size); + //ML: if one of the shape is sphere/capsule and the takeCoreShape flag is true, the contact point for sphere/capsule will be the sphere center or a point in the + //capsule segment. This will increase the stability for the manifold recycling code. Otherwise, we will return a contact point on the surface for sphere/capsule + //while the takeCoreShape flag is set to be false + if(takeCoreShape) + { + const BoolV aQuadratic = a.isMarginEqRadius(); + const BoolV bQuadratic = b.isMarginEqRadius(); + const FloatV shrunkFactorA = FSel(aQuadratic, zero, marginA); + const FloatV shrunkFactorB = FSel(bQuadratic, zero, marginB); + const FloatV sumShrunkFactor = FAdd(shrunkFactorA, shrunkFactorB); + contactA = V3NegScaleSub(v, shrunkFactorA, closA); + contactB = V3ScaleAdd(v, shrunkFactorB, closB); + penetrationDepth = FSub(dist, sumShrunkFactor); + + } + else + { + contactA = V3NegScaleSub(v, marginA, closA); + contactB = V3ScaleAdd(v, marginB, closB); + penetrationDepth = FSub(dist, sumOriginalMargin); + } + + return GJK_CONTACT; + } + + A[size] = supportA; + B[size] = supportB; + Q[size++]=support; + PX_ASSERT(size <= 4); + + //calculate the closest point between two convex hull + closest = GJKCPairDoSimplex(Q, A, B, aInd, bInd, support, size); + + dist = V3Length(closest); + v = V3ScaleInv(closest, dist); + + bNotDegenerated = FIsGrtr(prevDist, dist); + bNotTerminated = BAnd(FIsGrtr(dist, eps), bNotDegenerated); + } + + if(BAllEqFFFF(bNotDegenerated)) + { + assignWarmStartValue(aIndices, bIndices, warmStartSize, aInd, bInd, size-1); + + //Reset back to older closest point + dist = prevDist; + closest = prevClos;//V3Sub(closA, closB); + Vec3V closA, closB; + getClosestPoint(Q, A, B, closest, closA, closB, size); + + PX_ASSERT(FAllGrtr(dist, FEps())); + const Vec3V n = V3ScaleInv(closest, dist);//normalise + normal = n; + + if(takeCoreShape) + { + const FloatV sumExpandedMargin = FAdd(sumOriginalMargin, contactDist); + //const FloatV sqExpandedMargin = FMul(sumExpandedMargin, sumExpandedMargin); + const BoolV aQuadratic = a.ConvexA::isMarginEqRadius(); + const BoolV bQuadratic = b.ConvexB::isMarginEqRadius(); + const FloatV shrunkFactorA = FSel(aQuadratic, zero, marginA); + const FloatV shrunkFactorB = FSel(bQuadratic, zero, marginB); + const FloatV sumShrunkFactor = FAdd(shrunkFactorA, shrunkFactorB); + contactA = V3NegScaleSub(n, shrunkFactorA, closA); + contactB = V3ScaleAdd(n, shrunkFactorB, closB); + penetrationDepth = FSub(dist, sumShrunkFactor); + if(FAllGrtrOrEq(sumExpandedMargin, dist)) + return GJK_CONTACT; + } + else + { + contactA = V3NegScaleSub(n, marginA, closA); + contactB = V3ScaleAdd(n, marginB, closB); + penetrationDepth = FSub(dist, sumOriginalMargin); + } + + + return GJK_DEGENERATE; + + } + else + { + //this two shapes are deeply intersected with each other, we need to use EPA algorithm to calculate MTD + assignWarmStartValue(aIndices, bIndices, warmStartSize, aInd, bInd, size); + return EPA_CONTACT; + + } + } + +}//Gu + +}//physx + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKRaycast.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKRaycast.h new file mode 100644 index 00000000..32b12790 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKRaycast.h @@ -0,0 +1,291 @@ +// 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_GJKRAYCAST_H +#define GU_GJKRAYCAST_H + +#include "GuGJKType.h" +#include "GuGJKSimplex.h" +#include "GuConvexSupportTable.h" +#include "GuGJKPenetration.h" +#include "GuEPA.h" + + +namespace physx +{ + + +namespace Gu +{ + + /* + ConvexA is in the local space of ConvexB + lambda : the time of impact(TOI) + initialLambda : the start time of impact value (disable) + s : the sweep ray origin + r : the normalized sweep ray direction scaled by the sweep distance. r should be in ConvexB's space + normal : the contact normal + inflation : the amount by which we inflate the swept shape. If the inflated shapes aren't initially-touching, + the TOI will return the time at which both shapes are at a distance equal to inflation separated. If inflation is 0 + the TOI will return the time at which both shapes are touching. + + */ + template<class ConvexA, class ConvexB> + bool gjkRaycast(const ConvexA& a, const ConvexB& b, const Ps::aos::Vec3VArg initialDir, const Ps::aos::FloatVArg initialLambda, const Ps::aos::Vec3VArg s, const Ps::aos::Vec3VArg r, Ps::aos::FloatV& lambda, Ps::aos::Vec3V& normal, Ps::aos::Vec3V& closestA, const PxReal _inflation) + { + PX_UNUSED(initialLambda); + + using namespace Ps::aos; + + const FloatV inflation = FLoad(_inflation); + const Vec3V zeroV = V3Zero(); + const FloatV zero = FZero(); + const FloatV one = FOne(); + const BoolV bTrue = BTTTT(); + + const FloatV maxDist = FLoad(PX_MAX_REAL); + + FloatV _lambda = zero;//initialLambda; + Vec3V x = V3ScaleAdd(r, _lambda, s); + PxU32 size=1; + + //const Vec3V dir = V3Sub(a.getCenter(), b.getCenter()); + const Vec3V _initialSearchDir = V3Sel(FIsGrtr(V3Dot(initialDir, initialDir), FEps()), initialDir, V3UnitX()); + const Vec3V initialSearchDir = V3Normalize(_initialSearchDir); + + const Vec3V initialSupportA(a.ConvexA::support(V3Neg(initialSearchDir))); + const Vec3V initialSupportB( b.ConvexB::support(initialSearchDir)); + + Vec3V Q[4] = {V3Sub(initialSupportA, initialSupportB), zeroV, zeroV, zeroV}; //simplex set + Vec3V A[4] = {initialSupportA, zeroV, zeroV, zeroV}; //ConvexHull a simplex set + Vec3V B[4] = {initialSupportB, zeroV, zeroV, zeroV}; //ConvexHull b simplex set + + + Vec3V v = V3Neg(Q[0]); + Vec3V supportA = initialSupportA; + Vec3V supportB = initialSupportB; + Vec3V support = Q[0]; + + const FloatV minMargin = FMin(a.ConvexA::getSweepMargin(), b.ConvexB::getSweepMargin()); + const FloatV eps1 = FMul(minMargin, FLoad(0.1f)); + const FloatV inflationPlusEps(FAdd(eps1, inflation)); + const FloatV eps2 = FMul(eps1, eps1); + + const FloatV inflation2 = FMul(inflationPlusEps, inflationPlusEps); + + Vec3V clos(Q[0]); + Vec3V preClos = clos; + //Vec3V closA(initialSupportA); + FloatV sDist = V3Dot(v, v); + FloatV minDist = sDist; + //Vec3V closAA = initialSupportA; + //Vec3V closBB = initialSupportB; + + BoolV bNotTerminated = FIsGrtr(sDist, eps2); + BoolV bNotDegenerated = bTrue; + + Vec3V nor = v; + + while(BAllEqTTTT(bNotTerminated)) + { + + minDist = sDist; + preClos = clos; + + const Vec3V vNorm = V3Normalize(v); + const Vec3V nvNorm = V3Neg(vNorm); + + supportA=a.ConvexA::support(vNorm); + supportB=V3Add(x, b.ConvexB::support(nvNorm)); + + //calculate the support point + support = V3Sub(supportA, supportB); + const Vec3V w = V3Neg(support); + const FloatV vw = FSub(V3Dot(vNorm, w), inflationPlusEps); + const FloatV vr = V3Dot(vNorm, r); + if(FAllGrtr(vw, zero)) + { + + if(FAllGrtrOrEq(vr, zero)) + { + return false; + } + else + { + const FloatV _oldLambda = _lambda; + _lambda = FSub(_lambda, FDiv(vw, vr)); + if(FAllGrtr(_lambda, _oldLambda)) + { + if(FAllGrtr(_lambda, one)) + { + return false; + } + const Vec3V bPreCenter = x; + x = V3ScaleAdd(r, _lambda, s); + + const Vec3V offSet =V3Sub(x, bPreCenter); + const Vec3V b0 = V3Add(B[0], offSet); + const Vec3V b1 = V3Add(B[1], offSet); + const Vec3V b2 = V3Add(B[2], offSet); + + B[0] = b0; + B[1] = b1; + B[2] = b2; + + Q[0]=V3Sub(A[0], b0); + Q[1]=V3Sub(A[1], b1); + Q[2]=V3Sub(A[2], b2); + + supportB = V3Add(x, b.ConvexB::support(nvNorm)); + support = V3Sub(supportA, supportB); + minDist = maxDist; + nor = v; + //size=0; + } + } + } + + PX_ASSERT(size < 4); + A[size]=supportA; + B[size]=supportB; + Q[size++]=support; + + //calculate the closest point between two convex hull + clos = GJKCPairDoSimplex(Q, A, B, support, size); + v = V3Neg(clos); + sDist = V3Dot(clos, clos); + + bNotDegenerated = FIsGrtr(minDist, sDist); + bNotTerminated = BAnd(FIsGrtr(sDist, inflation2), bNotDegenerated); + } + + + const BoolV aQuadratic = a.isMarginEqRadius(); + //ML:if the Minkowski sum of two objects are too close to the original(eps2 > sDist), we can't take v because we will lose lots of precision. Therefore, we will take + //previous configuration's normal which should give us a reasonable approximation. This effectively means that, when we do a sweep with inflation, we always keep v because + //the shapes converge separated. If we do a sweep without inflation, we will usually use the previous configuration's normal. + nor = V3Sel(BAnd(FIsGrtr(sDist, eps2), bNotDegenerated), v, nor); + nor = V3Neg(V3NormalizeSafe(nor, V3Zero())); + normal = nor; + lambda = _lambda; + + const Vec3V closestP = V3Sel(bNotDegenerated, clos, preClos); + Vec3V closA = zeroV, closB = zeroV; + getClosestPoint(Q, A, B, closestP, closA, closB, size); + closestA = V3Sel(aQuadratic, V3NegScaleSub(nor, a.getMargin(), closA), closA); + + return true; + } + + + + /* + ConvexA is in the local space of ConvexB + lambda : the time of impact(TOI) + initialLambda : the start time of impact value (disable) + s : the sweep ray origin in ConvexB's space + r : the normalized sweep ray direction scaled by the sweep distance. r should be in ConvexB's space + normal : the contact normal in ConvexB's space + closestA : the tounching contact in ConvexB's space + inflation : the amount by which we inflate the swept shape. If the inflated shapes aren't initially-touching, + the TOI will return the time at which both shapes are at a distance equal to inflation separated. If inflation is 0 + the TOI will return the time at which both shapes are touching. + + */ + template<class ConvexA, class ConvexB> + bool gjkRaycastPenetration(const ConvexA& a, const ConvexB& b, const Ps::aos::Vec3VArg initialDir, const Ps::aos::FloatVArg initialLambda, const Ps::aos::Vec3VArg s, const Ps::aos::Vec3VArg r, Ps::aos::FloatV& lambda, + Ps::aos::Vec3V& normal, Ps::aos::Vec3V& closestA, const PxReal _inflation, const bool initialOverlap) + { + using namespace Ps::aos; + Vec3V closA; + Vec3V norm; + FloatV _lambda; + if(gjkRaycast(a, b, initialDir, initialLambda, s, r, _lambda, norm, closA, _inflation)) + { + const FloatV zero = FZero(); + lambda = _lambda; + if(FAllEq(_lambda, zero) && initialOverlap) + { + + //time of impact is zero, the sweep shape is intesect, use epa to get the normal and contact point + const FloatV contactDist = getSweepContactEps(a.getMargin(), b.getMargin()); + + Vec3V closAA; + Vec3V closBB; + FloatV sDist; + PxU8 aIndices[4]; + PxU8 bIndices[4]; + PxU8 size=0; + + //PX_COMPILE_TIME_ASSERT(typename Shrink<ConvexB>::Type != Gu::BoxV); + + typename ConvexA::ShrunkConvex convexA = a.getShrunkConvex(); + typename ConvexB::ShrunkConvex convexB = b.getShrunkConvex(); + + + GjkStatus status = gjkPenetration<typename ConvexA::ShrunkConvex, typename ConvexB::ShrunkConvex>(convexA, convexB, + initialDir, contactDist, closAA, closBB, norm, sDist, aIndices, bIndices, size, false); + //norm = V3Neg(norm); + if(status == GJK_CONTACT) + { + closA = closAA;//V3Sel(aQuadratic, V3Add(closAA, V3Scale(norm, a.getMargin())),closAA); + } + else if(status == EPA_CONTACT) + { + status = epaPenetration(a, b, aIndices, bIndices, size, closAA, closBB, norm, sDist); + + if (status == EPA_CONTACT || status == EPA_DEGENERATE) + { + closA = closAA; + } + else + { + //ML: if EPA fail, we will use the ray direction as the normal and set pentration to be zero + norm = V3Normalize(V3Neg(r)); + closA = V3Zero(); + sDist = zero;//FNeg(V3Length(V3Sub(closBB, closAA))); + } + } + else + { + //ML:: this will be gjk degenerate case, we will take the normal and sDist from the gjkRelativePenetration + closA = closAA; + } + lambda = FMin(zero, sDist); + } + closestA = closA; + normal = norm; + return true; + } + return false; + } +} +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKSimplex.cpp b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKSimplex.cpp new file mode 100644 index 00000000..e74e0d03 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKSimplex.cpp @@ -0,0 +1,216 @@ +// 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 "GuGJKSimplex.h" + +namespace physx +{ +namespace Gu +{ + + using namespace Ps::aos; + + static Vec3V getClosestPtPointTriangle(Vec3V* PX_RESTRICT Q, const BoolVArg bIsOutside4, PxU32* indices, PxU32& size) + { + FloatV bestSqDist = FMax(); + + PxU32 _indices[3] = {0, 1, 2}; + + Vec3V closestPt = V3Zero(); + + if(BAllEqTTTT(BGetX(bIsOutside4))) + { + //use the original indices, size, v and w + bestSqDist = closestPtPointTriangleBaryCentric(Q[0], Q[1], Q[2], indices, size, closestPt); + } + + if(BAllEqTTTT(BGetY(bIsOutside4))) + { + + PxU32 _size = 3; + _indices[0] = 0; _indices[1] = 2; _indices[2] = 3; + Vec3V tClosestPt; + const FloatV sqDist = closestPtPointTriangleBaryCentric(Q[0], Q[2], Q[3], _indices, _size, tClosestPt); + + const BoolV con = FIsGrtr(bestSqDist, sqDist); + if(BAllEqTTTT(con)) + { + closestPt = tClosestPt; + bestSqDist = sqDist; + + indices[0] = _indices[0]; + indices[1] = _indices[1]; + indices[2] = _indices[2]; + + size = _size; + } + } + + if(BAllEqTTTT(BGetZ(bIsOutside4))) + { + PxU32 _size = 3; + + _indices[0] = 0; _indices[1] = 3; _indices[2] = 1; + + Vec3V tClosestPt; + const FloatV sqDist = closestPtPointTriangleBaryCentric(Q[0], Q[3], Q[1], _indices, _size, tClosestPt); + + const BoolV con = FIsGrtr(bestSqDist, sqDist); + if(BAllEqTTTT(con)) + { + closestPt = tClosestPt; + bestSqDist = sqDist; + + indices[0] = _indices[0]; + indices[1] = _indices[1]; + indices[2] = _indices[2]; + + size = _size; + } + + } + + if(BAllEqTTTT(BGetW(bIsOutside4))) + { + + + PxU32 _size = 3; + _indices[0] = 1; _indices[1] = 3; _indices[2] = 2; + Vec3V tClosestPt; + const FloatV sqDist = closestPtPointTriangleBaryCentric(Q[1], Q[3], Q[2], _indices, _size, tClosestPt); + + const BoolV con = FIsGrtr(bestSqDist, sqDist); + + if(BAllEqTTTT(con)) + { + closestPt = tClosestPt; + bestSqDist = sqDist; + + indices[0] = _indices[0]; + indices[1] = _indices[1]; + indices[2] = _indices[2]; + + size = _size; + } + } + + return closestPt; + } + + PX_NOALIAS Vec3V closestPtPointTetrahedron(Vec3V* PX_RESTRICT Q, Vec3V* PX_RESTRICT A, Vec3V* PX_RESTRICT B, PxU32& size) + { + + const FloatV eps = FLoad(1e-4f); + const Vec3V a = Q[0]; + const Vec3V b = Q[1]; + const Vec3V c = Q[2]; + const Vec3V d = Q[3]; + + //degenerated + const Vec3V ab = V3Sub(b, a); + const Vec3V ac = V3Sub(c, a); + const Vec3V n = V3Normalize(V3Cross(ab, ac)); + const FloatV signDist = V3Dot(n, V3Sub(d, a)); + if(FAllGrtr(eps, FAbs(signDist))) + { + size = 3; + return closestPtPointTriangle(Q, A, B, size); + } + + const BoolV bIsOutside4 = PointOutsideOfPlane4(a, b, c, d); + + if(BAllEqFFFF(bIsOutside4)) + { + //All inside + return V3Zero(); + } + + PxU32 indices[3] = {0, 1, 2}; + + const Vec3V closest = getClosestPtPointTriangle(Q, bIsOutside4, indices, size); + + const Vec3V q0 = Q[indices[0]]; const Vec3V q1 = Q[indices[1]]; const Vec3V q2 = Q[indices[2]]; + const Vec3V a0 = A[indices[0]]; const Vec3V a1 = A[indices[1]]; const Vec3V a2 = A[indices[2]]; + const Vec3V b0 = B[indices[0]]; const Vec3V b1 = B[indices[1]]; const Vec3V b2 = B[indices[2]]; + Q[0] = q0; Q[1] = q1; Q[2] = q2; + A[0] = a0; A[1] = a1; A[2] = a2; + B[0] = b0; B[1] = b1; B[2] = b2; + + return closest; + } + + PX_NOALIAS Vec3V closestPtPointTetrahedron(Vec3V* PX_RESTRICT Q, Vec3V* PX_RESTRICT A, Vec3V* PX_RESTRICT B, PxI32* PX_RESTRICT aInd, PxI32* PX_RESTRICT bInd, PxU32& size) + { + + const FloatV eps = FLoad(1e-4f); + const Vec3V zeroV = V3Zero(); + + const Vec3V a = Q[0]; + const Vec3V b = Q[1]; + const Vec3V c = Q[2]; + const Vec3V d = Q[3]; + + //degenerated + const Vec3V ab = V3Sub(b, a); + const Vec3V ac = V3Sub(c, a); + const Vec3V n = V3Normalize(V3Cross(ab, ac)); + const FloatV signDist = V3Dot(n, V3Sub(d, a)); + if(FAllGrtr(eps, FAbs(signDist))) + { + size = 3; + return closestPtPointTriangle(Q, A, B, aInd, bInd, size); + } + + const BoolV bIsOutside4 = PointOutsideOfPlane4(a, b, c, d); + + if(BAllEqFFFF(bIsOutside4)) + { + //All inside + return zeroV; + } + + PxU32 indices[3] = {0, 1, 2}; + const Vec3V closest = getClosestPtPointTriangle(Q, bIsOutside4, indices, size); + + const Vec3V q0 = Q[indices[0]]; const Vec3V q1 = Q[indices[1]]; const Vec3V q2 = Q[indices[2]]; + const Vec3V a0 = A[indices[0]]; const Vec3V a1 = A[indices[1]]; const Vec3V a2 = A[indices[2]]; + const Vec3V b0 = B[indices[0]]; const Vec3V b1 = B[indices[1]]; const Vec3V b2 = B[indices[2]]; + const PxI32 _aInd0 = aInd[indices[0]]; const PxI32 _aInd1 = aInd[indices[1]]; const PxI32 _aInd2 = aInd[indices[2]]; + const PxI32 _bInd0 = bInd[indices[0]]; const PxI32 _bInd1 = bInd[indices[1]]; const PxI32 _bInd2 = bInd[indices[2]]; + Q[0] = q0; Q[1] = q1; Q[2] = q2; + A[0] = a0; A[1] = a1; A[2] = a2; + B[0] = b0; B[1] = b1; B[2] = b2; + aInd[0] = _aInd0; aInd[1] = _aInd1; aInd[2] = _aInd2; + bInd[0] = _bInd0; bInd[1] = _bInd1; bInd[2] = _bInd2; + + return closest; + } +} + +} diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKSimplex.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKSimplex.h new file mode 100644 index 00000000..05ae2c33 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKSimplex.h @@ -0,0 +1,473 @@ +// 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_GJKSIMPLEX_H +#define GU_GJKSIMPLEX_H + +#include "CmPhysXCommon.h" +#include "PsVecMath.h" +#include "GuBarycentricCoordinates.h" + +#if (defined __GNUC__ && defined _DEBUG) +#define PX_GJK_INLINE PX_INLINE +#define PX_GJK_FORCE_INLINE PX_INLINE +#else +#define PX_GJK_INLINE PX_INLINE +#define PX_GJK_FORCE_INLINE PX_FORCE_INLINE +#endif + + +namespace physx +{ +namespace Gu +{ + + + PX_NOALIAS Ps::aos::Vec3V closestPtPointTetrahedron(Ps::aos::Vec3V* PX_RESTRICT Q, Ps::aos::Vec3V* PX_RESTRICT A, Ps::aos::Vec3V* PX_RESTRICT B, PxU32& size); + + PX_NOALIAS Ps::aos::Vec3V closestPtPointTetrahedron(Ps::aos::Vec3V* PX_RESTRICT Q, Ps::aos::Vec3V* PX_RESTRICT A, Ps::aos::Vec3V* PX_RESTRICT B, PxI32* PX_RESTRICT aInd, PxI32* PX_RESTRICT bInd, + PxU32& size); + + PX_NOALIAS PX_FORCE_INLINE Ps::aos::BoolV PointOutsideOfPlane4(const Ps::aos::Vec3VArg _a, const Ps::aos::Vec3VArg _b, const Ps::aos::Vec3VArg _c, const Ps::aos::Vec3VArg _d) + { + using namespace Ps::aos; + + // this is not 0 because of the following scenario: + // All the points lie on the same plane and the plane goes through the origin (0,0,0). + // On the Wii U, the math below has the problem that when point A gets projected on the + // plane cumputed by A, B, C, the distance to the plane might not be 0 for the mentioned + // scenario but a small positive or negative value. This can lead to the wrong boolean + // results. Using a small negative value as threshold is more conservative but safer. + const Vec4V zero = V4Load(-1e-6); + + const Vec3V ab = V3Sub(_b, _a); + const Vec3V ac = V3Sub(_c, _a); + const Vec3V ad = V3Sub(_d, _a); + const Vec3V bd = V3Sub(_d, _b); + const Vec3V bc = V3Sub(_c, _b); + + const Vec3V v0 = V3Cross(ab, ac); + const Vec3V v1 = V3Cross(ac, ad); + const Vec3V v2 = V3Cross(ad, ab); + const Vec3V v3 = V3Cross(bd, bc); + + const FloatV signa0 = V3Dot(v0, _a); + const FloatV signa1 = V3Dot(v1, _a); + const FloatV signa2 = V3Dot(v2, _a); + const FloatV signd3 = V3Dot(v3, _a); + + const FloatV signd0 = V3Dot(v0, _d); + const FloatV signd1 = V3Dot(v1, _b); + const FloatV signd2 = V3Dot(v2, _c); + const FloatV signa3 = V3Dot(v3, _b); + + const Vec4V signa = V4Merge(signa0, signa1, signa2, signa3); + const Vec4V signd = V4Merge(signd0, signd1, signd2, signd3); + return V4IsGrtrOrEq(V4Mul(signa, signd), zero);//same side, outside of the plane + + + } + + + PX_NOALIAS PX_FORCE_INLINE Ps::aos::Vec3V closestPtPointSegment(Ps::aos::Vec3V* PX_RESTRICT Q, PxU32& size) + { + using namespace Ps::aos; + const Vec3V a = Q[0]; + const Vec3V b = Q[1]; + + //const Vec3V origin = V3Zero(); + const FloatV zero = FZero(); + const FloatV one = FOne(); + + //Test degenerated case + const Vec3V ab = V3Sub(b, a); + const FloatV denom = V3Dot(ab, ab); + const Vec3V ap = V3Neg(a);//V3Sub(origin, a); + const FloatV nom = V3Dot(ap, ab); + const BoolV con = FIsGrtrOrEq(FEps(), denom);//FIsEq(denom, zero); + //TODO - can we get rid of this branch? The problem is size, which isn't a vector! + if(BAllEqTTTT(con)) + { + size = 1; + return Q[0]; + } + + /* const PxU32 count = BAllEq(con, bTrue); + size = 2 - count;*/ + + const FloatV tValue = FClamp(FDiv(nom, denom), zero, one); + return V3ScaleAdd(ab, tValue, a); + } + + + PX_FORCE_INLINE void getClosestPoint(const Ps::aos::Vec3V* PX_RESTRICT Q, const Ps::aos::Vec3V* PX_RESTRICT A, const Ps::aos::Vec3V* PX_RESTRICT B, const Ps::aos::Vec3VArg closest, Ps::aos::Vec3V& closestA, Ps::aos::Vec3V& closestB, const PxU32 size) + { + using namespace Ps::aos; + + switch(size) + { + case 1: + { + closestA = A[0]; + closestB = B[0]; + break; + } + case 2: + { + FloatV v; + barycentricCoordinates(closest, Q[0], Q[1], v); + const Vec3V av = V3Sub(A[1], A[0]); + const Vec3V bv = V3Sub(B[1], B[0]); + closestA = V3ScaleAdd(av, v, A[0]); + closestB = V3ScaleAdd(bv, v, B[0]); + + break; + } + case 3: + { + //calculate the Barycentric of closest point p in the mincowsky sum + FloatV v, w; + barycentricCoordinates(closest, Q[0], Q[1], Q[2], v, w); + + const Vec3V av0 = V3Sub(A[1], A[0]); + const Vec3V av1 = V3Sub(A[2], A[0]); + const Vec3V bv0 = V3Sub(B[1], B[0]); + const Vec3V bv1 = V3Sub(B[2], B[0]); + + closestA = V3Add(A[0], V3Add(V3Scale(av0, v), V3Scale(av1, w))); + closestB = V3Add(B[0], V3Add(V3Scale(bv0, v), V3Scale(bv1, w))); + } + }; + } + + PX_NOALIAS PX_GJK_FORCE_INLINE Ps::aos::FloatV closestPtPointTriangleBaryCentric(const Ps::aos::Vec3VArg a, const Ps::aos::Vec3VArg b, const Ps::aos::Vec3VArg c, + PxU32* PX_RESTRICT indices, PxU32& size, Ps::aos::Vec3V& closestPt) + { + using namespace Ps::aos; + + size = 3; + const FloatV zero = FZero(); + const FloatV eps = FEps(); + + const Vec3V ab = V3Sub(b, a); + const Vec3V ac = V3Sub(c, a); + + const Vec3V n = V3Cross(ab, ac); + //ML: if the shape is oblong, the degeneracy test sometime can't catch the degeneracy in the tetraheron. Therefore, we need to make sure we still can ternimate with the previous + //triangle by returning the maxinum distance. + const FloatV nn = V3Dot(n, n); + if (FAllEq(nn, zero)) + return FMax(); + + //const FloatV va = FNegScaleSub(d5, d4, FMul(d3, d6));//edge region of BC + //const FloatV vb = FNegScaleSub(d1, d6, FMul(d5, d2));//edge region of AC + //const FloatV vc = FNegScaleSub(d3, d2, FMul(d1, d4));//edge region of AB + + //const FloatV va = V3Dot(n, V3Cross(b, c));//edge region of BC, signed area rbc, u = S(rbc)/S(abc) for a + //const FloatV vb = V3Dot(n, V3Cross(c, a));//edge region of AC, signed area rac, v = S(rca)/S(abc) for b + //const FloatV vc = V3Dot(n, V3Cross(a, b));//edge region of AB, signed area rab, w = S(rab)/S(abc) for c + + const VecCrossV crossA = V3PrepareCross(a); + const VecCrossV crossB = V3PrepareCross(b); + const VecCrossV crossC = V3PrepareCross(c); + const Vec3V bCrossC = V3Cross(crossB, crossC); + const Vec3V cCrossA = V3Cross(crossC, crossA); + const Vec3V aCrossB = V3Cross(crossA, crossB); + + const FloatV va = V3Dot(n, bCrossC);//edge region of BC, signed area rbc, u = S(rbc)/S(abc) for a + const FloatV vb = V3Dot(n, cCrossA);//edge region of AC, signed area rac, v = S(rca)/S(abc) for b + const FloatV vc = V3Dot(n, aCrossB);//edge region of AB, signed area rab, w = S(rab)/S(abc) for c + + const BoolV isFacePoints = BAnd(FIsGrtrOrEq(va, zero), BAnd(FIsGrtrOrEq(vb, zero), FIsGrtrOrEq(vc, zero))); + + + //face region + if(BAllEqTTTT(isFacePoints)) + { + const FloatV t = FDiv(V3Dot(n, a), nn); + const Vec3V q = V3Scale(n, t); + closestPt = q; + return V3Dot(q, q); + } + + const Vec3V ap = V3Neg(a); + const Vec3V bp = V3Neg(b); + const Vec3V cp = V3Neg(c); + + const FloatV d1 = V3Dot(ab, ap); // snom + const FloatV d2 = V3Dot(ac, ap); // tnom + const FloatV d3 = V3Dot(ab, bp); // -sdenom + const FloatV d4 = V3Dot(ac, bp); // unom = d4 - d3 + const FloatV d5 = V3Dot(ab, cp); // udenom = d5 - d6 + const FloatV d6 = V3Dot(ac, cp); // -tdenom + + + const FloatV unom = FSub(d4, d3); + const FloatV udenom = FSub(d5, d6); + + size = 2; + //check if p in edge region of AB + const BoolV con30 = FIsGrtrOrEq(zero, vc); + const BoolV con31 = FIsGrtrOrEq(d1, zero); + const BoolV con32 = FIsGrtrOrEq(zero, d3); + const BoolV con3 = BAnd(con30, BAnd(con31, con32));//edge AB region + if(BAllEqTTTT(con3)) + { + const FloatV toRecipAB = FSub(d1, d3); + const FloatV recipAB = FSel(FIsGrtr(FAbs(toRecipAB), eps), FRecip(toRecipAB), zero); + const FloatV t = FMul(d1, recipAB); + const Vec3V q = V3ScaleAdd(ab, t, a); + closestPt = q; + return V3Dot(q, q); + } + + //check if p in edge region of BC + const BoolV con40 = FIsGrtrOrEq(zero, va); + const BoolV con41 = FIsGrtrOrEq(d4, d3); + const BoolV con42 = FIsGrtrOrEq(d5, d6); + const BoolV con4 = BAnd(con40, BAnd(con41, con42)); //edge BC region + if(BAllEqTTTT(con4)) + { + const Vec3V bc = V3Sub(c, b); + const FloatV toRecipBC = FAdd(unom, udenom); + const FloatV recipBC = FSel(FIsGrtr(FAbs(toRecipBC), eps), FRecip(toRecipBC), zero); + const FloatV t = FMul(unom, recipBC); + indices[0] = indices[1]; + indices[1] = indices[2]; + const Vec3V q = V3ScaleAdd(bc, t, b); + closestPt = q; + return V3Dot(q, q); + } + + //check if p in edge region of AC + const BoolV con50 = FIsGrtrOrEq(zero, vb); + const BoolV con51 = FIsGrtrOrEq(d2, zero); + const BoolV con52 = FIsGrtrOrEq(zero, d6); + + const BoolV con5 = BAnd(con50, BAnd(con51, con52));//edge AC region + if(BAllEqTTTT(con5)) + { + const FloatV toRecipAC = FSub(d2, d6); + const FloatV recipAC = FSel(FIsGrtr(FAbs(toRecipAC), eps), FRecip(toRecipAC), zero); + const FloatV t = FMul(d2, recipAC); + indices[1]=indices[2]; + const Vec3V q = V3ScaleAdd(ac, t, a); + closestPt = q; + return V3Dot(q, q); + } + + size = 1; + //check if p in vertex region outside a + const BoolV con00 = FIsGrtrOrEq(zero, d1); // snom <= 0 + const BoolV con01 = FIsGrtrOrEq(zero, d2); // tnom <= 0 + const BoolV con0 = BAnd(con00, con01); // vertex region a + if(BAllEqTTTT(con0)) + { + closestPt = a; + return V3Dot(a, a); + } + + //check if p in vertex region outside b + const BoolV con10 = FIsGrtrOrEq(d3, zero); + const BoolV con11 = FIsGrtrOrEq(d3, d4); + const BoolV con1 = BAnd(con10, con11); // vertex region b + if(BAllEqTTTT(con1)) + { + indices[0] = indices[1]; + closestPt = b; + return V3Dot(b, b); + } + + //p is in vertex region outside c + indices[0] = indices[2]; + closestPt = c; + return V3Dot(c, c); + + } + + PX_NOALIAS PX_GJK_FORCE_INLINE Ps::aos::Vec3V closestPtPointTriangle(Ps::aos::Vec3V* PX_RESTRICT Q, Ps::aos::Vec3V* A, Ps::aos::Vec3V* B, PxU32& size) + { + + using namespace Ps::aos; + + size = 3; + + const FloatV eps = FEps(); + const Vec3V a = Q[0]; + const Vec3V b = Q[1]; + const Vec3V c = Q[2]; + const Vec3V ab = V3Sub(b, a); + const Vec3V ac = V3Sub(c, a); + const Vec3V signArea = V3Cross(ab, ac);//0.5*(abXac) + const FloatV area = V3Dot(signArea, signArea); + if(FAllGrtrOrEq(eps, area)) + { + //degenerate + size = 2; + return closestPtPointSegment(Q, size); + } + + PxU32 _size; + PxU32 indices[3]={0, 1, 2}; + Vec3V closestPt; + closestPtPointTriangleBaryCentric(a, b, c, indices, _size, closestPt); + + if(_size != 3) + { + + const Vec3V q0 = Q[indices[0]]; const Vec3V q1 = Q[indices[1]]; + const Vec3V a0 = A[indices[0]]; const Vec3V a1 = A[indices[1]]; + const Vec3V b0 = B[indices[0]]; const Vec3V b1 = B[indices[1]]; + + Q[0] = q0; Q[1] = q1; + A[0] = a0; A[1] = a1; + B[0] = b0; B[1] = b1; + + size = _size; + } + + return closestPt; + } + + PX_NOALIAS PX_GJK_FORCE_INLINE Ps::aos::Vec3V closestPtPointTriangle(Ps::aos::Vec3V* PX_RESTRICT Q, Ps::aos::Vec3V* A, Ps::aos::Vec3V* B, PxI32* PX_RESTRICT aInd, PxI32* PX_RESTRICT bInd, + PxU32& size) + { + + using namespace Ps::aos; + + size = 3; + + const FloatV eps = FEps(); + + const Vec3V a = Q[0]; + const Vec3V b = Q[1]; + const Vec3V c = Q[2]; + const Vec3V ab = V3Sub(b, a); + const Vec3V ac = V3Sub(c, a); + const Vec3V signArea = V3Cross(ab, ac);//0.5*(abXac) + const FloatV area = V3Dot(signArea, signArea); + if(FAllGrtrOrEq(eps, area)) + { + //degenerate + size = 2; + return closestPtPointSegment(Q, size); + } + + PxU32 _size; + PxU32 indices[3]={0, 1, 2}; + Vec3V closestPt; + closestPtPointTriangleBaryCentric(a, b, c, indices, _size, closestPt); + + if(_size != 3) + { + + const Vec3V q0 = Q[indices[0]]; const Vec3V q1 = Q[indices[1]]; + const Vec3V a0 = A[indices[0]]; const Vec3V a1 = A[indices[1]]; + const Vec3V b0 = B[indices[0]]; const Vec3V b1 = B[indices[1]]; + const PxI32 aInd0 = aInd[indices[0]]; const PxI32 aInd1 = aInd[indices[1]]; + const PxI32 bInd0 = bInd[indices[0]]; const PxI32 bInd1 = bInd[indices[1]]; + + Q[0] = q0; Q[1] = q1; + A[0] = a0; A[1] = a1; + B[0] = b0; B[1] = b1; + aInd[0] = aInd0; aInd[1] = aInd1; + bInd[0] = bInd0; bInd[1] = bInd1; + + size = _size; + } + + return closestPt; + } + + + + + PX_NOALIAS PX_FORCE_INLINE Ps::aos::Vec3V GJKCPairDoSimplex(Ps::aos::Vec3V* PX_RESTRICT Q, Ps::aos::Vec3V* PX_RESTRICT A, Ps::aos::Vec3V* PX_RESTRICT B, const Ps::aos::Vec3VArg support, + PxU32& size) + { + using namespace Ps::aos; + + //const PxU32 tempSize = size; + //calculate a closest from origin to the simplex + switch(size) + { + case 1: + { + return support; + } + case 2: + { + return closestPtPointSegment(Q, size); + } + case 3: + { + return closestPtPointTriangle(Q, A, B, size); + } + case 4: + return closestPtPointTetrahedron(Q, A, B, size); + default: + PX_ASSERT(0); + } + return support; + } + + + PX_NOALIAS PX_FORCE_INLINE Ps::aos::Vec3V GJKCPairDoSimplex(Ps::aos::Vec3V* PX_RESTRICT Q, Ps::aos::Vec3V* PX_RESTRICT A, Ps::aos::Vec3V* PX_RESTRICT B, PxI32* PX_RESTRICT aInd, PxI32* PX_RESTRICT bInd, + const Ps::aos::Vec3VArg support, PxU32& size) + { + using namespace Ps::aos; + + //const PxU32 tempSize = size; + //calculate a closest from origin to the simplex + switch(size) + { + case 1: + { + return support; + } + case 2: + { + return closestPtPointSegment(Q, size); + } + case 3: + { + return closestPtPointTriangle(Q, A, B, aInd, bInd, size); + } + case 4: + return closestPtPointTetrahedron(Q, A, B, aInd, bInd, size); + default: + PX_ASSERT(0); + } + return support; + } +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKTest.cpp b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKTest.cpp new file mode 100644 index 00000000..530634c2 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKTest.cpp @@ -0,0 +1,92 @@ +// 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 "GuGJK.h" +#include "GuGJKRaycast.h" +#include "GuGJKPenetration.h" +#include "GuGJKTest.h" + +namespace physx +{ +namespace Gu +{ + +using namespace Ps::aos; + +GjkStatus testGjk(GjkConvex& a, GjkConvex& b, const Vec3VArg initialSearchDir, const FloatVArg contactDist, Vec3V& closestA, Vec3V& closestB, Vec3V& normal, FloatV& dist) +{ + return gjk<GjkConvex, GjkConvex>(a, b, initialSearchDir, contactDist, closestA, closestB, normal, dist); +} + + +bool testGjkRaycast(GjkConvex& a, GjkConvex& b, const Vec3VArg initialSearchDir, const Ps::aos::FloatVArg initialLambda, const Ps::aos::Vec3VArg s, const Ps::aos::Vec3VArg r, Ps::aos::FloatV& lambda, + Ps::aos::Vec3V& normal, Ps::aos::Vec3V& closestA, const PxReal inflation) +{ + return gjkRaycast(a, b, initialSearchDir, initialLambda, s, r, lambda, normal, closestA, inflation); +} + +GjkStatus testGjkPenetration (GjkConvex& a, GjkConvex& b, const Vec3VArg initialSearchDir, const FloatVArg contactDist, Vec3V& closestA, Vec3V& closestB, Vec3V& normal, FloatV& sqDist) +{ + const bool takeCoreShape = a.getMarginIsRadius() || b.getMarginIsRadius(); + PxU8 aIndices[4]; + PxU8 bIndices[4]; + PxU8 size=0; + return gjkPenetration<GjkConvex, GjkConvex>(a, b, initialSearchDir, contactDist, closestA, closestB, normal, + sqDist, aIndices, bIndices, size, takeCoreShape); +} + +GjkStatus testGjkPenetration(GjkConvex& a, GjkConvex& b, const Vec3VArg initialSearchDir, const FloatVArg contactDist, Vec3V& closestA, Vec3V& closestB, Vec3V& normal, FloatV& sqDist, + PxU8* aIndices, PxU8* bIndices, PxU8 size) +{ + const bool takeCoreShape = a.getMarginIsRadius() || b.getMarginIsRadius(); + return gjkPenetration<GjkConvex, GjkConvex>(a, b, initialSearchDir, contactDist, closestA, closestB, normal, + sqDist, aIndices, bIndices, size, takeCoreShape); +} + +GjkStatus testEpaPenetration(GjkConvex& a, GjkConvex& b, Ps::aos::Vec3V& contactA, Ps::aos::Vec3V& contactB, Ps::aos::Vec3V& normal, + Ps::aos::FloatV& penetrationDepth) +{ + const bool takeCoreShape = a.getMarginIsRadius() || b.getMarginIsRadius(); + PxU8 aIndices[4]; + PxU8 bIndices[4]; + PxU8 size=0; + return epaPenetration(a, b, aIndices, bIndices, size, contactA, contactB, normal, penetrationDepth, takeCoreShape); +} + +GjkStatus testEpaPenetration(GjkConvex& a, GjkConvex& b, Ps::aos::Vec3V& contactA, Ps::aos::Vec3V& contactB, Ps::aos::Vec3V& normal, + Ps::aos::FloatV& penetrationDepth, PxU8* aIndices, PxU8* bIndices, PxU8 size) +{ + const bool takeCoreShape = a.getMarginIsRadius() || b.getMarginIsRadius(); + return epaPenetration(a, b, aIndices, bIndices, size, contactA, contactB, normal, penetrationDepth, takeCoreShape); +} + +} +} + diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKTest.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKTest.h new file mode 100644 index 00000000..f32690c7 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKTest.h @@ -0,0 +1,64 @@ +// 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_GJK_TEST_H +#define GU_GJK_TEST_H + +#include "PxPhysXCommonConfig.h" +#include "CmPhysXCommon.h" +#include "GuGJKUtil.h" + +namespace physx +{ +namespace Gu +{ + struct GjkConvex; + + + PX_PHYSX_COMMON_API GjkStatus testGjk(GjkConvex& a, GjkConvex& b, const Ps::aos::Vec3VArg initialSearchDir, const Ps::aos::FloatVArg contactDist, Ps::aos::Vec3V& closestA, Ps::aos::Vec3V& closestB, + Ps::aos::Vec3V& normal, Ps::aos::FloatV& dist); + + PX_PHYSX_COMMON_API bool testGjkRaycast(GjkConvex& a, GjkConvex& b, const Ps::aos::Vec3VArg initialSearchDir, const Ps::aos::FloatVArg initialLambda, const Ps::aos::Vec3VArg s, const Ps::aos::Vec3VArg r, + Ps::aos::FloatV& lambda, Ps::aos::Vec3V& normal, Ps::aos::Vec3V& closestA, const PxReal _inflation, const bool initialOverlap); + + PX_PHYSX_COMMON_API GjkStatus testGjkPenetration(GjkConvex& a, GjkConvex& b, const Ps::aos::Vec3VArg initialSearchDir, const Ps::aos::FloatVArg contactDist, Ps::aos::Vec3V& closestA, + Ps::aos::Vec3V& closestB, Ps::aos::Vec3V& normal, Ps::aos::FloatV& sqDist); + + PX_PHYSX_COMMON_API GjkStatus testGjkPenetration(GjkConvex& a, GjkConvex& b, const Ps::aos::Vec3VArg initialSearchDir, const Ps::aos::FloatVArg contactDist, Ps::aos::Vec3V& closestA, + Ps::aos::Vec3V& closestB, Ps::aos::Vec3V& normal, Ps::aos::FloatV& sqDist, PxU8* aIndices, PxU8* bIndices, PxU8 size); + + PX_PHYSX_COMMON_API GjkStatus testEpaPenetration(GjkConvex& a, GjkConvex& b, Ps::aos::Vec3V& contactA, Ps::aos::Vec3V& contactB, Ps::aos::Vec3V& normal, + Ps::aos::FloatV& penetrationDepth); + + PX_PHYSX_COMMON_API GjkStatus testEpaPenetration(GjkConvex& a, GjkConvex& b, Ps::aos::Vec3V& contactA, Ps::aos::Vec3V& contactB, Ps::aos::Vec3V& normal, + Ps::aos::FloatV& penetrationDepth, PxU8* aIndices, PxU8* bIndices, PxU8 size); +} +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKType.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKType.h new file mode 100644 index 00000000..dc823e0a --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKType.h @@ -0,0 +1,175 @@ +// 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_GJKTYPE_H +#define GU_GJKTYPE_H + +#include "GuVecConvex.h" +#include "PsVecTransform.h" + +namespace physx +{ +namespace Gu +{ + class ShrunkBoxV; + class ShrunkConvexHullV; + class ShrunkConvexHullNoScaleV; + class ConvexHullV; + class ConvexHullNoScaleV; + class BoxV; + + template <typename Convex> struct Shrink { typedef Convex Type; }; + template <> struct Shrink<ConvexHullV> { typedef ShrunkConvexHullV Type; }; + template <> struct Shrink<ConvexHullNoScaleV> { typedef ShrunkConvexHullNoScaleV Type; }; + template <> struct Shrink<BoxV> { typedef ShrunkBoxV Type; }; + + struct GjkConvexBase + { + + GjkConvexBase(const ConvexV& convex) : mConvex(convex){} + PX_FORCE_INLINE Ps::aos::FloatV getMinMargin() const { return mConvex.getMinMargin(); } + PX_FORCE_INLINE Ps::aos::BoolV isMarginEqRadius() const { return mConvex.isMarginEqRadius(); } + PX_FORCE_INLINE bool getMarginIsRadius() const { return mConvex.getMarginIsRadius(); } + PX_FORCE_INLINE Ps::aos::FloatV getMargin() const { return mConvex.getMargin(); } + PX_FORCE_INLINE Ps::aos::Vec3V getCenter() const { return mConvex.getCenter(); } + + template <typename Convex> + PX_FORCE_INLINE const Convex& getConvex() const { return static_cast<const Convex&>(mConvex); } + + virtual Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif) const = 0; + virtual Ps::aos::Vec3V support(const Ps::aos::Vec3VArg v) const = 0; + virtual Ps::aos::Vec3V support(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const = 0; + virtual Ps::aos::FloatV getSweepMargin() const = 0; + virtual ~GjkConvexBase(){} + + + private: + GjkConvexBase& operator = (const GjkConvexBase&); + protected: + const ConvexV& mConvex; + }; + + struct GjkConvex : public GjkConvexBase + { + GjkConvex(const ConvexV& convex) : GjkConvexBase(convex) { } + + virtual Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif) const { return doVirtualSupportPoint(index, marginDif); } + virtual Ps::aos::Vec3V support(const Ps::aos::Vec3VArg v) const { return doVirtualSupport(v); } + virtual Ps::aos::Vec3V support(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const{ return doVirtualSupport(dir, index, marginDif); } + + virtual Ps::aos::FloatV getSweepMargin() const { return doVirtualGetSweepMargin(); } + + private: + Ps::aos::Vec3V doVirtualSupportPoint(const PxI32 index,Ps::aos::FloatV* marginDif) const + { + return supportPoint(index, marginDif); //Call the v-table + } + Ps::aos::Vec3V doVirtualSupport(const Ps::aos::Vec3VArg v) const + { + return support(v); //Call the v-table + } + Ps::aos::Vec3V doVirtualSupport(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const + { + return support(dir, index, marginDif); //Call the v-table + } + + Ps::aos::FloatV doVirtualGetSweepMargin() const { return getSweepMargin(); } + + GjkConvex& operator = (const GjkConvex&); + }; + + template <typename Convex> + struct LocalConvex : public GjkConvex + { + LocalConvex(const Convex& convex) : GjkConvex(convex){} + + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif) const { return getConvex<Convex>().supportPoint(index, marginDif); } + Ps::aos::Vec3V support(const Ps::aos::Vec3VArg v) const { return getConvex<Convex>().supportLocal(v); } + Ps::aos::Vec3V support(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const + { + return getConvex<Convex>().supportLocal(dir, index, marginDif); + } + + //ML: we can't force inline function, otherwise win modern will throw compiler error + PX_INLINE LocalConvex<typename Shrink<Convex>::Type > getShrunkConvex() const + { + return LocalConvex<typename Shrink<Convex>::Type >(static_cast<const typename Shrink<Convex>::Type&>(GjkConvex::mConvex)); + } + + PX_INLINE Ps::aos::FloatV getSweepMargin() const { return getConvex<Convex>().getSweepMargin(); } + + typedef LocalConvex<typename Shrink<Convex>::Type > ShrunkConvex; + + typedef Convex Type; + + + private: + LocalConvex<Convex>& operator = (const LocalConvex<Convex>&); + }; + + template <typename Convex> + struct RelativeConvex : public GjkConvex + { + RelativeConvex(const Convex& convex, const Ps::aos::PsMatTransformV& aToB) : GjkConvex(convex), mAToB(aToB), mAToBTransposed(aToB) + { + shdfnd::aos::V3Transpose(mAToBTransposed.rot.col0, mAToBTransposed.rot.col1, mAToBTransposed.rot.col2); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif) const { return mAToB.transform(getConvex<Convex>().supportPoint(index, marginDif)); } + Ps::aos::Vec3V support(const Ps::aos::Vec3VArg v) const { return getConvex<Convex>().supportRelative(v, mAToB, mAToBTransposed); } + Ps::aos::Vec3V support(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const + { + return getConvex<Convex>().supportRelative(dir, mAToB, mAToBTransposed, index, marginDif); + } + + PX_FORCE_INLINE Ps::aos::PsMatTransformV& getRelativeTransform(){ return mAToB; } + + //ML: we can't force inline function, otherwise win modern will throw compiler error + PX_INLINE RelativeConvex<typename Shrink<Convex>::Type > getShrunkConvex() const + { + return RelativeConvex<typename Shrink<Convex>::Type >(static_cast<const typename Shrink<Convex>::Type&>(GjkConvex::mConvex), mAToB); + } + + PX_INLINE Ps::aos::FloatV getSweepMargin() const { return getConvex<Convex>().getSweepMargin(); } + + typedef RelativeConvex<typename Shrink<Convex>::Type > ShrunkConvex; + + typedef Convex Type; + + private: + RelativeConvex<Convex>& operator = (const RelativeConvex<Convex>&); + const Ps::aos::PsMatTransformV& mAToB; + Ps::aos::PsMatTransformV mAToBTransposed; // PT: precomputed mAToB transpose (because 'rotate' is faster than 'rotateInv') + }; + +} +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKUtil.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKUtil.h new file mode 100644 index 00000000..aa463e78 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuGJKUtil.h @@ -0,0 +1,57 @@ +// 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_GJKUTIL_H +#define GU_GJKUTIL_H + +/* + This file is used to avoid the inner loop cross DLL calls +*/ +namespace physx +{ +namespace Gu +{ + +enum GjkStatus +{ + GJK_NON_INTERSECT, // two shapes doesn't intersect + GJK_CLOSE, // two shapes doesn't intersect and gjk algorithm will return closest point information + GJK_CONTACT, // two shapes overlap within margin + GJK_UNDEFINED, // undefined status + GJK_DEGENERATE, // gjk can't converage + + EPA_CONTACT, // two shapes intersect + EPA_DEGENERATE, // epa can't converage + EPA_FAIL // epa fail to construct an initial polygon to work with +}; + +}//Gu +}//physx + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecBox.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecBox.h new file mode 100644 index 00000000..15f3b28d --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecBox.h @@ -0,0 +1,217 @@ +// 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_VEC_BOX_H +#define GU_VEC_BOX_H + +/** \addtogroup geomutils +@{ +*/ +#include "foundation/PxTransform.h" +#include "PxPhysXCommonConfig.h" +#include "GuVecConvex.h" +#include "PsVecTransform.h" +#include "GuConvexSupportTable.h" +#include "PxBoxGeometry.h" + +namespace physx +{ +PX_PHYSX_COMMON_API extern const Ps::aos::BoolV boxVertexTable[8]; + +namespace Gu +{ + +#define BOX_MARGIN_RATIO 0.15f +#define BOX_MIN_MARGIN_RATIO 0.05f +#define BOX_SWEEP_MARGIN_RATIO 0.05f + +#define BOX_MARGIN_CCD_RATIO 0.01f +#define BOX_MIN_MARGIN_CCD_RATIO 0.005f + + + class CapsuleV; + + + PX_FORCE_INLINE void CalculateBoxMargin(const Ps::aos::Vec3VArg extent, PxReal& margin, PxReal& minMargin, PxReal& sweepMargin, + const PxReal marginR = BOX_MARGIN_RATIO, const PxReal minMarginR = BOX_MIN_MARGIN_RATIO) + { + using namespace Ps::aos; + + const FloatV min = V3ExtractMin(extent); + + const FloatV margin_ = FMul(min, FLoad(marginR)); + const FloatV minMargin_ = FMul(min, FLoad(minMarginR)); + const FloatV sweepMargin_ = FMul(min, FLoad(BOX_SWEEP_MARGIN_RATIO)); + + FStore(margin_, &margin); + FStore(minMargin_, &minMargin); + FStore(sweepMargin_, &sweepMargin); + } + + PX_FORCE_INLINE Ps::aos::FloatV CalculateBoxTolerance(const Ps::aos::Vec3VArg extent) + { + using namespace Ps::aos; + + const FloatV r0 = FLoad(0.01f); + const FloatV min = V3ExtractMin(extent);//FMin(V3GetX(extent), FMin(V3GetY(extent), V3GetZ(extent))); + return FMul(min, r0); + } + + //This method is called in the PCM contact gen for the refreshing contacts + PX_FORCE_INLINE Ps::aos::FloatV CalculatePCMBoxMargin(const Ps::aos::Vec3VArg extent) + { + using namespace Ps::aos; + + const FloatV min = V3ExtractMin(extent);//FMin(V3GetX(extent), FMin(V3GetY(extent), V3GetZ(extent))); + return FMul(min, FLoad(BOX_MARGIN_RATIO)); + } + + class BoxV : public ConvexV + { + public: + + /** + \brief Constructor + */ + PX_INLINE BoxV() : ConvexV(ConvexType::eBOX) + { + } + + PX_FORCE_INLINE BoxV(const Ps::aos::Vec3VArg origin, const Ps::aos::Vec3VArg extent) : + ConvexV(ConvexType::eBOX, origin), extents(extent) + { + CalculateBoxMargin(extent, margin, minMargin, sweepMargin); + marginDif = Ps::aos::FZero(); + } + + PX_FORCE_INLINE BoxV(const PxGeometry& geom) : ConvexV(ConvexType::eBOX, Ps::aos::V3Zero()) + { + using namespace Ps::aos; + const PxBoxGeometry& boxGeom = static_cast<const PxBoxGeometry&>(geom); + const Vec3V extent = Ps::aos::V3LoadU(boxGeom.halfExtents); + extents = extent; + CalculateBoxMargin(extent, margin, minMargin, sweepMargin, BOX_MARGIN_CCD_RATIO, BOX_MIN_MARGIN_CCD_RATIO); + marginDif = Ps::aos::FZero(); + } + + /** + \brief Destructor + */ + PX_INLINE ~BoxV() + { + } + + //! Assignment operator + PX_INLINE const BoxV& operator=(const BoxV& other) + { + center = other.center; + extents = other.extents; + margin = other.margin; + minMargin = other.minMargin; + marginDif = other.marginDif; + sweepMargin = other.sweepMargin; + return *this; + } + + PX_FORCE_INLINE void populateVerts(const PxU8* inds, PxU32 numInds, const PxVec3* originalVerts, Ps::aos::Vec3V* verts)const + { + using namespace Ps::aos; + + for(PxU32 i=0; i<numInds; ++i) + verts[i] = V3LoadU_SafeReadW(originalVerts[inds[i]]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'populateVerts' is always called with polyData.mVerts) + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* /*marginDif*/)const + { + using namespace Ps::aos; + const BoolV con = boxVertexTable[index]; + return V3Sel(con, extents, V3Neg(extents)); + } + + PX_FORCE_INLINE void getIndex(const Ps::aos::BoolV con, PxI32& index)const + { + using namespace Ps::aos; + index = PxI32(BGetBitMask(con) & 0x7); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir)const + { + using namespace Ps::aos; + return V3Sel(V3IsGrtr(dir, V3Zero()), extents, V3Neg(extents)); + } + + //this is used in the sat test for the full contact gen + PX_SUPPORT_INLINE void supportLocal(const Ps::aos::Vec3VArg dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + using namespace Ps::aos; + const Vec3V point = V3Sel(V3IsGrtr(dir, V3Zero()), extents, V3Neg(extents)); + max = V3Dot(dir, point); + min = FNeg(max); + } + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, const Ps::aos::PsMatTransformV& aTobT) const + { + //a is the current object, b is the other object, dir is in the local space of b + using namespace Ps::aos; +// const Vec3V _dir = aTob.rotateInv(dir);//relTra.rotateInv(dir);//from b to a + const Vec3V _dir = aTobT.rotate(dir);//relTra.rotateInv(dir);//from b to a + const Vec3V p = supportLocal(_dir); + //transfer p into the b space + return aTob.transform(p);//relTra.transform(p); + } + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* /*marginDif_*/)const + { + using namespace Ps::aos; + const BoolV comp = V3IsGrtr(dir, V3Zero()); + getIndex(comp, index); + return V3Sel(comp, extents, V3Neg(extents)); + } + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif_)const + { + //a is the current object, b is the other object, dir is in the local space of b + using namespace Ps::aos; +// const Vec3V _dir = aTob.rotateInv(dir);//relTra.rotateInv(dir);//from b to a + const Vec3V _dir = aTobT.rotate(dir);//relTra.rotateInv(dir);//from b to a + const Vec3V p = supportLocal(_dir, index, marginDif_); + //transfer p into the b space + return aTob.transform(p);//relTra.transform(p); + } + + Ps::aos::Vec3V extents; + Ps::aos::FloatV marginDif; + }; +} //PX_COMPILE_TIME_ASSERT(sizeof(Gu::BoxV) == 96); + +} + +/** @} */ +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecCapsule.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecCapsule.h new file mode 100644 index 00000000..e6c7d53c --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecCapsule.h @@ -0,0 +1,256 @@ +// 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_VEC_CAPSULE_H +#define GU_VEC_CAPSULE_H + +/** \addtogroup geomutils +@{ +*/ + +#include "GuVecConvex.h" +#include "GuConvexSupportTable.h" +#include "PxCapsuleGeometry.h" + + +namespace physx +{ +namespace Gu +{ + + PX_FORCE_INLINE Ps::aos::FloatV CalculateCapsuleMinMargin(const Ps::aos::FloatVArg radius) + { + using namespace Ps::aos; + const FloatV ratio = Ps::aos::FLoad(0.05f); + return FMul(radius, ratio); + } + + class CapsuleV : public ConvexV + { + public: + /** + \brief Constructor + */ + + PX_INLINE CapsuleV():ConvexV(ConvexType::eCAPSULE) + { + bMarginIsRadius = true; + } + + //constructor for sphere + PX_INLINE CapsuleV(const Ps::aos::Vec3VArg p, const Ps::aos::FloatVArg radius_) : ConvexV(ConvexType::eCAPSULE) + { + using namespace Ps::aos; + center = p; + radius = radius_; + p0 = p; + p1 = p; + FStore(radius, &margin); + FStore(radius, &minMargin); + FStore(radius, &sweepMargin); + bMarginIsRadius = true; + } + + PX_INLINE CapsuleV(const Ps::aos::Vec3VArg center_, const Ps::aos::Vec3VArg v_, const Ps::aos::FloatVArg radius_) : + ConvexV(ConvexType::eCAPSULE, center_) + { + using namespace Ps::aos; + radius = radius_; + p0 = V3Add(center_, v_); + p1 = V3Sub(center_, v_); + FStore(radius, &margin); + FStore(radius, &minMargin); + FStore(radius, &sweepMargin); + bMarginIsRadius = true; + } + + PX_INLINE CapsuleV(const PxGeometry& geom) : ConvexV(ConvexType::eCAPSULE, Ps::aos::V3Zero()) + { + using namespace Ps::aos; + const PxCapsuleGeometry& capsuleGeom = static_cast<const PxCapsuleGeometry&>(geom); + + const Vec3V axis = V3Scale(V3UnitX(), FLoad(capsuleGeom.halfHeight)); + const FloatV r = FLoad(capsuleGeom.radius); + p0 = axis; + p1 = V3Neg(axis); + radius = r; + FStore(radius, &margin); + FStore(radius, &minMargin); + FStore(radius, &sweepMargin); + bMarginIsRadius = true; + } + + /** + \brief Constructor + + \param _radius Radius of the capsule. + */ + + /** + \brief Destructor + */ + PX_INLINE ~CapsuleV() + { + } + + PX_FORCE_INLINE void initialize(const Ps::aos::Vec3VArg _p0, const Ps::aos::Vec3VArg _p1, const Ps::aos::FloatVArg _radius) + { + using namespace Ps::aos; + radius = _radius; + p0 = _p0; + p1 = _p1; + FStore(radius, &margin); + FStore(radius, &minMargin); + FStore(radius, &sweepMargin); + center = V3Scale(V3Add(_p0, _p1), FHalf()); + } + + PX_INLINE Ps::aos::Vec3V computeDirection() const + { + return Ps::aos::V3Sub(p1, p0); + } + + PX_FORCE_INLINE Ps::aos::FloatV getRadius() const + { + return radius; + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* /*marginDif*/)const + { + return (&p0)[1-index]; + } + + PX_FORCE_INLINE void getIndex(const Ps::aos::BoolV con, PxI32& index)const + { + using namespace Ps::aos; + const VecI32V v = VecI32V_From_BoolV(con); + const VecI32V t = VecI32V_And(v, VecI32V_One()); + PxI32_From_VecI32V(t, &index); + } + + PX_FORCE_INLINE void setCenter(const Ps::aos::Vec3VArg _center) + { + using namespace Ps::aos; + Vec3V offset = V3Sub(_center, center); + center = _center; + + p0 = V3Add(p0, offset); + p1 = V3Add(p1, offset); + } + + //dir, p0 and p1 are in the local space of dir + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir)const + { + using namespace Ps::aos; + //const Vec3V _dir = V3Normalize(dir); + const FloatV dist0 = V3Dot(p0, dir); + const FloatV dist1 = V3Dot(p1, dir); + return V3Sel(FIsGrtr(dist0, dist1), p0, p1); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aToB, const Ps::aos::PsMatTransformV& aTobT) const + { + using namespace Ps::aos; + //transform dir into the local space of a +// const Vec3V _dir = aToB.rotateInv(dir); + const Vec3V _dir = aTobT.rotate(dir); + const Vec3V p = supportLocal(_dir); + //transform p back to the local space of b + return aToB.transform(p); + } + + //dir, p0 and p1 are in the local space of dir + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* /*marginDif*/)const + { + using namespace Ps::aos; + + const FloatV dist0 = V3Dot(p0, dir); + const FloatV dist1 = V3Dot(p1, dir); + const BoolV comp = FIsGrtr(dist0, dist1); + getIndex(comp, index); + return V3Sel(comp, p0, p1); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aToB, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif)const + { + using namespace Ps::aos; + //transform dir into the local space of a +// const Vec3V _dir = aToB.rotateInv(dir); + const Vec3V _dir = aTobT.rotate(dir); + + const Vec3V p = supportLocal(_dir, index, marginDif); + //transform p back to the local space of b + return aToB.transform(p); + } + + //PX_FORCE_INLINE Ps::aos::BoolV supportLocalIndex(const Ps::aos::Vec3VArg dir, PxI32& index)const + //{ + // using namespace Ps::aos; + // //scale dir and put it in the vertex space + // const FloatV dist0 = V3Dot(p0, dir); + // const FloatV dist1 = V3Dot(p1, dir); + // const BoolV comp = FIsGrtr(dist0, dist1); + // getIndex(comp, index); + // return comp; + //} + + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(Ps::aos::Vec3V& support, const PxI32& index, const Ps::aos::BoolV comp)const + { + PX_UNUSED(index); + + using namespace Ps::aos; + const Vec3V p = V3Sel(comp, p0, p1); + support = p; + return p; + } + + //PX_FORCE_INLINE Ps::aos::BoolV supportRelativeIndex(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, PxI32& index)const + //{ + // using namespace Ps::aos; + // //scale dir and put it in the vertex space + // const Vec3V _dir =aTob.rotateInv(dir);//relTra.rotateInv(dir); + // return supportLocalIndex(_dir, index); + //} + + PX_FORCE_INLINE Ps::aos::FloatV getSweepMargin() const + { + return Ps::aos::FZero(); + } + + //don't change the order of p0 and p1, the getPoint function depend on the order + Ps::aos::Vec3V p0; //!< Start of segment + Ps::aos::Vec3V p1; //!< End of segment + Ps::aos::FloatV radius; + }; +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvex.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvex.h new file mode 100644 index 00000000..2ba97446 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvex.h @@ -0,0 +1,173 @@ +// 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_VEC_CONVEX_H +#define GU_VEC_CONVEX_H + +#include "CmPhysXCommon.h" +#include "PsVecMath.h" + +#define PX_SUPPORT_INLINE PX_FORCE_INLINE +#define PX_SUPPORT_FORCE_INLINE PX_FORCE_INLINE + +namespace physx +{ +namespace Gu +{ + + struct ConvexType + { + enum Type + { + eCONVEXHULL = 0, + eCONVEXHULLNOSCALE = 1, + eSPHERE = 2, + eBOX = 3, + eCAPSULE = 4, + eTRIANGLE = 5 + }; + }; + + class ConvexV + { + public: + + PX_FORCE_INLINE ConvexV(const ConvexType::Type type_) : type(type_), bMarginIsRadius(false) + { + margin = 0.f; + minMargin = 0.f; + sweepMargin = 0.f; + center = Ps::aos::V3Zero(); + } + + PX_FORCE_INLINE ConvexV(const ConvexType::Type type_, const Ps::aos::Vec3VArg center_) : type(type_), bMarginIsRadius(false) + { + using namespace Ps::aos; + center = center_; + margin = 0.f; + minMargin = 0.f; + sweepMargin = 0.f; + } + + + //everytime when someone transform the object, they need to up + PX_FORCE_INLINE void setCenter(const Ps::aos::Vec3VArg _center) + { + center = _center; + } + + PX_FORCE_INLINE void setMargin(const Ps::aos::FloatVArg margin_) + { + Ps::aos::FStore(margin_, &margin); + } + + PX_FORCE_INLINE void setMargin(const PxReal margin_) + { + margin = margin_; + } + + PX_FORCE_INLINE void setMinMargin(const Ps::aos::FloatVArg minMargin_) + { + Ps::aos::FStore(minMargin_, & minMargin); + } + + PX_FORCE_INLINE void setSweepMargin(const Ps::aos::FloatVArg sweepMargin_) + { + Ps::aos::FStore(sweepMargin_, &sweepMargin); + } + + PX_FORCE_INLINE Ps::aos::Vec3V getCenter()const + { + return center; + } + + PX_FORCE_INLINE Ps::aos::FloatV getMargin() const + { + return Ps::aos::FLoad(margin); + } + + PX_FORCE_INLINE Ps::aos::FloatV getMinMargin() const + { + return Ps::aos::FLoad(minMargin); + } + + PX_FORCE_INLINE Ps::aos::FloatV getSweepMargin() const + { + return Ps::aos::FLoad(sweepMargin); + } + + PX_FORCE_INLINE ConvexType::Type getType() const + { + return type; + } + + PX_FORCE_INLINE Ps::aos::BoolV isMarginEqRadius()const + { + return Ps::aos::BLoad(bMarginIsRadius); + } + + PX_FORCE_INLINE bool getMarginIsRadius() const + { + return bMarginIsRadius; + } + + protected: + ~ConvexV(){} + Ps::aos::Vec3V center; + PxReal margin; //margin is the amount by which we shrunk the shape for a convex or box. If the shape are sphere/capsule, margin is the radius + PxReal minMargin; //minMargin is some percentage of marginBase, which is used to determine the termination condition for gjk + PxReal sweepMargin;// sweepMargin minMargin is some percentage of marginBase, which is used to determine the termination condition for gjkRaycast + ConvexType::Type type; + bool bMarginIsRadius; + }; + + PX_FORCE_INLINE Ps::aos::FloatV getContactEps(const Ps::aos::FloatV& _marginA, const Ps::aos::FloatV& _marginB) + { + using namespace Ps::aos; + + const FloatV ratio = FLoad(0.25f); + const FloatV minMargin = FMin(_marginA, _marginB); + + return FMul(minMargin, ratio); + } + + PX_FORCE_INLINE Ps::aos::FloatV getSweepContactEps(const Ps::aos::FloatV& _marginA, const Ps::aos::FloatV& _marginB) + { + using namespace Ps::aos; + + const FloatV ratio = FLoad(100.f); + const FloatV minMargin = FAdd(_marginA, _marginB); + + return FMul(minMargin, ratio); + } +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvexHull.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvexHull.h new file mode 100644 index 00000000..114944e6 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvexHull.h @@ -0,0 +1,475 @@ +// 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_VEC_CONVEXHULL_H +#define GU_VEC_CONVEXHULL_H + +#include "PxPhysXCommonConfig.h" +#include "GuVecConvex.h" +#include "GuConvexMeshData.h" +#include "GuBigConvexData.h" +#include "GuConvexSupportTable.h" +#include "GuCubeIndex.h" +#include "PsFPU.h" +#include "GuGeometryUnion.h" +#include "PsVecQuat.h" +#include "PxMeshScale.h" + +namespace physx +{ +namespace Gu +{ +#define CONVEX_MARGIN_RATIO 0.1f +#define CONVEX_MIN_MARGIN_RATIO 0.05f +#define CONVEX_SWEEP_MARGIN_RATIO 0.025f + + //This margin is used in Persistent contact manifold + PX_SUPPORT_FORCE_INLINE Ps::aos::FloatV CalculatePCMConvexMargin(const Gu::ConvexHullData* hullData, const Ps::aos::Vec3VArg scale) + { + using namespace Ps::aos; + const Vec3V extents= V3Mul(V3LoadU(hullData->mInternal.mExtents), scale); + const FloatV min = V3ExtractMin(extents); + //ML: 25% of the minimum extents of the internal AABB as this convex hull's margin + return FMul(min, FLoad(0.25f)); + } + + + //This margin is used in PCM contact gen + PX_SUPPORT_FORCE_INLINE void CalculateConvexMargin(const Gu::ConvexHullData* hullData, PxReal& margin, PxReal& minMargin, PxReal& sweepMargin, const Ps::aos::Vec3VArg scale) + { + using namespace Ps::aos; + const Vec3V extents = V3Mul(V3LoadU(hullData->mInternal.mExtents), scale); + const FloatV min = V3ExtractMin(extents); + + //Margin is used in the plane shifting for the shrunk convex hull + const FloatV margin_ = FMul(min, FLoad(CONVEX_MARGIN_RATIO)); + //minMargin is used in the GJK termination condition + const FloatV minMargin_ = FMul(min, FLoad(CONVEX_MIN_MARGIN_RATIO)); + + const FloatV sweepMargin_ = FMul(min, FLoad(CONVEX_SWEEP_MARGIN_RATIO)); + + FStore(margin_, &margin); + FStore(minMargin_, &minMargin); + FStore(sweepMargin_, &sweepMargin); + } + + PX_SUPPORT_FORCE_INLINE Ps::aos::Mat33V ConstructSkewMatrix(const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg rotation) + { + using namespace Ps::aos; + Mat33V rot; + QuatGetMat33V(rotation, rot.col0, rot.col1, rot.col2); + Mat33V trans = M33Trnsps(rot); + trans.col0 = V3Scale(trans.col0, V3GetX(scale)); + trans.col1 = V3Scale(trans.col1, V3GetY(scale)); + trans.col2 = V3Scale(trans.col2, V3GetZ(scale)); + return M33MulM33(trans, rot); + } + + PX_SUPPORT_FORCE_INLINE void ConstructSkewMatrix(const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg rotation, Ps::aos::Mat33V& vertex2Shape, Ps::aos::Mat33V& shape2Vertex, const bool idtScale) + { + using namespace Ps::aos; + + PX_ASSERT(!V3AllEq(scale, V3Zero())); + + if(idtScale) + { + //create identity buffer + const Mat33V identity = M33Identity(); + vertex2Shape = identity; + shape2Vertex = identity; + } + else + { + const FloatV scaleX = V3GetX(scale); + const Vec3V invScale = V3Recip(scale); + + //this is uniform scale + if(V3AllEq(V3Splat(scaleX), scale)) + { + vertex2Shape = M33Diagonal(scale); + shape2Vertex = M33Diagonal(invScale); + } + else + { + Mat33V rot; + QuatGetMat33V(rotation, rot.col0, rot.col1, rot.col2); + const Mat33V trans = M33Trnsps(rot); + /* + vertex2shape + skewMat = Inv(R)*Diagonal(scale)*R; + */ + + const Mat33V temp(V3Scale(trans.col0, scaleX), V3Scale(trans.col1, V3GetY(scale)), V3Scale(trans.col2, V3GetZ(scale))); + vertex2Shape = M33MulM33(temp, rot); + + //don't need it in the support function + /* + shape2Vertex + invSkewMat =(invSkewMat)= Inv(R)*Diagonal(1/scale)*R; + */ + + shape2Vertex.col0 = V3Scale(trans.col0, V3GetX(invScale)); + shape2Vertex.col1 = V3Scale(trans.col1, V3GetY(invScale)); + shape2Vertex.col2 = V3Scale(trans.col2, V3GetZ(invScale)); + shape2Vertex = M33MulM33(shape2Vertex, rot); + + //shape2Vertex = M33Inverse(vertex2Shape); + } + } + } + + PX_SUPPORT_FORCE_INLINE Ps::aos::Mat33V ConstructVertex2ShapeMatrix(const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg rotation) + { + using namespace Ps::aos; + Mat33V rot; + QuatGetMat33V(rotation, rot.col0, rot.col1, rot.col2); + const Mat33V trans = M33Trnsps(rot); + /* + vertex2shape + skewMat = Inv(R)*Diagonal(scale)*R; + */ + + const Mat33V temp(V3Scale(trans.col0, V3GetX(scale)), V3Scale(trans.col1, V3GetY(scale)), V3Scale(trans.col2, V3GetZ(scale))); + return M33MulM33(temp, rot); + } + + + class ConvexHullV : public ConvexV + { + + class TinyBitMap + { + public: + PxU32 m[8]; + PX_FORCE_INLINE TinyBitMap() { m[0] = m[1] = m[2] = m[3] = m[4] = m[5] = m[6] = m[7] = 0; } + PX_FORCE_INLINE void set(PxU8 v) { m[v>>5] |= 1<<(v&31); } + PX_FORCE_INLINE bool get(PxU8 v) const { return (m[v>>5] & 1<<(v&31)) != 0; } + }; + + + public: + /** + \brief Constructor + */ + PX_SUPPORT_INLINE ConvexHullV(): ConvexV(ConvexType::eCONVEXHULL) + { + } + + PX_SUPPORT_INLINE ConvexHullV(const Gu::ConvexHullData* _hullData, const Ps::aos::Vec3VArg _center, const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg scaleRot, const bool idtScale): + ConvexV(ConvexType::eCONVEXHULL, _center) + { + using namespace Ps::aos; + + hullData = _hullData; + const PxVec3* PX_RESTRICT tempVerts = _hullData->getHullVertices(); + //const PxU8* PX_RESTRICT polyInds = _hullData->getFacesByVertices8(); + //const HullPolygonData* PX_RESTRICT polygons = _hullData->mPolygons; + verts = tempVerts; + numVerts = _hullData->mNbHullVertices; + CalculateConvexMargin( _hullData, margin, minMargin, sweepMargin, scale); + ConstructSkewMatrix(scale, scaleRot, vertex2Shape, shape2Vertex, idtScale); + /*skewScale = Mat33V temp(V3Scale(trans.col0, V3GetX(scale)), V3Scale(trans.col1, V3GetY(scale)), V3Scale(trans.col2, V3GetZ(scale))); + skewRot = QuatGetMat33V(scaleRot);*/ + + data = _hullData->mBigConvexRawData; + } + + PX_SUPPORT_INLINE ConvexHullV(const PxGeometry& geom) : ConvexV(ConvexType::eCONVEXHULL, Ps::aos::V3Zero()) + { + using namespace Ps::aos; + const PxConvexMeshGeometryLL& convexGeom = static_cast<const PxConvexMeshGeometryLL&>(geom); + const Gu::ConvexHullData* hData = convexGeom.hullData; + + const Vec3V vScale = V3LoadU_SafeReadW(convexGeom.scale.scale); // PT: safe because 'rotation' follows 'scale' in PxMeshScale + const QuatV vRot = QuatVLoadU(&convexGeom.scale.rotation.x); + const bool idtScale = convexGeom.scale.isIdentity(); + + hullData = hData; + const PxVec3* PX_RESTRICT tempVerts = hData->getHullVertices(); + verts = tempVerts; + numVerts = hData->mNbHullVertices; + CalculateConvexMargin( hData, margin, minMargin, sweepMargin, vScale); + ConstructSkewMatrix(vScale, vRot, vertex2Shape, shape2Vertex, idtScale); + + data = hData->mBigConvexRawData; + } + + PX_SUPPORT_INLINE void initialize(const Gu::ConvexHullData* _hullData, const Ps::aos::Vec3VArg _center, const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg scaleRot, const bool idtScale) + { + using namespace Ps::aos; + + const PxVec3* tempVerts = _hullData->getHullVertices(); + CalculateConvexMargin(_hullData, margin, minMargin, sweepMargin, scale); + ConstructSkewMatrix(scale, scaleRot, vertex2Shape, shape2Vertex, idtScale); + + verts = tempVerts; + numVerts = _hullData->mNbHullVertices; + //rot = _rot; + + center = _center; + + // searchIndex = 0; + data = _hullData->mBigConvexRawData; + + hullData = _hullData; + if(_hullData->mBigConvexRawData) + { + Ps::prefetchLine(hullData->mBigConvexRawData->mValencies); + Ps::prefetchLine(hullData->mBigConvexRawData->mValencies,128); + Ps::prefetchLine(hullData->mBigConvexRawData->mAdjacentVerts); + } + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* /*marginDif*/)const + { + using namespace Ps::aos; + + return M33MulV3(vertex2Shape, V3LoadU_SafeReadW(verts[index])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + } + + PX_NOINLINE PxU32 hillClimbing(const Ps::aos::Vec3VArg _dir)const + { + using namespace Ps::aos; + + const Gu::Valency* valency = data->mValencies; + const PxU8* adjacentVerts = data->mAdjacentVerts; + + //NotSoTinyBitMap visited; + PxU32 smallBitMap[8] = {0,0,0,0,0,0,0,0}; + + // PxU32 index = searchIndex; + PxU32 index = 0; + + { + PxVec3 vertexSpaceDirection; + V3StoreU(_dir, vertexSpaceDirection); + const PxU32 offset = ComputeCubemapNearestOffset(vertexSpaceDirection, data->mSubdiv); + //const PxU32 offset = ComputeCubemapOffset(vertexSpaceDirection, data->mSubdiv); + index = data->mSamples[offset]; + } + + Vec3V maxPoint = V3LoadU_SafeReadW(verts[index]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + FloatV max = V3Dot(maxPoint, _dir); + + PxU32 initialIndex = index; + + do + { + initialIndex = index; + const PxU32 numNeighbours = valency[index].mCount; + const PxU32 offset = valency[index].mOffset; + + for(PxU32 a = 0; a < numNeighbours; ++a) + { + const PxU32 neighbourIndex = adjacentVerts[offset + a]; + + const Vec3V vertex = V3LoadU_SafeReadW(verts[neighbourIndex]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + const FloatV dist = V3Dot(vertex, _dir); + if(FAllGrtr(dist, max)) + { + const PxU32 ind = neighbourIndex>>5; + const PxU32 mask = PxU32(1 << (neighbourIndex & 31)); + if((smallBitMap[ind] & mask) == 0) + { + smallBitMap[ind] |= mask; + max = dist; + index = neighbourIndex; + } + } + } + + }while(index != initialIndex); + + return index; + } + + PX_SUPPORT_INLINE PxU32 bruteForceSearch(const Ps::aos::Vec3VArg _dir)const + { + using namespace Ps::aos; + //brute force + //get the support point from the orignal margin + FloatV max = V3Dot(V3LoadU_SafeReadW(verts[0]), _dir); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + PxU32 maxIndex=0; + + // PT: TODO: not sure SIMD is useful here... + + for(PxU32 i = 1; i < numVerts; ++i) + { +// Ps::prefetchLine(&verts[i], 128); // PT: TODO: 128 doesn't help when your cache line is 64. HW prefetchers do a better job here. + const Vec3V vertex = V3LoadU_SafeReadW(verts[i]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + const FloatV dist = V3Dot(vertex, _dir); + if(FAllGrtr(dist, max)) + { + max = dist; + maxIndex = i; + } + } + return maxIndex; + } + + //points are in vertex space, _dir in vertex space + PX_NOINLINE PxU32 supportVertexIndex(const Ps::aos::Vec3VArg _dir)const + { + using namespace Ps::aos; + if(data) + return hillClimbing(_dir); + else + return bruteForceSearch(_dir); + } + + //dir is in the vertex space + PX_SUPPORT_INLINE void bruteForceSearchMinMax(const Ps::aos::Vec3VArg dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + using namespace Ps::aos; + //brute force + //get the support point from the orignal margin + FloatV _max = V3Dot(V3LoadU_SafeReadW(verts[0]), dir); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + FloatV _min = _max; + + for(PxU32 i = 1; i < numVerts; ++i) + { +// Ps::prefetchLine(&verts[i], 128); // PT: TODO: 128 doesn't help when your cache line is 64. HW prefetchers do a better job here. + const FloatV dist = V3Dot(V3LoadU_SafeReadW(verts[i]), dir); + _max = FMax(dist, _max); + _min = FMin(dist, _min); + } + + + min = _min; + max = _max; + } + + //This function is used in the full contact manifold generation code, points are in vertex space. + //This function support scaling, _dir is in the shape space + PX_SUPPORT_INLINE void supportVertexMinMax(const Ps::aos::Vec3VArg _dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + using namespace Ps::aos; + + //dir is in the vertex space + const Vec3V dir = M33TrnspsMulV3(vertex2Shape, _dir); + + if(data) + { + const PxU32 maxIndex= hillClimbing(dir); + const PxU32 minIndex= hillClimbing(V3Neg(dir)); + const Vec3V maxPoint= M33MulV3(vertex2Shape, V3LoadU_SafeReadW(verts[maxIndex])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + const Vec3V minPoint= M33MulV3(vertex2Shape, V3LoadU_SafeReadW(verts[minIndex])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + min = V3Dot(_dir, minPoint); + max = V3Dot(_dir, maxPoint); + } + else + { + //dir is in the vertex space + bruteForceSearchMinMax(dir, min, max); + } + } + + //This function is used in the full contact manifold generation code + PX_SUPPORT_INLINE void populateVerts(const PxU8* inds, PxU32 numInds, const PxVec3* originalVerts, Ps::aos::Vec3V* _verts)const + { + using namespace Ps::aos; + + for(PxU32 i=0; i<numInds; ++i) + _verts[i] = M33MulV3(vertex2Shape, V3LoadU_SafeReadW(originalVerts[inds[i]])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'populateVerts' is always called with polyData.mVerts) + } + + //This function is used in epa + //dir is in the shape space + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir)const + { + using namespace Ps::aos; + //scale dir and put it in the vertex space + const Vec3V _dir = M33TrnspsMulV3(vertex2Shape, dir); + const PxU32 maxIndex = supportVertexIndex(_dir); + return M33MulV3(vertex2Shape, V3LoadU_SafeReadW(verts[maxIndex])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + } + + //this is used in the sat test for the full contact gen + PX_SUPPORT_INLINE void supportLocal(const Ps::aos::Vec3VArg dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + using namespace Ps::aos; + //dir is in the shape space + supportVertexMinMax(dir, min, max); + } + + //This function is used in epa + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, const Ps::aos::PsMatTransformV& aTobT) const + { + using namespace Ps::aos; + + //transform dir into the shape space +// const Vec3V dir_ = aTob.rotateInv(dir);//relTra.rotateInv(dir); + const Vec3V dir_ = aTobT.rotate(dir);//relTra.rotateInv(dir); + const Vec3V maxPoint =supportLocal(dir_); + //translate maxPoint from shape space of a back to the b space + return aTob.transform(maxPoint);//relTra.transform(maxPoint); + } + + //dir in the shape space, this function is used in gjk + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* /*marginDif*/)const + { + using namespace Ps::aos; + //scale dir and put it in the vertex space, for non-uniform scale, we don't want the scale in the dir, therefore, we are using + //the transpose of the inverse of shape2Vertex(which is vertex2shape). This will allow us igore the scale and keep the rotation + const Vec3V dir_ = M33TrnspsMulV3(vertex2Shape, dir); + //get the extreme point index + const PxU32 maxIndex = supportVertexIndex(dir_); + index = PxI32(maxIndex); + //p is in the shape space + return M33MulV3(vertex2Shape, V3LoadU_SafeReadW(verts[index])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + } + + //this function is used in gjk + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif)const + { + using namespace Ps::aos; + + //transform dir from b space to the shape space of a space +// const Vec3V dir_ = aTob.rotateInv(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V dir_ = aTobT.rotate(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V p = supportLocal(dir_, index, marginDif); + //transfrom from a to b space + return aTob.transform(p); + } + + Ps::aos::Mat33V vertex2Shape;//inv(R)*S*R + Ps::aos::Mat33V shape2Vertex;//inv(vertex2Shape) + + const Gu::ConvexHullData* hullData; + const BigConvexRawData* data; + const PxVec3* verts; + PxU8 numVerts; + }; + +} + +} + +#endif // diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvexHullNoScale.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvexHullNoScale.h new file mode 100644 index 00000000..a50532dc --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecConvexHullNoScale.h @@ -0,0 +1,250 @@ +// 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_VEC_CONVEXHULL_NOSCALE_H +#define GU_VEC_CONVEXHULL_NOSCALE_H + +#include "foundation/PxUnionCast.h" +#include "PxPhysXCommonConfig.h" +#include "GuVecConvexHull.h" + + +namespace physx +{ +namespace Gu +{ + + class ConvexHullNoScaleV : public ConvexHullV + { + + + public: + /** + \brief Constructor + */ + PX_SUPPORT_INLINE ConvexHullNoScaleV(): ConvexHullV() + { + } + + PX_SUPPORT_INLINE ConvexHullNoScaleV(const Gu::ConvexHullData* _hullData, const Ps::aos::Vec3VArg _center, const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg scaleRot) + { + PX_UNUSED(scaleRot); + PX_UNUSED(_center); + + using namespace Ps::aos; + + hullData = _hullData; + const PxVec3* PX_RESTRICT tempVerts = _hullData->getHullVertices(); + verts = tempVerts; + numVerts = _hullData->mNbHullVertices; + CalculateConvexMargin( _hullData, margin, minMargin, sweepMargin, scale); + data = _hullData->mBigConvexRawData; + + PxU8* startAddress = reinterpret_cast<PxU8*>(_hullData->mPolygons); + PxI32 totalPrefetchBytes = PxI32((_hullData->getFacesByVertices8() + _hullData->mNbHullVertices * 3) - startAddress); + + //Prefetch core data + + while(totalPrefetchBytes > 0) + { + totalPrefetchBytes -= 128; + Ps::prefetchLine(startAddress); + startAddress += 128; + } + + if(data) + { + PxI32 totalSize = PxI32(data->mNbSamples + data->mNbVerts * sizeof(Gu::Valency) + data->mNbAdjVerts); + startAddress = data->mSamples; + while(totalSize > 0) + { + totalSize -= 128; + Ps::prefetchLine(startAddress); + startAddress += 128; + } + } + + } + + + /* PX_SUPPORT_INLINE ConvexHullNoScaleV(const Gu::ConvexHullData* _hullData, const Ps::aos::Vec3VArg _center, const Ps::aos::FloatVArg _margin, const Ps::aos::FloatVArg _minMargin, const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg scaleRot) + { + PX_UNUSED(scaleRot); + PX_UNUSED(_center); + PX_UNUSED(scale); + + using namespace Ps::aos; + + hullData = _hullData; + margin = _margin; + minMargin = _minMargin; + + const PxVec3* tempVerts = _hullData->getHullVertices(); + const PxU8* PX_RESTRICT polyInds = _hullData->getFacesByVertices8(); + const HullPolygonData* PX_RESTRICT polygons = _hullData->mPolygons; + verts = tempVerts; + numVerts = _hullData->mNbHullVertices; + + Ps::prefetchLine(tempVerts); + Ps::prefetchLine(tempVerts,128); + Ps::prefetchLine(tempVerts,256); + + Ps::prefetchLine(polyInds); + Ps::prefetchLine(polyInds,128); + + Ps::prefetchLine(polygons); + Ps::prefetchLine(polygons, 128); + Ps::prefetchLine(polygons, 256); + }*/ + + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* /*marginDif*/)const + { + using namespace Ps::aos; + return V3LoadU_SafeReadW(verts[index]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + } + + + // PT: TODO: is there a difference between 'originalVerts' and the 'verts' class member? Also why is this a member function at all? + PX_SUPPORT_INLINE void populateVerts(const PxU8* inds, PxU32 numInds, const PxVec3* originalVerts, Ps::aos::Vec3V* verts_)const + { + using namespace Ps::aos; + + for(PxU32 i=0; i<numInds; ++i) + verts_[i] = V3LoadU_SafeReadW(originalVerts[inds[i]]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'populateVerts' is always called with polyData.mVerts) + } + + + //This function is used in epa + //dir is in the shape space + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir)const + { + using namespace Ps::aos; + const PxU32 maxIndex = supportVertexIndex(dir); + return V3LoadU_SafeReadW(verts[maxIndex]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + } + + //this is used in the sat test for the full contact gen + PX_SUPPORT_INLINE void supportLocal(const Ps::aos::Vec3VArg dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + supportVertexMinMax(dir, min, max); + } + + + //This function is used in epa + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, const Ps::aos::PsMatTransformV& aTobT) const + { + using namespace Ps::aos; + + //transform dir into the shape space +// const Vec3V _dir = aTob.rotateInv(dir);//relTra.rotateInv(dir); + const Vec3V _dir = aTobT.rotate(dir);//relTra.rotateInv(dir); + const Vec3V maxPoint = supportLocal(_dir); + //translate maxPoint from shape space of a back to the b space + return aTob.transform(maxPoint);//relTra.transform(maxPoint); + } + + //dir in the shape space, this function is used in gjk + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* /*marginDif*/)const + { + using namespace Ps::aos; + //scale dir and put it in the vertex space, for non-uniform scale, we don't want the scale in the dir, therefore, we are using + //the transpose of the inverse of shape2Vertex(which is vertex2shape). This will allow us igore the scale and keep the rotation + //get the extreme point index + const PxU32 maxIndex = supportVertexIndex(dir); + index = PxI32(maxIndex); + return V3LoadU_SafeReadW(verts[index]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + } + + //this function is used in gjk + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif)const + { + using namespace Ps::aos; + + //transform dir from b space to the shape space of a space +// const Vec3V _dir = aTob.rotateInv(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V _dir = aTobT.rotate(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V p = supportLocal(_dir, index, marginDif); + //transfrom from a to b space + return aTob.transform(p); + } + + + PX_SUPPORT_INLINE void bruteForceSearchMinMax(const Ps::aos::Vec3VArg _dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + using namespace Ps::aos; + //brute force + //get the support point from the orignal margin + FloatV _max = V3Dot(V3LoadU_SafeReadW(verts[0]), _dir); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + FloatV _min = _max; + + for(PxU32 i = 1; i < numVerts; ++i) + { + Ps::prefetchLine(&verts[i], 128); + const Vec3V vertex = V3LoadU_SafeReadW(verts[i]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + const FloatV dist = V3Dot(vertex, _dir); + + _max = FMax(dist, _max); + _min = FMin(dist, _min); + } + + min = _min; + max = _max; + } + + //This function support no scaling, dir is in the shape space(the same as vertex space) + PX_SUPPORT_INLINE void supportVertexMinMax(const Ps::aos::Vec3VArg dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max)const + { + using namespace Ps::aos; + + if(data) + { + const PxU32 maxIndex= hillClimbing(dir); + const PxU32 minIndex= hillClimbing(V3Neg(dir)); + const Vec3V maxPoint= V3LoadU_SafeReadW(verts[maxIndex]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + const Vec3V minPoint= V3LoadU_SafeReadW(verts[minIndex]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + min = V3Dot(dir, minPoint); + max = V3Dot(dir, maxPoint); + } + else + { + bruteForceSearchMinMax(dir, min, max); + } + } + + + }; + + #define PX_CONVEX_TO_NOSCALECONVEX(x) (static_cast<ConvexHullNoScaleV*>(x)) +} + +} + +#endif // diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecPlane.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecPlane.h new file mode 100644 index 00000000..ad41cd3e --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecPlane.h @@ -0,0 +1,224 @@ +// 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_VEC_PLANE_H +#define GU_VEC_PLANE_H +/** \addtogroup geomutils +@{ +*/ + +#include "foundation/PxVec3.h" +#include "foundation/PxPlane.h" +#include "CmPhysXCommon.h" +#include "PsVecMath.h" + +/** +\brief Representation of a plane. + +Plane equation used: a*x + b*y + c*z + d = 0 +*/ +namespace physx +{ +namespace Gu +{ + + class PlaneV + { + public: + /** + \brief Constructor + */ + PX_FORCE_INLINE PlaneV() + { + } + + /** + \brief Constructor from a normal and a distance + */ + PX_FORCE_INLINE PlaneV(const Ps::aos::FloatVArg nx, const Ps::aos::FloatVArg ny, const Ps::aos::FloatVArg nz, const Ps::aos::FloatVArg _d) + { + set(nx, ny, nz, _d); + } + + PX_FORCE_INLINE PlaneV(const PxPlane& plane) + { + using namespace Ps::aos; + const Vec3V _n = V3LoadU(plane.n); + const FloatV _d = FLoad(plane.d); + nd = V4SetW(Vec4V_From_Vec3V(_n), _d); + } + + + /** + \brief Constructor from three points + */ + PX_FORCE_INLINE PlaneV(const Ps::aos::Vec3VArg p0, const Ps::aos::Vec3VArg p1, const Ps::aos::Vec3VArg p2) + { + set(p0, p1, p2); + } + + /** + \brief Constructor from a normal and a distance + */ + PX_FORCE_INLINE PlaneV(const Ps::aos::Vec3VArg _n, const Ps::aos::FloatVArg _d) + { + nd = Ps::aos::V4SetW(Ps::aos::Vec4V_From_Vec3V(_n), _d); + } + + /** + \brief Copy constructor + */ + PX_FORCE_INLINE PlaneV(const PlaneV& plane) : nd(plane.nd) + { + } + + /** + \brief Destructor + */ + PX_FORCE_INLINE ~PlaneV() + { + } + + /** + \brief Sets plane to zero. + */ + PX_FORCE_INLINE PlaneV& setZero() + { + nd = Ps::aos::V4Zero(); + return *this; + } + + PX_FORCE_INLINE PlaneV& set(const Ps::aos::FloatVArg nx, const Ps::aos::FloatVArg ny, const Ps::aos::FloatVArg nz, const Ps::aos::FloatVArg _d) + { + + using namespace Ps::aos; + const Vec3V n= V3Merge(nx, ny, nz); + nd = V4SetW(Vec4V_From_Vec3V(n), _d); + return *this; + } + + PX_FORCE_INLINE PlaneV& set(const Ps::aos::Vec3VArg _normal, Ps::aos::FloatVArg _d) + { + nd = Ps::aos::V4SetW(Ps::aos::Vec4V_From_Vec3V(_normal), _d); + return *this; + } + + /** + \brief Computes the plane equation from 3 points. + */ + PlaneV& set(const Ps::aos::Vec3VArg p0, const Ps::aos::Vec3VArg p1, const Ps::aos::Vec3VArg p2) + { + using namespace Ps::aos; + const Vec3V edge0 = V3Sub(p1, p0); + const Vec3V edge1 = V3Sub(p2, p0); + + const Vec3V n = V3Normalize(V3Cross(edge0, edge1)); + // See comments in set() for computation of d + const FloatV d = FNeg(V3Dot(p0, n)); + nd = V4SetW(Vec4V_From_Vec3V(n), d); + return *this; + } + + /*** + \brief Computes distance, assuming plane is normalized + \sa normalize + */ + PX_FORCE_INLINE Ps::aos::FloatV distance(const Ps::aos::Vec3VArg p) const + { + // Valid for plane equation a*x + b*y + c*z + d = 0 + using namespace Ps::aos; + const Vec3V n = Vec3V_From_Vec4V(nd); + return FAdd(V3Dot(p, n), V4GetW(nd)); + } + + PX_FORCE_INLINE Ps::aos::BoolV belongs(const Ps::aos::Vec3VArg p) const + { + using namespace Ps::aos; + const FloatV eps = FLoad(1.0e-7f); + return FIsGrtr(eps, FAbs(distance(p))); + } + + /** + \brief projects p into the plane + */ + PX_FORCE_INLINE Ps::aos::Vec3V project(const Ps::aos::Vec3VArg p) const + { + // Pretend p is on positive side of plane, i.e. plane.distance(p)>0. + // To project the point we have to go in a direction opposed to plane's normal, i.e.: + using namespace Ps::aos; + const Vec3V n = Vec3V_From_Vec4V(nd); + return V3Sub(p, V3Scale(n, V4GetW(nd))); + + } + + PX_FORCE_INLINE Ps::aos::FloatV signedDistanceHessianNormalForm(const Ps::aos::Vec3VArg point) const + { + using namespace Ps::aos; + const Vec3V n = Vec3V_From_Vec4V(nd); + return FAdd(V3Dot(n, point), V4GetW(nd)); + } + + PX_FORCE_INLINE Ps::aos::Vec3V getNormal() const + { + return Ps::aos::Vec3V_From_Vec4V(nd); + } + + PX_FORCE_INLINE Ps::aos::FloatV getSignDist() const + { + return Ps::aos::V4GetW(nd); + } + + /** + \brief find an arbitrary point in the plane + */ + PX_FORCE_INLINE Ps::aos::Vec3V pointInPlane() const + { + // Project origin (0,0,0) to plane: + // (0) - normal * distance(0) = - normal * ((p|(0)) + d) = -normal*d + using namespace Ps::aos; + const Vec3V n = Vec3V_From_Vec4V(nd); + return V3Neg(V3Scale(n, V4GetW(nd))); + } + + PX_FORCE_INLINE void normalize() + { + using namespace Ps::aos; + const Vec3V n = Vec3V_From_Vec4V(nd); + const FloatV denom = FRecip(V3Length(n)); + V4Scale(nd, denom); + } + + Ps::aos::Vec4V nd; //!< The normal to the plan , w store the distance from the origin + }; +} + +} + +/** @} */ +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkBox.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkBox.h new file mode 100644 index 00000000..8fbaa111 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkBox.h @@ -0,0 +1,191 @@ +// 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_VEC_SHRUNK_BOX_H +#define GU_VEC_SHRUNK_BOX_H + +/** \addtogroup geomutils +@{ +*/ +#include "PxPhysXCommonConfig.h" +#include "GuVecConvex.h" +#include "PsVecTransform.h" +#include "GuConvexSupportTable.h" +#include "GuVecBox.h" + + + +namespace physx +{ + +namespace Gu +{ + + /** + \brief Represents an oriented bounding box. + + As a center point, extents(radii) and a rotation. i.e. the center of the box is at the center point, + the box is rotated around this point with the rotation and it is 2*extents in width, height and depth. + */ + + /** + Box geometry + + The rot member describes the world space orientation of the box. + The center member gives the world space position of the box. + The extents give the local space coordinates of the box corner in the positive octant. + Dimensions of the box are: 2*extent. + Transformation to world space is: worldPoint = rot * localPoint + center + Transformation to local space is: localPoint = T(rot) * (worldPoint - center) + Where T(M) denotes the transpose of M. + */ + + class ShrunkBoxV : public BoxV + { + public: + + /** + \brief Constructor + */ + PX_INLINE ShrunkBoxV() : BoxV() + { + } + + PX_INLINE ShrunkBoxV(const PxGeometry& geom) : BoxV(geom) + { + initialiseMarginDif(); + } + + /** + \brief Constructor + + \param origin Center of the OBB + \param extent Extents/radii of the obb. + */ + + PX_FORCE_INLINE ShrunkBoxV(const Ps::aos::Vec3VArg origin, const Ps::aos::Vec3VArg extent) : + BoxV(origin, extent) + { + initialiseMarginDif(); + } + + /** + \brief Destructor + */ + PX_INLINE ~ShrunkBoxV() + { + } + + //! Assignment operator + PX_INLINE const ShrunkBoxV& operator=(const ShrunkBoxV& other) + { + center = other.center; + extents = other.extents; + margin = other.margin; + minMargin = other.minMargin; + return *this; + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif_)const + { + using namespace Ps::aos; + const Vec3V extents_ = V3Sub(extents, V3Splat(getMargin())); + const BoolV con = boxVertexTable[index]; + (*marginDif_) = marginDif; + return V3Sel(con, extents_, V3Neg(extents_)); + } + + //local space point + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir)const + { + using namespace Ps::aos; + + const Vec3V zero = V3Zero(); + const Vec3V extents_ = V3Sub(extents, V3Splat(getMargin())); + const BoolV comp = V3IsGrtr(dir, zero); + return V3Sel(comp, extents_, V3Neg(extents_)); + } + + //local space point + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif_)const + { + using namespace Ps::aos; + + const Vec3V zero = V3Zero(); + const Vec3V extents_ = V3Sub(extents, V3Splat(getMargin())); + const BoolV comp = V3IsGrtr(dir, zero); + getIndex(comp, index); + (*marginDif_) = marginDif; + return V3Sel(comp, extents_, V3Neg(extents_)); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, const Ps::aos::PsMatTransformV& aTobT) const + { + using namespace Ps::aos; + + //transfer dir into the local space of the box +// const Vec3V dir_ =aTob.rotateInv(dir);//relTra.rotateInv(dir); + const Vec3V dir_ = aTobT.rotate(dir);//relTra.rotateInv(dir); + const Vec3V p = supportLocal(dir_); + return aTob.transform(p);//relTra.transform(p);//V3Add(center, M33MulV3(rot, p)); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif_)const + { + using namespace Ps::aos; + + //transfer dir into the local space of the box +// const Vec3V dir_ =aTob.rotateInv(dir);//relTra.rotateInv(dir); + const Vec3V dir_ = aTobT.rotate(dir);//relTra.rotateInv(dir); + const Vec3V p = supportLocal(dir_, index, marginDif_); + return aTob.transform(p);//relTra.transform(p);//V3Add(center, M33MulV3(rot, p)); + } + + private: + + PX_FORCE_INLINE void initialiseMarginDif() + { + using namespace Ps::aos; + //calculate the marginDif + const PxReal sqMargin = margin * margin; + const PxReal tempMarginDif = sqrtf(sqMargin * 3.f); + const PxReal marginDif_ = tempMarginDif - margin; + marginDif = FLoad(marginDif_); + /* const FloatV sqMargin = FMul(margin, margin); + const FloatV tempMarginDif = FSqrt(FAdd(sqMargin, FAdd(sqMargin, sqMargin))); + marginDif = FSub(tempMarginDif, margin);*/ + } + }; +} + +} + +/** @} */ +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkConvexHull.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkConvexHull.h new file mode 100644 index 00000000..fe72bc1d --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkConvexHull.h @@ -0,0 +1,183 @@ +// 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_VEC_SHRUNK_CONVEX_HULL_H +#define GU_VEC_SHRUNK_CONVEX_HULL_H + +#include "PxPhysXCommonConfig.h" +#include "GuVecConvexHull.h" +#include "GuConvexMeshData.h" +#include "GuBigConvexData.h" +#include "GuConvexSupportTable.h" +#include "GuCubeIndex.h" +#include "PsFPU.h" + + +namespace physx +{ +namespace Gu +{ + + PX_SUPPORT_FORCE_INLINE Ps::aos::Vec3V intersectPlanes(const Ps::aos::Vec3VArg n1, const Ps::aos::FloatVArg d1, + const Ps::aos::Vec3VArg n2, const Ps::aos::FloatVArg d2, + const Ps::aos::Vec3VArg n3, const Ps::aos::FloatVArg d3) + { + using namespace Ps::aos; + const Vec3V u = V3Cross(n2, n3); + const FloatV denom = V3Dot(n1, u); + const Vec3V temp = V3NegScaleSub(n2, d3, V3Scale(n3, d2)); + const Vec3V p = V3NegScaleSub(u, d1, V3Cross(n1, temp)); + return V3ScaleInv(p, denom); + } + + + + /* + ML: + ShrinkedConvexHull is used in GJK code but not EPA code + */ + class ShrunkConvexHullV : public ConvexHullV + { + + + public: + /** + \brief Constructor + */ + PX_SUPPORT_INLINE ShrunkConvexHullV(): ConvexHullV() + { + } + + PX_SUPPORT_INLINE ShrunkConvexHullV(const PxGeometry& geom) : ConvexHullV(geom) + { + } + + PX_SUPPORT_INLINE ShrunkConvexHullV(const Gu::ConvexHullData* _hullData, const Ps::aos::Vec3VArg _center, const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg scaleRot, const bool idtScale): + ConvexHullV(_hullData, _center, scale, scaleRot, idtScale) + { + } + + + + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif) const + { + + return planeShift(PxU32(index), getMargin(), marginDif); + } + + //get the support point in vertex space + PX_SUPPORT_INLINE Ps::aos::Vec3V planeShift(const PxU32 index, const Ps::aos::FloatVArg margin_, Ps::aos::FloatV* marginDif) const + { + using namespace Ps::aos; + + //calculate the support point for the core(shrunk) shape + const PxU8* PX_RESTRICT polyInds = hullData->getFacesByVertices8(); + + //transfrom the vertex from vertex space to shape space + const Vec3V p = M33MulV3(vertex2Shape, V3LoadU_SafeReadW(verts[index])); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + + const PxU32 ind = index*3; + + const PxPlane& data1 = hullData->mPolygons[polyInds[ind]].mPlane; + const PxPlane& data2 = hullData->mPolygons[polyInds[ind+1]].mPlane; + const PxPlane& data3 = hullData->mPolygons[polyInds[ind+2]].mPlane; + + //transform the normal from vertex space to shape space + //This is only required if the scale is not uniform + const Vec3V n1 = V3Normalize(M33TrnspsMulV3(shape2Vertex, V3LoadU_SafeReadW(data1.n))); // PT: safe because 'd' follows 'n' in the plane class + const Vec3V n2 = V3Normalize(M33TrnspsMulV3(shape2Vertex, V3LoadU_SafeReadW(data2.n))); // PT: safe because 'd' follows 'n' in the plane class + const Vec3V n3 = V3Normalize(M33TrnspsMulV3(shape2Vertex, V3LoadU_SafeReadW(data3.n))); // PT: safe because 'd' follows 'n' in the plane class + + //This is only required if the scale is not 1 + const FloatV d1 = FSub(margin_, V3Dot(p, n1)); + const FloatV d2 = FSub(margin_, V3Dot(p, n2)); + const FloatV d3 = FSub(margin_, V3Dot(p, n3)); + + //This is unavoidable unless we pre-calc the core shape. The intersect point is in shape space + const Vec3V intersectPoints = intersectPlanes(n1, d1, n2, d2, n3, d3); + const Vec3V v =V3Sub(p, intersectPoints); + (*marginDif) = FSub(V3Length(v), margin_); + return intersectPoints; + } + + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir) const + { + PxI32 index; + Ps::aos::FloatV marginDif; + return supportLocal(dir, index, &marginDif); + } + + + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, const Ps::aos::PsMatTransformV& aTobT) const + { + PxI32 index; + Ps::aos::FloatV marginDif; + return supportRelative(dir, aTob, aTobT, index, &marginDif); + } + + //This function is used in gjk + //dir in the shape space + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const + { + using namespace Ps::aos; + //scale dir and put it in the vertex space, for non-uniform scale, we don't want the scale in the dir, therefore, we are using + //the transpose of the inverse of shape2Vertex(which is vertex2shape). This will allow us igore the scale and keep the rotation + const Vec3V _dir = M33TrnspsMulV3(vertex2Shape, dir); + //get the extreme point index + const PxU32 maxIndex = supportVertexIndex(_dir); + index = PxI32(maxIndex); + //p is in the shape space + return planeShift(maxIndex, getMargin(), marginDif); + } + + + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif) const + { + using namespace Ps::aos; + + //transform dir from b space to the shape space of a space +// const Vec3V _dir = aTob.rotateInv(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V _dir = aTobT.rotate(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V p = supportLocal(_dir, index, marginDif); + //transfrom from a to b space + return aTob.transform(p); + } + + }; + +} + +} + +#endif // diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkConvexHullNoScale.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkConvexHullNoScale.h new file mode 100644 index 00000000..9e5d8c0c --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecShrunkConvexHullNoScale.h @@ -0,0 +1,155 @@ +// 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_VEC_SHRUNK_CONVEX_HULL_NO_SCALE_H +#define GU_VEC_SHRUNK_CONVEX_HULL_NO_SCALE_H + +#include "foundation/PxUnionCast.h" +#include "GuVecShrunkConvexHull.h" + + +namespace physx +{ +namespace Gu +{ + + + /* + ML: + ShrinkedConvexHull is used in GJK code but not EPA code + */ + class ShrunkConvexHullNoScaleV : public ShrunkConvexHullV + { + + + public: + /** + \brief Constructor + */ + PX_SUPPORT_INLINE ShrunkConvexHullNoScaleV(): ShrunkConvexHullV() + { + } + + PX_SUPPORT_INLINE ShrunkConvexHullNoScaleV(const PxGeometry& geom) : ShrunkConvexHullV(geom) + { + } + + PX_SUPPORT_INLINE ShrunkConvexHullNoScaleV(const Gu::ConvexHullData* _hullData, const Ps::aos::Vec3VArg _center, const Ps::aos::Vec3VArg scale, const Ps::aos::QuatVArg scaleRot): + ShrunkConvexHullV(_hullData, _center, scale, scaleRot, true) + { + } + + + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* marginDif) const + { + return planeShift(PxU32(index), getMargin(), marginDif); + } + + //get the support point in vertex space + PX_SUPPORT_INLINE Ps::aos::Vec3V planeShift(const PxU32 index, const Ps::aos::FloatVArg margin_, Ps::aos::FloatV* marginDif) const + { + using namespace Ps::aos; + + //calculate the support point for the core(shrunk) shape + const PxU8* PX_RESTRICT polyInds = hullData->getFacesByVertices8(); + + const Vec3V p = V3LoadU_SafeReadW(verts[index]); // PT: safe because of the way vertex memory is allocated in ConvexHullData (and 'verts' is initialized with ConvexHullData::getHullVertices()) + + const PxU32 ind = index*3; + + const PxPlane& data1 = hullData->mPolygons[polyInds[ind]].mPlane; + const PxPlane& data2 = hullData->mPolygons[polyInds[ind+1]].mPlane; + const PxPlane& data3 = hullData->mPolygons[polyInds[ind+2]].mPlane; + + //ML: because we don't have scale in this type of convex hull so that normal in vertex space will be the same as shape space normal + //This is only required if the scale is not uniform + const Vec3V n1 = V3LoadU_SafeReadW(data1.n); // PT: safe because 'd' follows 'n' in the plane class + const Vec3V n2 = V3LoadU_SafeReadW(data2.n); // PT: safe because 'd' follows 'n' in the plane class + const Vec3V n3 = V3LoadU_SafeReadW(data3.n); // PT: safe because 'd' follows 'n' in the plane class + + //This is only required if the scale is not 1 + const FloatV d1 = FSub(margin_, V3Dot(p, n1)); + const FloatV d2 = FSub(margin_, V3Dot(p, n2)); + const FloatV d3 = FSub(margin_, V3Dot(p, n3)); + + //This is unavoidable unless we pre-calc the core shape + const Vec3V intersectPoints = intersectPlanes(n1, d1, n2, d2, n3, d3); + const Vec3V v =V3Sub(p, intersectPoints); + (*marginDif) = V3Length(v); + return intersectPoints; + } + + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir) const + { + PxI32 index; + Ps::aos::FloatV marginDif; + return supportLocal(dir, index, &marginDif); + } + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, const Ps::aos::PsMatTransformV& aTobT) const + { + PxI32 index; + Ps::aos::FloatV marginDif; + return supportRelative(dir, aTob, aTobT, index, &marginDif); + } + + //This function is used in gjk penetration + //dir in the shape space + PX_SUPPORT_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* marginDif) const + { + using namespace Ps::aos; + //get the extreme point index + const PxU32 maxIndex = supportVertexIndex(dir); + index = PxI32(maxIndex); + //p is in the shape space + return planeShift(maxIndex, getMargin(), marginDif); + } + + PX_SUPPORT_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aTob, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif) const + { + using namespace Ps::aos; + + //transform dir from b space to the shape space of a space +// const Vec3V dir_ = aTob.rotateInv(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V dir_ = aTobT.rotate(dir);//relTra.rotateInv(dir);//M33MulV3(skewInvRot, dir); + const Vec3V p = supportLocal(dir_, index, marginDif); + //transfrom from a to b space + return aTob.transform(p); + } + }; + + #define PX_SCONVEX_TO_NOSCALECONVEX(x) (static_cast<ShrunkConvexHullNoScaleV*>(x)) +} + +} + +#endif // diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecSphere.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecSphere.h new file mode 100644 index 00000000..fdb850ff --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecSphere.h @@ -0,0 +1,243 @@ +// 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_VEC_SPHERE_H +#define GU_VEC_SPHERE_H +/** \addtogroup geomutils +@{ +*/ + +#include "GuVecConvex.h" +#include "GuConvexSupportTable.h" +#include "PxSphereGeometry.h" + +/** +\brief Represents a sphere defined by its center point and radius. +*/ +namespace physx +{ +namespace Gu +{ + class SphereV : public ConvexV + { + public: + /** + \brief Constructor + */ + PX_INLINE SphereV(): ConvexV(ConvexType::eSPHERE) + { + radius = Ps::aos::FZero(); + bMarginIsRadius = true; + } + + PX_INLINE SphereV(const Ps::aos::Vec3VArg _center, const Ps::aos::FloatV _radius) : ConvexV(ConvexType::eSPHERE, _center) + { + using namespace Ps::aos; + radius = _radius; + FStore(radius, &margin); + FStore(radius, &minMargin); + FStore(radius, &sweepMargin); + bMarginIsRadius = true; + } + + + /** + \brief Copy constructor + */ + PX_INLINE SphereV(const SphereV& sphere) : ConvexV(ConvexType::eSPHERE), radius(sphere.radius) + { + + margin = sphere.margin; + minMargin = sphere.minMargin; + sweepMargin = sphere.sweepMargin; + bMarginIsRadius = true; + } + + PX_INLINE SphereV(const PxGeometry& geom) : ConvexV(ConvexType::eSPHERE, Ps::aos::V3Zero()) + { + using namespace Ps::aos; + const PxSphereGeometry& sphereGeom = static_cast<const PxSphereGeometry&>(geom); + const FloatV r = FLoad(sphereGeom.radius); + radius = r; + margin = sphereGeom.radius; + minMargin = sphereGeom.radius; + sweepMargin = sphereGeom.radius; + bMarginIsRadius = true; + } + + /** + \brief Destructor + */ + PX_INLINE ~SphereV() + { + } + + PX_INLINE void setV(const Ps::aos::Vec3VArg _center, const Ps::aos::FloatVArg _radius) + { + center = _center; + radius = _radius; + } + + /** + \brief Checks the sphere is valid. + + \return true if the sphere is valid + */ + PX_INLINE bool isValid() const + { + // Consistency condition for spheres: Radius >= 0.0f + using namespace Ps::aos; + return BAllEqTTTT(FIsGrtrOrEq(radius, FZero())) != 0; + } + + /** + \brief Tests if a point is contained within the sphere. + + \param[in] p the point to test + \return true if inside the sphere + */ + PX_INLINE bool contains(const Ps::aos::Vec3VArg p) const + { + using namespace Ps::aos; + const FloatV rr = FMul(radius, radius); + const FloatV cc = V3LengthSq(V3Sub(center, p)); + return FAllGrtrOrEq(rr, cc) != 0; + } + + /** + \brief Tests if a sphere is contained within the sphere. + + \param sphere [in] the sphere to test + \return true if inside the sphere + */ + PX_INLINE bool contains(const SphereV& sphere) const + { + using namespace Ps::aos; + + const Vec3V centerDif= V3Sub(center, sphere.center); + const FloatV radiusDif = FSub(radius, sphere.radius); + const FloatV cc = V3Dot(centerDif, centerDif); + const FloatV rr = FMul(radiusDif, radiusDif); + + const BoolV con0 = FIsGrtrOrEq(radiusDif, FZero());//might contain + const BoolV con1 = FIsGrtr(rr, cc);//return true + return BAllEqTTTT(BAnd(con0, con1))==1; + } + + /** + \brief Tests if a box is contained within the sphere. + + \param minimum [in] minimum value of the box + \param maximum [in] maximum value of the box + \return true if inside the sphere + */ + PX_INLINE bool contains(const Ps::aos::Vec3VArg minimum, const Ps::aos::Vec3VArg maximum) const + { + + //compute the sphere which wrap around the box + using namespace Ps::aos; + const FloatV zero = FZero(); + const FloatV half = FHalf(); + + const Vec3V boxSphereCenter = V3Scale(V3Add(maximum, minimum), half); + const Vec3V v = V3Scale(V3Sub(maximum, minimum), half); + const FloatV boxSphereR = V3Length(v); + + const Vec3V w = V3Sub(center, boxSphereCenter); + const FloatV wLength = V3Length(w); + const FloatV dif = FSub(FSub(radius, wLength), boxSphereR); + + return FAllGrtrOrEq(dif, zero) != 0; + } + + /** + \brief Tests if the sphere intersects another sphere + + \param sphere [in] the other sphere + \return true if spheres overlap + */ + PX_INLINE bool intersect(const SphereV& sphere) const + { + using namespace Ps::aos; + const Vec3V centerDif = V3Sub(center, sphere.center); + const FloatV cc = V3Dot(centerDif, centerDif); + const FloatV r = FAdd(radius, sphere.radius); + const FloatV rr = FMul(r, r); + return FAllGrtrOrEq(rr, cc) != 0; + } + + //return point in local space + PX_FORCE_INLINE Ps::aos::Vec3V getPoint(const PxU8) + { + return Ps::aos::V3Zero(); + } + // + //sweep code need to have full version + PX_FORCE_INLINE Ps::aos::Vec3V supportSweep(const Ps::aos::Vec3VArg dir)const + { + using namespace Ps::aos; + const Vec3V _dir = V3Normalize(dir); + return V3ScaleAdd(_dir, radius, center); + } + + //make the support function the same as support margin + PX_FORCE_INLINE Ps::aos::Vec3V support(const Ps::aos::Vec3VArg)const + { + return center;//_margin is the same as radius + } + + + PX_FORCE_INLINE Ps::aos::Vec3V supportMargin(const Ps::aos::Vec3VArg dir, const Ps::aos::FloatVArg _margin, Ps::aos::Vec3V& support)const + { + PX_UNUSED(_margin); + PX_UNUSED(dir); + + support = center; + return center;//_margin is the same as radius + } + + PX_FORCE_INLINE Ps::aos::BoolV isMarginEqRadius()const + { + return Ps::aos::BTTTT(); + } + + PX_FORCE_INLINE Ps::aos::FloatV getSweepMargin() const + { + return Ps::aos::FZero(); + } + + + Ps::aos::FloatV radius; //!< Sphere's center, w component is radius + + }; +} + +} + +#endif diff --git a/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecTriangle.h b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecTriangle.h new file mode 100644 index 00000000..004cc560 --- /dev/null +++ b/PhysX_3.4/Source/GeomUtils/src/gjk/GuVecTriangle.h @@ -0,0 +1,268 @@ +// 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_VEC_TRIANGLE_H +#define GU_VEC_TRIANGLE_H +/** \addtogroup geomutils + @{ +*/ + +#include "GuVecConvex.h" +#include "GuConvexSupportTable.h" +#include "GuDistancePointTriangleSIMD.h" + +namespace physx +{ +namespace Gu +{ + + + class TriangleV : public ConvexV + { + public: + /** + \brief Constructor + */ + PX_FORCE_INLINE TriangleV() : ConvexV(ConvexType::eTRIANGLE) + { + margin = 0.02f; + minMargin = PX_MAX_REAL; + sweepMargin = PX_MAX_REAL; + } + /** + \brief Constructor + + \param[in] p0 Point 0 + \param[in] p1 Point 1 + \param[in] p2 Point 2 + */ + + PX_FORCE_INLINE TriangleV(const Ps::aos::Vec3VArg p0, const Ps::aos::Vec3VArg p1, const Ps::aos::Vec3VArg p2): ConvexV(ConvexType::eTRIANGLE) + { + using namespace Ps::aos; + //const FloatV zero = FZero(); + const FloatV num = FLoad(0.333333f); + center = V3Scale(V3Add(V3Add(p0, p1), p2), num); + verts[0] = p0; + verts[1] = p1; + verts[2] = p2; + margin = 0.f; + minMargin = PX_MAX_REAL; + sweepMargin = PX_MAX_REAL; + } + + PX_FORCE_INLINE TriangleV(const PxVec3* pts) : ConvexV(ConvexType::eTRIANGLE) + { + using namespace Ps::aos; + const Vec3V p0 = V3LoadU(pts[0]); + const Vec3V p1 = V3LoadU(pts[1]); + const Vec3V p2 = V3LoadU(pts[2]); + const FloatV num = FLoad(0.333333f); + center = V3Scale(V3Add(V3Add(p0, p1), p2), num); + verts[0] = p0; + verts[1] = p1; + verts[2] = p2; + margin = 0.f; + minMargin = PX_MAX_REAL; + sweepMargin = PX_MAX_REAL; + } + + /** + \brief Copy constructor + + \param[in] triangle Tri to copy + */ + PX_FORCE_INLINE TriangleV(const Gu::TriangleV& triangle) : ConvexV(ConvexType::eTRIANGLE) + { + using namespace Ps::aos; + verts[0] = triangle.verts[0]; + verts[1] = triangle.verts[1]; + verts[2] = triangle.verts[2]; + + center = triangle.center; + margin = 0.f; + minMargin = PX_MAX_REAL; + sweepMargin = PX_MAX_REAL; + } + /** + \brief Destructor + */ + PX_FORCE_INLINE ~TriangleV() + { + } + + PX_FORCE_INLINE void populateVerts(const PxU8* inds, PxU32 numInds, const PxVec3* originalVerts, Ps::aos::Vec3V* vertexs)const + { + using namespace Ps::aos; + + for(PxU32 i=0; i<numInds; ++i) + { + vertexs[i] = V3LoadU(originalVerts[inds[i]]); + } + } + + PX_FORCE_INLINE Ps::aos::FloatV getSweepMargin() const + { + return Ps::aos::FMax(); + } + + PX_FORCE_INLINE void setCenter(const Ps::aos::Vec3VArg _center) + { + using namespace Ps::aos; + Vec3V offset = V3Sub(_center, center); + center = _center; + verts[0] = V3Add(verts[0], offset); + verts[1] = V3Add(verts[1], offset); + verts[2] = V3Add(verts[2], offset); + } + + /** + \brief Compute the normal of the Triangle. + + \return Triangle normal. + */ + PX_FORCE_INLINE Ps::aos::Vec3V normal() const + { + using namespace Ps::aos; + const Vec3V ab = V3Sub(verts[1], verts[0]); + const Vec3V ac = V3Sub(verts[2], verts[0]); + const Vec3V n = V3Cross(ab, ac); + return V3Normalize(n); + } + + /** + \brief Compute the unnormalized normal of the Triangle. + + \param[out] _normal Triangle normal (not normalized). + */ + PX_FORCE_INLINE void denormalizedNormal(Ps::aos::Vec3V& _normal) const + { + using namespace Ps::aos; + const Vec3V ab = V3Sub(verts[1], verts[0]); + const Vec3V ac = V3Sub(verts[2], verts[0]); + _normal = V3Cross(ab, ac); + } + + PX_FORCE_INLINE Ps::aos::FloatV area() const + { + using namespace Ps::aos; + const FloatV half = FLoad(0.5f); + const Vec3V ba = V3Sub(verts[0], verts[1]); + const Vec3V ca = V3Sub(verts[0], verts[2]); + const Vec3V v = V3Cross(ba, ca); + return FMul(V3Length(v), half); + } + + //dir is in local space, verts in the local space + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir) const + { + using namespace Ps::aos; + const Vec3V v0 = verts[0]; + const Vec3V v1 = verts[1]; + const Vec3V v2 = verts[2]; + const FloatV d0 = V3Dot(v0, dir); + const FloatV d1 = V3Dot(v1, dir); + const FloatV d2 = V3Dot(v2, dir); + + const BoolV con0 = BAnd(FIsGrtr(d0, d1), FIsGrtr(d0, d2)); + const BoolV con1 = FIsGrtr(d1, d2); + return V3Sel(con0, v0, V3Sel(con1, v1, v2)); + } + + PX_FORCE_INLINE void supportLocal(const Ps::aos::Vec3VArg dir, Ps::aos::FloatV& min, Ps::aos::FloatV& max) const + { + using namespace Ps::aos; + const Vec3V v0 = verts[0]; + const Vec3V v1 = verts[1]; + const Vec3V v2 = verts[2]; + FloatV d0 = V3Dot(v0, dir); + FloatV d1 = V3Dot(v1, dir); + FloatV d2 = V3Dot(v2, dir); + + max = FMax(d0, FMax(d1, d2)); + min = FMin(d0, FMin(d1, d2)); + } + + //dir is in b space + PX_FORCE_INLINE Ps::aos::Vec3V supportRelative(const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aToB, const Ps::aos::PsMatTransformV& aTobT) const + { + using namespace Ps::aos; + //verts are in local space +// const Vec3V _dir = aToB.rotateInv(dir); //transform dir back to a space + const Vec3V _dir = aTobT.rotate(dir); //transform dir back to a space + const Vec3V maxPoint = supportLocal(_dir); + return aToB.transform(maxPoint);//transform maxPoint to the b space + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportLocal(const Ps::aos::Vec3VArg dir, PxI32& index, Ps::aos::FloatV* /*marginDif*/) const + { + + using namespace Ps::aos; + const VecI32V vZero = VecI32V_Zero(); + const VecI32V vOne = VecI32V_One(); + const VecI32V vTwo = VecI32V_Two(); + const Vec3V v0 = verts[0]; + const Vec3V v1 = verts[1]; + const Vec3V v2 = verts[2]; + const FloatV d0 = V3Dot(v0, dir); + const FloatV d1 = V3Dot(v1, dir); + const FloatV d2 = V3Dot(v2, dir); + const BoolV con0 = BAnd(FIsGrtr(d0, d1), FIsGrtr(d0, d2)); + const BoolV con1 = FIsGrtr(d1, d2); + const VecI32V vIndex = VecI32V_Sel(con0, vZero, VecI32V_Sel(con1, vOne, vTwo)); + PxI32_From_VecI32V(vIndex, &index); + return V3Sel(con0, v0, V3Sel(con1, v1, v2)); + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportRelative( const Ps::aos::Vec3VArg dir, const Ps::aos::PsMatTransformV& aToB, + const Ps::aos::PsMatTransformV& aTobT, PxI32& index, Ps::aos::FloatV* marginDif)const + { + //don't put margin in the triangle + using namespace Ps::aos; + //transfer dir into the local space of triangle +// const Vec3V _dir = aToB.rotateInv(dir); + const Vec3V _dir = aTobT.rotate(dir); + return aToB.transform(supportLocal(_dir, index, marginDif));//transform the support poin to b space + } + + PX_FORCE_INLINE Ps::aos::Vec3V supportPoint(const PxI32 index, Ps::aos::FloatV* /*marginDif*/)const + { + return verts[index]; + } + + /** + \brief Array of Vertices. + */ + Ps::aos::Vec3V verts[3]; + }; +} + +} + +#endif |