3D Region Guarding and Star Decomposition

Wuyi Yu, Xin Li, "Computing 3D Shape Guarding and Star Decomposition," Computer Graphics Forum (CGF),, Volume 30, Issue 7, pages 2087¨C2096, 2011.

[Paper| Slides | 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.

Wuyi, Xin Li,"Computing Optimal Guarding and Star Decomposition of 3D Models,"SIGGRAPH 2011, Poster.

[Abstract | Poster | Video]

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

Please email xinli@cct.lsu.edu to obtain the executable program.

[ Download Executable | An Example 3D Model ]

Software Usage

This program computes a set of guarding points from (1) an input surface mesh and (2) its skeleton nodes.

You need a skeletonization software to compute the skeleton. For example, in our paper, we used: http://www.cse.ohio-state.edu/~tamaldey/cskel.html We are developing effective heuristic skeletonization algorithms for region guarding.

Usage: Guarding.exe input_mesh.obj skeletons config guards.cm

input_mesh.obj: The file name of the triangle mesh (in OBJ format).

skeletons: The skeleton file. Each line is a skeleton node, following the format: x y z, where x, y, z is the coordinate of the skeleton node.

config: The configure file indicates the number of faces for each resolution mesh. For example, a config file with 2000 10000 20000 means that there are three resolutions for the mesh, with face number 2000, 10000, 20000 respectively.

guards.cm: The output guards file. The format is the same as the skeletons.

Run the test data:

1. Download the executable and the test data, then unzip them into the same directory;

2. Run "Guarding.exe david.obj david.skc conf david.txt";

3. The result is david.txt.

Please contact xinli@cct.lsu.edu if you have questions in executing this program.