We propose an optimization framework for computing guarding and star decomposition of 3D shapes/regions based on a progressive integer linear programming (PILP) scheme. The guarding (visibility coverage) problem and star decomposition in 3D have broad applications in graphics and robotics. Despite its importance, seeking their optimal solutions is highly challenging and little explored for general 3D models. Based on the intuition that shape skeleton possesses great visibility, we convert this optimal guarding to a set-covering problem. An efficient progressive integer linear programming (PILP) scheme is developed, on multi-resolutional shape tessellations and skeletons, to solve the optimal set of guarding points. These guarding points provide natural seeds for region growing in the computation of star decomposition of the model. We explore their applications of guarding and star decomposition in graphics (morphing, shape retrieval) and robotics (autonomous environment inspection).
[ Paper (to appear soon) | Slides (to appear soon) | Bibtex ]
This paper proposes an effective framework to compute the visibility guarding and star decomposition of 3D solid shapes. We propose a progressive integer linear programming algorithm to solve the optimal set of guarding points that can visibility cover the entire region; we also develop a constrained region growing scheme seeded on these guarding points to get the star decomposition. We demonstrate this guarding/decomposition framework can benefit graphics tasks such as shape interpolation and shape matching/retrieval.