两个移动四面体之间的连续碰撞检测
我的问题很简单。 我有两个四面体，每个四面体都有当前位置、空间线速度、角速度和质心（实际上是旋转中心）。
有了这些数据，我试图找到一种（快速）算法，该算法可以精确确定（1）它们是否会在某个时间点发生碰撞，如果是这种情况，（2）它们碰撞了多长时间以及（3） ) 碰撞点。
大多数人会通过进行三角形-三角形碰撞检测来解决这个问题，但这会在冗余操作上浪费一些 CPU 周期，例如在检查不同的三角形时，检查一个四面体的相同边与另一个四面体的相同边。 这仅意味着我会稍微优化一些事情。 完全不用担心。
问题是我不知道有任何公共 CCD（连续碰撞检测）三角-三角算法会考虑自旋转。
因此，我需要一个算法，输入以下数据：
- 三个三角形的顶点数据
- 位置和旋转中心/质量
- 线速度和角速度
并输出以下数据：
- 是否存在碰撞
- 碰撞发生后多长时间
- 在碰撞发生在空间的哪个点
预先感谢您的帮助。
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).
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.
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.
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:
- vertex data for three triangles
- position and center of rotation/mass
- linear velocity and angular velocity
And would output the following:
- Whether there is a collision
- After how much time the collision occurred
- In which point in space the collision occurred
Thanks in advance for your help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
您的问题可以转化为线性规划问题并精确解决。
首先，假设第一个四面体的 (p0,p1,p2,p3) 是 t0 时刻的顶点，(q0,q1,q2,q3) 是 t1 时刻的顶点，那么在 4d 时空中，它们填充下面是 4d 闭合体积
这里 a0...a3 和 b0...b3 参数在区间 [0,1] 内并且总和为 1：
第二个四面体类似地是一个凸多边形（在上面的所有内容中添加 ' 来定义 V'）移动四面体的 4d 体积
现在两个凸多边形的交集是凸多边形，第一次发生这种情况将满足以下线性规划问题：
如果 (p0,p1,p2,p3) 移动到 (q0,q1,q2)。 ,q3)
(p0',p1',p2',p3') 移动到 (q0',q1',q2',q3')
那么第一次相交发生在点/时间 (r,t)：
最小化 t0*(a0+a1+a2+a3)+t1*(b0+b1+b2+b3) 最后实际上
是 4 个方程， (r,t) 的每个维度都有一个。
这是 16 个值 ak、bk、ak' 和 bk' 的总共 20 个线性约束。
如果有解，则
是第一个交点。 否则它们不相交。
Your problem can be cast into a linear programming problem and solved exactly.
First, suppose (p0,p1,p2,p3) are the vertexes at time t0, and (q0,q1,q2,q3) are the vertexes at time t1 for the first tetrahedron, then in 4d space-time, they fill the following 4d closed volume
Here the a0...a3 and b0…b3 parameters are in the interval [0,1] and sum to 1:
The second tetrahedron is similarly a convex polygon (add a ‘ to everything above to define V’ the 4d volume for that moving tetrahedron.
Now the intersection of two convex polygon is a convex polygon. The first time this happens would satisfy the following linear programming problem:
If (p0,p1,p2,p3) moves to (q0,q1,q2,q3)
and (p0’,p1’,p2’,p3’) moves to (q0’,q1’,q2’,q3’)
then the first time of intersection happens at points/times (r,t):
Minimize t0*(a0+a1+a2+a3)+t1*(b0+b1+b2+b3) subject to
The last is actually 4 equations, one for each dimension of (r,t).
This is a total of 20 linear constraints of the 16 values ak,bk,ak', and bk'.
If there is a solution, then
Is a point of first intersection. Otherwise they do not intersect.
过去曾想过这个问题，但失去了兴趣……解决这个问题的最佳方法是抽象出一个对象。
创建一个以第一个四面体为中心的坐标系（重心坐标或以一点为原点的倾斜系统），并通过使另一个四面体绕中心旋转来抽象出旋转。 如果您将旋转时间乘以时间，这将为您提供参数方程。
将质心向第一个物体的运动及其旋转相加，就得到了一组相对于第一个物体（距离）的运动方程。
求解距离为零的 t。
显然，使用这种方法，添加的效果越多（例如风阻），方程就越混乱，但它仍然可能是最简单的（几乎所有其他碰撞技术都使用这种抽象方法）。 最大的问题是，如果添加任何有反馈但没有解析解的效应，整个方程将变得无法求解。
注意：如果您走的是倾斜系统的路线，请注意距离上的陷阱。 您必须位于正确的八分圆中！ 不过，这种方法有利于向量和四元数，而重心坐标有利于矩阵。 因此，请选择您的系统使用最有效的那个。
Thought about this in the past but lost interest... The best way to go about solving it would be to abstract out one object.
Make a coordinate system where the first tetrahedron is the center (barycentric coords or a skewed system with one point as the origin) and abstract out the rotation by making the other tetrahedron rotate around the center. This should give you parametric equations if you make the rotation times time.
Add the movement of the center of mass towards the first and its spin and you have a set of equations for movement relative to the first (distance).
Solve for t where the distance equals zero.
Obviously with this method the more effects you add (like wind resistance) the messier the equations get buts its still probably the simplest (almost every other collision technique uses this method of abstraction). The biggest problem is if you add any effects that have feedback with no analytical solution the whole equation becomes unsolvable.
Note: If you go the route of of a skewed system watch out for pitfalls with distance. You must be in the right octant! This method favors vectors and quaternions though, while the barycentric coords favors matrices. So pick whichever your system uses most effectively.
常用的离散碰撞检测将在连续的离散时间点上检查每个形状的三角形是否发生碰撞。 虽然计算起来很简单，但由于测试的离散时间点之间发生碰撞，它可能会错过一个快速移动的物体撞击另一个物体的情况。
连续碰撞检测将首先计算每个三角形在无限时间内追踪的体积。 对于以恒定速度移动且不旋转的三角形，该体积可能看起来像三棱柱。 然后，CCD 会检查体积之间的碰撞，最后追溯三角形是否以及何时共享同一空间。
当引入角速度时，每个三角形所描绘的体积不再看起来像棱柱。 它可能看起来更像螺丝的形状，就像一条 DNA 链，或者通过绕某个任意轴旋转三角形并线性拖动它可能得到的其他一些不平凡的形状。 计算这样体积的形状并不是一件容易的事。
一种方法可能首先计算当四面体以给定角速度矢量旋转时包含整个四面体的球体（如果它不是线性移动的话）。 您可以计算每个顶点的旋转圆，并从中导出球体。 给定一个球体，我们现在可以将挤压的 CCD 体积近似为一个具有球体半径并沿着线速度矢量前进的圆柱体。 查找此类圆柱体的碰撞使我们能够对搜索碰撞的区域进行第一个近似。
第二种补充方法可能会尝试通过将每个三角形分解为小的、几乎棱柱形的子体积来近似每个三角形所追踪的实际体积。 它将在两个时间增量处获取三角形位置，并添加通过在这些时刻追踪三角形顶点生成的曲面。 这是一个近似值，因为它连接的是直线而不是实际的曲线。 为了避免严重误差的近似，每个连续时刻之间的持续时间需要足够短，使得三角形仅完成旋转的一小部分。 持续时间可以从角速度导出。
第二种方法创建了更多的多边形！ 您可以使用第一种方法来限制搜索量，然后使用第二种方法来获得更高的精度。
如果您正在为游戏引擎解决这个问题，您可能会发现上述精度已经足够了（我仍然会对计算成本感到不寒而栗）。 相反，如果您正在编写 CAD 程序或撰写论文，您可能会发现它不太令人满意。 在后一种情况下，您可能需要改进第二种方法，也许是通过对转动、移动的三角形所占据的体积进行更好的几何描述（当限制为小转动角度时）。
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.
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.
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.
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.
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.
我花了很多时间思考像这样的几何问题，尽管陈述很简单，但精确的解决方案似乎太复杂而无法实用，即使对于类似的 2D 情况也是如此。
但凭直觉，当你考虑线性平移速度和线性角速度时，我发现这样的解决方案确实存在。 不要认为您会在网络或任何书籍中找到答案，因为我们在这里讨论的是特殊但复杂的案例。 无论如何，迭代解决方案可能就是您想要的——世界其他地方都对这些感到满意，那么您为什么不应该呢？
I have spent quite a lot of time wondering about geometry problems like this one, and it seems like accurate solutions, despite their simple statements, are way too complicated to be practical, even for analogous 2D cases.
But intuitively I see that such solutions do exist when you consider linear translation velocities and linear angular velocities. Don't think you'll find the answer on the web or in any book because what we're talking about here are special, yet complex, cases. An iterative solution is probably what you want anyway -- the rest of the world is satisfied with those, so why shouldn't you be?
如果您尝试碰撞非旋转四面体，我建议采用 Minkowski 和并执行光线检查，但这不适用于旋转。
我能想到的最好办法是使用它们的边界球体执行扫掠球体碰撞，以便为您提供一系列时间来使用二等分或其他方法进行检查。
If you were trying to collide non-rotating tetrahedra, I'd suggest a taking the Minkowski sum and performing a ray check, but that won't work with rotation.
The best I can come up with is to perform swept-sphere collision using their bounding spheres to give you a range of times to check using bisection or what-have-you.
这是封闭式数学方法的概述。 其中的每个元素都很容易单独表达，如果可以写出来的话，这些元素的最终组合将是一个封闭形式的表达式：
1）四面体每个点的运动方程在其自己的坐标中相当简单系统。 质心 (CM) 的运动将沿着直线平滑移动，角点将绕通过 CM 的轴旋转，此处假设为 z 轴，因此每个角点的方程（参数化为时间，t) 为 p = vt + x + r(sin(wt+s)i + cos(wt + s)j )，其中 v 是质心的矢量速度； r 是 xy 平面上投影的半径； i、j 和 k 是 x、y 和 z 单位向量； x 和 s 表示 t=0 时的起始位置和旋转相位。
2) 请注意，每个对象都有自己的坐标系来轻松表示运动，但为了比较它们，您需要将每个对象旋转到一个公共坐标系中，该坐标系也可能是屏幕的坐标系。 （请注意，不同的坐标系在空间中是固定的，并且不随四面体移动。）因此，确定旋转矩阵并将它们应用于每个轨迹（即每个四面体的点和 CM） 。
3) 现在你有了一个在同一坐标系内的每条轨迹的方程，你需要找到相交的时间。 这可以通过测试从四面体的点到 CM 的任何线段是否与另一个四面体的任何三角形相交来发现。 这也有一个封闭式表达式，可以在此处找到。
将这些步骤分层将产生非常丑陋的方程，但通过计算解决它们并不难（尽管随着四面体的旋转，您需要确保不会陷入局部最小值）。 另一种选择可能是将其插入 Mathematica 之类的东西中来为您进行启动。 （并非所有问题都有简单的答案。）
Here's an outline of a closed-form mathematical approach. Each element of this will be easy to express individually, and the final combination of these would be a closed form expression if one could ever write it out:
1) The equation of motion for each point of the tetrahedra is fairly simple in it's own coordinate system. The motion of the center of mass (CM) will just move smoothly along a straight line and the corner points will rotate around an axis through the CM, assumed to be the z-axis here, so the equation for each corner point (parameterized by time, t) is p = vt + x + r(sin(wt+s)i + cos(wt + s)j ), where v is the vector velocity of the center of mass; r is the radius of the projection onto the x-y plane; i, j, and k are the x, y and z unit vectors; and x and s account for the starting position and phase of rotation at t=0.
2) Note that each object has it's own coordinate system to easily represent the motion, but to compare them you'll need to rotate each into a common coordinate system, which may as well be the coordinate system of the screen. (Note though that the different coordinate systems are fixed in space and not traveling with the tetrahedra.) So determine the rotation matrices and apply them to each trajectory (i.e. the points and CM of each of the tetrahedra).
3) Now you have an equation for each trajectory all within the same coordinate system and you need to find the times of the intersections. This can be found by testing whether any of the line segments from the points to the CM of a tetrahedron intersects the any of the triangles of another. This also has a closed-form expression, as can be found here.
Layering these steps will make for terribly ugly equations, but it wouldn't be hard to solve them computationally (although with the rotation of the tetrahedra you need to be sure not to get stuck in a local minimum). Another option might be to plug it into something like Mathematica to do the cranking for you. (Not all problems have easy answers.)
抱歉，我不是数学爱好者，不知道正确的术语是什么。 希望我的蹩脚术语不会掩盖我的意思太多。
选择一些任意的时间步长。
计算每个形状在垂直于时间步移动轴的二维方向上的边界。
对于时间步：
如果任何两个对象的这些边界的轴相交，则半个时间步长并开始递归。
一种精度越来越高的二分搜索，用于发现有限相交发生的点。
Sorry I'm not a math boff and have no idea what the correct terminology is. Hope my poor terms don't hide my meaning too much.
Pick some arbitrary timestep.
Compute the bounds of each shape in two dimensions perpendicular to the axis it is moving on for the timestep.
For a timestep:
If the shaft of those bounds for any two objects intersect, half timestep and start recurse in.
A kind of binary search of increasingly fine precision to discover the point at which a finite intersection occurs.