Fast Multipole Representation of Diffusion Curves and Points

Timothy Sun*, Papoj Thamjaroenporn*, Changxi Zheng (*joint first authors)
ACM SIGGRAPH 2014 / Transactions on Graphics


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.




bibtex Timothy Sun, Papoj Thamjaroenporn, Changxi Zheng, Fast Multipole Representation of Diffusion Curves and Points, ACM Transactions on Graphics 33(4) (Proc. SIGGRAPH 2014), Aug, 2014.


We thank the anonymous reviewers for their feedback. We also thank Orzan et al. for making their DCIs publicly accessible, Dingzeyu Li and Henrique Maia for help with revising an earlier draft, and Yun Fei and Angela Wei for assistance in video and figure editing. This research was supported in part by Columbia Junior Faculty Startup Fund as well as donations from Intel. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of funding agencies or others.


Columbia University

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.