Approximate Convex Decomposition for 3D Meshes with
Collision-Aware Concavity and Tree Search
by XINYUE WEI, MINGHUA LIU, ZHAN LING, HAO SU
Approximate convex decomposition of #polyhedra is a very important problem in #gamedev, #virtualreality, #3d.
Convex objects allow us to test if a point is in that object in \(O\log(n)\). This operation is used to check if an object is colliding with another. Unfortunately, the objects that we manage are rarely convex, so most of the times developers tend to approximate the mesh of a model into a convex one (a cube, sphere, etc).
In the most representative cases, a #convex decomposition happens -> we divide the domain of the mesh into convex ones. What happens? If the mesh is very complex, we can have a very high of convex meshes! More colliders for the scene 🤯
For that reason there are methods to have approximate convex decompositions, convex decompositions that "look like" the original one in order to respect its collision properties.
You can read the paper in more detail here: https://arxiv.org/pdf/2205.02961.pdf
#research #math #geometry #collision #physics #computerscience #paper
