How to determine concavity?

I don’t mean to post a “How do I do this?”, but I’m somewhat stumped.

How do you best determine if a given vertex lies within a concave region of a closed 3d surface?

Any help would be appreciated.


It’s a lovely problem. I came across it while writing my unfolder. The method I found was to visit each face using a tree-shaped motion (recursively visit a face’s neighbours) while tracking the angle between neighbouring faces’ normals; when the angle flips sign (or >pi ) then the current face is on a boundary between convex & concave regions and you can mark faces (& their verts) from there.
Another method might be (although I can see problems) to take the convex hull and just find verts that don’t lie on it. But that wouldn’t be able to deal with overhangs.

OK. That’s very good. However, I was hoping for something different. What, I’m not sure.
Perhaps I should re-word my question.

How do you determine which direction to translate a vertex (or vertices) in order to move it “inside” the object?

I was hoping for a solution that was independent from face normals (which do not always point the way one would want them to). You might say I want an algorithm similar to what may be used in the “calculate normals outside” function, but for vertices instead of faces.

Thanks again!