Stress-aware large-scale mesh editing using a domain-decomposed multigrid solver. (English) Zbl 1441.65027
Summary: In this paper, we develop a domain-decomposed subspace and multigrid solver to analyze the stress distribution for large-scale finite element meshes with millions of degrees of freedom. Through the domain decomposition technique, the shape editing directly updates the data structure of local finite element matrices. Doing so avoids the expensive factorization step in a direct solver and provides users with a progressive feedback of the stress distribution corresponding to the mesh operations: a fast preview is achieved through the subspace solver, and the multigrid solver refines the preview result if the user needs to examine the stress distribution carefully at certain design stages. Our system constructs the subspace for stress analysis using reduced constrained modes and builds a three-level multigrid solver through the algebraic multigrid method. We remove mid-edge nodes and lump unknowns with the Schur complement method. The updating and solving of the large global stiffness matrix are implemented in parallel after the domain decomposition. Experimental results show that our solver outperforms the parallel Intel MKL solver. Speedups of \(50 \% - 100\%\) can be achieved for large-scale meshes with reasonable pre-computation costs when setting the stopping criterion of the multigrid solver to be \(1\mathrm{e}-3\) relative error.
MSC:
| 65D17 | Computer-aided design (modeling of curves and surfaces) |
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
References:
| [1] | Adams, M., Evaluation of three unstructured multigrid methods on 3D finite element problems in solid mechanics, Int. J. Numer. Methods Eng., 55, 5, 519-534, (2002) · Zbl 1076.74547 |
| [2] | Bächer, M.; Bickel, B.; James, D. L.; Pfister, H., Fabricating articulated characters from skinned meshes, ACM Trans. Graph., 31, 4, (July 2012) |
| [3] | Baran, I.; Popović, J., Automatic rigging and animation of 3D characters, ACM Trans. Graph., 26, 3, (July 2007) |
| [4] | Barbič, J.; Zhao, Y., Real-time large-deformation substructuring, (ACM SIGGRAPH 2011 Papers, SIGGRAPH ’11, (2011)) |
| [5] | Bickel, B.; Bächer, M.; Otaduy, M. A.; Lee, H. R.; Pfister, H.; Gross, M.; Matusik, W., Design and fabrication of materials with desired deformation behavior, ACM Trans. Graph., 29, 4, (July 2010) |
| [6] | Bro-Nielsen, M.; Cotin, S., Real-time volumetric deformable models for surgery simulation using finite elements and condensation, Comput. Graph. Forum, 15, 3, 57-66, (1996) |
| [7] | Calì, J.; Calian, D. A.; Amati, C.; Kleinberger, R.; Steed, A.; Kautz, J.; Weyrich, T., 3D-printing of non-assembly, articulated models, ACM Trans. Graph., 31, 6, (Nov. 2012) |
| [8] | Ceylan, D.; Li, W.; Mitra, N. J.; Agrawala, M.; Pauly, M., Designing and fabricating mechanical automata from mocap sequences, ACM Trans. Graph., 32, 6, (Nov. 2013) |
| [9] | Chen, D.; Levin, D. I.W.; Didyk, P.; Sitthi-Amorn, P.; Matusik, W., Spec2fab: a reducer-tuner model for translating specifications to 3D prints, ACM Trans. Graph., 32, 4, (July 2013) |
| [10] | Cohen-Steiner, D.; Alliez, P.; Desbrun, M., Variational shape approximation, ACM Trans. Graph., 23, 3, 905-914, (Aug. 2004) |
| [11] | Coros, S.; Thomaszewski, B.; Noris, G.; Sueda, S.; Forberg, M.; Sumner, R. W.; Matusik, W.; Bickel, B., Computational design of mechanical characters, ACM Trans. Graph., 32, 4, (July 2013) · Zbl 1305.68224 |
| [12] | Courtecuisse, H.; Allard, J., Parallel dense Gauss-Seidel algorithm on many-core processors, (HPCC, (2009), IEEE), 139-147 |
| [13] | Craig, R. J., A review of time-domain and frequency-domain component mode synthesis methods, Int. J. Anal. Exp. Modal Anal., 2, 2, 59-72, (Jan. 1987) |
| [14] | Dong, Y.; Wang, J.; Pellacini, F.; Tong, X.; Guo, B., Fabricating spatially-varying subsurface scattering, ACM Trans. Graph., 29, 4, (July 2010) |
| [15] | Falgout, R. D., An introduction to algebraic multigrid, Comput. Sci. Eng., 8, 6, 24-33, (2006) |
| [16] | Farhat, C.; Lesoinne, M.; LeTallec, P.; Pierson, K.; Rixen, D., FETI-DP: a dual-primal unified FETI method - part I: a faster alternative to the two-level FETI method, Int. J. Numer. Methods Eng., 50, 7, 1523-1544, (2001) · Zbl 1008.74076 |
| [17] | Farhat, C.; Roux, F.-X., A method of finite element tearing and interconnecting and its parallel solution algorithm, Int. J. Numer. Methods Eng., 32, 6, 1205-1227, (1991) · Zbl 0758.65075 |
| [18] | Formlabs, Validating isotropy in SLA 3D printing, (October 2016) |
| [19] | Gal, R.; Sorkine, O.; Mitra, N. J.; Cohen-Or, D., Iwires: an analyze-and-edit approach to shape manipulation, ACM Trans. Graph. (SIGGRAPH), 28, 3, (2009) |
| [20] | Geveler, M.; Ribbrock, D.; Göddeke, D.; Zajac, P.; Turek, S., Towards a complete FEM-based simulation toolkit on GPUs: unstructured grid finite element geometric multigrid solvers with strong smoothers based on sparse approximate inverses, Comput. Fluids, 80, 327-332, (2013) · Zbl 1284.76249 |
| [21] | Golub, G. H.; Loan, C. F.V., Matrix computations, (1996), The Johns Hopkins University Press · Zbl 0865.65009 |
| [22] | Jeon, I.; Choi, K.-J.; Kim, T.-Y.; Choi, B.-O.; Ko, H.-S., Constrainable multigrid for cloth, Comput. Graph. Forum, 32, 31-39, (2013), Wiley Online Library |
| [23] | Karer, E.; Kraus, J. K., Algebraic multigrid for finite element elasticity equations: determination of nodal dependence via edge-matrices and two-level convergence, Int. J. Numer. Methods Eng., 83, 5, 642-670, (2010) · Zbl 1197.74181 |
| [24] | Kawaguchi, A.; Itoh, S.; Mochizuki, M.; Kameyama, M., Large-scale computation of welding residual stress, Progr. Nucl. Sci. Technol., 2, 613-619, (2011) |
| [25] | Kim, T.; James, D. L., Physics-based character skinning using multi-domain subspace deformations, (Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’11, (2011)), 63-72 |
| [26] | Kim, K.; Leem, K. H.; Pelekanos, G.; Song, M., Algebraic multigrid preconditioner for a finite element method in TM electromagnetic scattering, J. Comput. Anal. Appl., 11, 4, 597-605, (2009) · Zbl 1168.78316 |
| [27] | Lan, Y.; Dong, Y.; Pellacini, F.; Tong, X., Bi-scale appearance fabrication, ACM Trans. Graph., 32, 4, (July 2013) · Zbl 1305.68251 |
| [28] | Lau, M.; Ohgawara, A.; Mitani, J.; Igarashi, T., Converting 3D furniture models to fabricatable parts and connectors, ACM Trans. Graph., 30, 4, (July 2011) |
| [29] | Li, D.; Levin, D. I.W.; Matusik, W.; Zheng, C., Acoustic voxels: computational optimization of modular acoustic filters, ACM Trans. Graph., 35, 4, (July 2016) |
| [30] | Li, X.; Yu, W.; Liu, C., Geometry-aware partitioning of complex domains for parallel quad meshing, Comput. Aided Des., 85, 20-33, (2017) |
| [31] | McAdams, A.; Sifakis, E.; Teran, J., A parallel multigrid Poisson solver for fluids simulation on large grids, (Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, (2010), Eurographics Association), 65-74 |
| [32] | McAdams, A.; Zhu, Y.; Selle, A.; Empey, M.; Tamstorf, R.; Teran, J.; Sifakis, E., Efficient elasticity for character skinning with contact and collisions, ACM Trans. Graph. (SIGGRAPH), 30, 4, (July 2011) |
| [33] | Ni, S.; Zhong, Z.; Liu, Y.; Wang, W.; Chen, Z.; Guo, X., Sliver-suppressing tetrahedral mesh optimization with gradient-based shape matching energy, Comput. Aided Geom. Des., 52, C, 247-261, (Mar. 2017) · Zbl 1366.65043 |
| [34] | Panetta, J.; Zhou, Q.; Malomo, L.; Pietroni, N.; Cignoni, P.; Zorin, D., Elastic textures for additive fabrication, ACM Trans. Graph., 34, 4, (July 2015) · Zbl 1334.68283 |
| [35] | Patterson, T.; Mitchell, N.; Sifakis, E., Simulation of complex nonlinear elastic bodies using lattice deformers, ACM Trans. Graph. (SIGGRAPH Asia), 31, 6, (Nov. 2012) |
| [36] | Reusken, A., A multigrid method based on incomplete Gaussian elimination, Numer. Linear Algebra Appl., 3, 5, 369-390, (1996) · Zbl 0906.65118 |
| [37] | Shi, L.; Yu, Y.; Bell, N.; Feng, W.-W., A fast multigrid algorithm for mesh deformation, ACM Trans. Graph., 25, 1108-1117, (2006) |
| [38] | Skouras, M.; Thomaszewski, B.; Coros, S.; Bickel, B.; Gross, M., Computational design of actuated deformable characters, ACM Trans. Graph., 32, 4, (July 2013) |
| [39] | Stava, O.; Vanek, J.; Benes, B.; Carr, N.; Měch, R., Stress relief: improving structural strength of 3D printable objects, ACM Trans. Graph., 31, 4, (July 2012) |
| [40] | Tamstorf, R.; Jones, T.; McCormick, S. F., Smoothed aggregation multigrid for cloth simulation, ACM Trans. Graph., 34, 6, (Oct. 2015) |
| [41] | Teng, Y.; Meyer, M.; DeRose, T.; Kim, T., Subspace condensation: full space adaptivity for subspace deformations, ACM Trans. Graph., 34, 4, (July 2015) · Zbl 1334.68269 |
| [42] | Toselli, A.; Widlund, O., Domain decomposition methods, (2004), Springer |
| [43] | Umetani, N.; Takayama, K.; Mitani, J.; Igarashi, T., A responsive finite element method to aid interactive geometric modeling, IEEE Comput. Graph. Appl., 31, 5, 43-53, (Sept. 2011) |
| [44] | Wagner, C.; Kinzelbach, W.; Wittum, G., Schur-complement multigrid, Numer. Math., 75, 4, 523-545, (1997) · Zbl 0876.76066 |
| [45] | Wang, E.; Zhang, Q.; Shen, B.; Zhang, G.; Lu, X.; Wu, Q.; Wang, Y., Intel math kernel library, (High-Performance Computing on the Intel^{®} Xeon Phi, (2014), Springer), 167-188 |
| [46] | Xie, Y.; Xu, W.; Yang, Y.; Guo, X.; Zhou, K., Agile structural analysis for fabrication-aware shape editing, Comput. Aided Geom. Des., 35, C, 163-179, (May 2015) · Zbl 1417.68255 |
| [47] | Yang, U. M., Boomeramg: a parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math., 41, 1, 155-177, (2002) · Zbl 0995.65128 |
| [48] | Yang, Y.; Xu, W.; Guo, X.; Zhou, K.; Guo, B., Boundary-aware multidomain subspace deformation, IEEE Trans. Vis. Comput. Graph., 19, 10, 1633-1645, (2013) |
| [49] | Yu, W.; Li, X., Computing 3D shape guarding and star decomposition, Comput. Graph. Forum, 30, 7, 2087-2096, (2011) |
| [50] | Zhou, Q.; Panetta, J.; Zorin, D., Worst-case structural analysis, ACM Trans. Graph., 32, 4, (July 2013) · Zbl 1305.68323 |
| [51] | Zhu, Y.; Sifakis, E.; Teran, J.; Brandt, A., An efficient multigrid method for the simulation of high-resolution elastic solids, ACM Trans. Graph., 29, 2, (Apr. 2010) |
| [52] | Zhu, L.; Xu, W.; Snyder, J.; Liu, Y.; Wang, G.; Guo, B., Motion-guided mechanical toy modeling, ACM Trans. Graph., 31, 6, (Nov. 2012) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
