Doug L. James
Dinesh K. Pai
Skip Abstract Section
Abstract
We present a framework for low-latency interactive simulation of linear elastostatic models, and other systems arising from linear elliptic partial differential equations, which makes it feasible to interactively simulate large-scale physical models. The deformation of the models is described using precomputed Green's functions (GFs), and runtime boundary value problems (BVPs) are solved using existing Capacitance Matrix Algorithms (CMAs). Multiresolution techniques are introduced to control the amount of information input and output from the solver thus making it practical to simulate and store very large models. A key component is the efficient compressed representation of the precomputed GFs using second-generation wavelets on surfaces. This aids in reducing the large memory requirement of storing the dense GF matrix, and the fast inverse wavelet transform allows for fast summation methods to be used at run-time for response synthesis. Resulting GF compression factors are directly related to interactive simulation speedup, and examples are provided with hundredfold improvements at modest error levels. We also introduce a multiresolution constraint satisfaction technique formulated as a hierarchical CMA, so named because of its use of hierarchical GFs describing the response due to hierarchical basis constraints. This direct solution approach is suitable for hard real-time simulation since it provides a mechanism for gracefully degrading to coarser resolution constraint approximations. The GFs' multiresolution displacement fields also allow for run-time adaptive multiresolution rendering.
- Alpert, B., Beylkin, G., Coifman, R., and Rokhlin, V. 1993. Wavelet-like bases for the fast solution of second-kind integral equations. SIAM J. Sci. Comput. 14, 1 (Jan.), 159--184. Google Scholar
Digital Library
- Ascher, U. M. and Petzold, L. R. 1998. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM, Philadelphia. Google Scholar
- Astley, O. and Hayward, V. 1998. Multirate haptic simulation achieved by coupling finite element meshes through Norton equivalents. In Proceedings of the IEEE International Conference on Robotics and Automation.Google Scholar
- Balaniuk, R. 2000. Building a haptic interface based on a buffer model. In Proceedings of the IEEE International Conference on Robotics and Automation (San Francisco).Google Scholar
- Baraff, D. and Witkin, A. 1992. Dynamic simulation of non-penetrating flexible bodies. In Computer Graphics (SIGGRAPH 92 Conference Proceedings), 303--308. Google Scholar
- Baraff, D. and Witkin, A. 1998. Large steps in cloth simulation. In SIGGRAPH 98 Conference Proceedings, 43--54. Google Scholar
- Barber, J. R. 1992. Elasticity, first ed. Kluwer, Dordrecht.Google Scholar
- Basdogan, C. 2001. Real-time simulation of dynamically deformable finite element models using modal analysis and spectral Lanczos decomposition methods. In Proceedings of the Medicine Meets Virtual Reality (MMVR'2001) Conference, 46--52.Google Scholar
- Berkley, J., Weghorst, S., Gladstone, H., Raugi, G., Berg, D., and Ganter, M. 1999. Fast finite element modeling for surgical simulation. In Proceedings of Medicine Meets Virtual Reality, 55--61.Google Scholar
- Beylkin, G. 1992. On the representation of operators in bases of compactly supported wavelets. SIAM J. Numer. Anal. 29, 6 (Dec.), 1716--1740. Google ScholarDigital Library
- Beylkin, G., Coifman, R., and Rokhlin, V. 1991a. Fast wavelet transforms and numerical algorithms. Commun. Pure Appl. Math. 44, 141--183.Google ScholarCross Ref
- Beylkin, G., Coifman, R., and Rokhlin, V. 1991b. Fast wavelet transforms and numerical algorithms I. Commun. Pure Appl. Math. 44, 141--183.Google ScholarCross Ref
- Brebbia, C. A., Telles, J. C. F., and Wrobel, L. C. 1984. Boundary Element Techniques: Theory and Applications in Engineering, second ed. Springer-Verlag, New York.Google Scholar
- Bro-Nielsen, M. and Cotin, S. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Comput. Graph. Forum 15, 3 (Aug.), 57--66.Google ScholarCross Ref
- Çavuşoğlu, M. C. and Tendick, F. 2000. Multirate simulation for high fidelity haptic interaction with deformable objects in virtual environments. In Proceedings of the IEEE International Conference on Robotics and Automation (San Francisco).Google Scholar
- Cotin, S., Delingette, H., and Ayache, N. 1999. Realtime elastic deformations of soft tissues for surgery simulation. IEEE Trans. Vis. Comput. Graph. 5, 1, 62--73. Google ScholarDigital Library
- Cyberware. Available at http://www.cyberware.com.Google Scholar
- Dahmen, W. 1996. Stability of multiscale transformations. J. Fourier Anal. Appl. 4, 341--362.Google Scholar
- Daubechies, I. and Sweldens, W. 1996. Factoring wavelet transforms into lifting steps. Tech. Rep. Bell Laboratories, Lucent Technologies.Google Scholar
- Debunne, G., Desbrun, M., Barr, A., and Cani, M.-P. 2001. Dynamic real-time deformations using space and time adaptive sampling. In Computer Graphics (SIGGRAPH 2001 Conference Proceedings). Google Scholar
- Desbrun, M., Schröder, P., and Barr, A. 1999. Interactive animation of structured deformable objects. In Proceedings of Graphics Interface, 1--8. Google Scholar
- DeVore, R., Jawerth, B., and Lucier, B. 1992. Image compression through wavelet transform coding. IEEE Trans. Inf. Theor. 38, 719--746.Google ScholarCross Ref
- Dyn, N., Levin, D., and Gregory, J. A. 1990. A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph. 9, 2 (Apr.), 160--169. Google ScholarDigital Library
- Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. Comput. Graph. 29, Annual Conference Series, 173--182. Google Scholar
- Ezawa, Y. and Okamoto, N. 1989. High-speed boundary element contact stress analysis using a super computer. In Proceedings of the Fourth International Conference on Boundary Element Technology, 405--416.Google Scholar
- Gibson, S. F. and Mirtich, B. 1997. A survey of deformable models in computer graphics. Tech. Rep. TR-97-19, Mitsubishi Electric Research Laboratories, Cambridge, Mass. November.Google Scholar
- Golub, G. H. and Loan, C. F. V. 1996. Matrix Computations, third ed. Johns Hopkins University Press, Baltimore. Google Scholar
- Gortler, S. J., Schröder, P., Cohen, M. F., and Hanrahan, P. 1993. Wavelet radiosity. In Computer Graphics Proceedings, Annual Conference Series, 221--230. Google Scholar
- Greengard, L. and Rokhlin, V. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 325--348. Google ScholarDigital Library
- Guskov, I., Vidimce, K., Sweldens, W., and Schröder, P. 2000. Normal meshes. In SIGGRAPH 2000 Conference Proceedings, K. Akeley, Ed., Annual Conference Series. ACM Press/ACM SIGGRAPH/Addison Wesley Longman, Reading, Mass., 95--102. Google Scholar
- Hackbusch, W. 1985. Multi-Grid Methods and Applications. Springer, Berlin.Google Scholar
- Hackbusch, W. and Nowak, Z. P. 1989. On the fast matrix multiplication in the boundary element method by panel clustering. Numerische Mathematik 54, 4, 463--491.Google ScholarDigital Library
- Hager, W. W. 1989. Updating the inverse of a matrix. SIAM Rev. 31, 2 (June), 221--239. Google ScholarDigital Library
- Hartmann, F. 1985. The mathematical foundation of structural mechanics. Springer-Verlag, New York.Google Scholar
- Hauth, M. and Etzmuss, O. 2001. A high performance solver for the animation of deformable objects using advanced numerical methods. In Proceedings of Eurographics 2001 (to appear).Google Scholar
- Hirota, K. and Kaneko, T. 1998. Representation of soft objects in virtual environments. In Proceedings of the Second International Conference on Artificial Reality and Tele-Existence.Google Scholar
- James, D. L. 2001. Multiresolution Green's function methods for interactive simulation of large-scale elastostatic objects and other physical systems in equilibrium. Ph.D. Thesis, Institute of Applied Mathematics, University of British Columbia, Vancouver, British Columbia, Canada. Google Scholar
- James, D. L. and Pai, D. K. 1999. ArtDefo: Accurate real time deformable objects. Comput. Graph. 33, Annual Conference Series, 65--72. Google Scholar
- James, D. L. and Pai, D. K. 2001. A unified treatment of elastostatic contact simulation for real time haptics. Haptics-e, Elect. J. Haptics Res. 2, 1 (Sept.). Available at www.haptics-e.org.Google Scholar
- James, D. L. and Pai, D. K. 2002a. DyRT: Dynamic response textures for real time deformation simulation with graphics hardware. In SIGGRAPH 2002 Conference Proceedings. Annual Conference Series. ACM Press/ACM SIGGRAPH (to appear). Google Scholar
- James, D. L. and Pai, D. K. 2002b. Real time simulation of multizone elastokinematic models. In Proceedings of the IEEE International Conference on Robotics and Automation (Washington, DC), 927--932.Google Scholar
- Jaswon, M. A. and Symm, G. T. 1977. Integral Equation Methods in Potential Theory and Elastostatics. Academic, New York.Google Scholar
- Kang, Y.-M., Choi, J.-H., Cho, H.-G., Lee, D.-H., and Park, C.-J. 2000. Real-time animation technique for flexible and thin objects. In Proceedings of WSCG, 322--329.Google Scholar
- Kassim, A. M. A. and Topping, B. H. V. 1987. Static reanalysis: A review. J. Struct. Eng. 113, 1029--1045.Google ScholarCross Ref
- Kellogg, O. D. 1929. Foundations of Potential Theory. Springer, Berlin.Google Scholar
- Khodakovsky, A., Schröder, P., and Sweldens, W. 2000. Progressive geometry compression. In SIGGRAPH 2000 Conference Proceedings, K. Akeley, Ed., Annual Conference Series. ACM Press / ACM SIGGRAPH / Addison Wesley Longman, Reading, Mass., 271--278. Google Scholar
- Kolarov, K. and Lynch, W. 1997. Compression of functions defined on the surface of 3D objects. In Proceedings of Data Compression Conference, J. Storer and M. Cohn, Eds., IEEE Computer Society Press, Los Almitos, Calif., 281--291. Google Scholar
- Krishnamurthy, V. and Levoy, M. 1996. Fitting smooth surfaces to dense polygon meshes. Comput. Graph. 30, Annual Conference Series, 313--324. Google Scholar
- Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. Numer. Meth. Eng. 51, 479--504.Google ScholarCross Ref
- Kühnapfel, U., Çakmak, H., and Maass, H. 1999. 3D modeling for endoscopic surgery. In Proceedings of IEEE Symposium on Simulation (Delft University, Delft, NL), 22--32.Google Scholar
- Lang, J. 2001. Deformable model acquisition and verification. PhD Thesis, Department of Computer Science, University of British Columbia. Google Scholar
- Lee, A., Moreton, H., and Hoppe, H. 2000. Displaced subdivision surfaces. In SIGGRAPH 2000 Conference Proceedings, 85--94. Google Scholar
- Lee, A., Sweldens, W., Schröder, P., Cowsar, L., and Dobkin, D. 1998. MAPS: Multiresolution adaptive parameterization of surfaces. In SIGGRAPH 98 Conference Proceedings, 95--104. Google Scholar
- Loop, C. 1987. Smooth subdivision surfaces based on triangles. MS Thesis, University of Utah, Department of Mathematics.Google Scholar
- Lounsbery, M., DeRose, T. D., and Warren, J. 1997. Multiresolution analysis for surfaces of arbitrary topological type. ACM Trans. Graph. 16, 1 (Jan.), 34--73. Google ScholarDigital Library
- Man, K. W., Aliabadi, M. H., and Rooke, D. P. 1993. Analysis of contact friction using the boundary element method. In Computational Methods in Contact Mechanics, M. H. Aliabadi and C. A. Brebbia, Eds. Computational Mechanics and Elsevier Applied Science, New York, Chapter 1, 1--60.Google Scholar
- Morgenbesser, H. B. and Srinivasan, M. A. 1996. Force shading for haptic shape perception. In Proceedings of the ASME Dynamics Systems and Control Division, vol. 58.Google Scholar
- Pai, D. K., van den Doel, K., James, D. L., Lang, J., Lloyd, J. E., Richmond, J. L., and Yau, S. H. 2001. Scanning physical interaction behavior of 3D objects. In SIGGRAPH 2001 Conference Proceedings, ACM SIGGRAPH, New York. Google Scholar
- Paraform. Available at http://www.paraform.com.Google Scholar
- Pentland, A. and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. Computer Graphics (Proceedings of SIGGRAPH 89) 23, 3, (Boston, July), 215--222. Google Scholar
- Picinbono, G., Delingette, H., and Ayache, N. 2001. Non-linear and anisotropic elastic soft tissue models for medical simulation. In Proceedings of IEEE International Conference on Robotics and Automation (Seoul, Korea).Google Scholar
- Proskurowski, W. and Widlund, O. 1980. A finite element-capacitance matrix method for the Neumann problem for Laplace's equation. SIAM J. Sci. Stat. Comput. 1, 4 (Dec.), 410--425.Google ScholarDigital Library
- Raindrop Geomagic, Inc. Available at http://www.geomagic.com.Google Scholar
- Reachin. Available at http://www.reachin.se.Google Scholar
- Said, A. and Pearlman, W. A. 1996. A new fast and efficient image codec based on set partitioning in hierarchical trees. IEEE Trans. Circ. Syst. Video Technol. 6, 243--250. Google ScholarDigital Library
- Schröder, P. and Sweldens, W. 1995a. Spherical wavelets: Efficiently representing functions on the sphere. In Computer Graphics (Proceedings of SIGGRAPH 95). ACM SIGGRAPH, New York, 161--172. Google Scholar
- Schröder, P. and Sweldens, W. 1995b. Spherical wavelets: Texture processing. In Rendering Techniques '95 (Proceedings of the Sixth Eurographics Workshop on Rendering), P. M. Hanrahan and W. Purgathofer, Eds., Springer-Verlag, New York, 252--263.Google Scholar
- Shapiro, J. M. 1993. Embedded image coding using zerotrees of wavelet coefficients. IEEE Trans. Acoustics, Speech Signal Process. 41, 12, 3445--3462.Google ScholarDigital Library
- Stam, J. 1997. Stochastic dynamics: Simulating the effects of turbulence on flexible structures. Comput. Graph. Forum (EUROGRAPHICS 2001 Proceedings) 16, 3.Google Scholar
- Sweldens, W. 1998. The lifting scheme: A construction of second generation wavelets. SIAM J. Math. Anal. 29, 2 (Mar.), 511--546. Google ScholarDigital Library
- Székely, G., Brechböhler, C., Dual, J., Enzler, R., Hug, J., Hutter, R., Ironmonger, N., Kauer, M., Meier, V., Niederer, P., Romberg, A., Schmid, P., Schweitzer, G., Thaler, M., Vuskovic, V., Tröster, G., Haller, U., and Bajka, M. 2000. Virtual reality-based simulation of endoscopic surgery. Presence 9, 3 (June), 310--333. Google ScholarDigital Library
- Terzopoulos, D. and Fleischer, K. 1988. Deformable models. Vis. Comput. 4, 306--331.Google ScholarCross Ref
- Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Comput. Graph. (Proceedings of SIGGRAPH 87), M. C. Stone, Ed, ACM, New York, 205--214. Google Scholar
- van den Doel, K. and Pai, D. K. 1998. The sounds of physical shapes. Presence 7, 4, 382--395. Google ScholarDigital Library
- Weimer, H. and Warren, J. 1998. Subdivision schemes for thin plate splines. Comput. Graph. Forum 17, 3, 303--314.Google ScholarCross Ref
- Weimer, H. and Warren, J. 1999. Subdivision schemes for fluid flow. In SIGGRAPH 1999 Conference Proceedings, A. Rockwood, Ed, Addison Wesley Longman, Los Angeles, 111--120. Google Scholar
- Wu, X., Downes, M., Goktekin, T., and Tendick, F. 2001. Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshes. In Eurographics 2001, A. Chalmers and T.-M. Rhyne, Eds.Google Scholar
- Xia, J. C., El-Sana, J., and Varshney, A. 1997. Adaptive real-time level-of-detail-based rendering for polygonal models. IEEE Trans. Vis. Comput. Graph. 3, 2, 171--183. Google ScholarDigital Library
- Yoshida, K., Nishimura, N., and Kobayashi, S. 2001. Application of fast multipole Galerkin boundary integral equation method to elastostatic crack problems in 3D. Int. J. Numer. Meth. Eng. 50, 525--547.Google ScholarCross Ref
- Yserentant, H. 1986. On the multilevel splitting of finite element spaces. Numer. Math. 49, 379--412. Google ScholarDigital Library
- Zhuang, Y. and Canny, J. 2000. Haptic interaction with global deformations. In Proceedings of the IEEE International Conference on Robotics and Automation (San Francisco).Google Scholar
- Zienkiewicz, O. C. 1977. The Finite Element Method. McGraw-Hill, Maidenhead, Berkshire, England.Google Scholar
- Zilles, C. B. and Salisbury, J. K. 1994. A constraint-based god-object method for haptic display. In ASME Haptic Interfaces for Virtual Environment and Teleoperator Systems, vol. 1 (Chicago), 149--150.Google Scholar
- Zorin, D. and Schröder, P., Eds. 2000. Course notes: Subdivision for modeling and animation. ACM SIGGRAPH, New York.Google Scholar
Index Terms
- Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects
Recommendations
Wavelet bi-frames with uniform symmetry for curve multiresolution processing
This paper is about the construction of univariate wavelet bi-frames with each framelet being symmetric. As bivariate filter banks are used for surface multiresolution processing, it is required that the corresponding decomposition and reconstruction ...
An adaptive wavelet collocation method for the solution of partial differential equations on the sphere
A dynamic adaptive numerical method for solving partial differential equations on the sphere is developed. The method is based on second generation spherical wavelets on almost uniform nested spherical triangular grids, and is an extension of the ...
Comments