PDA

View Full Version : Invalid triangle detection

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

Zyx_2000
04-16-2012, 02:24 AM
Since zero area is equivalent to three colinear points, and two overlapping points is a special case of them, it is enough to check if the area is zero. (posting this in case someone else finds this thread and doesn't know it.)

A fast way to compute the area of a triangle is abs((p2 - p1) X (p3 - p1))/2, where X denotes the cross product.

ZbuffeR
04-16-2012, 02:54 AM
For one you can skip the costly sqrt, as well as division, on the last line because you don't need the actual area, but only to know if the surface is larger than epsilon.

devdept
04-16-2012, 05:10 AM
Thanks, but more in general should we work on area or collinear point direction to go faster?

paintmanoj
07-05-2012, 12:47 AM
Hello am completely new to max script. can you please tel me how can i select a vertex through max script. i wanted to use it to find out zero area polygon in scene