Question How to check if a mesh is concave?

I'm generating meshes dynamically and applying physics to them, which isn't supported for concave mesh colliders, so I have to check the convex box in the mesh collider. This works fine for convex meshes but not for concave meshes so, if I can detect if the mesh is concave, I'd like to run a script on them to convert them to multiple convex colliders instead.

Are there any built-in or straightforward methods to determining if a mesh is concave or convex?


Concave mesh collider (won't work with a Rigidbody)

Convex box checked (not ideal for this concave mesh)

After running script to generate multiple convex colliders

 

This might not be trivial to solve, especially efficiently. But you could do something relatively simple (brute force) like use raycasting to to test the count of hits. Cast a ray through every vertex from the geometric center of the mesh. If any of these raycasts hit the mesh surface twice (i.e. the ray enters and exits the mesh), the mesh is concave.

But since you are generating your own meshes, couldn't you use some sort of case-by-case solutions that are simple? i.e. in the case of that tree-like structure, place capsules or boxes between nodes of your structure?

 

If any two triangles which share an edge have converging normals, the whole mesh is concave. If you have the midpoints Am and Bm and normals An and Bn of triangle A and B, then the dot product of (Bm-Am) and (An) would be positive [ and so would (Am-Bm) vs (Bn) ] if their normals converged.

 

I'm generating the meshes using the Marching Cubes algorithm, so I do have access to the 16x16x16 grid of voxels used to generate each mesh. I have it visualized in the below screenshot with red spheres at the "empty" voxels and gray spheres at the "solid" voxels (hard to see in the screenshot, but you can see a few gray spheres sticking out).

Maybe there's a more efficient way of determining if the mesh is concave using this grid of points?

 

I did come up with a fairly rudimentary method that seems to work for what I want:

1. Find the "outlier" solid voxels in the grid (furthest solid voxels in each direction)
2. For each outlier voxel, count the number of empty voxels between it and the other outlier voxels
   • I use a form of Bresenham's algorithm to get the integer points between them
   • I exclude empty voxels that are next to solid voxels to allow for some error. For example, the trunk of the tree would be considered concave otherwise, because it's not at an exact 45 degree angle for all of the voxels to pass through it
3. The number of empty voxels returned is how concave it is, in a sense

The blue spheres in the image below represent the empty voxels found between the "outlier" voxels and indicate where it found the mesh to be concave (note the tree is divided into chunks, so these are not the points that would be found for the tree mesh as a whole):

 

This is a really nice walk down the theoretical algorithm trail, don't get me wrong. Hopefully it's of use to you.

But the only thing that matters to Unity in regards to the physics efficiency is whether or not the Mesh Collider has the flag

.m_Convex

turned on. If you give the physics engine a mesh that you think is convex, and flag the Mesh Collider to tell it to use it as if it were a Convex mesh, it will do its own checking to see if it's true, and also if it has few enough sides, and if it has the slightest inclination to believe it might not be compliant with its own undocumented little rules, it will do a reduction and convex hull pass on your mesh's vertices and construct a whole new mesh all by itself, and use it instead.