查找两个三角形是否相交或不

（（X1，Y1，Z1），（X2，Y2，Z2），（X3，Y3，Z3））和

（（p1，q1，r1），（p2，q2，r2），（p3，q3，r3））在3D空间中形成三角形。

如何找出这些三角形是否相交？

这个问题的一个明显的解决方案是找到由每个三角形形成的平面方程。如果平面平行，则它们不相交。

否则，用这些平面的法向矢量找出由这些平面相交形成的直线方程。

现在，如果这条线位于两个三角形区域中，那么这两个三角形相交，否则不相交。

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的其他实现？

有没有更快的算法来解决这个问题？访问礼貌realtimerendering.com

来源

2011-08-18 Atishay

尝试询问[math.stackexchange.com]（http://math.stackexchange.com））代替。 SO是编程问题。 – PengOne

http://www.applet-magic.com/trintersection.htm – Jacob

+17

我很失望，这个问题已经结束。这是一个众所周知的编程问题，在计算机图形学，光线追踪，视频游戏等方面出现。我已经不止一次地编写了它。这怎么可能成为题外话题？ –

this table of geometric intersection algorithms，看看在三角形/三角形交叉进入，并遵循引用，例如克里斯特埃里克森，Real-Time Collision Detection，172页（一本书，我建议高度。）

的基本想法很简单。如果两个三角形相交，则一个三角形的任意两个边相交（下图中的左边配置），或者每个三角形的一个边相交（右边的配置）。

enter image description here

所以执行的六个线段 - 三角形相交测试，看看是否任一这些结构的发现。

现在，你问，你怎么做一个线段/三角形的交叉点测试？好吧，这很容易。请访问this table of geometric intersection algorithms，查看线段（射线）/三角形交点的条目，并参考参考文献...

（重要的是要提到上面简单的测试不能正确处理共面三角形。这并不重要：例如，当检测到三角形网格之间的碰撞时，共面情况是不明确的，因此返回哪个结果并不重要，但是如果您的应用程序是例外情况之一，则需要检查作为一种特殊情况，或者在Ericson上阅读其他一些方法，例如separating-axis method或TomasMöller的interval overlap method。）

来源

2011-08-19 20:12:48

共面三角形（相当容易用平面方程检测，用normal1 == normal2 __and__ d1 == d2）可以很容易地用[ptInPoly测试使用重心坐标]进行测试（http://gamedev.stackexchange.com/questions/23743/什么是最有效的方式找到重心坐标）在所有三角形的角落。 – bobobobo

顺便说一下，[穆勒的区间重叠方法在这里]的C代码（http://web.archive.org/web/19990203013328/http://www.acm.org/jgt/papers/Moller97/tritri.html ）。 – bobobobo

查找两个三角形是否相交或不

回答

相关问题