A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
#ifndef GU_MESH_MESH_COLLISION_H
#define GU_MESH_MESH_COLLISION_H
#include "foundation/PxAssert.h"
#include "foundation/PxMath.h"
#include "foundation/PxPreprocessor.h"
#include "foundation/PxSimpleTypes.h"
#include "foundation/PxVec3.h"
#include "GuCollisionSDF.h"
#include "GuDistancePointTriangle.h"
#include "GuTriangle.h"
namespace physx
{
namespace Gu
{
template <typename T>
int argmin(const T& v0, const T& v1)
{
if (v0 < v1)
return 0;
return 1;
}
template <typename T>
int argmin(const T& v0, const T& v1, const T& v2, const T& v3)
{
const int ma = argmin(v0, v1), mb = argmin(v2, v3);
if (!argmin((!ma ? v0 : v1),(!mb ? v2: v3)))
return ma;
return mb+2;
}
// Based on one SDF evaluation at the centroid, can the circumsphere of the triangle
// `v0`, `v1`, `v2` get closer to the surface given by `sdf` than `cutoffDistance`?
static PX_INLINE bool sdfTriangleSphericalCull(
const CollisionSDF& PX_RESTRICT sdf,
const PxVec3& PX_RESTRICT v0, const PxVec3& PX_RESTRICT v1, const PxVec3& PX_RESTRICT v2,
PxReal cutoffDistance)
{
const PxReal third = 1.0f / 3.0f;
const PxVec3 centroid = (v0 + v1 + v2) * third;
const PxReal sphereRadiusSq = PxMax(
(v0 - centroid).magnitudeSquared(),
PxMax((v1 - centroid).magnitudeSquared(), (v2 - centroid).magnitudeSquared()));
const PxVec3 boxPos = sdf.clampToBox(centroid);
const PxReal centroidToBoxSq = (centroid - boxPos).magnitudeSquared();
// TODO(CA): consider minimum of SDF on box boundary, making this check tighter
if (PxSqrt(centroidToBoxSq) > PxSqrt(sphereRadiusSq) + cutoffDistance)
return false; //Early out without touching SDF data
const PxReal centroidSdf = sdf.dist(centroid);
return centroidSdf < PxSqrt(sphereRadiusSq) + cutoffDistance;
}
// Find maximum separation of an sdf and a triangle and find the contact point and normal separation is below `cutoffDistance`
// Return the separation, or`PX\_MAX\_F32` if it exceeds `cutoffDistance`
template <PxU32 TMaxLineSearchIters = 0, PxU32 TMaxPGDIterations = 32, bool TFastGrad = true>
PX_INLINE PxReal sdfTriangleCollision(
const CollisionSDF& PX_RESTRICT sdf,
const PxVec3& PX_RESTRICT v0, const PxVec3& PX_RESTRICT v1, const PxVec3& PX_RESTRICT v2,
PxVec3& point, PxVec3& dir, PxReal cutoffDistance)
{
const PxReal third = 1.0f / 3.0f;
const PxVec3 centroid = (v0 + v1 + v2) * third;
// barycentric coordinates, corresponding to v0, v1, v2
PxVec3 c(0.f);
// choose starting iterate
const int start = argmin(sdf.dist(v0), sdf.dist(v1), sdf.dist(v2), sdf.dist(centroid));
switch (start)
{
case 0:
c.x = 1.f; break;
case 1:
c.y = 1.f; break;
case 2:
c.z = 1.f; break;
case 3:
c = PxVec3(third); break;
default:
PX_ASSERT(false);
}
PxReal stepSize = 0.25;
// we could also compute the gradient's lipschitz constant when baking!
PxVec3 dfdp; // gradient w.r.t. p
const PxReal toleranceSq = 1e-10f;
for (PxU32 i = 0; i < TMaxPGDIterations; ++i)
{
const PxVec3 p = c.x * v0 + c.y * v1 + c.z * v2;
PxReal dist_old = 0;
if (TFastGrad)
dist_old = sdf.dist(p, &dfdp);
else
dfdp = sdf.grad(p);
const PxReal dfdpMagSq = dfdp.magnitudeSquared();
if (dfdpMagSq == 0.0f)
{
// TODO(CA): consider expanding this into a stopping criterion
// At a critical point. Take a small step away into an arbitrary direction
dfdp = PxVec3(0.5718465865353257f, 0.7055450997557186f, 0.41856611625714474f);
}
else
dfdp *= PxRecipSqrt(dfdpMagSq);
// Simple projected gradient descent
const PxVec3 dfdc = PxVec3(dfdp.dot(v0-p), dfdp.dot(v1-p), dfdp.dot(v2-p));
const PxVec3 c_old = c;
if (TMaxLineSearchIters) //Line Search is quite expensive since it increases the number of expensive calls to sdf.dist by approximately a factor of MAX_LINE_SEARCH_ITERATIONS
{
PxReal s = 1;
if (!TFastGrad)
dist_old = sdf.dist(p);
c = closestPtPointBaryTriangle(c_old - s * dfdc);
for (PxU32 ls_it = 0; ls_it < TMaxLineSearchIters; ++ls_it)
{
// restore barycentric coordinates
const PxVec3 p_new = c.x * v0 + c.y * v1 + c.z * v2;
if (sdf.dist(p_new) <= dist_old)
{
#if 0
if (ls_it > 0)
printf("%d: %d ls iterations\n", i, ls_it+1);
#endif
break;
}
s *= 0.5f;
c = closestPtPointBaryTriangle(c_old - s * dfdc);
}
}
else
{
// take step and restore barycentric coordinates
c = closestPtPointBaryTriangle(c - stepSize * dfdc);
}
// this detects a minimum found on the boundary
if ((c - c_old).magnitudeSquared() < toleranceSq)
break;
stepSize *= 0.8f; // line search will get rid of this
}
const PxVec3 p = c.x * v0 + c.y * v1 + c.z * v2;
point = p;
return sdf.distUsingGradient(p, dir, cutoffDistance);
}
// Get the indices of the triangle at position `triIdx`.
// `T` should be `PxU16` if the mesh has 16 bit indices, and `PxU32` otherwise
template <typename T>
PX_INLINE Gu::IndexedTriangle32 getTriangleVertexIndices(const void* triangles, PxU32 triIdx)
{
const T* trisCast = reinterpret_cast<const T*>(triangles);
return {trisCast[triIdx*3], trisCast[triIdx*3+1], trisCast[triIdx*3+2]};
}
} // namespace Gu
} // namespace physx
#endif