Strategies for polyhedral surface decomposition: an experimental study. (English) Zbl 1133.52305
From the text: This paper addresses the problem of decomposing a complex polyhedral surface into a small number of “convex” patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and in the second half an experimental search for good heuristics is undertaken. The authors implement 8 different heuristics and test them on the objects in a library of interesting polyhedral bodies. The results show clear advantage of some of these heuristics over the others; in particular, they conclude that the so-called flood-and-retract heuristic should be the method of choice in practical problems.
MSC:
| 52B55 | Computational aspects related to convexity |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Citations:
Zbl 0869.00047References:
| [1] | Amenta, N.; Levy, S.; Munzner, T.; Phillips, M.: Geomview: A system for geometric visualization. Proc. 11th ann. ACM sympos. Comput. geom., C12-C13 (1995) |
| [2] | Aronov, B.; Sharir, M.: Triangles in space or building (and analyzing) castles in the air. Combinatorica 10, 137-173 (1990) · Zbl 0717.68099 |
| [3] | Aronov, B.; Sharir, M.: Castles in the air revisited. Discrete comput. Geom. 12, 119-150 (1994) · Zbl 0805.52005 |
| [4] | Bajaj, C. L.; Dey, T. K.: Convex decompositions of polyhedra and robustness. SIAM J. Comput. 21, 339-364 (1992) · Zbl 0747.68093 |
| [5] | Bern, M.: Compatible tetrahedralizations. Proc. 9th ann. ACM sympos. Comput. geom., 281-288 (1993) · Zbl 0815.68113 |
| [6] | Bern, M.; Eppstein, D.: Mesh generation and optimal triangulation. World scientific series in computer science, 23-90 (1992) |
| [7] | Bern, M.; Eppstein, D.; Gilbert, J.: Provably good mesh generation. Proc. 31st ann. IEEE sympos. Found. comput. Sci., 231-241 (1990) · Zbl 0799.65119 |
| [8] | Chazelle, B.: Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 488-507 (1984) · Zbl 0545.68031 |
| [9] | Chazelle, B.; Dobkin, D. P.; Shouraboura, N.; Tal, A.: Convex surface decomposition. Proc. 11th ann. ACM sympos. Comput. geom., V9-V10 (1995) |
| [10] | Chazelle, B.; Palios, L.: Triangulating a nonconvex polytope. Discrete comput. Geom. 5, 505-526 (1990) · Zbl 0701.68038 |
| [11] | Chazelle, B.; Palios, L.: Decomposing the boundary of a nonconvex polytope. Proc. 3rd scandinavian workshop on algorithm theory, 364-375 (1992) |
| [12] | Chazelle, B.; Palios, L.: Decomposition algorithms in geometry. Algebraic geometry and its applications, 419-447 (1994) · Zbl 0807.68093 |
| [13] | Chazelle, B.; Shouraboura, N.: Bounds on the size of tetrahedralizations. Proc. 10th ann. ACM sympos. Comput. geom., 231-239 (1994) · Zbl 0841.68119 |
| [14] | Dobkin, D. P.; Kirkpartick, D. G.: Fast detection of polyhedral intersection. Theor. comput. Sci. 27, 241-253 (1983) · Zbl 0553.68033 |
| [15] | . Comput. graph. 14, 124-133 (1980) |
| [16] | Mitchell, S.; Vavasis, S.: Quality mesh generation in three dimensions. Proc. 8th ann. ACM sympos. Comput. geom., 212-221 (1992) |
| [17] | O’rourke, J.: Art gallery theorems and algorithms. (1987) · Zbl 0653.52001 |
| [18] | Ruppert, J.; Seidel, R.: On the difficulty of triangulating three-dimensional non-convex polyhedra. Discrete comput. Geom. 7, 227-253 (1992) · Zbl 0747.52009 |
| [19] | Schröder, P.; Hanrahan, P.: On the form factor between two polygons. Proc. SIGGRAPH ’93, 163-164 (1993) |
| [20] | . Comput. graph. 27, 321-334 (1993) |
| [21] | Tal, A.; Dobkin, D. P.: Visualization of geometric algorithms. IEEE trans. Visual. comput. Graphics 1, 194-204 (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
