“Approximate pyramidal shape decomposition” by Hu, Li, Zhang and Cohen-Or
Conference:
Type(s):
Title:
- Approximate pyramidal shape decomposition
Session/Category Title: 3D Printing
Presenter(s)/Author(s):
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.
References:
1. 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.
2. Asafi, S., Goren, A., and Cohen-Or, D. 2013. Weak convex decomposition by lines-of-sight. Computer Graphics Forum (SGP) 32, 5, 23–31.
3. 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.
4. Chandru, V., Rajan, V. T., and Swaminathan, R. 1992. Monotone pieces of chains. ORSA Journal on Computing 4, 4, 439–446.Cross Ref
5. Chazelle, B. 1984. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 488–507.
6. Chvatal, V. 1979. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 3, pp. 233–235.
7. 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.Cross Ref
8. 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.Cross Ref
9. Fekete, S. P., and Mitchell, J. S. B. 2001. Terrain decomposition and layered manufacturing. International Journal of Computational Geometry & Applications 11, 06, 647–668.Cross Ref
10. Heckbert, P. S., and Garland, M. 1997. Survey of polygonal surface simplication algorithms. In SIGGRAPH Course on Multiresolution Surface Modeling.
11. Knuth, D. 2000. Dancing links. Millenial Perspectives in Computer Science, 159–187.
12. 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.Cross Ref
13. 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.
14. Liu, R., and Ntafos, S. 1988. On decomposing polygons into uniformly monotone parts. Information Processing Letters 27, 2, 85–89.
15. 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.
16. 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.
17. Ochotta, T., and Saupe, D. 2008. Image-based surface compression. Computer Graphics Forum 27, 6, 1647–1663.Cross Ref
18. Pauly, M., and Gross, M. 2001. Spectral processing of point-sampled geometry. In Proc. of SIGGRAPH, 379–386.
19. 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.
20. Priyadarshi, A., and Gupta, S. K. 2004. Geometric algorithms for automated design of multi-piece permanent molds. Computer-Aided Design 36, 3, 241–260.Cross Ref
21. Rappaport, D., and Rosenbloom, A. 1994. Moldable and castable polygons. Computational Geometry 4, 219–233.
22. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.Cross Ref
23. 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.
24. Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on 22, 8, 888–905.
25. 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.
26. Tor, S. B., and Middleditch, A. E. 1984. Convex decomposition of simple polygons. ACM Trans. on Graph 3, 4 (Oct.), 244–265.
27. Vazirani, V. V. 2001. Approximation Algorithms. Springer.
28. 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.
29. Zelnik-Manor, L., and Perona, P. 2004. Self-tuning spectral clustering. In Proc. Advances in Neural Information Processing Systems (NIPS), vol. 17, 1601–1608.
