On finding large empty convex bodies in 3D scenes of polygonal models

This paper presents a method for finding large empty convex bodies within a 3D scene of polygonal models. The convex bodies we pack are discrete orientation polytopes (k-dops) with a small number of facets. The algorithm searches for a large empty k-dop within the scene, using a combination of random sampling and physical simulation, allowing the body to grow and interact (via rotation, translation, and scaling) with the environment when collisions are detected. We pack multiple empty k-dops in a 3D scene using a greedy incremental approach, attempting to maximize the volume of each new body found. We demonstrate the practicality of our method experimentally, showing that it is fast and that it does an effective job of packing on a variety of models.