Revision control
- // Redistribution and use in source and binary forms, with or without
- // modification, are permitted provided that the following conditions
- // are met:
- // * Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimer.
- // * Redistributions in binary form must reproduce the above copyright
- // notice, this list of conditions and the following disclaimer in the
- // documentation and/or other materials provided with the distribution.
- // * Neither the name of NVIDIA CORPORATION nor the names of its
- // contributors may be used to endorse or promote products derived
- // from this software without specific prior written permission.
- //
- // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
- // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
- // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- // OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- //
- // Copyright (c) 2008-2026 NVIDIA Corporation. All rights reserved.
- // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// 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_COLLISION_SDF_H
#define GU_COLLISION_SDF_H
#include "GuSDF.h"
#include "foundation/PxPreprocessor.h"
namespace physx
{
namespace Gu
{
// SDF wrapper for collision computations
// may be shared by CPU/GPU code in the future
//
// \detailed CollisionSDF wraps an `SDF` object, providing useful methods for SDF collision.
//
// Conventions
// * The coarse or background SDF is always referred to as _coarse_. Its associated coordinates are called `cPos` and
// are in units of `mSpacing*mSubgridSize`. The origin is normally at the first grid point.
// * The fine SDF is always referred to as _fine_. Its associated coordinates are called `fPos` and are in units of
// `mSpacing`. If the sdf is dense, `cPos` is equivalent to `fPos`. The origin is normally at the first grid point.
// * Coordinates in the native space of the SDF are denoted `sPos` and are in native units.
template <int BytesPerSparsePixelT>
PX_FORCE_INLINE PxReal decodeSample(PxReal subgridScalingFactor, PxReal subgridMinSdfValue, const PxU8* data, PxU32 index);
template <>
PX_FORCE_INLINE PxReal decodeSample<1>(PxReal subgridScalingFactor, PxReal subgridMinSdfValue, const PxU8* data, PxU32 index)
{
return static_cast<PxReal>(data[index]) * subgridScalingFactor + subgridMinSdfValue;
}
template <>
PX_FORCE_INLINE PxReal decodeSample<2>(PxReal subgridScalingFactor, PxReal subgridMinSdfValue, const PxU8* data, PxU32 index)
{
const PxU16* ptr = reinterpret_cast<const PxU16*>(data);
return static_cast<PxReal>(ptr[index]) * subgridScalingFactor + subgridMinSdfValue;
}
template <>
PX_FORCE_INLINE PxReal decodeSample<4>(PxReal /*unused*/, PxReal /*unused*/, const PxU8* data, PxU32 index)
{
//If 4 bytes per subgrid pixel are available, then normal floats are used. No need to
//de-normalize integer values since the floats already contain real distance values
const PxReal* ptr = reinterpret_cast<const PxReal*>(data);
return ptr[index];
}
struct CollisionSDF
{
CollisionSDF(const SDF& sdf): mSdf(sdf), mSdfBoxLower(sdf.mMeshLower), mFDims(sdf.mDims), mInvGridDx(1.0f / sdf.mSpacing),
mInvSubgridSize(sdf.mSubgridSize ? 1.0f / sdf.mSubgridSize : 0), mIsDense(sdf.mSubgridSize == 0)
{
// assume that `mMeshLower` is also the location of the lowest grid point
if (mIsDense)
{
mCDims = mFDims;
mCSamples = mCDims;
mSdfBoxUpper = sdf.mMeshLower + sdf.mSpacing * PxVec3(static_cast<PxReal>(mFDims.x-1), static_cast<PxReal>(mFDims.y-1), static_cast<PxReal>(mFDims.z-1));
}
else
{
mCDims = Dim3(mFDims.x / sdf.mSubgridSize, mFDims.y / sdf.mSubgridSize, mFDims.z / sdf.mSubgridSize);
mCSamples = Dim3(mCDims.x + 1, mCDims.y + 1, mCDims.z + 1);
mSdfBoxUpper = sdf.mMeshLower + sdf.mSpacing * PxVec3(mFDims);
}
if (mSdf.mBytesPerSparsePixel == 1)
mSubgridScalingFactor = (1.0f / 255.0f) * (mSdf.mSubgridsMaxSdfValue - mSdf.mSubgridsMinSdfValue);
else if (mSdf.mBytesPerSparsePixel == 2)
mSubgridScalingFactor = (1.0f / 65535.0f) * (mSdf.mSubgridsMaxSdfValue - mSdf.mSubgridsMinSdfValue);
const PxU32 fW = mSdf.mSdfSubgrids3DTexBlockDim.x * (mSdf.mSubgridSize + 1),
fH = mSdf.mSdfSubgrids3DTexBlockDim.y * (mSdf.mSubgridSize + 1);
mFStrideY = fW;
mFStrideZ = fW*fH;
}
// clamp `fPos` to the grid on which `sdf` is defined
PX_INLINE PxVec3 clampToFine(const PxVec3& fPos) const
{
if (!mIsDense)
return fPos.maximum(PxVec3(0.0f)).minimum(PxVec3(mFDims));
return fPos.maximum(PxVec3(0.5f)).minimum(PxVec3(mFDims) + PxVec3(0.5f));
}
// clamp `sPos` to the grid on which `sdf` is defined
PX_INLINE PxVec3 clampToBox(const PxVec3& sPos) const
{
if (mIsDense)
return sPos.maximum(mSdfBoxLower+PxVec3(0.5f*mSdf.mSpacing)).minimum(mSdfBoxUpper+PxVec3(0.5f*mSdf.mSpacing));
return sPos.maximum(mSdfBoxLower).minimum(mSdfBoxUpper);
}
// Utility to convert from x/y/z indices to a linear index given the grid size (only width and height required)
PX_FORCE_INLINE PX_CUDA_CALLABLE static PxU32 idx3D(PxU32 x, PxU32 y, PxU32 z, PxU32 width, PxU32 height)
{
return z * width * height + y * width + x;
}
static PX_INLINE PxReal TriLerpWithGradient(
const PxReal f000,
const PxReal f100,
const PxReal f010,
const PxReal f110,
const PxReal f001,
const PxReal f101,
const PxReal f011,
const PxReal f111,
const PxReal tx,
const PxReal ty,
const PxReal tz,
PxVec3* grad = NULL)
{
if (grad)
{
const PxReal a = f100 - f000;
const PxReal b = f110 - f010;
const PxReal c = f101 - f001;
const PxReal d = f111 - f011;
grad->x = a + (b - (a)) * ty + (c + (d - (c)) * ty - (a + (b - (a)) * ty)) * tz;
grad->y = f010 + tx * (b) - (f000 + tx * (a)) + (f011 + tx * (d) - (f001 + tx * (c)) - (f010 + tx * (b) - (f000 + tx * (a)))) * tz;
grad->z = f001 + tx * (c) + ty * (f011 + tx * (d) - (f001 + tx * (c))) - (f000 + tx * (a) + ty * (f010 + tx * (b) - (f000 + tx * (a))));
}
return PxTriLerp(
f000,
f100,
f010,
f110,
f001,
f101,
f011,
f111,
tx,
ty,
tz);
}
template <int BytesPerSparsePixelT>
PX_INLINE PxReal interpolateSubgrid (const PxU8* subgridBase, PxU32 baseIdx, PxReal x, PxReal y, PxReal z, PxVec3* gradient = NULL) const
{
PX_COMPILE_TIME_ASSERT(
BytesPerSparsePixelT == 1 || BytesPerSparsePixelT == 2 || BytesPerSparsePixelT == 4);
return TriLerpWithGradient(
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+1 ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+mFStrideY ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+mFStrideY+1 ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+mFStrideZ ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+mFStrideZ+1 ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+mFStrideZ+mFStrideY ),
decodeSample<BytesPerSparsePixelT>(mSubgridScalingFactor, mSdf.mSubgridsMinSdfValue, subgridBase, baseIdx+mFStrideZ+mFStrideY+1),
x, y, z, gradient);
}
// interpolate the values of `array` at position `fPos`
// input vector `fPos` is in units of subgrid cells, with 0 corresponding to the subgrid origin
PX_INLINE PxReal evaluateSubgrid(const PxU32 subgridInfo, const PxVec3& fPos, PxVec3* gradient = NULL) const
{
const PxU32 sgSamples = mSdf.mSubgridSize + 1;
PX_ASSERT(fPos.x >= 0 && fPos.y >= 0 && fPos.z >= 0);
PX_ASSERT(fPos.x < sgSamples && fPos.y < sgSamples && fPos.z < sgSamples);
// find the subgrid offset in memory
PxU32 xSubgrid, ySubgrid, zSubgrid;
SDF::decodeTriple(subgridInfo, xSubgrid, ySubgrid, zSubgrid);
xSubgrid *= (mSdf.mSubgridSize + 1);
ySubgrid *= (mSdf.mSubgridSize + 1);
zSubgrid *= (mSdf.mSubgridSize + 1);
// reference subgrid point
const PxU32 x = PxMin(static_cast<PxU32>(fPos.x), sgSamples - 2),
y = PxMin(static_cast<PxU32>(fPos.y), sgSamples - 2),
z = PxMin(static_cast<PxU32>(fPos.z), sgSamples - 2);
// offset values by the subgrid memory offset
const PxU32 xM = xSubgrid + x, yM = ySubgrid + y, zM = zSubgrid + z;
const PxU32 base = mFStrideZ * zM + mFStrideY * yM + xM;
switch (mSdf.mBytesPerSparsePixel)
{
case 1:
return interpolateSubgrid<1>(mSdf.mSubgridSdf, base, fPos.x - x, fPos.y - y, fPos.z - z, gradient);
case 2:
return interpolateSubgrid<2>(mSdf.mSubgridSdf, base, fPos.x - x, fPos.y - y, fPos.z - z, gradient);
case 4:
return interpolateSubgrid<4>(mSdf.mSubgridSdf, base, fPos.x - x, fPos.y - y, fPos.z - z, gradient);
default: // never reached
PX_ASSERT(0);
return 0;
}
}
// interpolate the values of `array` at position `cPos`.
// `cPos` must be >= 0 and < `cDims`
PX_INLINE PxReal evaluateCoarse(const PxVec3& cPos, PxVec3* gradient = NULL) const
{
PX_ASSERT(cPos.x >= 0 && cPos.y >= 0 && cPos.z >= 0);
PX_ASSERT(cPos.x < mCSamples.x && cPos.y < mCSamples.y && cPos.z < mCSamples.z);
// reference grid point
const PxU32 x = PxMin(static_cast<PxU32>(cPos.x), mCSamples.x - 2),
y = PxMin(static_cast<PxU32>(cPos.y), mCSamples.y - 2),
z = PxMin(static_cast<PxU32>(cPos.z), mCSamples.z - 2);
const PxU32 w = mCSamples.x, h = mCSamples.y;
const PxU32 cStrideY = w, cStrideZ = w*h; // Note that this is sample, not cell, stride
const PxU32 base = cStrideZ * z + cStrideY * y + x;
return TriLerpWithGradient(
mSdf.mSdf[base],
mSdf.mSdf[base+1],
mSdf.mSdf[base+cStrideY],
mSdf.mSdf[base+cStrideY+1],
mSdf.mSdf[base+cStrideZ],
mSdf.mSdf[base+cStrideZ+1],
mSdf.mSdf[base+cStrideZ+cStrideY],
mSdf.mSdf[base+cStrideZ+cStrideY+1],
cPos.x - x, cPos.y - y, cPos.z - z, gradient);
}
// sample the SDF at `fPos`
// input vector `fPos` is in units of (sub-) grid cells, with integer values representing nodes
PX_INLINE PxReal sample(PxVec3 fPos, PxVec3* gradient = NULL) const
{
if (mIsDense)
fPos -= PxVec3(0.5);
PX_ASSERT(fPos.x >= 0 && fPos.y >= 0 && fPos.z >= 0);
PX_ASSERT(fPos.x <= mFDims.x && fPos.y <= mFDims.y && fPos.z <= mFDims.z);
if (mIsDense) // fPos = cPos
return evaluateCoarse(fPos, gradient);
// coarse reference gridpoint index
const Dim3 cBase(
PxMin(static_cast<PxU32>(fPos.x * mInvSubgridSize), mCSamples.x - 2),
PxMin(static_cast<PxU32>(fPos.y * mInvSubgridSize), mCSamples.y - 2),
PxMin(static_cast<PxU32>(fPos.z * mInvSubgridSize), mCSamples.z - 2)
);
const PxU32 i = idx3D(cBase.x, cBase.y, cBase.z, mCDims.x, mCDims.y);
const PxU32 subgridInfo = mSdf.mSubgridStartSlots[i];
if (subgridInfo == 0xFFFFFFFF) // Evaluate (coarse) background of sparse SDF
return evaluateCoarse((fPos * mInvSubgridSize).minimum(PxVec3(PxReal(mCSamples.x), PxReal(mCSamples.y), PxReal(mCSamples.z))), gradient);
// offset to subgrid origin
PxVec3 fPosInSubgrid;
fPosInSubgrid.x = PxMax(0.f, fPos.x - cBase.x * mSdf.mSubgridSize);
fPosInSubgrid.y = PxMax(0.f, fPos.y - cBase.y * mSdf.mSubgridSize);
fPosInSubgrid.z = PxMax(0.f, fPos.z - cBase.z * mSdf.mSubgridSize);
return evaluateSubgrid(subgridInfo, fPosInSubgrid, gradient);
}
// evaluate & interpolate `sdf` (in `sdf`'s "vertex" space) at `sPos`
// when outside the sdf grid, this should be considered an upper bound
// TODO(CA): add more clamps or prove they're unnecessary
inline PxReal dist(const PxVec3& sPos, PxVec3* gradient = NULL) const
{
// clamped to SDF support
const PxVec3 boxPos = clampToBox(sPos);
const PxVec3 diff = sPos - boxPos;
const PxReal diffMag = diff.magnitude();
const PxVec3 fPos = (boxPos - mSdfBoxLower) * mInvGridDx;
const PxReal distance = sample(clampToFine(fPos), gradient) + diffMag; // division inaccuracy necessitates clamp
if (gradient && diffMag > 0.0f)
*gradient = diff; //A quite coarse approximation but it's only used if the sample point is outside of the sdf's bounding box
return distance;
}
// evaluate & interpolate `sdf` at `sPos` (in `sdf`'s "vertex" space), and compute its gradient
inline PxVec3 grad(const PxVec3& sPos) const
{
// clamped to SDF support
const PxVec3 boxPos = clampToBox(sPos);
const PxVec3 fPos = (boxPos - mSdfBoxLower) * mInvGridDx;
PxVec3 gradient;
if ( fPos.x >= 1.0f && fPos.x <= mFDims.x - 2.0f &&
fPos.y >= 1.0f && fPos.y <= mFDims.y - 2.0f &&
fPos.z >= 1.0f && fPos.z <= mFDims.z - 2.0f)
{
gradient.x = sample(PxVec3(fPos.x+1, fPos.y, fPos.z)) - sample(PxVec3(fPos.x-1, fPos.y, fPos.z));
gradient.y = sample(PxVec3(fPos.x, fPos.y+1, fPos.z)) - sample(PxVec3(fPos.x, fPos.y -1, fPos.z));
gradient.z = sample(PxVec3(fPos.x, fPos.y, fPos.z+1)) - sample(PxVec3(fPos.x, fPos.y, fPos.z -1));
}
else
{
const PxReal h = mSdf.mSpacing;
gradient.x = dist(PxVec3(sPos.x+h, sPos.y, sPos.z)) - dist(PxVec3(sPos.x-h, sPos.y, sPos.z));
gradient.y = dist(PxVec3(sPos.x, sPos.y+h, sPos.z)) - dist(PxVec3(sPos.x, sPos.y-h, sPos.z));
gradient.z = dist(PxVec3(sPos.x, sPos.y, sPos.z+h)) - dist(PxVec3(sPos.x, sPos.y, sPos.z-h));
}
gradient *= 0.5f / mSdf.mSpacing;
return gradient;
}
// Estimate the value and gradient of `sdf` at `sPos`, using gradient information when `sPos` is
// outside the SDF grid. Return `PX_MAX_F32` when the distance exceeds `cutoffDistance`
PX_INLINE PxReal distUsingGradient(const PxVec3& sPos, PxVec3& gradient, const PxReal& cutoffDistance) const
{
// clamped to SDF support
const PxVec3 boxPos = clampToBox(sPos);
const PxVec3 diff = sPos - boxPos;
const PxVec3 fPos = (boxPos - mSdfBoxLower) * mInvGridDx;
const PxReal dist = sample(clampToFine(fPos));
if (dist > cutoffDistance)
return PX_MAX_F32;
gradient = grad(sPos);
gradient = (gradient.getNormalized() * PxAbs(dist) + diff).getNormalized();
return dist + gradient.dot(diff);
}
// data members
const SDF& mSdf;
PxVec3 mSdfBoxLower, mSdfBoxUpper; // Positions of the first and last grid points
Dim3 mCDims, mFDims; // background and high-resolution SDF dimensions in cells. Equal if dense.
// fDims is equally divisible by subgridSize, which is also in cells, for sparse SDFs
// the coarse grid has cDims+1 (cDims) samples per dimension for sparse (dense) SDFs
// subgrids have subgridSize+1 samples per dimension
Dim3 mCSamples; // Number of samples in each dimension. Equal to cDims for dense, and cDims + 1 for spares SDFs
PxReal mInvGridDx; // invSdfDx
PxReal mInvSubgridSize; // fineToCoarse
bool mIsDense;
PxReal mSubgridScalingFactor; // purely for optimization
PxU32 mFStrideY, mFStrideZ;
};
}
}
#endif