Subdivision-based multilevel methods for large scale engineering simulation of thin shells

ABSTRACT

This paper presents a multilevel algorithm to accelerate the numerical solution of thin shell finite element problems de-scribed by subdivision surfaces. Subdivision surfaces have become a widely used geometric representation for general curved three dimensional boundary models and thin shells as they provide a compact and robust framework for mod-eling 3D geometry. More recently, the shape functions used in the subdivision surfaces framework have been proposed as candidates for use as finite element basis functions in the analysis and simulation of the mechanical deformation of thin shell structures. When coupled with standard solvers, however, such simulations do not scale well. Run time costs associated with high-resolution simulations (105 degrees of freedom or more) become prohibitive. The main contribution of the paper is to show that the subdivision framework can be used for accelerating such sim-ulations. Specifically the subdivision matrix is used as the intergrid information transfer operator in a multilevel pre-conditioner. The method described in the paper allows the practical simulation or a broad range of problems. Included examples show that the run time of the algorithm presented scales nearly linearly in time with problem size.

References

1. G. Arden. Approximation Properties of Subdivision Surfaces. PhD thesis, University of Washington, 2001
2. S. Ashby and R. Falgout. A Parallel Multigrid Preconditioned Conjugate Gradient Algorithm for Groundwater Flow Simulations. Nuclear Science and Engineering, (124):145--159, 1996
3. Bathe. Finite Element Procedures. Prentice-Hall, Englewood Clffs, N.J., 1996
4. F. Cirak and M. Ortiz. Fully C 1 -conforming subdivision elements for finite deformation thin-shell analysis. International Journal for Numerical Methods in Engineering, 51(7):813--833, July 2001
5. F. Cirak, M. Ortiz, and P. Schröder. Subdivision Surfaces: a New Paradigm for Thin-Shell Finite-Element Analysis. International Journal for Numerical Methods in Engineering, 47(12):2039--72, April 2000
6. F. Cirak, M. J. Scott, E. Antonsson, M. Ortiz, and P. Schröder. Integrated Modeling, Finite-Element Analysis, and Engineering Design for Thin-Shell Structures using Subdivision Surfaces. Preprint
7. P. Schröder D. Zorin, editor. SIGGRAPH: Subdivision Course Notes, CDROM supplement, 2000
8. W. G. Davids and G. M. Turkiyyah. Multigrid Preconditioner for Unstructured Nonlinear 3D FE Models. Journal of Engineering Mechanics, 125(2):186--196, February 1999
9. J. W. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, and Joseph W. H. Liu. A supernodal approach to sparse partial pivoting. SIAM Journal on Matrix Analysis and Applications, 20(3):720--755, 1999
10. T. DeRose, M. Kass, and Tien Truong. Subdivision Surfaces in Character Animation. In Computer Graphics (Siggraph 1998 Proceedings), pages 85--94, 1998
11. L. Guibas and J. Stolfi. Primitives for the Manipulation of General Subdivisions and the Compuation of Voronoi Diagrams. ACM Transactions on Graphics, 4(2):74--123, 1985
12. H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, and W. Stuetzle. Piecewise smooth surface reconstruction. Computer Graphics, 28(Annual Conference Series):295--302, 1994
13. C. Loop. Smooth Subdivision Surfaces Based on Triangles. Master's thesis, University of Utah, 1987
14. C. Mandal, H. Qin, and B. C. Vemuri. A novel fem=based dynamic framework for subdivision surfaces. In Sixth ACM Symposium on Solid Modeling and Applications. ACM Press, 1999
15. J. C. Meza and R. S. Tuminaro. A Multigrid Preconditioner for the Semiconductor Equations. SIAM J. Sci. Comput., 17(1):118--132, January 1996
16. I. D. Parsons and J. F. Hall. The Multigrid Method in Solid Mechanics: Part I - Algorithm Description and Behavior. International Journal for Numerical Methods in Engineering, 29:719--737, 1990
17. Hong Qin, Chhandomay Mandal, and Baba C. Vemuri. Dynamic catmull-clark subdivision surfaces. IEEE Transactions on Visualization and Computer Graphics, 4(3):215--229, 1998
18. Y. Saad. Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, MA, 1996
19. J. C. Simo and D. D. Fox. On A Stress Resultant Geometrically Exact Shell Model. Part I: Formulation and Optimal Parameterization. Computer Methods in Applied Mechanics and Engineering, 72:267--304, 1989
20. J. Stam. Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values. In Computer Graphics, pages 395--404. ACM, 1998
21. J. Stam. Exact Evaluation of Loop Triangular Subdivision Surfaces at Arbitrary Parameter Values. In Computer Graphics. ACM, 1998. CD-ROM Supplement
22. G. Taubin. Is This A Quadrisected Mesh? In D. C. Anderson and K. Lee, editors, Sixth ACM Symposium on Solid Modeling and Applications, pages 261--266. ACM Press, 2001
23. U. Trottenberg, C. Oosterlee, and A. Schüller. Multigrid. Academic Press, London, UK, 2001
24. P. Schröder U. Reif. Curvature integrability of subdivision surfaces. Advances in Computational Mathematics, 14(2):157--174, 2001
25. D. Zorin. Stationary Subdivision and Multiresolution Surface Representation. PhD thesis, Cal.Tech., 1998

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design