“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