2

在 3D 网格中检测无效三角形的最快方法是什么？作为无效我的意思是：

  • 零区
  • 三个共线点
  • 两个重叠点

我们目前使用这种 - 非常慢 - 方法：

    if (Area(p1,p2,p3) < 1e-3)

         Debug.WriteLine("Invalid triangle found!");

    public double Area(Point p1, Point p2, Point p3)
    {

        double[,] m = new double[3, 3];

        m[0, 0] = p1.Y; m[0, 1] = p1.Z; m[0, 2] = 1;
        m[1, 0] = p2.Y; m[1, 1] = p2.Z; m[1, 2] = 1;
        m[2, 0] = p3.Y; m[2, 1] = p3.Z; m[2, 2] = 1;

        double det1 = Matrix.Determinant3(m);

        m[0, 0] = p1.Z; m[0, 1] = p1.X; m[0, 2] = 1;
        m[1, 0] = p2.Z; m[1, 1] = p2.X; m[1, 2] = 1;
        m[2, 0] = p3.Z; m[2, 1] = p3.X; m[2, 2] = 1;

        double det2 = Matrix.Determinant3(m);

        m[0, 0] = p1.X; m[0, 1] = p1.Y; m[0, 2] = 1;
        m[1, 0] = p2.X; m[1, 1] = p2.Y; m[1, 2] = 1;
        m[2, 0] = p3.X; m[2, 1] = p3.Y; m[2, 2] = 1;

        double det3 = Matrix.Determinant3(m);

        return Math.Sqrt(det1 * det1 + det2 * det2 + det3 * det3) / 2;


    }

谢谢。

4

2 回答 2

0

面积为零的唯一方法是这些点都是共线的。

尝试以下操作：

p1_p2_slope = (p2.y - p1.y) / (p2.x - p1.x);
p2_p3_slope = (p3.y - p2.y) / (p3.x - p2.x);
if(p1_p2_slope == p2_p3_slope) {
 // points are collinear
}

if(p1.x == p2.x && p1.y == p2.y) {
  // p1 and p2 overlap
}
if(p1.x == p3.x && p1.y == p3.y) {
  // p1 and p3 overlap
}
if(p3.x == p2.x && p3.y == p2.y) {
  // p3 and p2 overlap
}
于 2012-04-12T14:55:58.647 回答
0

我认为这样做

abs(dot(sub(b,a), cross(sub(c,b)))) < epsilon

如果您只想扩展它，我认为它可以解决：

abs((b.x - a.x) * (c.y - b.y) + (b.y - a.y) * (b.x - c.x)) < epsilon
于 2012-04-12T16:34:59.953 回答