三角形-三角形相交测试

你说:

我想知道外面有没有 并实现一个三角形

然后你说:

满页的公式我真的不知道 想知道吗

我注意到这两种说法完全相互矛盾。那是哪一个呢?您是想了解三角形交集是如何工作的,还是只是想要一个可以工作但您不了解的实现?

并不是所有的网页都充满了 数学。所有的数学都是 必要的

一旦你知道这些词的意思,步骤5、6和7就很容易理解了。交线是两个平面的交线。每个三角形位于一个平面上。有三种情况:

• 这些飞机是同一架飞机。三角形可能相交,也可能不相交。
• 这些平面是在一条直线上相交的两个不同平面。如果三角形相交,它们显然必须在那条线上相交。

通过将线段投影到方便的轴上,并查看该轴上的线段是否重叠,可以解决此问题。基本上,它是这样工作的:假设您在线段上照射灯光,使其阴影落在轴上。如果轴上的阴影相交,则线段必须相交。如果轴上的阴影之间存在间隙,则直线段之间显然必须存在间隙,因此三角形不相交。

如果你想了解它是如何工作的,那么就不能回避你需要了解的事实 全部的 这些东西——所有计算平面如何相交以及投影到轴上的代数。这都是必要的。所有这些都是基本的构建块,更复杂的转换、投影等等都将从这些构建块中构建出来,所以如果你想走得更远,就要彻底理解这些基础。

下面的示例不是优化的,它只是为了理解解决方案而编写的。异常及其相应的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;
    }

这是一个包含许多交叉点参考的网站:

Real-Time Rendering Object/Object Intersection Page

以下是Tri/Tri的列表:

Möller jgt 2(2) ;
Held jgt 2(4)
GTweb ;
Möller ;
GPGp.393;
GTCGp.539;
TGS
RTCDp.155172;
Shen jgt 8(1) ;
Guigue jgt 8(1) ;
SoftSurfer ;
实时渲染,第二版,第590页;

我假设你有三角形顶点的x,y坐标。 如。
对于三角形A:
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

您发布的方法似乎使用了类似于 this algorithm 基于分离轴定理,检测凸多边形是否相交。这不难理解。

如果可以在两个多边形之间绘制一条称为分离轴的线,则它们不会相交。每个多边形的每条边都是候选分离轴。多边形投影到垂直于该轴的向量上,并测试1D范围的重叠。如果没有1D重叠,则当前边是分离轴,两个多边形不相交。如果存在1D重叠,则在测试所有候选边之前,结果是不确定的,此时可以得出两个多边形确实相交的结论。请注意,允许两个多边形共享一条边。