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