How to find out whether a triangle mesh is concave or not?

Question

Given a three dimensional triangle mesh, how can I find out whether it is convex or concave? Is there an algorithm to check that? If so it would be useful to define a tolerance range to ignore small concavities.

^{Image Source: http://www.rustycode.com/tutorials/convex.html}

Answer 1

A convex polyhedron may be defined as an intersection of a finite number of half-spaces. These half-spaces are in fact the facet-defining half-space.

EDIT: Assuming your mesh actually defines a polyhedron (i.e. there is an "inside" and an "outside")

You can do something like this (pseudocode):

for each triangle
    p = triangle plane
    n = normal of p (pointing outside)
    d = distance from the origin of p
    //Note: '*' is the dot product.
    //so that X*N + d = 0 is the plane equation
    //if you write a plane equation like (X-P)*n = 0 (where P is any point which lays in the plane), then d = -P*n (it's a scalar).

    for each vertex v in the mesh
         h = v*N + d
         if (h > Tolerance) return NOT CONVEX
         //Notice that when v is a vertex of the triangle from which n and d come from,
         //h is always zero, so the tolerance is required (or you can avoid testing those vertices)
    end
end
return CONVEX

Answer 2

For a simple polygon as you described it, you can check for every inner angle at every vertice and check if the angle is below 180 degrees. If so, there is no way it is concave. If a single vertice is over 180°, it is concave.

Edit: for 3D meshes the same idea applies, but you have to test at every vertex every single triangle to each other whether the angle between the triangles is higher or lower than 180°