devdept

04-16-2012, 12:17 AM

What is the fastest way to detect an invalid triangle in a 3D Mesh?

With invalid I mean:

• zero area

• three collinear points

• two overlapping points

We currently use this - very slow - approach:

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;

}

Thanks,

Alberto

With invalid I mean:

• zero area

• three collinear points

• two overlapping points

We currently use this - very slow - approach:

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;

}

Thanks,

Alberto