“Non-polynomial Galerkin projection on deforming meshes” by Stanton, Sheng, Wicke, Perazzi, Yuen, et al. …
Conference:
Type:
Title:
- Non-polynomial Galerkin projection on deforming meshes
Session/Category Title: Data-Driven Animation
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
