Miaojun Yao
Zhili Chen
Huamin Wang
Skip Abstract Section
Skip Supplemental Material SectionAbstract
As the 3D printing technology starts to revolutionize our daily life and the manufacturing industries, a critical problem is about to e-merge: how can we find an automatic way to divide a 3D model into multiple printable pieces, so as to save the space, to reduce the printing time, or to make a large model printable by small printers. In this paper, we present a systematic study on the partitioning and packing of 3D models under the multi-phase level set framework. We first construct analysis tools to evaluate the qualities of a partitioning using six metrics: stress load, surface details, interface area, packed size, printability, and assembling. Based on this analysis, we then formulate level set methods to improve the qualities of the partitioning according to the metrics. These methods are integrated into an automatic system, which repetitively and locally optimizes the partitioning. Given the optimized partitioning result, we further provide a container structure modeling algorithm to facilitate the packing process of the printed pieces. Our experiment shows that the system can generate quality partitioning of various 3D models for space saving and fast production purposes.
Supplemental Material
Available for Download
zip
a214-yao.zip (94 MB)
Supplemental files.
- Bächer, M., Bickel, B., James, D. L., and Pfister, H. 2012. Fabricating articulated characters from skinned meshes. ACM Trans. Graph. (SIGGRAPH) 31, 4 (July), 47:1--47:9. Google Scholar
Digital Library
- Bacher, M., Whiting, E., Bickel, B., and Sorkine-Hornung, O. 2014. Spin-It: Optimizing moment of inertia for spinnable objects. ACM Trans. Graph. (SIGGRAPH) 33, 4 (August), 96:1--96:10. Google ScholarDigital Library
- Calì, J., Calian, D. A., Amati, C., Kleinberger, R., Steed, A., Kautz, J., and Weyrich, T. 2012. 3D-printing of non-assembly, articulated models. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6 (Nov.), 130:1--130:8. Google ScholarDigital Library
- Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. Graph. (SIGGRAPH) 28, 3 (July), 73:1--73:12. Google ScholarDigital Library
- Chen, X., Zheng, C., Xu, W., and Zhou, K. 2014. An asymptotic numerical method for inverse elastic shape design. ACM Trans. Graph. (SIGGRAPH) 33, 4 (August), 95:1--95:11. Google ScholarDigital Library
- Deuss, M., Panozzo, D., Whiting, E., Liu, Y., Block, P., Sorkine-Hornung, O., and Pauly, M. 2014. Assembling self-supporting structures. ACM Trans. Graph. (SIGGRAPH Asia) 33, 6 (Nov.), 214:1--214:10. Google ScholarDigital Library
- Dickinson, J. K., and Knopf, G. K. 1998. Serial packing of arbitrary 3D objects for optimizing layered manufacturing. In Procedings of SPIE 3522, Intelligent Robots and Computer Vision XVII: Algorithms, Techniques, and Active Vision.Google Scholar
- Dumas, J., Hergel, J., and Lefebvre, S. 2014. Bridging the gap: Automated steady scaffoldings for 3D printing. ACM Trans. Graph. (SIGGRAPH) 33, 4 (August), 98:1--98:10. Google ScholarDigital Library
- Egeblad, J., Nielsen, B. K., and Brazil, M. 2009. Translational packing of arbitrary polytopes. Computational Geometry 42, 4, 269--288. Google ScholarDigital Library
- Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. J. Comput. Phys. 183, 1 (Nov.), 83--116. Google ScholarDigital Library
- Gibou, F., and Fedkiw, R. 2005. A fast hybrid k-means level set algorithm for segmentation. In 4th Annual Hawaii International Conference on Statistics and Mathematics, 281--291.Google Scholar
- Gomes, A. M., and Oliveira, J. F. 2006. Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research 171, 3, 811--829.Google ScholarCross Ref
- Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. (SIGGRAPH) 22, 3 (July), 871--878. Google ScholarDigital Library
- Hu, R., Li, H., Zhang, H., and Cohen-Or, D. 2014. Approximate pyramidal shape decomposition. ACM Trans. Graph. (SIGGRAPH Asia) 33, 6 (Nov.), 213:1--213:12. Google ScholarDigital Library
- Imamichi, T., and Nagamochi, H. 2007. A multi-sphere scheme for 2D and 3D packing problems. In Proc. of SLS, 207--211. Google ScholarDigital Library
- Imamichi, T., Yagiura, M., and Nagamochi, H. 2009. An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optimization 6, 4, 345--361. Google ScholarDigital Library
- Junior, B., Pinheiro, P., and Saraiva, R. 2013. Tackling the irregular strip packing problem by hybridizing genetic algorithm and bottom-left heuristic. In 2013 IEEE Congress on Evolutionary Computation, 3012--3018.Google Scholar
- Kim, B. 2010. Multi-phase fluid simulations using regional level sets. ACM Trans. Graph. (SIGGRAPH) 29, 6 (Dec.), 175:1--175:8. Google ScholarDigital Library
- Lau, M., Ohgawara, A., Mitani, J., and Igarashi, T. 2011. Converting 3D furniture models to fabricatable parts and connectors. ACM Trans. Graph. (SIGGRAPH) 30, 4 (July), 85:1--85:6. Google ScholarDigital Library
- Li, H., Alhashim, I., Zhang, H., Shamir, A., and Cohen-Or, D. 2012. Stackabilization. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6 (Nov.), 158:1--158:9. Google ScholarDigital Library
- Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM Trans. Graph. (SIGGRAPH) 25, 3 (July), 812--819. Google ScholarDigital Library
- Lu, L., Sharf, A., Zhao, H., Wei, Y., Fan, Q., Chen, X., Savoye, Y., Tu, C., Cohen-Or, D., and Chen, B. 2014. Build-to-last: Strength to weight 3D printed objects. ACM Trans. Graph. (SIGGRAPH) 33, 4 (August), 97:1--97:10. Google ScholarDigital Library
- Luo, L., Baran, I., Rusinkiewicz, S., and Matusik, W. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6 (Nov.), 129:1--129:9. Google ScholarDigital Library
- Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. (SIGGRAPH) 24, 3 (July), 471--478. Google ScholarDigital Library
- Nooruddin, F. S., and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Transactions on Visualization and Computer Graphics 9, 2, 191--205. Google ScholarDigital Library
- Novotni, M., and Klein, R. 2002. Computing geodesic distances on triangular meshes. In Proc. of WSCG, 341--347.Google Scholar
- Osher, S., and Sethian, J. A. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79, 1 (Nov.), 12--49. Google ScholarDigital Library
- Panozzo, D., Block, P., and Sorkine-Hornung, O. 2013. Designing unreinforced masonry models. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July), 91:1--91:12. Google ScholarDigital Library
- Ruuth, S. J. 1998. A diffusion-generated approach to multiphase motion. J. Comput. Phys. 145, 1 (Sept.), 166--192. Google ScholarDigital Library
- Saye, R. I., and Sethian, J. A. 2011. The Voronoi implicit interface method for computing multiphase physics. Proceedings of the National Academy of Sciences 108, 49, 19498--19503.Google ScholarCross Ref
- Shamir, A. 2008. A survey on mesh segmentation techniques. Comput. Graph. Forum 27, 6, 1539--1556.Google ScholarCross Ref
- Smith, K., Solis, F., and Chopp, D. 2002. A projection method for motion of triple junctions by level sets. Interfaces and Free Boundaries 4, 3Google Scholar
- Song, P., Fu, C.-W., and Cohen-Or, D. 2012. Recursive interlocking puzzles. ACM Trans. Graph. (SIGGRAPH) 31, 6 (Nov.), 128:1--128:10. 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. Graph. (SIGGRAPH) 31, 4 (July), 48:1--48:11. Google ScholarDigital Library
- Telea, A., and Jalba, A. 2011. Voxel-based assessment of printability of 3D shapes. In Proc. of ISMM, 393--404. Google ScholarDigital Library
- Vanek, J., Galicia, J. A. G., Benes, B., Mch, R., Carr, N., Stava, O., and Miller, G. S. 2014. Packmerger: A 3D print volume optimizer. Computer Graphics Forum 33, 6 (Sept.), 322--332.Google ScholarDigital Library
- Vese, L. A., and Chan, T. F. 2002. A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vision 50, 3 (Dec.), 271--293. 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. Graph. (SIGGRAPH Asia) 32, 6 (Nov.), 177:1--177:10. Google ScholarDigital Library
- Whiting, E., Shin, H., Wang, R., Ochsendorf, J., and Durand, F. 2012. Structural optimization of 3D masonry buildings. ACM Trans. Graph (SIGGRAPH Asia). 31, 6 (Nov.), 159:1--159:11. Google ScholarDigital Library
- Wu, S., Kay, M., King, R. E., Vila-Parrish, A., and Warsing, D. 2014. Multi-objective optimization of 3D packing problem in additive manufacturing. In Proceedings of the 2014 Industrial and Systems Engineering Research Conference.Google Scholar
- Xin, S., Lai, C.-F., Fu, C.-W., Wong, T.-T., He, Y., and Cohen-Or, D. 2011. Making burr puzzles from 3D models. ACM Trans. Graph. (SIGGRAPH) 30, 4 (July), 97:1--97:8. Google ScholarDigital Library
- Yang, Y.-L., and Huang, Q.-X. 2013. Traygen: Arranging objects for exhibition and packaging. Comput. Graph. Forum (Pacific Graphics) 32, 7, 187--195.Google ScholarCross Ref
- Zhao, H.-K., Chan, T., Merriman, B., and Osher, S. 1996. A variational level set approach to multiphase motion. J. Comput. Phys. 127, 1 (Aug.), 179--195. Google ScholarDigital Library
- Zhou, Q., Panetta, J., and Zorin, D. 2013. Worst-case structural analysis. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July), 137:1--137:12. Google ScholarDigital Library
Index Terms
- Level-set-based partitioning and packing optimization of a printable model
Recommendations
Fabrication of a conductive nanoscale electrode for functional devices using nanoimprint lithography with printable metallic nanoink
This paper proposes two metal patterning processes. In each process, nanoimprint lithography (NIL) is used with commercialized particle-based silver nanoink which has appropriate properties for NIL. One process is a direct NIL process with a ...
Printable Hydroponics: Digital Fabrication of Ecological Systems
ISS '18: Proceedings of the 2018 ACM International Conference on Interactive Surfaces and SpacesWe demonstrate a technique to 3D print hydroponic systems which support the growth of various plant species. Our technique fabricates a landscape made entirely out of plastic, and automatically attaches plants seeds to predesignated positions on its ...
Printing 3D objects with interlocking parts
Recent advances in 3D printing technologies bring wide range of applications from fast prototyping to product manufacturing. However, one intrinsic limitation of 3D printing is that we cannot fabricate a single object that is larger than the working ...
Comments