Continuous optimization of interior carving in 3D fabrication

doi:10.1007/s11704-016-5465-y

Front. Comput. Sci.

2017, Vol. 11

Issue (2) : 332-346 https://doi.org/10.1007/s11704-016-5465-y

RESEARCH ARTICLE

Continuous optimization of interior carving in 3D fabrication

Yue XIE¹,Ye YUAN¹,Xiang CHEN¹(

),Changxi ZHENG²,Kun ZHOU¹

¹. State Key Lab of CAD&CG, Zhejiang University, Hangzhou 310058, China
². Columbia University, New York NY 10027, USA

Download: PDF(762 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Xiang CHEN

Just Accepted Date: 31 March 2016 Online First Date: 31 October 2016 Issue Date: 06 April 2017

Cite this article:

Yue XIE,Ye YUAN,Xiang CHEN, et al. Continuous optimization of interior carving in 3D fabrication[J]. Front. Comput. Sci., 2017, 11(2): 332-346.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5465-y
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I2/332

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 https://doi.org/10.1145/2461912.2461957
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 https://doi.org/10.1145/2601097.2601157
3	Christiansen A N, Schmidt R, Bærentzen J A. Automatic balancing of 3D models. Computer-Aided Design, 2015, 58: 236–241 https://doi.org/10.1016/j.cad.2014.07.009
4	Chen S, Torterelli D. Three-dimensional shape optimization with variational geometry. Structural Optimization, 1997, 13(2): 81–94 https://doi.org/10.1007/BF01199226
5	Braibant V, Fleury C. Shape optimal design using B-splines. Computer Methods in Applied Mechanics and Engineering, 1984, 44(3): 247–267 https://doi.org/10.1016/0045-7825(84)90132-4
6	Xu D, Ananthasuresh G K. Freeform skeletal shape optimization of compliant mechanisms. Journal of Mechanical Design, 2003, 125(2): 253–261 https://doi.org/10.1115/1.1563634
7	Bendsoe M P. Optimal shape design as a material distribution problem. Structural Optimization, 1989, 1(4): 193–202 https://doi.org/10.1007/BF01650949
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 https://doi.org/10.1016/S0045-7825(02)00559-5
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 https://doi.org/10.1007/s00158-003-0351-2
10	Haftka R T, Grandhi R V. Structural shape optimizationa——a survey. Computer Methods in Applied Mechanics and Engineering, 1986, 57(1): 91–106 https://doi.org/10.1016/0045-7825(86)90072-1
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 https://doi.org/10.1115/1.2013290
12	Luo L, Baran I, Rusinkiewicz S, Matusik W. Chopper: partitioning models into 3D-printable parts. ACM Transactions on Graphics, 2012, 31(6) https://doi.org/10.1145/2366145.2366148
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 https://doi.org/10.1145/2601097.2601173
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 https://doi.org/10.1145/2185520.2185614
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 https://doi.org/10.1145/2461912.2461979
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 https://doi.org/10.1145/2601097.2601189
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 https://doi.org/10.1145/2185520.2185543
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 https://doi.org/10.1145/2366145.2366149
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 https://doi.org/10.1145/2366145.2366146
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 https://doi.org/10.1145/2461912.2461953
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 https://doi.org/10.1145/2185520.2185582
23	Vouga E, Höbinger M, Wallner J, Pottmann H. Design of selfsupporting surfaces. ACM Transactions on Graphics, 2012, 31(4): 87 https://doi.org/10.1145/2185520.2185583
24	Panozzo D, Block P, Sorkine-Hornung O. Designing unreinforced masonry models. ACM Transactions on Graphics, 2013, 32(4): 91 https://doi.org/10.1145/2461912.2461958
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 https://doi.org/10.1145/2461912.2461932
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 https://doi.org/10.1145/2508363.2508382
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 https://doi.org/10.1145/2601097.2601168
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 https://doi.org/10.1145/2185520.2185544
29	Zhou Q, Panetta J, Zorin D. Worst-case structural analysis. ACM Transactions on Graphics, 2013, 32(4): 137 https://doi.org/10.1145/2461912.2461967
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 https://doi.org/10.1016/j.cagd.2015.03.019
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 https://doi.org/10.1145/2766955
32	Delfour M C, Zolésio J P. Shapes and Geometries: Metrics, Analysis, Differential Calculus, and Optimization. Philadelphia: Siam, 2011 https://doi.org/10.1137/1.9780898719826
33	Brakke K A. The surface evolver. Experimental Mathematics, 1992, 1(2): 141–165 https://doi.org/10.1080/10586458.1992.10504253
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 https://doi.org/10.1137/1.9781611970791
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 https://doi.org/10.1137/080737617
39	Sorkine O, Cohen-Or D. Least-squares meshes. In: Proceedings of Shape Modeling Applications. 2004 https://doi.org/10.1109/smi.2004.1314506
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 https://doi.org/10.1007/s002110050020
42	Mégel J, Kliava J. Metacenter and ship stability. American Journal of Physics, 2010, 78(7): 738–747 https://doi.org/10.1119/1.3285975
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 https://doi.org/10.1007/0-387-30065-1_4

[1]	Jin HUANG, Jiong CHEN, Weiwei XU, Hujun BAO. A survey on fast simulation of elastic objects[J]. Front. Comput. Sci., 2019, 13(3): 443-459.
[2]	Yu HAN,Guozhu JIA. Optimizing product manufacturability in 3D printing[J]. Front. Comput. Sci., 2017, 11(2): 347-357.
[3]	ZHANG Jian, ZHANG Wenhui, ZHAN Naijun, SHEN Yidong, CHEN Haiming, ZHANG Yunquan, WANG Yongji, WU Enhua, WANG Hongan, ZHU Xueyang. Basic research in computer science and software engineering at SKLCS[J]. Front. Comput. Sci., 2008, 2(1): 1-11.

Viewed

Full text

Abstract

Cited

Shared

Discussed