“Non-polynomial Galerkin projection on deforming meshes” by Stanton, Sheng, Wicke, Perazzi, Yuen, et al. …

  • ©Matt Stanton, Yu Sheng, Martin Wicke, Federico Perazzi, Amos Yuen, Srinivasa Narasimhan, and Adrien Treuille



Session Title:

    Data-Driven Animation


    Non-polynomial Galerkin projection on deforming meshes




    This paper extends Galerkin projection to a large class of non-polynomial functions typically encountered in graphics. We demonstrate the broad applicability of our approach by applying it to two strikingly different problems: fluid simulation and radiosity rendering, both using deforming meshes. Standard Galerkin projection cannot efficiently approximate these phenomena. Our approach, by contrast, enables the compact representation and approximation of these complex non-polynomial systems, including quotients and roots of polynomials. We rely on representing each function to be model-reduced as a composition of tensor products, matrix inversions, and matrix roots. Once a function has been represented in this form, it can be easily model-reduced, and its reduced form can be evaluated with time and memory costs dependent only on the dimension of the reduced space.


    1. An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Transactions on Graphics 27, 5 (Dec.), 165:1–165:10. Google ScholarDigital Library
    2. Ausseur, J., Pinier, J., Glauser, M., and Higuchi, H. 2004. Predicting the dynamics of the flow over a NACA 4412 using POD. APS Meeting Abstracts, D8.Google Scholar
    3. Barbič, J., and James, D. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. In Proc. SIGGRAPH ’05. Google ScholarDigital Library
    4. Barbič, J., and Popović, J. 2008. Real-time control of physically based simulations using gentle forces. ACM Transactions on Graphics 27, 5. Google ScholarDigital Library
    5. Benzi, M., Golub, G. H., and Liesen, J. 2005. Numerical solution of saddle point problems. Acta Numerica 14, 1–137.Google ScholarCross Ref
    6. Carlberg, K., Bou-Mosleh, C., and Farhat, C. 2011. Efficient non-linear model reduction via a least-squares Petrov-Galerkin projection and compressive tensor approximations. International Journal for Numerical Methods in Engineering 86, 2, 155–181.Google ScholarCross Ref
    7. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.Google Scholar
    8. Chadwick, J., An, S. S., and James, D. L. 2009. Harmonic shells: A practical nonlinear sound model for near-rigid thin shells. ACM Transactions on Graphics 28, 5 (Dec.), 119:1–119:10. Google ScholarDigital Library
    9. Chahlaoui, Y., and van Dooren, P. 2005. Model reduction of time-varying systems. In Dimension Reduction of Large-Scale Systems. Springer, 131–148.Google Scholar
    10. de Witt, T., Lessig, C., and Fiume, E. 2012. Fluid simulation using Laplacian eigenfunctions. ACM Transactions on Graphics 31, 1 (Jan.). Google ScholarDigital Library
    11. Debusschere, B. J., Najm, H. N., Pebay, P. P., Knio, O. M., Ghanem, R. G., and Maitre, O. P. L. 2004. Numerical challenges in the use of polynomial chaos representations for stochastic processes. SIAM J. Sci. Comp. 26, 2, 698–719. Google ScholarDigital Library
    12. Deconinck, H., and Ricchiuto, M. 2007. Residual distribution schemes: foundation and analysis. In Encyclopedia of Computational Mechanics, E. Stein, E. de Borst, and T. Hughes, Eds., vol. 3. John Wiley and Sons, Ltd.Google Scholar
    13. Dobes, J., and Deconinck, H. 2006. An ALE formulation of the multidimensional residual distribution scheme for computations on moving meshes. In Proc. Int. Conf. CFD.Google Scholar
    14. Dorsey, J., Sillion, F., and Greenberg, D. 1991. Design and simulation of opera lighting and projection effects. In Computer Graphics (Proceedings of SIGGRAPH 91), 41–50. Google ScholarDigital Library
    15. Drettakis, G., and Sillion, F. 1997. Interactive update of global illumination using a line-space hierarchy. In Proceedings of SIGGRAPH 97, Computer Graphics Proceedings, Annual Conference Series, 57–64. Google ScholarDigital Library
    16. Ebert, F., and Stykel, T. 2007. Rational interpolation, minimal realization and model reduction. Tech. rep., DFG Research Center Matheon.Google Scholar
    17. Elcott, S., Tong, Y., Kanso, E., Schröder, P., and Desbrun, M. 2007. Stable, circulation-preserving, simplicial fluids. ACM Transactions on Graphics 26, 1 (Jan.). Google ScholarDigital Library
    18. Farhood, M., and Dullerud, G. E. 2007. Model reduction of nonstationary LPV systems. IEEE Transactions on Automatic Control 52, 2, 181–196.Google ScholarCross Ref
    19. Feldman, B. E., O’Brien, J. F., and Klingner, B. M. 2005. Animating gases with hybrid meshes. In Proc. SIGGRAPH ’05. Google ScholarDigital Library
    20. Feldman, B. E., O’Brien, J. F., Klingner, B. M., and Goktekin, T. G. 2005. Fluids in deforming meshes. In 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 255–260. Google ScholarDigital Library
    21. Fogleman, M., Lumley, J., Rempfer, D., and Haworth, D. 2004. Application of the proper orthogonal decomposition to datasets of internal combustion engine flows. Journal of Turbulence 5, 23 (June).Google ScholarCross Ref
    22. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graphical Models and Image Processing 58, 5. Google ScholarDigital Library
    23. Gallivan, K., Grimme, E., and Dooren, P. V. 1996. A rational Lanczos algorithm for model reduction. Numerical Algorithms 12, 33–63.Google ScholarCross Ref
    24. Goral, C. M., Torrance, K. E., Greenberg, D. P., and Battaile, B. 1984. Modeling the interaction of light between diffuse surfaces. Computer Graphics 18, 3 (July), 213–222. Google ScholarDigital Library
    25. Grimme, E. J. 1997. Krylov Projection Methods For Model Reduction. PhD thesis, Ohio State University.Google Scholar
    26. Gugercin, S., and Antoulas, A. 2004. A survey of model reduction by balanced truncation and some new results. International Journal of Control 77, 8, 748–766.Google ScholarCross Ref
    27. Gugercin, S., Antoulas, A., and Beattie, C. A. 2006. A rational Krylov iteration for optimal H2 model reduction. In Intl. Symposium on Mathematical Theory of Networks and Systems.Google Scholar
    28. Gupta, M., and Narasimhan, S. G. 2007. Legendre fluids: A unified framework for analytic reduced space modeling and rendering of participating media. In 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 17–26. Google ScholarDigital Library
    29. Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. In Proc of SIGGRAPH. Google ScholarDigital Library
    30. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface, CIPS, Canadian Human-Computer Commnication Society, 247–256.Google Scholar
    31. Hossain, M.-S., and Benner, P. 2008. Projection-based model reduction for time-varying descriptor systems using recycled Krylov subspaces. Proceedings in Applied Mathematics and Mechanics 8, 1, 10081–10084.Google ScholarCross Ref
    32. James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. In Proc. SIGGRAPH ’03. Google ScholarDigital Library
    33. James, D. L., and Pai, D. K. 2002. DyRT: Dynamic response textures for real time deformation simulation with graphics hardware. ACM Transactions on Graphics 21, 3 (July), 582–585. Google ScholarDigital Library
    34. James, D. L., Barbic, J., and Pai, D. K. 2006. Precomputed acoustic transfer: output-sensitive, accurate sound generation for geometrically complex vibration sources. ACM Transactions on Graphics 25, 3 (July), 987–995. Google ScholarDigital Library
    35. Kim, T., and Delaney, J. 2013. Subspace fluid re-simulation. ACM Transactions on Graphics 32, 4. Google ScholarDigital Library
    36. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Transactions on Graphics 28, 5 (Dec.), 123:1–123:9. Google ScholarDigital Library
    37. Kim, T., and James, D. L. 2011. Physics-based character skinning using multi-domain subspace deformations. In Proc. SCA ’11. Google ScholarDigital Library
    38. Klingner, B. M., and Shewchuk, J. R. 2007. Agressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable, 3–23.Google Scholar
    39. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. ACM Transactions on Graphics 25, 3 (July), 820–825. Google ScholarDigital Library
    40. Li, J.-R. 2000. Model Reduction of Large Linear Systems. PhD thesis, Massachusetts Institute of Techology.Google Scholar
    41. Liua, C., Yuan, X., Mullaguru, A., and Fan, J. 2008. Model order reduction via rational transfer function fitting and eigenmode analysis. In International Conference on Modeling, Identification and Control.Google Scholar
    42. Loos, B. J., Antani, L., Mitchell, K., Nowrouzezahrai, D., Jarosz, W., and Sloan, P.-P. 2011. Modular radiance transfer. ACM Transactions on Graphics 30, 6 (Dec.). Google ScholarDigital Library
    43. Loos, B. J., Nowrouzezahrai, D., Jarosz, W., and Sloan, P.-P. 2012. Delta radiance transfer. In Proceedings of the 2012 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM, New York, NY, USA, I3D 2012. Google ScholarDigital Library
    44. Mullen, P., Crane, K., Pavlov, D., Tong, Y., and Desbrun, M. 2009. Energy-preserving integrators for fluid animation. ACM Transactions on Graphics 28, 3 (July), 38:1–38:8. Google ScholarDigital Library
    45. Olssen, K. H. A. 2005. Model Order Reduction with Rational Krylov Methods. PhD thesis, KTH Stockholm.Google Scholar
    46. Pavlov, D., Mullen, P., Tong, Y., Kanso, E., Marsden, J., and Desbrun, M. 2011. Structure-preserving discretization of incompressible fluids. Physica D: Nonlinear Phenomena 240, 6, 443–458.Google ScholarCross Ref
    47. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. Computer Graphics (SIGGRAPH 89) 23, 3 (July), 215–222. Held in Boston, Massachusetts. Google ScholarDigital Library
    48. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
    49. Phillips, J. R. 1998. Model reduction of time-varying linear systems using approximate multipoint Krylov-subspace projectors. Computer Aided Design, 96–102. Google ScholarDigital Library
    50. Rowley, C. W., and Marsden, J. E. 2000. Reconstruction equations and the Karhunen-Loéve expansion for systems with symmetry. Phys. D 142, 1-2, 1–19. Google ScholarDigital Library
    51. Rowley, C. W., Kevrekidis, I. G., Marsden, J. E., and Lust, K. 2003. Reduction and reconstruction for self-similar dynamical systems. Nonlinearity 16 (July), 1257–1275.Google ScholarCross Ref
    52. Sandberg, H., and Rantzer, A. 2004. Balanced truncation of linear time-varying systems. IEEE Transactions on Automatic Control 49, 2, 217–229.Google ScholarCross Ref
    53. Savas, B., and Eldén, L. 2009. Krylov subspace methods for tensor computations. Tech. Rep. LITH-MAT-R-2009-02-SE, Department of Mathematics, Linköpings Universitet.Google Scholar
    54. Schmit, R., and Glasuer, M. 2002. Low dimensional tools for flow-structure interaction problems: Application to micro air vehicles. APS Meeting Abstracts (Nov.), D1+.Google Scholar
    55. Sewall, J., Mecklenburg, P., Mitran, S., and Lin, M. 2007. Fast fluid simulation using residual distribution schemes. In Proc. Eurographics Workshop on Natural Phenomena. Google ScholarDigital Library
    56. Si, H. 2007. A quality tetrahedral mesh generator and 3-dimensional Delaunay triangulator. http://tetgen.berlios.de/.Google Scholar
    57. Sloan, P.-P., Kautz, J., and Snyder, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. In Proc. SIGGRAPH ’02. Google ScholarDigital Library
    58. Sloan, P.-P., Luna, B., and Snyder, J. 2005. Local, deformable precomputed radiance transfer. ACM Transactions on Graphics 24, 3 (Aug.), 1216–1224. Google ScholarDigital Library
    59. Sorkine, O. 2006. Differential representations for mesh processing. Computer Graphics Forum 25, 4, 789–807.Google ScholarCross Ref
    60. Stam, J. 1999. Stable fluids. In Computer Graphics (SIGGRAPH 99). Google ScholarDigital Library
    61. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. In Proc. SIGGRAPH ’06. Google ScholarDigital Library
    62. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Transactions on Graphics 28, 3. Google ScholarDigital Library
    63. Zatz, H. R. 1993. Galerkin radiosity: a higher order solution method for global illumination. In Proc. SIGGRAPH ’93, ACM. Google ScholarDigital Library
    64. Zhou, Y. 2002. Numerical Methods for Large Scale Matrix Equations with Applications in LTI System Model Reduction. PhD thesis, Rice University.Google Scholar

ACM Digital Library Publication: