algorithm - 仅整数运算 3D 三角形-三角形碰撞检测

Question

我需要仅使用整数数学进行 3D 三角形-三角形碰撞检测。不幸的是，我无法使用 64 位整数(仅 32 位)并且我的顶点值可以大于 24 位值。这使得溢出成为一个棘手的问题——否则我可能只使用定点运算。

好消息是我不需要完美的准确性——毕竟我们使用的是整数。此外，它不需要连续碰撞检测——速度将为零。但我可能会测试大三角形与小三角形的碰撞，因此法线的粗略近似会导致严重的相对误差。

三角形本身表示为 32 位整数向量的三元组。

有没有办法做到这一点？

Answer 1

这可以通过多次使用计算四面体的有符号体积来实现。我在这篇 MSE 帖子中描述了这个想法:“Find whether two triangles intersect or not in 3D”。

那么你的问题就简化为确保立方体积计算不会溢出。您可以检测溢出并仅在必要时才求助于浮点计算。