Numerical Methods for Geometry Processing
Fast and Exact (Poisson) Solvers on Symmetric Geometries
Abstract
In computer graphics, numerous geometry processing applications reduce to the solution of a Poisson equation. When considering geometries with symmetry, a natural question to consider is whether and how the symmetry can be leveraged to derive an efficient solver for the underlying system of linear equations. In this work we provide a simple representation-theoretic analysis that demonstrates how symmetries of the geometry translate into block diagonalization of the linear operators and we show how this results in efficient linear solvers for surfaces of revolution with and without angular boundaries.
References
- Agarwala A., Dontcheva M., Agrawala M., Drucker S., Colburn A., Curless B., Salesin D., Cohen M.: Interactive digital photomontage. ACM Transactions on Graphics (SIGGRAPH ‘04) (2004), 294–302. 6
- Aksoylu B., Khodakovsky A., Schröder P.: Multilevel solvers for unstructured surface meshes. SIAM Journal of Scientific Computing 26, 4 (2005), 1146–1165. 2
- Bindel D., Bruyns C.: Shape-changing symmetric objects for sound synthesis. In Audio Engineering Society 121 (2006), pp. 875–881. 2, 3, 4
- Botsch M., Bommes D., Kobbelt L.: Efficient linear system solvers for mesh processing. In In IMA Conference on the Mathematics of Surfaces (2005), Springer, pp. 62–83. 2, 7
- Bhat P., Curless B., Cohen M., Zitnick L.: Fourier analysis of the 2D screened Poisson equation for gradient domain problems. In European Conference on Computer Vision (2008), pp. 114–128. 6
- Briggs W., Henson V., McCormick S.: A Multigrid Tutorial. Society for Industrial and Applied Mathematics, 2000. 2
10.1137/1.9780898719505 Google Scholar
- Chen Y., Davis T., Hager W., Rajamanickam S.: Algorithm 887: Cholmod, supernodal sparse Cholesky factorization and update/downdate. ACM Transactions on Mathematical Software 35, 3 (2008), 22:1–22:14. 7
- Cleary A., Falgout R., Henson V., Jones J., Manteuffel T., McCormick S., Miranda G., Ruge J.: Robustness and scalability of algebraic multigrid. SIAM Journal of Scientific Computing 21, 5 (2000), 1886–1908. 2
- Chuang M., Luo L., Brown B., Rusinkiewicz S., Kazhdan M.: Estimating the Laplace-Beltrami operator by restricting 3d functions. In Proceedings of the Symposium on Geometry Processing (2009), pp. 1475–1484. 2
- Cooley J., Tukey J.: An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19 (1965), 297–301. 2
- Davis P.: Circulant matrices. Pure and applied mathematics. Wiley, 1979. 2, 3, 4
- Dagum L., Menon R.: OpenMP: An industry-standard API for shared-memory programming. IEEE Computational Science and Engineering 5, 1 (1998), 46–55. 6
- Elcott S., Tong T., Kanso E., Schröder P., Desbrun M.: Stable, circulation-preserving, simplicial fluids. ACM Trans. Graph. 26, 1 (2007). 7, 8
- Fulton W., Harris J.: Representation Theory: A First Course. Springer-Verlag, New York, 1991. 3
- Frigo M., Johnson S.: The design and implementation of FFTW3. Proceedings of the IEEE 93, 2 (2005), 216–231. Special issue on “Program Generation, Optimization, and Platform Adaptation”. 6
- Golub G., Loan C.V.: Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA, 1996. 2
- Hockney R.: A fast direct solution of Poisson's equation using Fourier analysis. Journal of the ACM 12, 1 (1965), 95–113. 2, 5, 11
- Höllig K.: Finite Element Methods with B-Splines. Society for Industrial and Applied Mathematics, 2003. 11
- Healy D., Rockmore D., Kostelec P., Moore S.: FFTs on the 2-sphere – improvements and variations. Journal of Fourier Analysis and Applications 9 (2003), 341–385. 6, 7
- Intel: MKL. https://software.intel.com/en-us/intel-mkl, 2013. 7
- Kobbelt L., Campagna S., Vorsatz J., Seidel H.-P.: Interactive multi-resolution modeling on arbitrary meshes. In ACM SIGGRAPH (1998), pp. 105–114. 2
- Kazhdan M., Hoppe H.: Metric-aware processing of spherical imagery. ACM Transactions on Graphics 29, 6 (2010), 149:1–149:10. 2, 6, 9
- Levin A., Zomet A., Peleg S., Weiss Y.: Seamless image stitching in the gradient domain. In European Conference on Computer Vision (2004), pp. 377–389. 6
- McCann J.: Recalling the single-FFT direct Poisson solve. In ACM SIGGRAPH 2008 Posters (2008), SIGGRAPH ‘08, pp. 71:1–71:1. 9
- Maslen D., Rockmore D.: Generalized FFTS - A Survey of Some Recent Results. Tech. rep., Dartmouth College, Hanover, NH, USA, 1996. 9
- Nickolls J., Buck I., Garland M., Skadron K.: Scalable parallel programming with CUDA. Queue 6, 2 (2008), 40–53. 9
10.1145/1365490.1365500 Google Scholar
- Pérez P., Gangnet M., Blake A.: Poisson image editing. ACM Transactions on Graphics (SIGGRAPH ‘03) (2003), 313–318. 6
- Ruge J., Stueben K.: Algebraic multigrid. In Multigrid Methods (1987), SIAM, pp. 73–130. 2
10.1137/1.9781611971057.ch4 Google Scholar
- Saad Y.: Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, 2003. 2, 6
10.1137/1.9780898718003 Google Scholar
- Serre J.: Linear representations of finite groups. Springer-Verlag, New York, 1977. 3
10.1007/978-1-4684-9458-7 Google Scholar
- Shewchuk J.: An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Tech. rep., Carnegie Mellon University, Pittsburgh, PA, USA, 1994. 2
10.1090/conm/180/2003 Google Scholar
- Schumann U., Sweet R.: Fast Fourier transforms for direct solution of Poisson's equation with staggered boundary conditions. Journal of Computational Physics 75, 1 (1988), 123–137. 2
- Stam J.: Stable fluids. In ACM SIGGRAPH Conference Proceedings (1999), pp. 121–128. 7
- Stam J.: A simple fluid solver based on the FFT. Journal of Graphics Tools 6 (2001), 43–52. 7
10.1080/10867651.2001.10487540 Google Scholar
- Stam J.: Flows on surfaces of arbitrary topology. ACM Transactions on Graphics (SIGGRAPH ‘03) 22 (2003), 724–731. 7
- Shi L., Yu Y., Bell N., Feng W.: A fast multigrid algorithm for mesh deformation. ACM Transactions on Graph 25, 3 (2006), 1108–1117. 2
- Vallet B., LÃl'vy B.: Spectral geometry processing with manifold harmonics. Computer Graphics Forum (Proceedings Eurographics) 27, 2 (2008), 251–260. 2
