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: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 10: Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.85-94, July 1998 [doi>10.1145/280814.280826]
• 11: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 12: Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994 [doi>10.1145/192161.192233]
• 13: C. Loop. Smooth Subdivision Surfaces Based on Triangles. Master's thesis, University of Utah, 1987
• 14: Chhandomay Mandal , Hong Qin , Baba C. Vemuri, A novel FEM-based dynamic framework for subdivision surfaces, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.191-202, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304031]
• 15: Juan C. Meza , Ray S. Tuminaro, A multigrid preconditioner for the semiconductor equations, SIAM Journal on Scientific Computing, v.17 n.1, p.118-132, Jan. 1996 [doi>10.1137/0917010]
• 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 , Baba C. Vemuri, Dynamic Catmull-Clark Subdivision Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.4 n.3, p.215-229, July 1998 [doi>10.1109/2945.722296]
• 18: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 19: J. C. Simo , D. D. Fox, On stress resultant geometrically exact shell model. Part I: formulation and optimal parametrization, Computer Methods in Applied Mechanics and Engineering, v.72 n.3, p.267-304, Mar. 1989 [doi>10.1016/0045-7825(89)90002-9]
• 20: Jos Stam, Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.395-404, July 1998 [doi>10.1145/280814.280945]
• 21: J. Stam. Exact Evaluation of Loop Triangular Subdivision Surfaces at Arbitrary Parameter Values. In Computer Graphics. ACM, 1998. CD-ROM Supplement
• 22: Gabriel Taubin, Is this a quadrisected mesh?, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.261-266, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376987]
• 23: Ulrich Trottenberg , Anton Schuller, Multigrid, Academic Press, Inc., Orlando, FL, 2000
• 24: P. Schröder U. Reif. Curvature integrability of subdivision surfaces. Advances in Computational Mathematics, 14(2):157--174, 2001
• 25: Denis N. Zorin, Stationary subdivision and multiresolution surface representations, 1998

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
multigrid, multilevel, multiresolution, numerical algorithm, subdivision surface, thin shell