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.
Abstract
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.
