Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 5 of 5

Thread: Invalid triangle detection

  1. #1
    Advanced Member Frequent Contributor
    Join Date
    Dec 2005
    Location
    Italy
    Posts
    655

    Invalid triangle detection

    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:

    Code :
        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

  2. #2
    Intern Contributor
    Join Date
    Sep 2010
    Posts
    74

    Re: Invalid triangle detection

    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.

  3. #3
    Super Moderator OpenGL Lord
    Join Date
    Dec 2003
    Location
    Grenoble - France
    Posts
    5,580

    Re: Invalid triangle detection

    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.

  4. #4
    Advanced Member Frequent Contributor
    Join Date
    Dec 2005
    Location
    Italy
    Posts
    655

    Re: Invalid triangle detection

    Thanks, but more in general should we work on area or collinear point direction to go faster?

  5. #5
    Junior Member Newbie
    Join Date
    Jul 2012
    Posts
    1
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •