Navigation-Driven Approximate Convex Decomposition


James Andrews, Epic Games
A shape like this furnished dollhouse* (a) has different collision accuracy requirements depending on the expected scale of characters or objects interacting with it. We find the navigable space where characters of a given size could actually fit, and use that space to generate an appropriate collision representation – e.g., (b) a 102-part approximate convex decomposition, appropriate for characters as small as 2% of the house’s width, or (c) a 4-part decomposition for characters at least as wide as the house.


Approximate convex decomposition – approximating a shape by a set of convex hulls – is a popular approach to creating efficient collision representations for games and simulations. Existing algorithms to construct such decompositions are typically driven by general surface- or volume-based error metrics that can’t ignore unreachable internal surfaces nor provide local control over the results. We introduce the problem of navigable approximate convex decomposition: First, define a navigable space for the input shape which other objects in the game or simulation must be able to move through, then find a decomposition which does not overlap that space. We show how to automatically find such navigable space, how to customize it, and we introduce an approximate convex decomposition algorithm that protects it. Our results demonstrate that this approach can generate decompositions that meet application requirements faster and with fewer convex hulls than previous methods, while providing a new level of flexibility in defining what those requirements are.


* Tiny House 3D models by RMTCTRL (CC-BY)