两个移动四面体之间的连续碰撞检测 [英] Continuous collision detection between two moving tetrahedra

问题描述

我的问题很简单.我有两个四面体，每个四面体具有当前位置，空间线速度，角速度和质心(实际上是旋转中心).

My question is fairly simple. I have two tetrahedra, each with a current position, a linear speed in space, an angular velocity and a center of mass (center of rotation, actually).

有了这些数据，我试图找到一种(快速)算法，该算法可以精确地确定(1)它们是否会在某个时间点发生碰撞；如果是，(2)在它们发生碰撞了多少时间之后和(3)碰撞点.

Having this data, I am trying to find a (fast) algorithm which would precisely determine (1) whether they would collide at some point in time, and if it is the case, (2) after how much time they collided and (3) the point of collision.

大多数人会通过执行三角形-三角形碰撞检测来解决此问题，但这将在冗余操作上浪费一些CPU周期，例如在检查不同的三角形时，将一个四面体的同一边与另一个四面体的同一边进行检查.这仅意味着我会稍微优化一下.不用担心.

Most people would solve this by doing triangle-triangle collision detection, but this would waste a few CPU cycles on redundant operations such as checking the same edge of one tetrahedron against the same edge of the other tetrahedron upon checking up different triangles. This only means I'll optimize things a bit. Nothing to worry about.

问题是我不知道有没有考虑到自旋转的公共CCD(连续碰撞检测)三角算法.

The problem is that I am not aware of any public CCD (continuous collision detection) triangle-triangle algorithm which takes self-rotation in account.

因此，我需要一种可以输入以下数据的算法:

Therefore, I need an algorithm which would be inputted the following data:

• 三个三角形的顶点数据
• 旋转的位置和中心/质量
• 线速度和角速度

并会输出以下内容:

• 是否有碰撞
• 发生了多少时间碰撞
• 发生碰撞的空间点

预先感谢您的帮助.

推荐答案

常用的离散碰撞检测将在连续的离散时间点上检查每种形状的三角形是否存在碰撞.尽管计算起来很简单，但由于在测试的离散时间点之间发生碰撞，它可能会错过快速移动的物体撞击另一个物体的情况.

The commonly used discrete collision detection would check the triangles of each shape for collision, over successive discrete points in time. While straightforward to compute, it could miss a fast moving object hitting another one, due to the collision happening between discrete points in time tested.

连续碰撞检测将首先计算每个三角形在无限长时间内所跟踪的体积.对于以恒定速度运动而没有旋转的三角形，此体积看起来像三角棱镜.然后，CCD将检查这些体积之间是否存在碰撞，最后追溯三角形是否以及在什么时候实际共享相同的空间.

Continuous collision detection would first compute the volumes traced by each triangle over an infinity of time. For a triangle moving at constant speed and without rotation, this volume could look like a triangular prism. CCD would then check for collision between the volumes, and finally trace back if and at what time the triangles actually shared the same space.

引入角速度后，每个三角形跟踪的体积不再像棱镜.它看起来更像是螺丝的形状(如一股DNA链)或其他一些非平凡的形状，您可以通过沿任意轴旋转三角形并线性拖动来获得三角形.计算如此体积的形状绝非易事.

When angular velocity is introduced, the volume traced by each triangle no longer looks like a prism. It might look more like the shape of a screw, like a strand of DNA, or some other non-trivial shapes you might get by rotating a triangle around some arbitrary axis while dragging it linearly. Computing the shape of such volume is no easy feat.

一种方法可能是，当它以给定的角速度矢量旋转时，如果它不是线性运动的，则首先会计算包含整个四面体的球.您可以为每个顶点计算一个旋转圆，然后从中导出球体.给定一个球体，我们现在可以将挤出的CCD体积近似为一个圆柱体，具有球体的半径并沿着线速度矢量进行扩展.找到这样的圆柱体的碰撞使我们对要在其中搜索碰撞的区域有了一个近似值.

One approach might first compute the sphere that contains an entire tetrahedron when it is rotating at the given angular velocity vector, if it was not moving linearly. You can compute a rotation circle for each vertex, and derive the sphere from that. Given a sphere, we can now approximate the extruded CCD volume as a cylinder with the radius of the sphere and progressing along the linear velocity vector. Finding collisions of such cylinders gets us a first approximation for an area to search for collisions in.

第二种补充方法可能是尝试通过将每个三角形分解为几乎是棱柱形的小子体积来近似每个三角形所跟踪的实际体积.它将以两个时间增量获取三角形位置，并添加通过在这些时刻跟踪三角形顶点而生成的曲面.这是一个近似值，因为它连接的是直线而不是实际的曲线.为了避免严重误差的逼近，每个连续力矩之间的持续时间必须足够短，以使三角形仅完成一小部分旋转.持续时间可以从角速度得出.

A second, complementary approach might attempt to approximate the actual volume traced by each triangle by breaking it down into small, almost-prismatic sub-volumes. It would take the triangle positions at two increments of time, and add surfaces generated by tracing the triangle vertices at those moments. It's an approximation because it connects a straight line rather than an actual curve. For the approximation to avoid gross errors, the duration between each successive moments needs to be short enough such that the triangle only completes a small fraction of a rotation. The duration can be derived from the angular velocity.

第二种方法可创建更多多边形！您可以使用第一种方法来限制搜索量，然后使用第二种方法来获得更高的精度.

The second approach creates many more polygons! You can use the first approach to limit the search volume, and then use the second to get higher precision.

如果您要为游戏引擎解决此问题，您可能会发现上述精度足够了(我仍然会以计算成本为代价).相反，如果您正在编写CAD程序或正在处理论文，则可能会发现它不尽如人意.在后一种情况下，您可能希望改进第二种方法，也许是通过对转弯移动的三角形所占据的体积进行更好的几何描述-当转弯角度较小时.

If you're solving this for a game engine, you might find the precision of above sufficient (I would still shudder at the computational cost). If, rather, you're writing a CAD program or working on your thesis, you might find it less than satisfying. In the latter case, you might want to refine the second approach, perhaps by a better geometric description of the volume occupied by a turning, moving triangle -- when limited to a small turn angle.

这篇关于两个移动四面体之间的连续碰撞检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！