三角形 – 三角交点测试
我想知道是否有一些教程或指南来理解和实现3D环境中的三角形 – 三角形交叉测试。 (我不需要知道交叉点发生的确切位置,但只知道交叉点已经发生)
我打算按照理论的pdf来实现它,但我很沮丧
- 三角形的计算平面方程2。
- 如果三角形1的所有点都在同一侧,则拒绝为微不足道。
- 三角形的计算平面方程1。
- 如果三角形2的所有点都在同一侧,则拒绝为微不足道。
- 计算交叉线和项目到最大轴。
- 计算每个三角形的间隔。
- 相交间隔。
本指南的第5点。 我真的不知道在问什么(所有5,6和7)。 XD
因为我没有很高的数学知识(好吧,我知道大学的几门考试给了我(我是一名原始程序员XD)),请尽量让我尽可能简单。 :D(我试图在谷歌搜索,但大多数链接指向大约4-5页的公式,我真的不知道,我不明白。)
谢谢您的帮助
你说:
我想知道是否有一些教程或指南来理解和实现3D环境中的三角形 – 三角形交叉测试。
然后你说:
大多数链接指向大约4-5页的完整公式,我真的不在乎
我注意到这两个陈述完全相互矛盾。 那是哪个呢? 您想了解三角形 – 三角形交叉点的工作原理,还是只想要一个有效但无法理解的实现?
这并不像所有那些网页都充满了不必要的数学。 所有数学都是理解交集算法如何工作所必需的 。 从头开始,了解所有工作原理。
一旦你知道单词的含义,步骤5,6和7就很容易理解。 交叉线是由两个平面的交点形成的线。 每个三角形都在一个平面上。 有三种情况:
- 这些平面是平行的,不相交。 三角形显然不相交。
- 飞机是同一架飞机。 三角形可能会遇到也可能不会。
- 飞机是两个不同的飞机,在一条线上相遇。 如果三角形相交,它们显然必须在该线上相交。
假设我们处于第三种情况。 计算第一个三角形中包含的交叉线的线段。 计算第二个三角形中的交叉线的线段。 现在的问题是“这些细分是否重叠?”
您可以通过将线段投影到方便的轴上,并查看该轴上的线段是否重叠来解决这个问题。 基本上,它的工作原理如下:想象一下你在线段上照射一个光线,使它们的阴影落在一个轴上。 如果轴上的阴影相交,则线段必须相交。 如果轴上的阴影之间存在间隙,则显然线段之间必须存在间隙,因此三角形不相交。
如果你想了解它是如何工作的,那么就无法理解你需要了解所有这些东西 – 所有代数都能解决平面如何交叉以及项目如何在轴上工作的问题。 这一切都是必要的。 所有这些东西都是基本的构建块,其中将构建更复杂的转换,投影等,因此如果您想要更进一步,请彻底了解基础知识。
我的回答很简单……这个问题在任意坐标系中都很难,所以把它改成让问题容易的东西。 xna中的Matrix类具有CreateLookAt函数,可用于在所有顶点上创建有用的转换。
以下示例未进行优化,仅为了解解决方案而编写。 可以删除exception及其相应的if语句以及一些向量转换。
public static bool CheckColision(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c) {//rotates each edge of the first triangle to the Z axis and checks the second triangle against it then repeats with the second one against the first, and lastly checks to see if all points of the second triangle are on the same side as the first if(! CheckColisionLookAt(t1a, t1b, t1c, t2a, t2b, t2c)) return false; if (!CheckColisionLookAt(t1b, t1c, t1a, t2a, t2b, t2c)) return false; if (!CheckColisionLookAt(t1c, t1a, t1b, t2a, t2b, t2c)) return false; if (!CheckColisionLookAt(t2a, t2b, t2c, t1a, t1b, t1c)) return false; if (!CheckColisionLookAt(t2b, t2c, t2a, t1a, t1b, t1c)) return false; if (!CheckColisionLookAt(t2c, t2a, t2b, t1a, t1b, t1c)) return false; return CheckColisionAllOnOneSide(t1a, t1b, t1c, t2a, t2b, t2c); } public static bool CheckColisionAllOnOneSide(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c) {//simply performs a transformation to check if all points on one triangle are on the same side of the other triangle Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a); t2a = Vector3.Transform(t2a, m); t2b = Vector3.Transform(t2b, m); t2c = Vector3.Transform(t2c, m); if (t2a.X < 0 && t2b.X < 0 && t2c.X < 0) return false; if (0 < t2a.X && 0 < t2b.X && 0 < t2c.X) return false; return true; } public static bool CheckColisionLookAt(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c) {//performs a transformation and checks if all points of the one triangle are under the other triangle after the transformation Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a); t1a = Vector3.Transform(t1a, m);// (0, 0, 0) if ( ZERRO < Math.Abs(t1a.X)|| ZERRO < Math.Abs(t1a.Y) || ZERRO < Math.Abs(t1a.Z)) throw new Exception(); t1b = Vector3.Transform(t1b, m);// (0, 0, maxZ) if (ZERRO < Math.Abs(t1a.X) || ZERRO < Math.Abs(t1a.Y)) throw new Exception(); t1c = Vector3.Transform(t1c, m);// (0, maxY, someZ) if (ZERRO < Math.Abs(t1a.X)) throw new Exception(); t2a = Vector3.Transform(t2a, m); t2b = Vector3.Transform(t2b, m); t2c = Vector3.Transform(t2c, m); if (t2a.Y < 0 && t2b.Y < 0 && t2c.Y < 0) return false; return true; }
这是一个包含许多交叉点参考的网站:
实时渲染对象/对象交点
以下是他们为Tri / Tri列出的内容:
Möllerjgt2(2) ;
jgt 2(4) ;
GTweb ;
Möller ;
GPG p.393;
GTCG第539页;
TGS ;
RTCD第155,172页;
沉jgt 8(1) ;
Guigue jgt 8(1) ;
SoftSurfer ;
实时渲染,第2版p.590;
Real-Time Rendering,第3版p.757
我想你有三角形顶点的x,y坐标。 例如。
对于Triangle A:
1.边A1:xa1,ya1 2.边A2:xa2,ya2 3.边A3:xa3,ya3为三角B:
1.边B1:xb1,yb1 2.边B2:xb2,yb2 3.边B3:xb3,yb3
如果它们的线的任何组合相互交叉,则三角形相交。 如果A1与B1或B2或B3相交,或者如果A2与B1或B2或B3相交,或者如果A3与B1或B2或B3相交,则表示含义。
因此,如果两条线相交,则需要算法。 这是我发现的最简单的例子: http : //www.mathopenref.com/coordintersection.html
您发布的方法看起来像是使用类似于此算法的东西来检测凸多边形是否相交,基于分离轴定理。 这不是很难理解。
如果可以在两个多边形之间绘制一条称为分离轴的线,则它们不会相交。 每个多边形的每个边缘是候选分离轴。 将多边形投影到垂直于该轴的矢量上,并测试1D范围的重叠。 如果没有1D重叠,则当前边缘是分离轴,并且两个多边形不相交。 如果存在1D重叠,则结果是不确定的,直到已经测试了所有候选边缘,此时得出两个多边形确实相交的结论。 请注意,允许两个多边形共享边缘。