research-article

Approximate pyramidal shape decomposition

Authors:

Daniel Cohen-OrAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 33, Issue 6

Article No.: 213, Pages 1 - 12

https://doi.org/10.1145/2661229.2661244

Published: 19 November 2014 Publication History

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.

Digital Library

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

Digital Library

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

Digital Library

[4]

Chandru, V., Rajan, V. T., and Swaminathan, R. 1992. Monotone pieces of chains. ORSA Journal on Computing 4, 4, 439--446.

[5]

Chazelle, B. 1984. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 488--507.

Digital Library

[6]

Chvatal, V. 1979. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 3, pp. 233--235.

Digital Library

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

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

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

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

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

Digital Library

[14]

Liu, R., and Ntafos, S. 1988. On decomposing polygons into uniformly monotone parts. Information Processing Letters 27, 2, 85--89.

Digital Library

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

Digital Library

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

[18]

Pauly, M., and Gross, M. 2001. Spectral processing of point-sampled geometry. In Proc. of SIGGRAPH, 379--386.

Digital Library

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

Digital Library

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

[21]

Rappaport, D., and Rosenbloom, A. 1994. Moldable and castable polygons. Computational Geometry 4, 219--233.

Digital Library

[22]

Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539--1556.

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

Digital Library

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

Digital Library

[26]

Tor, S. B., and Middleditch, A. E. 1984. Convex decomposition of simple polygons. ACM Trans. on Graph 3, 4 (Oct.), 244--265.

Digital Library

[27]

Vazirani, V. V. 2001. Approximation Algorithms. Springer.

Digital Library

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

Digital Library

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

Cited By

Białas KDymarek ADzitkowski T(2023)IMPACT OF 3D PRINTER VIBRATION REDUCTION ON THE QUALITY OF ITS PRINTOUTInternational Journal of Modern Manufacturing Technologies10.54684/ijmmt.2023.15.2.7915:2(79-90)Online publication date: 20-Dec-2023
https://doi.org/10.54684/ijmmt.2023.15.2.79
Latorre EWhiting E(2023)Laser Polishing: A Postprocessing Protocol for Fused Deposition Modeling 3D Printed Parts Using Existing ToolingProceedings of the 8th ACM Symposium on Computational Fabrication10.1145/3623263.3629154(1-3)Online publication date: 8-Oct-2023
https://dl.acm.org/doi/10.1145/3623263.3629154
Zhong FZhao HLi HYan XLiu JChen BLu L(2023)VASCO: Volume and Surface Co-Decomposition for Hybrid ManufacturingACM Transactions on Graphics10.1145/361832442:6(1-17)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618324
Show More Cited By

Index Terms

Approximate pyramidal shape decomposition
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

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 Imagery

In 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 33, Issue 6

November 2014

704 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2661229

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 November 2014

Published in TOG Volume 33, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Natural Sciences and Engineering Research Council of Canada
China Scholarship Council
Israeli Ministry of Science
Israel Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
903
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Białas KDymarek ADzitkowski T(2023)IMPACT OF 3D PRINTER VIBRATION REDUCTION ON THE QUALITY OF ITS PRINTOUTInternational Journal of Modern Manufacturing Technologies10.54684/ijmmt.2023.15.2.7915:2(79-90)Online publication date: 20-Dec-2023
https://doi.org/10.54684/ijmmt.2023.15.2.79
Latorre EWhiting E(2023)Laser Polishing: A Postprocessing Protocol for Fused Deposition Modeling 3D Printed Parts Using Existing ToolingProceedings of the 8th ACM Symposium on Computational Fabrication10.1145/3623263.3629154(1-3)Online publication date: 8-Oct-2023
https://dl.acm.org/doi/10.1145/3623263.3629154
Zhong FZhao HLi HYan XLiu JChen BLu L(2023)VASCO: Volume and Surface Co-Decomposition for Hybrid ManufacturingACM Transactions on Graphics10.1145/361832442:6(1-17)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618324
Zhong FXu YZhao HLu L(2023)As-Continuous-As-Possible Extrusion-Based Fabrication of Surface ModelsACM Transactions on Graphics10.1145/357585942:3(1-16)Online publication date: 17-Mar-2023
https://dl.acm.org/doi/10.1145/3575859
Alderighi TMalomo LAuzinger TBickel BCignoni PPietroni N(2022)State of the Art in Computational Mould DesignComputer Graphics Forum10.1111/cgf.1458141:6(435-452)Online publication date: 22-Aug-2022
https://doi.org/10.1111/cgf.14581
Tomar BShiva SNath T(2022)A review on wire arc additive manufacturing: Processing parameters, defects, quality improvement and recent advancesMaterials Today Communications10.1016/j.mtcomm.2022.10373931(103739)Online publication date: Jun-2022
https://doi.org/10.1016/j.mtcomm.2022.103739
Li CWu BZhang ZZhang Y(2022)A novel process planning method of 3 + 2-axis additive manufacturing for aero-engine blade based on machine learningJournal of Intelligent Manufacturing10.1007/s10845-021-01898-634:4(2027-2042)Online publication date: 29-Jan-2022
https://doi.org/10.1007/s10845-021-01898-6
Alderighi TMalomo LBickel BCignoni PPietroni N(2021)Volume decomposition for two-piece rigid castingACM Transactions on Graphics10.1145/3478513.348055540:6(1-14)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480555
Wang ZSong PPauly M(2021)State of the Art on Computational Design of Assemblies with Rigid PartsComputer Graphics Forum10.1111/cgf.14266040:2(633-657)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142660
Nuvoli STola AMuntoni APietroni NGobbetti EScateni R(2021)Automatic Surface Segmentation for Seamless Fabrication Using 4‐axis Milling MachinesComputer Graphics Forum10.1111/cgf.14262540:2(191-203)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142625
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents