查找是否两个三角形相交或不 [英] Find whether two triangles intersect or not
问题描述
由于2点集合
（（X1，Y1，Z1），（X2，Y2，Z2），（X3，Y3，Z3））和
((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and
（（P1，Q1，R1），（P2，Q2，R2），（P3，Q3，R3）），每个形成在三维空间中的三角形
((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space.
您将如何找出这些三角形是否相交或不？
How will you find out whether these triangles intersect or not?
的一个明显的解决这个问题的方法是找到由每个三角形形成的平面的方程式。如果平面是平行的，那么它们不相交。
One obvious solution to this problem is to find the equation of the plane formed by each triangle. If the planes are parallel, then they don't intersect.
否则，找出由这些平面使用这些平面的法向矢量的交点形成的直线的方程。
Else, find out the equation of line formed by the intersection of these planes using the normal vectors of these planes.
现在，如果这条线位于两个三角形区域的，那么这两个三角形相交，否则不
Now, if this line lies in both of the triangular regions, then these two triangles intersect, otherwise not.
trianglesIntersect(Triangle T1, Triangle T2)
{
if(trianglesOnParallelPlanes(T1, T2))
{
return false
}
Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))
if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1))
{
return true
}
return false
}
既然我知道如何编写上述功能，我应该考虑什么trianglesIntersect的其他实现？
Given that I know how to write the above functions, what other implementations of trianglesIntersect should I consider?
是否有更快的算法来解决这个问题？
Are there faster algorithms that solve this problem?
推荐答案
访问几何交集算法礼貌此表 realtimerendering.com ，看的三角形/三角形交点的条目，并按照参考，例如克里斯特埃里克森，的Real-Time碰撞检测的，172页（一本书，我建议高度。）
Visit this table of geometric intersection algorithms courtesy of realtimerendering.com, look at the entry for triangle/triangle intersections, and follow the references, for example to Christer Ericson, Real-Time Collision Detection, page 172. (A book which I recommend highly.)
的基本思想非常简单。如果两个三角形相交，则一个三角形的任两个边缘相交的另一个（左配置在图中下方），或者每个三角形的一个边缘相交的其他（右配置）。
The basic idea is straightforward. If two triangles intersect, then either two edges of one triangle intersect the other (left configuration in the diagram below), or one edge of each triangle intersects the other (right configuration).
所以执行六条线路段三角形相交测试，看看如果这些配置被找到。
So perform six line segment–triangle intersection tests and see if either of these configurations is found.
现在，你问，你怎么办线段/三角形相交测试？嗯，这很容易。访问该表的几何交集算法，看的线段（线）/三角形交点的条目，并按照参考......
Now, you ask, how do you do a line segment/triangle intersection test? Well, it's easy. Visit this table of geometric intersection algorithms, look at the entry for line segment (ray)/triangle intersections, and follow the references...
（重要的是要提的是上文所述的简单的测试不能正确处理共面的三角形对于许多应用，这并不重要。例如，检测三角形网格之间的碰撞时，共面的情况下是不明确的，因此不没有关系，则返回其结果。但是如果你的应用程序是一个例外，你需要检查，作为一个特殊的情况下，或在埃里克松阅读一些其他的方法，例如，<一个href="http://stackoverflow.com/questions/4226319/collision-with-shapes-other-than-rectangles/4228915#4228915">separating-axis法或托马斯·默勒的<一个href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.9981&rep=rep1&type=pdf">interval重叠法。）
(It's important to mention that the simple test outlined above doesn't handle coplanar triangles correctly. For many applications this does not matter: for example, when detecting a collision between meshes of triangles, the coplanar cases are ambiguous so it does not matter which result is returned. But if your application is one of the exceptions, you'll need to check for that as a special case, or read on in Ericson for some other methods, for example, the separating-axis method, or Tomas Möller's interval overlap method.)
这篇关于查找是否两个三角形相交或不的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
