c++ - 在针对 AABB 进行 SAT 测试之前过滤掉三角形列表的快速方法

Question

我正在尝试与来自 tria 网格的三角形执行 AABB-三角形相交，而 AABB 是结构化 3D 网格/体素中的单个单元格。有没有什么聪明的方法/算法可以用来过滤和减少我必须执行 SAT 测试的三角形和 AABB 组合的数量？就目前而言，我正在针对网格中的每个单元格检查每个三角形，这是无效的。我还考虑根据三角形网格中的质心距离和最大三角形尺寸过滤掉三角形作为容差。但这又将涉及遍历所有三角形。我也在考虑 K 近邻。

Answer 1

有一些众所周知的技术，例如：

1. 给每个三角形一个 AABB。所以你先做AABB vs AABB交集。目标是快速丢弃不相交的三角形。

2. 一旦将所有三角形都包含在 AABB 中，就可以使用 I-COLLIDE 等算法进行大规模的 AABB 间碰撞检测。您还可以为网格创建 AABB 树（也称为 Bounding-Volume-Hierarchy 或 BVH），以便一次丢弃大量不相交的三角形。

一旦你减少了 AABB 与单元格的 AABB 相交的三角形集，那么你需要执行实际的 AABB/三角形测试，你可以使用分离轴定理。