“Fast multipole representation of diffusion curves and points” by Zheng, Sun and Thamjaroenporn
Conference:
Type:
Title:
- Fast multipole representation of diffusion curves and points
Session/Category Title: Non-Photorealistic Rendering
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We propose a new algorithm for random-access evaluation of diffusion curve images (DCIs) using the fast multipole method. Unlike all previous methods, our algorithm achieves real-time performance for rasterization and texture-mapping DCIs of up to millions of curves. After precomputation, computing the color at a single pixel takes nearly constant time. We also incorporate Gaussian radial basis functions into our fast multipole representation using the fast Gauss transform. The fast multipole representation is not only a data structure for fast color evaluation, but also a framework for vector graphics analogues of bitmap editing operations. We exhibit this capability by devising new tools for fast diffusion curve Poisson cloning and composition with masks.
References:
1. Abraham, R., 2010. Strange attractors, http://www.chaoscope.org.Google Scholar
2. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., S alesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. Graph. (SIGGRAPH 2004) 23, 3 (Aug.), 294–302. Google ScholarDigital Library
3. Bezerra, H., Eisemann, E., DeCarlo, D., and Thollot, J. 2010. Diffusion constraints for vector graphics. In Proceedings of the 8th International Symposium on Non-Photorealistic Animation and Rendering, ACM, 35–42. Google ScholarDigital Library
4. Bowers, J. C., Leahey, J., and Wang, R. 2011. A ray tracing approach to diffusion curves. In Computer Graphics Forum, vol. 30, Wiley Online Library, 1345–1352. Google ScholarDigital Library
5. Boyé, S., Barla, P., and Guennebaud, G. 2012. A vectorial solver for free-form vector gradients. ACM Trans. Graph. 31, 6 (Nov.), 173:1–173:9. Google ScholarDigital Library
6. Brochu, T., Keeler, T., and Bridson, R. 2012. Linear-time smoke animation with vortex sheet meshes. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’12, 87–95. Google ScholarDigital Library
7. Farbman, Z., Hoffer, G., Lipman, Y., Cohen-Or, D., and Lischinski, D. 2009. Coordinates for instant image cloning. ACM Trans. Graph. (SIGGRAPH 2009) 28, 3 (July), 67:1–67:9. Google ScholarDigital Library
8. Finch, M., Snyder, J., and Hoppe, H. 2011. Freeform vector graphics with controlled thin-plate splines. ACM Trans. Graph. (SIGGRAPH Asia 2011) 30, 6 (Dec.), 166:1–166:10. Google ScholarDigital Library
9. Greengard, L., and Rokhlin, V. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 2 (Dec.), 325–348. Google ScholarDigital Library
10. Greengard, L., and Strain, J. 1991. The fast gauss transform. SIAM J. Sci. Stat. Comput. 12, 1 (Jan.), 79–94. Google ScholarDigital Library
11. Gumerov, N. A., and Duraiswami, R. 2006. Fast multipole method for the biharmonic equation in three dimensions. Journal of Computational Physics 215, 1, 363–383. Google ScholarDigital Library
12. Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. SIGGRAPH Comput. Graph. 25, 4 (July), 197–206. Google ScholarDigital Library
13. Ilbery, P., Kendall, L., Concolato, C., and McCosker, M. 2013. Biharmonic diffusion curve images from boundary elements. ACM Trans. Graph. (SIGGRAPH Asia 2013) 32, 6 (Nov.), 219:1–219:12. Google ScholarDigital Library
14. Jeschke, S., Cline, D., and Wonka, P. 2009. A gpu laplacian solver for diffusion curves and poisson image editing. ACM Trans. Graph. (SIGGRAPH Asia 2009) 28, 5 (Dec.), 116:1–116:8. Google ScholarDigital Library
15. Kemp, M. 1998. Attractive attractors. Nature 394, 627 (Aug.).Google ScholarCross Ref
16. Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. ACM Trans. Graph. 24, 3 (July), 777–786. Google ScholarDigital Library
17. Li, Y., Sharan, L., and Adelson, E. H. 2005. Compressing and companding high dynamic range images with subband architectures. ACM Trans. Graph. (SIGGRAPH 2005) 24, 3 (July), 836–844. Google ScholarDigital Library
18. Liu, Y., and Nishimura, N. 2006. The fast multipole boundary element method for potential problems: a tutorial. Engineering Analysis with Boundary Elements 30, 5, 371–381.Google ScholarCross Ref
19. Munkberg, J., Clarberg, P., Hasselgren, J., and Akenine-Möller, T. 2006. High dynamic range texture compression for graphics hardware. ACM Trans. Graph. 25, 3 (July), 698–706. Google ScholarDigital Library
20. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: A vector representation for smooth-shaded images. ACM Trans. on Graphics (SIGGRAPH 2008) 27, 3 (Aug.), 92:1–92:8. Google ScholarDigital Library
21. Pang, W.-M., Qin, J., Cohen, M., Heng, P.-A., and Choi, K.-S. 2012. Fast rendering of diffusion curves with triangles. IEEE Computer Graphics and Applications 32, 4, 68–78. Google ScholarDigital Library
22. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. (SIGGRAPH 2003) 22, 3 (July), 313–318. Google ScholarDigital Library
23. Porter, T., and Duff, T. 1984. Compositing digital images. In ACM Siggraph Computer Graphics, vol. 18, ACM, 253–259. Google ScholarDigital Library
24. Sun, X., Xie, G., Dong, Y., Lin, S., Xu, W., Wang, W., Tong, X., and Guo, B. 2012. Diffusion curve textures for resolution independent texture mapping. ACM Trans. Graph. (SIGGRAPH 2012) 31, 4 (July). Google ScholarDigital Library
25. Takayama, K., Sorkine, O., Nealen, A., and Igarashi, T. 2010. Volumetric modeling with diffusion surfaces. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 29, 6, 180:1–180:8. Google ScholarDigital Library
26. Zheng, C., and James, D. L. 2010. Rigid-body fracture sound with precomputed soundbanks. ACM Transactions on Graphics 29, 4 (July), 69:1–69:13. Google ScholarDigital Library
27. Zheng, C., and James, D. L. 2011. Toward high-quality modal contact sound. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2011) 30, 4 (Aug.). Google ScholarDigital Library
