Progressive Convex Hull Simplification
This work provides a practical solution for generating tight bounding proxies with controlled complexity, benefiting applications like collision detection and ray intersection.
The paper tackles the problem of conservatively simplifying a convex hull to a specified number of half-spaces while minimizing added volume or surface area, proposing an efficient O(n log n) greedy optimization in the dual representation that outperforms existing methods in efficiency, tightness, and safety.
Convex hulls are useful as tight bounding proxies for a variety of tasks including collision detection, ray intersection, and distance computation. Unfortunately, the complexity of polyhedral convex hulls grows linearly with their input. We consider the problem of conservatively simplifying a convex hull to a specified number of half-spaces while minimizing added volume or surface area. By working in the dual representation, we propose an efficient $O(n \log n)$ greedy optimization. In comparisons, we show that existing methods either exhibit poor efficiency, tightness or safety. We demonstrate the success of our method on a variety of input shapes and downstream application domains.