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
#include "geomutils/PxContactBuffer.h"
#include "GuIntersectionRayBox.h"
#include "GuDistanceSegmentBox.h"
#include "GuInternal.h"
#include "GuContactMethodImpl.h"
#include "GuBoxConversion.h"
#include "foundation/PxUtilities.h"
using namespace physx;
using namespace Gu;
/*namespace Gu
{
const PxU8* getBoxEdges();
}*/
/////////
/*#include "common/PxRenderOutput.h"
#include "PxsContext.h"
static void gVisualizeBox(const Box& box, PxcNpThreadContext& context, PxU32 color=0xffffff)
{
PxMat33 rot(box.base.column0, box.base.column1, box.base.column2);
PxMat44 m(rot, box.origin);
DebugBox db(box.extent);
PxRenderOutput& out = context.mRenderOutput;
out << color << m;
out << db;
}
static void gVisualizeLine(const PxVec3& a, const PxVec3& b, PxcNpThreadContext& context, PxU32 color=0xffffff)
{
PxMat44 m = PxMat44::identity();
RenderOutput& out = context.mRenderOutput;
out << color << m << RenderOutput::LINES << a << b;
}*/
/////////
static const PxReal fatBoxEdgeCoeff = 0.01f;
static bool intersectEdgeEdgePreca(const PxVec3& p1, const PxVec3& p2, const PxVec3& v1, const PxPlane& plane, PxU32 i, PxU32 j, float coeff, const PxVec3& dir, const PxVec3& p3, const PxVec3& p4, PxReal& dist, PxVec3& ip)
{
// if colliding edge (p3,p4) does not cross plane return no collision
// same as if p3 and p4 on same side of plane return 0
//
// Derivation:
// d3 = d(p3, P) = (p3 | plane.n) - plane.d; Reversed sign compared to Plane::Distance() because plane.d is negated.
// d4 = d(p4, P) = (p4 | plane.n) - plane.d; Reversed sign compared to Plane::Distance() because plane.d is negated.
// if d3 and d4 have the same sign, they're on the same side of the plane => no collision
// We test both sides at the same time by only testing Sign(d3 * d4).
// ### put that in the Plane class
// ### also check that code in the triangle class that might be similar
const PxReal d3 = plane.distance(p3);
PxReal temp = d3 * plane.distance(p4);
if(temp>0.0f) return false;
// if colliding edge (p3,p4) and plane are parallel return no collision
PxVec3 v2 = p4 - p3;
temp = plane.n.dot(v2);
if(temp==0.0f) return false; // ### epsilon would be better
// compute intersection point of plane and colliding edge (p3,p4)
ip = p3-v2*(d3/temp);
// compute distance of intersection from line (ip, -dir) to line (p1,p2)
dist = (v1[i]*(ip[j]-p1[j])-v1[j]*(ip[i]-p1[i]))*coeff;
if(dist<0.0f) return false;
// compute intersection point on edge (p1,p2) line
ip -= dist*dir;
// check if intersection point (ip) is between edge (p1,p2) vertices
temp = (p1.x-ip.x)*(p2.x-ip.x)+(p1.y-ip.y)*(p2.y-ip.y)+(p1.z-ip.z)*(p2.z-ip.z);
if(temp<0.0f) return true; // collision found
return false; // no collision
}
static bool GuTestAxis(const PxVec3& axis, const Segment& segment, PxReal radius, const Box& box, PxReal& depth)
{
// Project capsule
PxReal min0 = segment.p0.dot(axis);
PxReal max0 = segment.p1.dot(axis);
if(min0>max0) PxSwap(min0, max0);
min0 -= radius;
max0 += radius;
// Project box
PxReal Min1, Max1;
{
const PxReal BoxCen = box.center.dot(axis);
const PxReal BoxExt =
PxAbs(box.rot.column0.dot(axis)) * box.extents.x
+ PxAbs(box.rot.column1.dot(axis)) * box.extents.y
+ PxAbs(box.rot.column2.dot(axis)) * box.extents.z;
Min1 = BoxCen - BoxExt;
Max1 = BoxCen + BoxExt;
}
// Test projections
if(max0<Min1 || Max1<min0)
return false;
const PxReal d0 = max0 - Min1;
PX_ASSERT(d0>=0.0f);
const PxReal d1 = Max1 - min0;
PX_ASSERT(d1>=0.0f);
depth = physx::intrinsics::selectMin(d0, d1);
return true;
}
static bool GuCapsuleOBBOverlap3(const Segment& segment, PxReal radius, const Box& box, PxReal* t=NULL, PxVec3* pp=NULL)
{
PxVec3 Sep(PxReal(0));
PxReal PenDepth = PX_MAX_REAL;
// Test normals
for(PxU32 i=0;i<3;i++)
{
PxReal d;
if(!GuTestAxis(box.rot[i], segment, radius, box, d))
return false;
if(d<PenDepth)
{
PenDepth = d;
Sep = box.rot[i];
}
}
// Test edges
PxVec3 CapsuleAxis(segment.p1 - segment.p0);
CapsuleAxis = CapsuleAxis.getNormalized();
for(PxU32 i=0;i<3;i++)
{
PxVec3 Cross = CapsuleAxis.cross(box.rot[i]);
if(!isAlmostZero(Cross))
{
Cross = Cross.getNormalized();
PxReal d;
if(!GuTestAxis(Cross, segment, radius, box, d))
return false;
if(d<PenDepth)
{
PenDepth = d;
Sep = Cross;
}
}
}
const PxVec3 Witness = segment.computeCenter() - box.center;
if(Sep.dot(Witness) < 0.0f)
Sep = -Sep;
if(t)
*t = PenDepth;
if(pp)
*pp = Sep;
return true;
}
static void GuGenerateVFContacts( PxContactBuffer& contactBuffer,
//
const Segment& segment,
PxReal radius,
//
const Box& worldBox,
//
const PxVec3& normal,
PxReal contactDistance)
{
const PxVec3 Max = worldBox.extents;
const PxVec3 Min = -worldBox.extents;
const PxVec3 tmp2 = - worldBox.rot.transformTranspose(normal);
const PxVec3* PX_RESTRICT Ptr = &segment.p0;
for(PxU32 i=0;i<2;i++)
{
const PxVec3& Pos = Ptr[i];
const PxVec3 tmp = worldBox.rot.transformTranspose(Pos - worldBox.center);
PxReal tnear, tfar;
int Res = intersectRayAABB(Min, Max, tmp, tmp2, tnear, tfar);
if(Res!=-1 && tnear < radius + contactDistance)
{
contactBuffer.contact(Pos - tnear * normal, normal, tnear - radius);
}
}
}
// PT: this looks similar to PxcGenerateEEContacts2 but it is mandatory to properly handle thin capsules.
static void GuGenerateEEContacts( PxContactBuffer& contactBuffer,
//
const Segment& segment,
const PxReal radius,
//
const Box& worldBox,
//
const PxVec3& normal)
{
const PxU8* PX_RESTRICT Indices = getBoxEdges();
PxVec3 Pts[8];
worldBox.computeBoxPoints(Pts);
PxVec3 s0 = segment.p0;
PxVec3 s1 = segment.p1;
makeFatEdge(s0, s1, fatBoxEdgeCoeff);
// PT: precomputed part of edge-edge intersection test
// const PxVec3 v1 = segment.p1 - segment.p0;
const PxVec3 v1 = s1 - s0;
PxPlane plane;
plane.n = v1.cross(normal);
// plane.d = -(plane.normal|segment.p0);
plane.d = -(plane.n.dot(s0));
PxU32 ii,jj;
closestAxis(plane.n, ii, jj);
const float coeff = 1.0f /(v1[ii]*normal[jj]-v1[jj]*normal[ii]);
for(PxU32 i=0;i<12;i++)
{
// PxVec3 p1 = Pts[*Indices++];
// PxVec3 p2 = Pts[*Indices++];
// makeFatEdge(p1, p2, fatBoxEdgeCoeff); // PT: TODO: make fat segment instead
const PxVec3& p1 = Pts[*Indices++];
const PxVec3& p2 = Pts[*Indices++];
// PT: keep original code in case something goes wrong
// PxReal dist;
// PxVec3 ip;
// if(intersectEdgeEdge(p1, p2, -normal, segment.p0, segment.p1, dist, ip))
// contactBuffer.contact(ip, normal, - (radius + dist));
PxReal dist;
PxVec3 ip;
if(intersectEdgeEdgePreca(s0, s1, v1, plane, ii, jj, coeff, normal, p1, p2, dist, ip))
// if(intersectEdgeEdgePreca(segment.p0, segment.p1, v1, plane, ii, jj, coeff, normal, p1, p2, dist, ip))
{
contactBuffer.contact(ip-normal*dist, normal, - (radius + dist));
// if(contactBuffer.count==2) // PT: we only need 2 contacts to be stable
// return;
}
}
}
static void GuGenerateEEContacts2( PxContactBuffer& contactBuffer,
//
const Segment& segment,
PxReal radius,
//
const Box& worldBox,
//
const PxVec3& normal,
PxReal contactDistance)
{
const PxU8* PX_RESTRICT Indices = getBoxEdges();
PxVec3 Pts[8];
worldBox.computeBoxPoints(Pts);
PxVec3 s0 = segment.p0;
PxVec3 s1 = segment.p1;
makeFatEdge(s0, s1, fatBoxEdgeCoeff);
// PT: precomputed part of edge-edge intersection test
// const PxVec3 v1 = segment.p1 - segment.p0;
const PxVec3 v1 = s1 - s0;
PxPlane plane;
plane.n = -(v1.cross(normal));
// plane.d = -(plane.normal|segment.p0);
plane.d = -(plane.n.dot(s0));
PxU32 ii,jj;
closestAxis(plane.n, ii, jj);
const float coeff = 1.0f /(v1[jj]*normal[ii]-v1[ii]*normal[jj]);
for(PxU32 i=0;i<12;i++)
{
// PxVec3 p1 = Pts[*Indices++];
// PxVec3 p2 = Pts[*Indices++];
// makeFatEdge(p1, p2, fatBoxEdgeCoeff); // PT: TODO: make fat segment instead
const PxVec3& p1 = Pts[*Indices++];
const PxVec3& p2 = Pts[*Indices++];
// PT: keep original code in case something goes wrong
// PxReal dist;
// PxVec3 ip;
// bool contact = intersectEdgeEdge(p1, p2, normal, segment.p0, segment.p1, dist, ip);
// if(contact && dist < radius + contactDistance)
// contactBuffer.contact(ip, normal, dist - radius);
PxReal dist;
PxVec3 ip;
// bool contact = intersectEdgeEdgePreca(segment.p0, segment.p1, v1, plane, ii, jj, coeff, -normal, p1, p2, dist, ip);
bool contact = intersectEdgeEdgePreca(s0, s1, v1, plane, ii, jj, coeff, -normal, p1, p2, dist, ip);
if(contact && dist < radius + contactDistance)
{
contactBuffer.contact(ip-normal*dist, normal, dist - radius);
// if(contactBuffer.count==2) // PT: we only need 2 contacts to be stable
// return;
}
}
}
bool Gu::contactCapsuleBox(GU_CONTACT_METHOD_ARGS)
{
PX_UNUSED(renderOutput);
PX_UNUSED(cache);
// Get actual shape data
const PxCapsuleGeometry& shapeCapsule = checkedCast<PxCapsuleGeometry>(shape0);
const PxBoxGeometry& shapeBox = checkedCast<PxBoxGeometry>(shape1);
// PT: TODO: move computations to local space
// Capsule data
Segment worldSegment;
getCapsuleSegment(transform0, shapeCapsule, worldSegment);
const PxReal inflatedRadius = shapeCapsule.radius + params.mContactDistance;
// Box data
Box worldBox;
buildFrom(worldBox, transform1.p, shapeBox.halfExtents, transform1.q);
// Collision detection
PxReal t;
PxVec3 onBox;
const PxReal squareDist = distanceSegmentBoxSquared(worldSegment.p0, worldSegment.p1, worldBox.center, worldBox.extents, worldBox.rot, &t, &onBox);
if(squareDist >= inflatedRadius*inflatedRadius)
return false;
PX_ASSERT(contactBuffer.count==0);
if(squareDist != 0.0f)
{
// PT: the capsule segment doesn't intersect the box => distance-based version
const PxVec3 onSegment = worldSegment.getPointAt(t);
onBox = worldBox.center + worldBox.rot.transform(onBox);
PxVec3 normal = onSegment - onBox;
PxReal normalLen = normal.magnitude();
if(normalLen > 0.0f)
{
normal *= 1.0f/normalLen;
// PT: generate VF contacts for segment's vertices vs box
GuGenerateVFContacts(contactBuffer, worldSegment, shapeCapsule.radius, worldBox, normal, params.mContactDistance);
// PT: early exit if we already have 2 stable contacts
if(contactBuffer.count==2)
return true;
// PT: else generate slower EE contacts
GuGenerateEEContacts2(contactBuffer, worldSegment, shapeCapsule.radius, worldBox, normal, params.mContactDistance);
// PT: run VF case for box-vertex-vs-capsule only if we don't have any contact yet
if(!contactBuffer.count)
contactBuffer.contact(onBox, normal, sqrtf(squareDist) - shapeCapsule.radius);
}
else
{
// On linux we encountered the following:
// For a case where a segment endpoint lies on the surface of a box, the squared distance between segment and box was tiny but still larger than 0.
// However, the computation of the normal length was exactly 0. In that case we should have switched to the penetration based version so we do it now
// instead.
goto PenetrationBasedCode;
}
}
else
{
PenetrationBasedCode:
// PT: the capsule segment intersects the box => penetration-based version
// PT: compute penetration vector (MTD)
PxVec3 sepAxis;
PxReal depth;
if(!GuCapsuleOBBOverlap3(worldSegment, shapeCapsule.radius, worldBox, &depth, &sepAxis)) return false;
// PT: generate VF contacts for segment's vertices vs box
GuGenerateVFContacts(contactBuffer, worldSegment, shapeCapsule.radius, worldBox, sepAxis, params.mContactDistance);
// PT: early exit if we already have 2 stable contacts
if(contactBuffer.count==2)
return true;
// PT: else generate slower EE contacts
GuGenerateEEContacts(contactBuffer, worldSegment, shapeCapsule.radius, worldBox, sepAxis);
if(!contactBuffer.count)
{
contactBuffer.contact(worldSegment.computeCenter(), sepAxis, -(shapeCapsule.radius + depth));
return true;
}
}
return true;
}