Continuous optimization of interior carving in 3D fabrication

Abstract

In this paper we propose an optimization framework for interior carving of 3D fabricated shapes. Interior carving is an important technique widely used in industrial and artistic designs to achieve functional purposes by hollowing interior shapes in objects. We formulate such functional purpose as the objective function of an optimization problem whose solution indicates the optimal interior shape. In contrast to previous volumetric methods, we directly represent the boundary of the interior shape as a triangular mesh. We use Eulerian semiderivative to relate the time derivative of the object function to a virtual velocity field and iteratively evolve the interior shape guided by the velocity field with surface tracking. In each iteration, we compute the velocity field guaranteeing the decrease of objective function by solving a linear programming problem. We demonstrate this general framework in a novel application of designing objects floating in fluid and two previously investigated applications, and print various optimized objects to verify its effectiveness.

Keywords

computer graphics / 3D printing / interior carving / shape optimization / Eulerian semiderivative

References

[1] Prévost R, Whiting E, Lefebvre S, Sorkine-Hornung O. Make it stand: balancing shapes for 3D fabrication. ACM Transactions on Graphics, 2013, 32(4): 81

[2] Bächer M, Whiting E, Bickel B, Sorkine-Hornung O. Spin-it: optimizing moment of inertia for spinnable objects. ACM Transactions on Graphics, 2014, 33(4): 96

[3] Christiansen A N, Schmidt R, Bærentzen J A. Automatic balancing of 3D models. Computer-Aided Design, 2015, 58: 236–241

[4] Chen S, Torterelli D. Three-dimensional shape optimization with variational geometry. Structural Optimization, 1997, 13(2): 81–94

[5] Braibant V, Fleury C. Shape optimal design using B-splines. Computer Methods in Applied Mechanics and Engineering, 1984, 44(3): 247–267

[6] Xu D, Ananthasuresh G K. Freeform skeletal shape optimization of compliant mechanisms. Journal of Mechanical Design, 2003, 125(2): 253–261

[7] Bendsoe M P. Optimal shape design as a material distribution problem. Structural Optimization, 1989, 1(4): 193–202

[8] Wang M Y, Wang X M, Guo D M. A level set method for structural topology optimization. Computer Methods in Applied Mechanics and Engineering, 2003, 192(1): 227–246

[9] Zhou M, Pagaldipti N, Thomas H, Shyy Y. An integrated approach to topology, sizing, and shape optimization. Structural and Multidisciplinary Optimization, 2004, 26(5): 308–317

[10] Haftka R T, Grandhi R V. Structural shape optimizationa——a survey. Computer Methods in Applied Mechanics and Engineering, 1986, 57(1): 91–106

[11] Saitou K, Izui K, Nishiwaki S, Papalambros P. A survey of structural optimization in mechanical product development. Journal of Computing and Information Science in Engineering, 2005, 5(3): 214–226

[12] Luo L, Baran I, Rusinkiewicz S, Matusik W. Chopper: partitioning models into 3D-printable parts. ACM Transactions on Graphics, 2012, 31(6)

[13] Attene M. Shapes in a box: disassembling 3D objects for efficient packing and fabrication. Computer Graphics Forum, 2015

[14] Zhou Y B, Sueda S, Matusik W, Shamir A. Boxelization: folding 3D objects into boxes. ACM Transactions on Graphics, 2014, 33(4): 71

[15] Bickel B, Kaufmann P, Skouras M, Thomaszewski B, Bradley D, Beeler T, Jackson P, Marschner S, Matusik W, Gross M. Physical face cloning. ACM Transactions on Graphics, 2012, 31(4): 118

[16] Skouras M, Thomaszewski B, Coros S, Bickel B, Gross M. Computational design of actuated deformable characters. ACM Transactions on Graphics, 2013, 32(4): 82

[17] Chen X, Zheng C, Xu W, Zhou K. An asymptotic numerical method for inverse elastic shape design. ACM Transactions on Graphics, 2014, 33(4): 95

[18] Bächer M, Bickel B, James D L, Pfister H. Fabricating articulated characters from skinned meshes. ACM Transactions on Graphics, 2012, 31(4): 47

[19] Calì J, Calian D A, Amati C, Kleinberger R, Steed A, Kautz J, Weyrich T. 3D-printing of non-assembly, articulated models. ACM Transactions on Graphics, 2012, 31(6): 130

[20] Zhu L, Xu W, Snyder J, Liu Y, Wang G, Guo B. Motion-guided mechanical toy modeling. ACM Transactions on Graphics, 2012, 31(6): 127

[21] Coros S, Thomaszewski B, Noris G, Sueda S, Forberg M, Sumner R W, Matusik W, Bickel B. Computational design of mechanical characters. ACM Transactions on Graphics, 2013, 32(4): 83

[22] Umetani N, Igarashi T, Mitra N J. Guided exploration of physically valid shapes for furniture design. ACM Transactions on Graphics, 2012, 31(4): 86

[23] Vouga E, Höbinger M, Wallner J, Pottmann H. Design of selfsupporting surfaces. ACM Transactions on Graphics, 2012, 31(4): 87

[24] Panozzo D, Block P, Sorkine-Hornung O. Designing unreinforced masonry models. ACM Transactions on Graphics, 2013, 32(4): 91

[25] De Goes F, Alliez P, Owhadi H, Desbrun M. On the equilibrium of simplicial masonry structures. ACM Transactions on Graphics, 2013, 32(4): 93

[26] Wang W, Wang T Y, Yang Z, Liu L, Tong X, Tong W, Deng J, Chen F, Liu X. Cost-effective printing of 3D objects with skin-frame structures. ACM Transactions on Graphics, 2013, 32(6): 177

[27] Lu L, Sharf A, Zhao H, Wei Y, Fan Q, Chen X, Savoye Y, Tu C, CohenOr D, Chen B. Build-to-last: strength to weight 3D printed objects. ACM Transactions on Graphics, 2014, 33(4): 97

[28] Stava O, Vanek J, Benes B, Carr N, Mˇech R. Stress relief: improving structural strength of 3D printable objects. ACM Transactions on Graphics, 2012, 31(4): 48

[29] Zhou Q, Panetta J, Zorin D. Worst-case structural analysis. ACM Transactions on Graphics, 2013, 32(4): 137

[30] Xie Y, Xu W, Yang Y, Guo X, Zhou K. Agile structural analysis for fabrication-aware shape editing. Computer Aided Geometric Design, 2015, 35: 163–179

[31] Musialski P, Auzinger T, Birsak M, Wimmer M, Kobbelt L. Reducedorder shape optimization using offset surfaces. ACM Transactions on Graphics, 2015, 34(4): 102

[32] Delfour M C, Zolésio J P. Shapes and Geometries: Metrics, Analysis, Differential Calculus, and Optimization. Philadelphia: Siam, 2011

[33] Brakke K A. The surface evolver. Experimental Mathematics, 1992, 1(2): 141–165

[34] Sethian J A. Level set methods and fast marching methods. Journal of Computing and Information Technology, 2003, 11(1): 1–2

[35] Nesterov Y, Nemirovskii A. Interior-Point Polynomial Algorithms in Convex Programming. Philadelphia: Siam, 1994

[36] Makhorin A, Andrew O. GLPK (GNU linear programming kit). 2008

[37] Osher S, Fedkiw R. Level set methods and dynamic implicit surfaces. Surfaces, 2002, 44

[38] Brochu T, Bridson R. Robust topological operations for dynamic explicit surfaces. SIAM Journal on Scientific Computing, 2009, 31(4): 2472–2493

[39] Sorkine O, Cohen-Or D. Least-squares meshes. In: Proceedings of Shape Modeling Applications. 2004

[40] McGrail S. Boats of the World: from the Stone Age to Medieval Times. New York: Oxford University Press, 2004

[41] Ascher U M, Chin H, Reich S. Stabilization of DAEs and invariant manifolds. Numerische Mathematik, 1994, 67(2): 131–149

[42] Mégel J, Kliava J. Metacenter and ship stability. American Journal of Physics, 2010, 78(7): 738–747

[43] Byrd R H, Nocedal J, Waltz R A. Knitro: an integrated package for nonlinear optimization. In: Di Pillo G, Roma M, <Eds/>. Large-Scale Nonlinear Optimization, Vol 83. Springer, 2006, 35–59

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg