Geometry Queries(碰撞检测)--翻译

发表于 2024-05-15 更新于 2023-11-09 分类于翻译， PhysX ， Geometry Queries 阅读次数：本文字数： 5.8k 阅读时长 ≈ 21 分钟

前言

solid half-space: 我对solid half-space的理解是: 正常封闭型固体分成内部和外部, half-space geometry表示外部与外界相交, 内部也能与外部相交的几何体. 例如平面就可以被当做solid half-space.

SPU和PPU是什么? 解释:PS3中的处理器核心.

序言

这篇文章介绍使用PhysX处理独立几何体的碰撞和形状查询. 碰撞和场景查询形成对比, 后者碰撞或者查询场景中所有的对象. 有四种主要的几何Geometry Query:

Raycasts(Raycast Queries): 射线是否与几何体相交
Sweeps(Sweep Queries): 沿着直线移动一个几何体, 找到与之相交的几何体的第一个点
Overlaps(Overlap Queries): 决定两个结合体怎么相交.
渗入深度计算(minimal translational distance queries, 缩写MTD): 查找能使两个Overlap的几何体分开的最小距离的方向.

另外, PhysX提供一个Geometry Object的计算AABB的方法, 以及计算一个点到Geometry Object的距离.

以下所有函数中, Geometry Object都是以PxGeometry structure定义形状, 以PxTransform structure定义姿势的. 所有的Transform和Vector都被解释为在任意空间, 并且返回该空间中的结果.

Raycasts

Raycast Query:沿着一条线段追踪一个点, 并记录与几何体表面相交的信息. PhysX支持向所有几何体打射线.

下面的代码举例说明如何使用Raycast Query:

PxRaycastHit hitInfo;
PxU32 maxHits = 1;
bool anyHit = false;
PxHitFlags hitFlags = PxHitFlag::ePOSITION|PxHitFlag::eNORMAL|PxHitFlag::eDISTANCE|PxHitFlag::eUV;
PxU32 hitCount = PxGeometryQuery::raycast(origin, unitDir,
                                          geom, pose,
                                          maxDist,
                                          hitFlags,
                                          maxHits, &hitInfo, anyHit);

对参数的解释如下:

Origin: 射线起始位置.
unitDir: 定义射线方向的单位向量.
maxDist: 沿射线搜寻的最大距离. maxDist必须在\([0, inf]\)范围之内. 如果1maxDist为0, 只有当射线起始点在图形内部才会返回一个hit, 下面对每个几何体进行详细说明.
geom: 被测试的几何体.
pose: 被测试几何体的位置
hitFlag: 指定查询应返回的值, 以及处理查询的选项.
maxHits: 返回的最大hit数量.
hitInfo: 指定射线结果存储的地方, 即PxRaycastHit结构体.
anyHit: 已废弃. 它等价于PxHitFlag::eMESH_ANY. 应该使用PxHitFlag::eMESH_ANY.

返回结果为交互的数量. 每个交互的信息, 都会用PxRaycastHit存储. 结构体属性如下:

PxRigidActor*   actor;
PxShape*        shape;
PxVec3          position;
PxVec3          normal;
PxF32           distance;
PxHitFlags      flags;
PxU32           faceIndex;
PxF32           u, v;

某些字段是可选的, flag字段指明哪些成员会被填充到结果中. 如果在输入中设置了相应的字段, 该字段将被填充到输出结构中. 例如, 如果hitFlags被设置成PxHitFlag::ePOSITION, 查询将会填充PxRaycastHit::position字段, 并且在PxRaycastHit::flags中填充PxRaycastHit::position值. 如果Input Flag中没有设置指定的成员, 输出结果中不一定会包含相应成员的数据. 如果输入中不包含eNormal和ePosition标记, 查询会更快.

对于那些最初不与几何体相交的射线, 字段填充如下(可选字段和控制它们的标记列在一起):

actor和shape不会被填充(这些字段只在scene-level raycast中被使用, 详情:Scene Queries).
position (PxHitFlag::ePOSITION):相交的位置.
normal (PxHitFlag::eNORMAL):交点的表面法线.
distance (PxHitFlag::eDISTANCE): 射线上找到交点的距离.
flag指明了结构体中哪些字段是可用的.
faceIndex:射线hit到的face的index. 对于三角形网格(triangle mesh)和高度场(height field)相交, 它表示三角形索引. 对于凸多边形(convex mesh)相交, 它是多边形的索引. 对于其他形状, 它永远是0xFFFFFFFF.
u和v(PxHitFlag::eUV)是交点的重心坐标系. 这些字段(以及标记)只支持mesh(不支持高度场(height field)).

Position字段和重心坐标系相关, 公式如下, 其中v0, v1和v2是被hit的三角形的顶点.

position = (1 - u - v)v0 + uv1 + v*v2;

如何在triangle mesh中检索面和顶点数据, 在凸多边形mesh(convex mesh)和高度场(height field)中使用面和顶点索引, 详情请查询Geometry.

当射线起点在几何体内部时, 除了应用上面的行为, 对于某些字段PhysX可能无法计算出有意义的值. 这种情况下, 这些字段不会发生更改, 并且对应的标记也不会被设置. 具体细节因几何类型而异, 如下所述.

射线交点的具体情况如下:

向`Spheres` `Capsules` `Boxs` `Convex Meshes`打射线

当射线原点在固体对象(Spheres, Capsules Boxs Convex Meshes)内部时,最多返回一个结果:

PxHitFlag::eDISTANCE被设置, 并且distance为0.
PxHitFlag::eNORMAL被设置, 并且交点法线方向与射线方向相反.
PxHitFlag::ePOSITION被设置, 并且position (impact point)设置为射线原点.

如果射线的起点和终点与物体表面非常近, 它有可能被看做成surface的任何一边(side).

向平面打射线

对于射线检测, 会把平面当做只有半个空间(half-space)的固体, (和overlap不同, 为什么不同?). 大多数情况下会返回一个结果, 如果射线原点在平面的后边, 即使射线和平面相交, 也不会有hit点.

如果射线的起始和结束点与平面非常接近, 它可能会被当做平面的任何一边.

向`Triangle meshes`打射线

把triangle meshes当做非常薄的三角形面而不是固体对象. 可以通过配置返回一个任意hit点, 或者很多个hit点.

如果maxHits为1, 并且没有设置PxHitFlag::eMESH_ANY(或者anyHit为true), 查询将会返回最近的交点.
如果maxHits为1, 并设置了PxHitFlag::eMESH_ANY(并且anyHit为false), 查询将会返回任意hit点. 对于line of sight或者shadow ray而言, 使用它就可以完全可以知道射线是否hit到mesh.
如果如果maxHit大于1, 查询将会返回多个交点, 最多为maxHits个. 如果交点个数超过maxHits, 无法保证结果中包含最近的hit. 使用示例: 击中多个三角行的穿墙(wall-piercing)子弹, 或者要求特定的过滤. 注意, 在这些例子中必须使用PxHitFlag::eMESH_MULTIPLE. 还要注意如果hit点彼此非常接近, SDK默认返回第一个found到的hit结果.

通常any hit 比closest hit 更快, closest hit 比multiple hits更快, 即:any hit 快于closest hit 快于multiple hits.

默认情况下, 背面hits(back face hits, 三角形外向法线和射线的点乘(dot)结果为负)会被剔除, ~~所以对于任何命中上述法线的三角形, 与射线方向的点乘结果都为负~~ 如果三角形正面法线(outward-face-normal)与射线的点乘为负, 则hit点被剔除.

如果PxMeshGeometryFlag::eDOUBLE_SIDED或者PxHitFlag::eMESH_BOTH_SIDES被设置, 则禁止剔除.
如果PxMeshGeometryFlag::eDOUBLE_SIDED被设置, back face hit将会把最终结果的法线反转.

这句话太难翻译直接贴原文了(reported-normal不知道怎么翻译):

For example a transparent glass window could be modeled as a double-sided mesh, so that a ray would hit either side with the reported normal facing opposite to the ray direction. A raycast tracing the path of a bullet that may penetrate the front side of a mesh and emerge from the back could use eMESH_BOTH_SIDES to find both front and back facing triangles even when the mesh is single-sided.

例如一个类型为double-sided mesh的玻璃窗, so that a ray would hit either side with the reported normal facing opposite to the ray direction. 有些子弹可以击穿mesh, 模拟这类子弹路径的射线, 可以使用eMESH_BOTH_SIDES来找正面和背面的三角形, 即使该mesh是single-side.

下图展示了当单一射线和一个mesh在几个不同的地方相交时, 不同flag会发生什么.

只针对某些mesh使用PxHitFlag::eMESH_BOTH_SIDES标志位, 并且该flag在PxQueryFilterCallback中设置.

如果射线开始和结束的点和三角面非常接近, 可能会被当成三角形的任何一边(正面/背面).

向`Heightfields`打射线

处理Heightfields和triangle meshes不同, heightfields会一直被当做double side, 意味着无论射线原点在heightfileds surface的上面或者下面, 最终的hits都会被注册.
hit normal一直是triangle hit的法线, 当thickness \(<=\) 0, 朝向(在heightfields空间)\(+y\)方向; 当thickness大于0, 朝向(在heightfields空间)\(-y\)方向.
除了上述情况, heightfields thickness对其他方面没有任何影响. 特殊的, 固体的heightfield部分不会生成hit.
当射线hit heightfield时候, UVs不会被设置, PxHitFlag::eUV标记也不会被设置.

overlap

overlap查询只是简单的查询两个几何体是否重叠了. 其中一个几何体必须是box,sphere,capsule或者凸多边形, 另一个几何体可以使任意类型.

下面代码说明了如何使用overlap查询:

1	bool isOverlapping = overlap(geom0, pose0, geom1, pose1);

overlap不支持hit flag, 只是返回一个bool类型的结果.

平面被当做solid half-space: 任何处于平面下的都被当做volume的一部分.
triangle mesh被当做非常薄的三角形表面, 而不是固体对象.
heightfield被当做由其厚度挤压成的三角形表面. overlap几何体不会与heightfield相交, 但是挤压空间将会上报hit

如果对于triagnle mesh和heightfield类型不仅仅需要一个bool结果, 使用PxMeshQuery API.

Penetration Depth

当两个对象相交, PhysX能够计算通过平移将二者分开的最小距离和方向(分开的量涉及到MTD, 即: 最小平移距离(minimum translational distance), 通过平移将二者分开的长度最小的向量). 其中一个几何体必须是box, sphere, capsule, 或者convex mesh, 另一个可以是任意类型.

如下代码阐述了如何使用penetration depth的查询:

1
2
3

bool isPenetrating = PxGeometryQuery::computePenetration(direction, depth,
                                                         geom0, pose0,
                                                         geom1, pose1);

参数解释如下:

direction: 第一个对象通过平移从第二个对象中脱离(depenetrate)出来的方向.
distance: 第一个对象从第二个对象中脱离(depenetrate)出来的距离.
geom0: 第一个几何体.
pos0: 第一个几何体的transform.
geom1:第二个几何体.
pos1: 第二个几个题的transform.

如果对象有渗入, 则返回true, 这种情况下, 会设置其方向和深度字段. 通过平移向量(\(\vec{D}=\vec{Direction}*depth\))将二者分离开来. 如果函数返回true, depth一定\(>=0\). 如果几何体没有overlap, 函数返回false, direction和depth都不会进行设置.

对于简单(convex)的形状, 返回结果是精确的.

对于mesh和heightfields, 在PxExtensions中, 将使用的循环算法和专用函数暴露出来了.

PxVec3 direction = PxComputeMeshPenetration(maxIter,
                                            geom, geomPose,
                                            meshGeom, meshPose,
                                            nb);

PxVec3 direction = PxComputeHeightFieldPenetration(maxIter,
                                                   geom, geomPose,
                                                   heightFieldGeom, heightFieldPose,
                                                   nb);

这里, maxIter是算法的最大循环次数, 并且nb是真正的循环执行数量, 并且作为output变量输出出来. 如果检测没有overlap, nb将会被设置成0. 代码尝试至多maxIter此循环, 但是如果找到depenetration向量, 可能会提前返回. 通常, maxIter = 4就会得出一个不错的结果.

这些函数只会计算出一个近似的depenetration向量, 当在几何体和mesh/heightfield之间的overlap数量比较小的时候, 会工作良好. 特别的, 当对象中心在三角形背面时, 将会忽略与三角形的交互. 如果所有相交的三角形都符合上述条件, 该函数将不会计算MTD向量.

Sweeps

sweep query追踪一个对象横穿空间的过程, 并找到在这个过程中与第二个几何体碰撞的点. 并且上报关于碰撞点的信息. PhysX只支持第一个对象(贯穿空间的那个对象)为sphere, box, capsule, 或者convex几何体, 第二个对象可以是任何类型.

下面的代码举例说明如何使用sweep query:

PxSweepHit hitInfo;
PxHitFlags hitFlags = PxHitFlag::ePOSITION|PxHitFlag::eNORMAL|PxHitFlag::eDISTANCE;
PxReal inflation = 0.0f;
PxU32 hitCount = PxGeometryQuery::sweep(unitDir, maxDist,
                                        geomToSweep, poseToSweep,
                                        geomSweptAgainst, poseSweptAgainst,
                                        hitInfo,
                                        hitFlags,
                                        inflation);

这些参数解释如下:

unitDir: 定义sweep的单位向量.
maxDist: 定义了沿着sweep查询的最大距离. 它必须在\([0, inf)\)之间, 并且通过SDK会被限制在PX_MAX_SWEEP_DISTANCE之内. 当sweep距离为0时, 等价于overlap检测.
geomToSweep: 将要sweep的几何体, 支持box, sphere, capsule, 或者convex mesh类型.
PosToSweep: 用于sweep几何体的初始位置.
geomSweptAgainst: sweep against的几何体.
hitInfo: 最终返回的结果. 一个sweep最多返回一个hit.
hitFlags: 决定sweep将被如何处理, 如果发现impact点, 会返回对应的数据.
inflation: 以对象表面向外扩展的方式膨胀第一个几何体, 并将所有角都做成圆角. 当使用sweep来测试movement是否可用时, 它用来保证几何体最小的空间边界.

正如射线检测一样, 如果某个flag在hitFlags中设置, 在输出结构体对应的字段会被填充. PxSweepHit的字段如下:

PxRigidActor*   actor;
PxShape*        shape;
PxVec3          position;
PxVec3          normal;
PxF32           distance;
PxHitFlags      flags;
PxU32           faceIndex;

actor和shape: actor和shape不会被设置(这些字段只有在scene-level sweep中才会被使用, 详见: Scene Queries).
position(PxHitFlag::ePOSITION): 交点的位置. 当有多个impact点时, 例如两个box, 面和面相撞, physX将任意选择一个点. 针对meshes或者height fields类型, 使用函数PxMeshQuery获取详细信息.
normal(PxHitFlag::eNORMAL):impact点的表面法线. 他是一个单位向量, 指向被击中对象的外侧, 与sweep方向相反(即: sweep方向和impact法线的点乘是负数.).
distance(PxHitFlag::eDISTANCE):沿着射线方向, 物体与碰撞点的距离.
flag: 指定结构体的哪些字段是可用的.
faceIndex: sweep hit的面索引. 这个是被击中对象的面, 而不是sweep对象. 对于和triangle mesh和heightfield的sweep交点, 它是三角形顶点索引, 与convex mesh的交点, 它是多边形顶点索引. 对于其他类型, 它是0xffffffff.

当sweep hit到triangle mesh或者convex mesh, 返回的被选择的三角形如下:

对于convex和box sweep, 选择距离最短的三角形.
对于capsule和sphere, 最短距离的三角形不一定会被选择, 最短距离在\(10^{-3}f(即1e-3f)\)范围内的都会被考虑, 选择法线(三角形的法线)方向与sweep方向几乎一致的三角形. 如果这些三角形法线相同, 会随机选择他们中的一个然后返回.

这些例子中, hit点, 位置(例如两个box的面和面sweep会随机选择其中一个点), 法线(对于capsule和sphere, 最短距离的三角形不一定会被选择, 最短距离在\(10^{-3}f(即1e-3f)\)范围内的都会被考虑, 选择法线(三角形的法线)方向与sweep方向几乎一致的三角形. 如果这些三角形法线相同, 会随机选择他们中的一个然后返回.),都会影响最终选择哪个三角形.

与raycast不同, sweep不支持u, v坐标.

对于几何对象的sweep against:

平面被当做半个空间的固体, 也就是说任何在平面后面的物体多会被当做volume的一部分进行sweep against.
相同的背面剔除规则(应用在raycast上的)也会应用到sweep上, 需要注意的是, 不支持eMESH_MULTIPLE和eMESH_BOTH_SIDES.

Initial Overlaps

和射线检测相似, 开始就在对象内部, 两个几何体sweep时候可能就已经相交了. 默认情况下, PhysX会检测并上报overlap. 使用PxSweepHit::hadInitialOverlap()来查看hit是否是initial overlap生成的.

对于triangle mesh和height field, 背面剔除在overlap check之前执行, 因为如果triangle被剔除了, 就不会上报overlap事件了.

PhysX是否计算MTD由PxHitFlag::eMTD决定. 如果PxHitFlag::eMTD没有被设置:

distance将被设置成0, PxHitFlag::eDISTANCE也会在PxSweepHit结构体中设置.
normal和sweep方向相反, 并且在结果PxSweepHit中PxHitFlag::eNORMAL会被设置.
position不会被定义, 并且在结果PxSweepHit中PxHitFlag::ePOSITION不会被设置.
faceIndex是第二个几何对象的面. 对于heightfield和triangle mesh, 他是第一个被发现的overlap triangle的索引. 对于其他几何类型, 将设置为0xffffffff.

如果PxHitFlag::eMTD被设置, hit结果的定义如下:

distance被设置成penetrate的深度, PxSweepHit 中的PxHitFlag::eDISTANCE被设置.
normal被设置成penetrate的方向, PxSweepHit中的PxHitFlag::eNORMAL被设置.
position为sweep几何对象上的一个点(即:第一个几何对象参数), 并且PxSweepHit中的PxHitFlag::ePOSITION会被设置.
faceIndex是第二个几何对象上的面.
- 对于convex mesh, 它是最小penetrate的面. 如果MTD可以通过edge或者convex顶点分离对象, 将选择法线(面的法线)最接近分开方向的面.
- 对于triangle mesh和heightfield, 它是在depenetration算法最后一次循环中查找到的最后一个penetrate三角形.
- 对于其他几何类型, faceIndex将会被设置成0xffffffff.

在initial overlap中, 这个标志将会带来额外负担的处理操作. 另外, 会启用如下限制:

PxHitFlag::eMTD与PxHitFlag::ePRECISE_SWEEP和PxHitFlag::eASSUME_NO_INITIAL_OVERLAP(见下文)不兼容. PxHitFlag::eMTD与他们中的任何一个组合使用都会报错, 并且与PxHitFlag::eMTD不兼容的标志将被忽略.
在PS3中, PxHitFlag::eMTD不支持SPU(Power Processing Element) sweep. 如果在SPU sweep中包含了PxHitFlag::eMTD, 将会报错. PPU(Synergistic Processing Elements)完全支持PxHitFlag::eMTD.

有时使用定制的代码路径测试initial overlap会带来性能消耗. 有必要保证几何对象不是initially overlapping, overlap支持使用PxHitFlag::eASSUME_NO_INITIAL_OVERLAP进行检测. 有一些使用该flag的限制, 详见:Pitfalls.

当initial overlap几何体处理未定义行为时, 会使用PxHitFlag::eASSUME_NO_INITIAL_OVERLAP标志.
PxHitFlag::eASSUME_NO_INITIAL_OVERLAP与zero sweep distance组合使用会导致warning和undefined behavior.

注意:
具有PxHitFlag::eMTD flag的sweep使用两种针对三角形的背面剔除. 首先, 在Sweep方向上被剔除的三角形决定这是否是一个overlap. 如果检测到overlap, 他们会进一步检测centroid(面心)是否在三角形后面, 如果没找到三角形, direction将设置为sweep diection的反方向, distance设置为0.

注意:
大多数情况下, 将第一个几何体平移-normal*distance距离, 会将对象分开. 尽管可以使用循环depenetration算法找到triangle mesh和height field的MTD, 但是有些情况下MTD可能不会将mesh完全分离开. 这种情况下, 在应用平移后, 要调用第二次查询.

注意:
在PhysX 3.3中一个已知的问题是当eMTD没有设置时, sweep against convex mesh的face index是undefined

Precise Sweeps

PxHitFlag::ePRECISE_SWEEP允许更加精确的sweep代码(默认情况下使用更快的但是精度不高的解决方案). PxHitFlag::ePRECISE_SWEEP和inflation和PxHitFlag::eMTD不兼容.

Sweeps against Height Fields

Height field被当做很薄的三角形面, 而不是固体对象.
厚度不会影响initial overlap检测和点的碰撞.
对于single height field, 如果厚度小于0, hit的法线方向为本地坐标系中的+Y方向, 如果厚度大于0, hit的法线方向为本地坐标系中的-Y方向.
如果设置了eDOUBLE_SIDED或者eMESH_BOTH_SIDES, height field将被认为是双面的.
- 返回的hit会一直朝向sweep方向.
eMESH_ANY不起作用.
ePRECISE_SWEEP不起作用.

Pitfalls

在使用sweep时候需要注意一些隐患:

由于精度问题, 当两个对象有非常巨大的大小差异, 会返回错误的结果.
由于算法不同, sweep query可能不仅仅检测到一个overlap查询, 而是会检测一个不同的overlapping形状的初始化集合. 执行一个overlap check还不足以判定PxHitFlag::eIGNORE_INITIAL_OVERLAP标志位的安全性, 需要一系列的overlap/sweep/penetration depth信息的应用程序应该使用带有initial overlap testing和PxHitFlag::eMTD标志的sweep check.

Additional PxGeometryQuery functions

下面的函数计算点和几何体之间的距离. 只支持box, sphere, capsule和convex shape.

1	PxReal dist = PxGeometryQuery::pointDistance(point, geom, pose, closestPoint);

closestPoint是一个可选地输出参数, 它返回最近的点.

下面的函数计算几何体轴对齐的包围盒(AABB), 并返回它的姿态.

1	PxBounds3 bounds = PxGeometryQuery::getWorldBounds(geom, pose, inflation);

AABB包围盒被inflation缩放, 如果没有显式指定, 它的值为`1.01f.

PxMeshQuery

对于triangle mesh, height field overlap, 以及对triangle数组的sweep, PhysX提供额外的函数可以获得多个结果. 只有boxes, spheres, capsules与mesh或heightFields被测试的时候使用这些函数.

Mesh Overlaps

下面的代码举例说明了如何处理mesh triangle与给定球状体积:

PxU32 triangleIndexBuffer[bufferSize];
PxU32 startIndex = 0;
bool bufferOverflowOccured = false;
PxU32 nbTriangles = PxMeshQuery::findOverlapTriangleMesh(sphereGeom, spherePose,
                                                         meshGeom, meshPose,
                                                         triangleIndexBuffer, bufferSize,
                                                         startIndex, bufferOverflowOccured);

for(PxU32 i=0; i < nbTriangles; i++)
{
    PxTriangle tri;
    PxU32 vertexIndices[3];
    PxMeshQuery::getTriangle(meshGeom, meshPose, triangleIndexBuffer[i], tri, vertexIndices);

     ...  // process triangle info
}

findOverlapTriangleMesh函数用于额外提取三角形索引.

sphereGeom和spherePose指定overlap的区域.
meshGeom和meshPose指定mesh和它的姿态.
triangleIndexBuffer和triangleSize指定buffer以及buffer的大小.
当buffer溢出时, startIndex用于重新启动查询. 在这里例子中, 为了查询更多的三角形集合, 将该参数设置为目前已检索的数量.
当查询的结果超过buffer的大小, 会设置bufferOverflowOccured标志位.

height field也存在类似的查询函数.

Sweeps against Triangles

有时候, 例如, 当使用mesh overlap API时, 它会很方便的与一组三角形进行sweep. 为此, PhysX提供指定的函数. 函数签名如下:

bool sweep(const PxVec3& unitDir,
           const PxReal distance,
           const PxGeometry& geom,
           const PxTransform& pose,
           PxU32 triangleCount,
           const PxTriangle* triangles,
           PxSweepHit& sweepHit,
           PxHitFlags hitFlags = PxHitFlag::eDEFAULT,
           const PxU32* cachedIndex = NULL,
           const PxReal inflation = 0.0f,
           bool doubleSided = false);