“Out-of-core multigrid solver for streaming meshes”
Conference:
Type(s):
Title:
- Out-of-core multigrid solver for streaming meshes
Session/Category Title: Reconstruction & modeling
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present an out-of-core multigrid for solving the Poisson equation defined over gigantic meshes. This enables gradient-domain operations on out-of-core meshes with irregular connectivity. Taking a streaming mesh and boundary constraints as input, our solver builds a multigrid hierarchy and refines the multigrid solution progressively by performing all operations as streaming computations. A set of rules are carefully designed to make neighboring multigrid nodes perform tasks cooperatively and efficiently. With a sublinear memory growth with respect to the number of mesh vertices, our approach handles meshes with 14M vertices using merely 84MB of memory, while an equivalent in-core multigrid implementation fails to fit into 2GB memory space.
References:
1. Bolitho, M., Kazhdan, M., Burns, R., and Hoppe, H. 2007. Multilevel streaming for out-of-core surface reconstruction. In Proceedings of ESGP’07, 69–78. Google ScholarDigital Library
2. Brandt, A. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 333–390.Google ScholarCross Ref
3. Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A Multigrid Tutorial. Society for Industrial and Applied Mathematics. Google ScholarDigital Library
4. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH’97, 209–216. Google ScholarDigital Library
5. Georgii, J., and Westermann, R. 2006. A multigrid framework for real-time simulation of deformable volumes. Computers&Graphics 30, 3, 408–415. Google ScholarDigital Library
6. Isenburg, M., Lindstrom, P., and Livermore, L. 2005. Streaming meshes. In Proceedings of Visualization’05, 231–238.Google Scholar
7. Isenburg, M., Liu, Y., Shewchuk, J., and Snoeyink, J. 2006. Streaming computation of delaunay triangulations. ACM Trans. Graph. 25, 3, 1049–1056. Google ScholarDigital Library
8. Kazhdan, M., and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27, 3, 21. Google ScholarDigital Library
9. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proceedings of SGP’06, 61–70. Google ScholarDigital Library
10. McCann, J., and Pollard, N. S. 2008. Real-time gradient-domain painting. ACM Trans. Graph. 27, 3, 93. Google ScholarDigital Library
11. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318. Google ScholarDigital Library
12. Sander, P. V., Nehab, D., and Barczak, J. 2007. Fast triangle reordering for vertex locality and reduced overdraw. ACM Trans. Graph. 26, 3, 89. Google ScholarDigital Library
13. Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. ACM Trans. Graph. 25, 3, 1108–1117. Google ScholarDigital Library
14. Silva, C. T., Chiang, Y.-J., El-Sana, J., and Lindstrom, P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. In Course Notes for IEEE Visualization 2002.Google Scholar
15. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proceedings of SGP’04, 175–184. Google ScholarDigital Library
16. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. ACM Trans. Graph. 23, 3, 644–651. Google ScholarDigital Library
17. Zhou, K., Huang, J., Snyder, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2005. Large mesh deformation using the volumetric graph laplacian. ACM Trans. Graph. 24, 3, 496–503. Google ScholarDigital Library
