How to check for convexity of a 3d mesh?

Question

Is there a fast way to do this? Searching online shows convexity of functions or single polygons. But I need the ability to check this for the whole model. An object can have convex faces but can be concave as a whole like a torus.

Answer 1

Kneejerk: if you build a leafy BSP tree and end up with all your geometry at one node, the object is convex.

Slightly smarter way to approach the same solution: for each polygon, get the hyperplane. Make sure every vertex in the model is behind that hyperplane.

Equivalently: check the line segment between every pair of vertices; if it doesn't intersect any faces then the object is convex.

I guess you could also get the convex hull, via quickhull or whatever, and compare it to the original object. Or, similarly, get the convex hull and check that every vertex of the original object lies on a face of the hull.

Answer 2

For every face, compute the equation of the plane of support and check that all vertices* yield the same sign when plugged in the plane equation.

Will take time O(F.V), for F faces and V vertices.

*For safety, disregard the vertices of the face being processed.

Alternatively, compute the 3D convex hull, in time O(V.Log(V)). If at any stage in the algorithm a vertex gets discarded, then the polyhedron was not convex.

Answer 3

bool IsConvex(std::vector<vec3> &points, std::vector<int> &triangles, float threshold = 0.001)
{
    for (unsigned long i = 0; i < triangles.size() / 3; i++)
    {
        vec3 Atmp = points[triangles[i * 3 + 0]];
        vec3 Btmp = points[triangles[i * 3 + 1]];
        vec3 Ctmp = points[triangles[i * 3 + 2]];

        btVector3 A(Atmp.x, Atmp.y, Atmp.z);
        btVector3 B(Btmp.x, Btmp.y, Btmp.z);
        btVector3 C(Ctmp.x, Ctmp.y, Ctmp.z);
        B -= A;
        C -= A;

        btVector3 BCNorm = B.cross(C).normalized();

        float checkPoint = btVector3(points[0].x - A.x(), points[0].y - A.y(), points[0].z - A.z()).dot(BCNorm);

        for (unsigned long j = 0; j < points.size(); j++)
        {
            float dist = btVector3(points[j].x - A.x(), points[j].y - A.y(), points[j].z - A.z()).dot(BCNorm);
        
            if((std::abs(checkPoint) > threshold) && (std::abs(dist) > threshold) && (checkPoint * dist < 0))
            {
                return false;
            }
        }
    }

    return true;
}