“Level-set-based partitioning and packing optimization of a printable model”
Conference:
Type(s):
Title:
- Level-set-based partitioning and packing optimization of a printable model
Session/Category Title: Fabrication
Presenter(s)/Author(s):
Abstract:
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.
References:
1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. Egeblad, J., Nielsen, B. K., and Brazil, M. 2009. Translational packing of arbitrary polytopes. Computational Geometry 42, 4, 269–288.
10. 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.
11. 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.
12. 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.
13. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. (SIGGRAPH) 22, 3 (July), 871–878.
14. 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.
15. Imamichi, T., and Nagamochi, H. 2007. A multi-sphere scheme for 2D and 3D packing problems. In Proc. of SLS, 207–211.
16. 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.
17. 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.
18. Kim, B. 2010. Multi-phase fluid simulations using regional level sets. ACM Trans. Graph. (SIGGRAPH) 29, 6 (Dec.), 175:1–175:8.
19. 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.
20. 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.
21. Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM Trans. Graph. (SIGGRAPH) 25, 3 (July), 812–819.
22. 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.
23. 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.
24. 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.
25. 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.
26. Novotni, M., and Klein, R. 2002. Computing geodesic distances on triangular meshes. In Proc. of WSCG, 341–347.
27. 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.
28. Panozzo, D., Block, P., and Sorkine-Hornung, O. 2013. Designing unreinforced masonry models. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July), 91:1–91:12.
29. Ruuth, S. J. 1998. A diffusion-generated approach to multiphase motion. J. Comput. Phys. 145, 1 (Sept.), 166–192.
30. 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.
31. Shamir, A. 2008. A survey on mesh segmentation techniques. Comput. Graph. Forum 27, 6, 1539–1556.
32. Smith, K., Solis, F., and Chopp, D. 2002. A projection method for motion of triple junctions by level sets. Interfaces and Free Boundaries 4, 3
33. Song, P., Fu, C.-W., and Cohen-Or, D. 2012. Recursive interlocking puzzles. ACM Trans. Graph. (SIGGRAPH) 31, 6 (Nov.), 128:1–128:10.
34. 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.
35. Telea, A., and Jalba, A. 2011. Voxel-based assessment of printability of 3D shapes. In Proc. of ISMM, 393–404.
36. 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.
37. 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.
38. 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.
39. 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.
40. 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.
41. 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.
42. Yang, Y.-L., and Huang, Q.-X. 2013. Traygen: Arranging objects for exhibition and packaging. Comput. Graph. Forum (Pacific Graphics) 32, 7, 187–195.
43. 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.
44. Zhou, Q., Panetta, J., and Zorin, D. 2013. Worst-case structural analysis. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July), 137:1–137:12.
