在3D中查找2个任意立方体的交点 [英] Finding the intersection of 2 arbitrary cubes in 3d
问题描述
如果立方体在旋转中不是任意的（但锁定到特定轴），则交点很简单;你通过检查它们的边界来检查它们是否在所有三维中相交，以查看它们在所有三个维度中是否交叉或在彼此之内。如果它们交叉或仅在两个之内，则它们不相交。这个方法可以用来确定任意立方体是否是交集的候选对象，用它们的最高/最低x，y和z来创建一个外部边界。
这就是第一步。理论上，根据这些信息我们可以知道它们之间存在哪个边，这意味着我们可以从我们的交集中消除一些四边形（边）。然而，我不能认为我们有这样的信息，因为立方体的旋转可能使得很难简单地确定。
我的想法是把每一对四边形，找到它们的平面的交点，然后确定该线是否与每对边中的至少一条边相交。如果任何一对边具有与其任何边相交的交线，则四边形相交。如果没有相交，则两个立方体不会相交。然后，我们可以确定第二个立方体上相交的深度，即平面相交线与其边缘相交处的深度（s）。
然而，这只是推测性的。有没有更好，更有效的方法来确定这两个立方体的交集？我可以想到很多不同的方法来做到这一点，而且我也可以告诉他们在所需的计算量方面可能会有很大的不同。
我是目前在Java中工作，但C / C ++解决方案也很酷（我可以移植它们）;甚至psuedocode，因为它可能是一个很大的问题。
你应该看看计算机图形学领域。他们有很多手段。例如。 Weiler-Atherton剪切算法。还有许多数据结构可以帮助您轻松完成流程。提及AABB（轴对齐边界框）。
So, I'd like to figure out a function that allows you to determine if two cubes of arbitrary rotation and size intersect.
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.
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.
You should take a look at the field of computer graphics. They have many means. E.g. Weiler–Atherton clipping algorithm. There are also many datastructures that could ease up the process for you. To mention AABBs (Axis-aligned bounding boxes).
这篇关于在3D中查找2个任意立方体的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
