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}

Kingdom

Here is a similar question. The second comment should help you. gamedev.stackexchange.com/questions/53142/… – Starlike

It's a NP Hard problem, so you just have to test every point with every other. – Logy

possible duplicate of How do determine if a polygon is complex/convex/nonconvex? – Impure

@PeterWood. That is a similar problem, but doesn't help here. My question is about 3d meshes, which vertices aren't in any given order. – Kingdom

@AntonRoth. Isn't there a faster way? – Kingdom

@Kingdom The Wikipedia article says it can be extended to higher dimensions. – Impure

@PeterWood The Wikipedia article also says that it's an algorithm for computing the convex hull. I don't need a convex hull nor to decompose the mesh. I just want a boolean result whether the mesh is concave or convex. – Kingdom

Well, for a polygon like that it should be possible to determine concave quite easily actually. Check every corner if there is an angle above 180 deg or not. If above 180, its concave, if below 180, its convex. This though gets close to impossible for 3D meshes. – Logy

@PeterWood As Anton Roth pointed out, there is a big difference between my question and the one you mentioned as duplicate. – Kingdom

there's no difference for 3d mesh. Just make sure that every face normalized vector is pointed outside of mesh (using counter-clockwise point placemetnt) – Loyola

@Loyola I'm not sure if I completely understand how this should work in 3d. Are there any research papers? – Kingdom

@Kingdom concave doesn't mean non-convex, it is a different concept. – Davison

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

Parmer

Honestly, I am not 100% sure about this. – Parmer

Thanks sbabbi, that looks great. Yes, my meshes have an inside and an outside, otherwise they couldn't be convex at all. But I haven't understand p * n + d = 0. Isn't a plane defined by (x - p) * n = 0? Is d a vector or a scalar? Do you mean by p = triangle plane that p is the origin vector? By the way, the tolerance isn't required by your algorithm and could be zero since a not concave mesh is allowed to contain collinear vertices. But it's nice to have to tolerance range in my case. – Kingdom

@danijar. Edited the answer with some clarifications. The tolerance is required to be nonzero because due to floating point approximation, you can't be sure that h will be exactly zero when you are testing the vertices which make the plane itself. – Parmer

Thanks for clarification, but isn't the plane X * N - d = 0 then, instead of plus? Got the thing about floating point precision. – Kingdom

@Kingdom Yes, fixed that too. – Parmer

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°

Logy

I read your edit. Assuming that I know whether the angles to all other triangles are higher or lower than 180 degrees, how does that lead to a classification of convex or concave? – Kingdom

If the angle inside the object is smaller 180, its convex. – Logy