“CHARMS: a simple framework for adaptive simulation”

  • ©Eitan Grinspun, Petr Krysl, and Peter Schröder

  • ©Eitan Grinspun, Petr Krysl, and Peter Schröder




    CHARMS: a simple framework for adaptive simulation



    Finite element solvers are a basic component of simulation applications; they are common in computer graphics, engineering, and medical simulations. Although adaptive solvers can be of great value in reducing the often high computational cost of simulations they are not employed broadly. Indeed, building adaptive solvers can be a daunting task especially for 3D finite elements. In this paper we are introducing a new approach to produce conforming, hierarchical, adaptive refinement methods (CHARMS). The basic principle of our approach is to refine basis functions, not elements. This removes a number of implementation headaches associated with other approaches and is a general technique independent of domain dimension (here 2D and 3D), element type (e.g., triangle, quad, tetrahedron, hexahedron), and basis function order (piece-wise linear, higher order B-splines, Loop subdivision, etc.). The (un-)refinement algorithms are simple and require little in terms of data structure support. We demonstrate the versatility of our new approach through 2D and 3D examples, including medical applications and thin-shell animations.


    1. ALPERT, B. K. 1993. A Class of Bases in L2 for the Sparse Representation of Integral Operators. SIAM Journal on Mathematical Analysis 24, 246-262. Google Scholar
    2. ARNOLD, D. N., MUKHERJEE, A., AND POULY, L. 2001. Locally Adapted Tetrahedra Meshes using Bisection. SIAM Journal on Scientific Computing 22, 2, 431-448. Google Scholar
    3. AZAR, F. S., METAXAS, D. N., AND SCHNALL, M. D. 2001. A Deformable Finite Element Model of the Breast for Predicting Mechanical Deformations under External Perturbations. Academic Radiology 8, 10, 965-975.Google Scholar
    4. BAJAJ, C., WARREN, J., AND XU, G. 2002. A Smooth Subdivision Scheme for Hexahedral Meshes. The Visual Computer. to appear.Google Scholar
    5. BANK, R., AND XU, J. 1996. An Algorithm for Coarsening Unstructured Meshes. Numerische Mathematik 73, 1, 1-36.Google Scholar
    6. BEY, J. 2000. Simiplicial Grid Refinement: On Freudenthal’s Algorithm and the Optimal Number of Congruence Classes. Numerische Mathematik 85, 1-29.Google Scholar
    7. CATMULL, E., AND CLARK, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. CAD 1O, 6, 350-355.Google Scholar
    8. CELNIKER, G., AND GOSSARD, D. 1991. Deformable Curve and Surface Finite Elements for Free-Form Shape Design. Computer Graphics (Proceedings of SIGGRAPH 91) 25, 4, 257-266 Google Scholar
    9. CIRAK, F., AND ORTIZ, M. 2001. Fully c1-conforming subdivision elements for finite deformation thin-shell analysis. IJNME 51, 7, 813-833.Google Scholar
    10. CIRAK, F., ORTIZ, M., AND SCHRÖDER, P. 2000. Subdivision surfaces: A new paradigm for thin-shell finite-element analysis. IJNME 47, 12, 2039-2072.Google Scholar
    11. COHEN, A., DEVORE, R., AND DAHMEN, W. 2001. Adaptive Wavelet Methods for Elliptic Operator Equations: Convergence Rates. Mathematics of Computation 70, 233, 27-75. Google Scholar
    12. DEBUNNE, G., DESBRUN, M., CANI, M.-P., AND BARR, A. H. 2001. Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling. Proceedings of SIGGRAPH 2001, 31-36. Google Scholar
    13. DESLAURIERS, G., AND DUBUC, S. 1989. Symmetric iterative interpolation processes. Constructive Approximation 5, 1, 49-68.Google Scholar
    14. DOO, D., AND SABIN, M. 1978. Analysis of the behaviour of recursive division surfaces near extraordinary points. CAD 10, 6, 356-360.Google Scholar
    15. DYN, N., LEVIN, D., AND GREGORY, J. A. 1990. A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control. ACM TOG 9, 2 (April), 160-169. Google Scholar
    16. FORSEY, D. R., AND BARTELS, R. H. 1988. Hierarchical B-Spline Refinement. Computer Graphics (Proceedings of SIGGRAPH 88) 22, 4, 205-212. Google Scholar
    17. FOSTER, N., AND FEDKIW, R. 2001. Practical Animation of Liquids. Proceedings of SIGGRAPH 2001, 23-30. Google Scholar
    18. GORTLER, S. J., AND COHEN, M. F. 1995. Hierarchical and Variational Geometric Modeling with Wavelets. 1995 Symposium on Interactive 3D Graphics, 35-42. Google Scholar
    19. GORTLER, S. J., SCHRÖDER, P., COHEN, M. F., AND HANRAHAN, P. 1993. Wavelet Radiosity. Proceedings of SIGGRAPH 93, 221-230. Google Scholar
    20. GOURRET, J.-P., THALMANN, N. M., AND THALMANN, D. 1989. Simulation of Object and Human Skin Deformations in a Grasping Task. Computer Graphics (Proceedings of SIGGRAPH 89) 23, 3, 21-30. Google Scholar
    21. HALSTEAD, M., KASS, M., AND DEROSE, T. 1993. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. Proceedings of SIGGRAPH 93, 35-44. Google Scholar
    22. HOPPE, H. 1996. Progressive Meshes. Proceedings of SIGGRAPH 96, 99-108. Google Scholar
    23. HOUSE, D. H., AND BREEN, D. E., Eds. 2000. Coth Modeling and Animation. A. K. Peters. Google Scholar
    24. JOHNSON, C. 2001. Adaptive finite element and local regularization methods for the inverse ECG problem. In Inverse Problems in Electrocardiology, WIT Press, P. Johnston, Ed.Google Scholar
    25. KAGAN, P., AND FISCHER, A. 2000. Integrated mechanically based CAE system using B-Spline finite elements. CAD 32, 8-9, 539-552.Google Scholar
    26. KOBBELT, L. 2000. √3 Subdivision. Proceedings of SIGGRAPH 2000, 103-112. Google Scholar
    27. KOBER, C., AND MULLER-HANNEMANN, M. 2000. Hexahedral Mesh Generation for the Simulation of the Human Mandible. In Proceedings of the 9th International Meshing Roundtable, Sandia National Laboratories, 423-434.Google Scholar
    28. KRAFT, R. 1997. Adaptive and linearly independent multilevel B-splines. In Surface Fitting and Multiresolution Methods, A. L. Méhauté, C. Rabut, and L. L. Schumaker, Eds., vol. 2. Vanderbilt University Press, 209-218.Google Scholar
    29. KRYSL, P., GRINSPUN, E., AND SCHRÖDER, P. 2002. Natural hierarchical refinement for finite element methods. To appear; IJNME, http://hogwarts.ucsd.edu/~pkrysl/pubs/adref.pdf.Google Scholar
    30. LANGTANGEN, H. P. 1999. Computational Partial Differential Equations. Springer Verlag. Google Scholar
    31. LEE, S., WOLBERG, G., AND SHIN, S. Y. 1997. Scattered Data Interpolation with Multilevel B-Splines. IEEE TVCG 3, 3, 228-244. Google Scholar
    32. LOOP, C. 1987. Smooth Subdivision Surfaces Based on Triangles. Master’s thesis, University of Utah, Department of Mathematics.Google Scholar
    33. LOUNSBERY, M., DEROSE, T. D., AND WARREN, J. 1997. Multiresolution analysis for surfaces of arbitrary topological type. ACM TOG 16, 1, 34-73. Google Scholar
    34. MANDAL, C., QIN, H., AND VEMURI, B. C. 1997. Dynamic Smooth Subdivision Surfaces for Data Visualization. In IEEE Visualization ’97, 371-378. Google Scholar
    35. METAXAS, D., AND TERZOPOULOS, D. 1992. Dynamic deformation of solid primitives with constraints. Computer Graphics (Proceedings of SIGGRAPH 92) 26, 2, 309-312. Google Scholar
    36. O’BRIEN, J. F., AND HODGINS, J. K. 1999. Graphical Modeling and Animation of Brittle Fracture. In Proceedings of SIGGRAPH 99, 137-146. Google Scholar
    37. RIVARA, M., AND INOSTROZA, P. 1997. Using Longest-side Bisection Techniques for the Automatic Refinement of Delaunay Triangulations. IJNME 40, 4, 581-597.Google Scholar
    38. STAM, J. 2001. On Subdivision Schemes Generalizing Uniform B-Spline Surfaces of Arbitrary Degree. CAGD 18, 5 (June), 383-396. Google Scholar
    39. STRANG, G., AND FIX, G. 1973. An Analysis of the Finite Element Method. Wellesley-Cambridge Press.Google Scholar
    40. STRANG, G., AND NGUYEN, T. 1996. Wavelets and Filter Banks. Wellesley-Cambridge Press.Google Scholar
    41. STRELA, V., HELLER, P. N., STRANG, G., TOPIWALA, P., AND HEIL, C. 1999. The Application of Multiwavelet Filterbanks to Image Processing. IEEE TIP 8, 4, 548-563. Google Scholar
    42. TERZOPOULOS, D., AND QIN, H. 1994. Dynamic NURBS with Geometric Constraints for Interactive Sculpting. ACM TOG 13, 2, 103-136. Google Scholar
    43. TERZOPOULOS, D., PLATT, J., BARR, A., AND FLEISCHER, K. 1987. Elastically Deformable Models. Computer Graphics (Proceedings of SIGGRAPH 87) 21, 4, 205-214. Google Scholar
    44. TIMOSHENKO, S., AND WOINOWSKY-KRIEGER, S. 1959. Theory of Plates and Shells. McGraw-Hill Book Company Inc.Google Scholar
    45. VELHO, L., AND ZORIN, D. 2001. 4-8 Subdivision. CAGD 18, 5 (June), 397-427. Google Scholar
    46. WARFIELD, S. K., FERRANT, M., GALLEZ, X., NABAVl, A., JOLESZ, F. A., AND KIKINIS, R. 2000. Real-time biomechanical simulation of volumetric brain deformation for image guided neurosurgery. In SC 2000: High performance networking and computing conference, vol. 230, 1-16. Google Scholar
    47. WELCH, W., AND WITKIN, A. 1992. Variational Surface Modeling. Computer Graphics (Proceedings of SIGGRAPH 92) 26, 2, 157-166. Google Scholar
    48. WU, X., DOWNES, M. S., GOKTEKIN, T., AND TENDICK, F. 2001. Adaptive Nonlinear Finite Elements for Deformable Body Simulation Using Dynamic Progressive Meshes. Computer Graphics Forum 20, 3, 349-358.Google Scholar
    49. YSERENTANT, H. 1986. On the multilevel splitting of finite-element spaces. Numerische Mathematik 49, 4, 379-412. Google Scholar
    50. ZIENKIEWICZ, O. C., AND TAYLOR, R. L. 2000. The finite element method: The basis, 5 ed., vol. 1. Butterworth and Heinemann.Google Scholar
    51. ZORIN, D., AND SCHRÖDER, P., Eds. 2000. Subdivision for Modeling and Animation. Course Notes. ACM Siggraph.Google Scholar
    52. ZORIN, D., AND SCHRÖDER, P. 2001. A Unified Framework for Primal/Dual Quadrilateral Subdivision Schemes. CAGD 18, 5, 429-454. Google Scholar
    53. ZORIN, D., SCHRÖDER, P., AND SWELDENS, W. 1996. Interpolating Subdivision for Meshes with Arbitrary Topology. Proceedings of SIGGRAPH 96, 189-192. Google Scholar
    54. ZORIN, D. 2000. Smoothness of Subdivision on Irregular Meshes. Constructive Approximation 16, 3, 359-397. Google Scholar

ACM Digital Library Publication:

Overview Page: