Ruizhen Hu
Honghua Li
Abstract
A shape is pyramidal if it has a flat base with the remaining boundary forming a height function over the base. Pyramidal shapes are optimal for molding, casting, and layered 3D printing. However, many common objects are not pyramidal. We introduce an algorithm for approximate pyramidal shape decomposition. The general exact pyramidal decomposition problem is NP-hard. We turn this problem into an NP-complete problem which admits a practical solution. Specifically, we link pyramidal decomposition to the Exact Cover Problem (ECP). Given an input shape S, we develop clustering schemes to derive a set of building blocks for approximate pyramidal parts of S. The building blocks are then combined to yield a set of candidate pyramidal parts. Finally, we employ Knuth's Algorithm X over the candidate parts to obtain solutions to ECP as pyramidal shape decompositions. Our solution is equally applicable to 2D or 3D shapes, and to shapes with polygonal or smooth boundaries, with or without holes. We demonstrate our algorithm on numerous shapes and evaluate its performance.
- Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., and Süsstrunk, S. 2012. SLIC superpixels compared to state-of-the-art superpixel methods. IEEE Trans. Pat. Ana. & Mach. Int. 34, 11, 2274--2282. Google Scholar
Digital Library
- Asafi, S., Goren, A., and Cohen-Or, D. 2013. Weak convex decomposition by lines-of-sight. Computer Graphics Forum (SGP) 32, 5, 23--31. Google ScholarDigital Library
- Calì, J., Calian, D., Amati, C., Kleinberger, R., Steed, A., Kautz, J., and Weyrich, T. 2012. 3D-printing of non-assembly, articulated models. ACM Trans. on Graph (SIGGRAPH Asia) 31, 6, 130:1--130:8. Google ScholarDigital Library
- Chandru, V., Rajan, V. T., and Swaminathan, R. 1992. Monotone pieces of chains. ORSA Journal on Computing 4, 4, 439--446.Google ScholarCross Ref
- Chazelle, B. 1984. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 488--507. Google ScholarDigital Library
- Chvatal, V. 1979. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 3, pp. 233--235. Google ScholarDigital Library
- Cohen-Or, D., Lev-Yehudi, S., Karol, A., and Tal, A. 2003. Inner-cover of non-convex shapes. International Journal of Shape Modeling 9, 2, 223--238.Google ScholarCross Ref
- Douglas, D., and Peucker, T. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer 10, 2, 112--122.Google ScholarCross Ref
- Fekete, S. P., and Mitchell, J. S. B. 2001. Terrain decomposition and layered manufacturing. International Journal of Computational Geometry & Applications 11, 06, 647--668.Google ScholarCross Ref
- Heckbert, P. S., and Garland, M. 1997. Survey of polygonal surface simplication algorithms. In SIGGRAPH Course on Multiresolution Surface Modeling.Google Scholar
- Knuth, D. 2000. Dancing links. Millenial Perspectives in Computer Science, 159--187.Google Scholar
- Li, W., Martin, R. R., and Langbein, F. C. 2009. Molds for meshes: Computing smooth parting lines and undercut removal. IEEE T. Automation Science and Engineering 6, 3, 423--432.Google ScholarCross Ref
- Lien, J.-M., and Amato, N. M. 2007. Approximate convex decomposition of polyhedra. In SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modeling, ACM Request Permissions. Google ScholarDigital Library
- Liu, R., and Ntafos, S. 1988. On decomposing polygons into uniformly monotone parts. Information Processing Letters 27, 2, 85--89. Google ScholarDigital Library
- Luo, L., Baran, I., Rusinkiewicz, S., and Matusik, W. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. on Graph (SIGGRAPH Asia) 31, 6, 129:1--129:9. Google ScholarDigital Library
- McMains, S., and Chen, X. 2005. Finding undercut-free parting directions for polygons with curved edges. Journal of Computing and Information Science in Engineering 6.Google Scholar
- Ochotta, T., and Saupe, D. 2008. Image-based surface compression. Computer Graphics Forum 27, 6, 1647--1663.Google ScholarCross Ref
- Pauly, M., and Gross, M. 2001. Spectral processing of point-sampled geometry. In Proc. of SIGGRAPH, 379--386. Google ScholarDigital Library
- Prévost, R., Whiting, E., Lefebvre, S., and Sorkine-Hornung, O. 2013. Make It Stand: Balancing shapes for 3D fabrication. ACM Trans. on Graph (SIGGRAPH) 32, 4, 81:1--81:10. Google ScholarDigital Library
- Priyadarshi, A., and Gupta, S. K. 2004. Geometric algorithms for automated design of multi-piece permanent molds. Computer-Aided Design 36, 3, 241--260.Google ScholarCross Ref
- Rappaport, D., and Rosenbloom, A. 1994. Moldable and castable polygons. Computational Geometry 4, 219--233. Google ScholarDigital Library
- Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539--1556.Google ScholarCross Ref
- Sharvit, D., Chan, J., Tek, H., and Kimia, B. B. 1998. Symmetry-based indexing of image databases. J. Visual Communication and image representation 9, 366--380.Google Scholar
- Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on 22, 8, 888--905. Google ScholarDigital Library
- Stava, O., Vanek, J., Benes, B., Carr, N., and Měch, R. 2012. Stress relief: improving structural strength of 3D printable objects. ACM Trans. on Graph (SIGGRAPH) 31, 4, 48:1--48:11. Google ScholarDigital Library
- Tor, S. B., and Middleditch, A. E. 1984. Convex decomposition of simple polygons. ACM Trans. on Graph 3, 4 (Oct.), 244--265. Google ScholarDigital Library
- Vazirani, V. V. 2001. Approximation Algorithms. Springer. Google ScholarDigital Library
- Wang, W., Wang, T. Y., Yang, Z., Liu, L., Tong, X., Tong, W., Deng, J., Chen, F., and Liu, X. 2013. Cost-effective printing of 3D objects with skin-frame structures. ACM Trans. on Graph (SIGGRAPH Asia) 32, 6, 177:1--177:10. Google ScholarDigital Library
- Zelnik-Manor, L., and Perona, P. 2004. Self-tuning spectral clustering. In Proc. Advances in Neural Information Processing Systems (NIPS), vol. 17, 1601--1608.Google Scholar
Index Terms
- Approximate pyramidal shape decomposition
Recommendations
Minimum Near-Convex Shape Decomposition
Shape decomposition is a fundamental problem for part-based shape representation. We propose the minimum near-convex decomposition (MNCD) to decompose arbitrary shapes into minimum number of "near-convex" parts. The near-convex shape decomposition is ...
Rectification of the chordal axis transform skeleton and criteria for shape decomposition
Skeletonization and parts-based decomposition are important to the analysis, characterization, and recognition of shapes. In earlier works we proposed the chordal axis transform (CAT), based on constrained Delaunay triangulations (CDT), for analyzing ...
Rectification of the chordal axis transform and a new criterion for shape decomposition
DGCI'05: Proceedings of the 12th international conference on Discrete Geometry for Computer ImageryIn an earlier work we proposed the chordal axis transform (CAT) as a more useful alternative to the medial axis transform (MAT) for obtaining skeletons of discrete shapes. Since then, the CAT has benefited various applications in 2D and 3D shape ...
Comments