“Fast multipole representation of diffusion curves and points” by Zheng, Sun and Thamjaroenporn

  • ©Changxi Zheng, Timothy Sun, and Papoj Thamjaroenporn



Session Title:

    Non-Photorealistic Rendering


    Fast multipole representation of diffusion curves and points




    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.


    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

ACM Digital Library Publication: