在 3d 中找到 2 个任意立方体的交集 [英] Finding the intersection of 2 arbitrary cubes in 3d
问题描述
所以，我想找出一个函数来确定两个任意旋转和大小的立方体是否相交.
So, I'd like to figure out a function that allows you to determine if two cubes of arbitrary rotation and size intersect.
如果立方体的旋转不是任意的(而是锁定在特定轴上)，那么相交很简单；您可以通过检查它们的边界来检查它们是否在所有三个维度中相交，以查看它们是否在所有三个维度中交叉或在彼此内.如果它们交叉或仅在两个范围内，则它们不相交.此方法可用于确定任意立方体是否甚至是交集的候选者，使用它们的最高/最低 x、y 和 z 来创建外边界.
If the cubes are not arbitrary in their rotation (but locked to a particular axis) the intersection is simple; you check if they intersect in all three dimensions by checking their bounds to see if they cross or are within one another in all three dimensions. If they cross or are within in only two, they do not intersect. This method can be used to determine if the arbitrary cubes are even candidates for intersection, using their highest/lowest x, y, and z to create an outer bounds.
这是第一步.从理论上讲，根据这些信息，我们可以分辨出它们在彼此的边"，这意味着我们可以从相交处消除一些四边形(边).但是，我不能假设我们有这些信息，因为立方体的旋转可能很难简单地确定.
That's the first step. In theory, from that information we can tell which 'side' they are on from each other, which means we can eliminate some of the quads (sides) from our intersection. However, I can't assume that we have that information, since the rotation of the cubes may make it difficult to determine simply.
我的想法是取每对四边形，找到它们平面的交点，然后确定该线是否与每对边的至少一条边相交.如果任何一对边有一条与它们的任何边相交的相交线，则四边形相交.如果不相交，则两个立方体不相交.
My thought is to take each pair of quads, find the intersection of their planes, then determine if that line intersects with at least one edge of each of the pairs of sides. If any pair of sides has a line of intersection that intersects with any of their edges, the quads intersect. If none intersect, the two cubes do not intersect.
然后我们可以通过平面相交线与其边缘相交的位置来确定第二个立方体上相交的深度.
We can then determine the depth of the intersection on the second cube by where the plane-intersection line intersects with its edge(s).
然而，这只是推测.有没有更好、更有效的方法来确定这两个立方体的交集?我可以想到许多不同的方法来做到这一点，而且我也可以看出它们在所需的计算量方面可能大不相同.
This is simply speculative, however. Is there a better, more efficient way to determine the intersection of these two cubes? I can think of a number of different ways to do this, and I can also tell that they could be very different in terms of amount of computation required.
我目前正在使用 Java，但 C/C++ 解决方案也很酷(我可以移植它们)；甚至是伪代码，因为这可能是一个大问题.
I'm working in Java at the moment, but C/C++ solutions are cool too (I can port them); even psuedocode since it is perhaps a big question.
推荐答案
要在三个维度上找到两个任意立方体的交(接触)点，你必须分两个阶段来做:
To find the intersection (contact) points of two arbitrary cubes in three dimensions, you have to do it in two phases:
- 检测碰撞.这通常是两个阶段本身，但为简单起见，我们将其称为碰撞检测".
该算法要么是 SAT(分离轴定理)，要么是多面体扩展/减少的一些变体.同样，为简单起见，我们假设您将使用 SAT.
The algorithm will be either SAT (Separating axis theorem), or some variant of polytope expansion/reduction. Again, for simplicity, let's assume you will be using SAT.
我不会详细解释，因为其他人已经做过很多次了，而且比我做的更好.从这里带回家"是，碰撞检测并不是用来告诉你哪里发生了碰撞；只是它已经发生了.
I won't explain in detail, as others have already done so many times, and better than I could. The "take-home" from this, is that collision detection is not designed to tell you where a collision has taken place; only that it has taken place.
- 检测到交叉点后，您需要计算接触点.这是通过多边形裁剪算法完成的.在这种情况下，让我们使用 https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
有更简单、更好的方法来做到这一点，但 SAT 在 3d 中很容易掌握，而且 SH 剪裁也很容易让你了解，所以对你来说是一个很好的起点.
There are easier, and better ways to do this, but SAT is easy to grasp in 3d, and SH clipping is also easy to get your head around, so is a good starting point for you.
这篇关于在 3d 中找到 2 个任意立方体的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
