“Parallel Poisson disk sampling with spectrum analysis on surfaces”
Conference:
Type(s):
Title:
- Parallel Poisson disk sampling with spectrum analysis on surfaces
Session/Category Title: Sampling & filtering
Presenter(s)/Author(s):
Moderator(s):
Abstract:
The ability to place surface samples with Poisson disk distribution can benefit a variety of graphics applications. Such a distribution satisfies the blue noise property, i.e. lack of low frequency noise and structural bias in the Fourier power spectrum. While many techniques are available for sampling the plane, challenges remain for sampling arbitrary surfaces. In this paper, we present new methods for Poisson disk sampling with spectrum analysis on arbitrary manifold surfaces. Our first contribution is a parallel dart throwing algorithm that generates high-quality surface samples at interactive rates. It is flexible and can be extended to adaptive sampling given a user-specified radius field. Our second contribution is a new method for analyzing the spectral quality of surface samples. Using the spectral mesh basis derived from the discrete mesh Laplacian operator, we extend standard concepts in power spectrum analysis such as radial means and anisotropy to arbitrary manifold surfaces. This provides a way to directly evaluate the spectral distribution quality of surface samples without requiring mesh parameterization. Finally, we implement our Poisson disk sampling algorithm on the GPU, and demonstrate practical applications involving interactive sampling and texturing on arbitrary surfaces.
References:
1. Alcantara, D. A., Sharf, A., Abbasinejad, F., Sengupta, S., Mitzenmacher, M., Owens, J. D., and Amenta, N. 2009. Real-time parallel hashing on the GPU. ACM Trans. Graph. 28, 5, 154:1–9. Google ScholarDigital Library
2. Alexa, M. 2002. Recent advances in mesh morphing. Comput. Graph. Forum 21, 2, 173–196.Google ScholarCross Ref
3. Alliez, P., Meyer, M., and Desbrun, M. 2002. Interactive geometry remeshing. ACM Trans. Graph. 21, 3, 347–354. Google ScholarDigital Library
4. Balzer, M., Schlömer, T., and Deussen, O. 2009. Capacity-constrained point distributions: a variant of Lloyd’s method. ACM Trans. Graph. 28, 3, 86:1–8. Google ScholarDigital Library
5. Cheslack-Postava, E., Wang, R., Akerlund, O., and Pellacini, F. 2008. Fast, realistic lighting and material design using nonlinear cut approximation. ACM Trans. Graph. 27, 5, 128:1–10. Google ScholarDigital Library
6. Cline, D., Jeschke, S., White, K., Razdan, A., and Wonka, P. 2009. Dart throwing on surfaces. Computer Graphics Forum 28, 4, 1217–1226. Google ScholarDigital Library
7. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics 5, 1, 51–72. Google ScholarDigital Library
8. Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, Springer-Verlag, 35–57.Google Scholar
9. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. ACM Trans. Graph. 25, 3, 1057–1066. Google ScholarDigital Library
10. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graph. 25, 3, 503–508. Google ScholarDigital Library
11. Dyer, R., Zhang, H., Moeller, T., and Clements, A. 2007. An investigation of the spectral robustness of mesh Laplacians. Tech. Rep. TR-2007-17, School of Computing Science, Simon Fraser University.Google Scholar
12. Fu, Y., and Zhou, B. 2008. Direct sampling on surfaces for high quality remeshing. In SPM ’08, 115–124. Google ScholarDigital Library
13. Glanville, S. 2004. Texture bombing. GPU Gems.Google Scholar
14. Grossman, J. P., and Dally, W. J. 1998. Point sample rendering. In Rendering Techniques, 181–192.Google Scholar
15. Jensen, H. W., and Buhler, J. 2002. A rapid hierarchical rendering technique for translucent materials. ACM Trans. Graph. 21, 3, 576–581. Google ScholarDigital Library
16. Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics Tools 11, 2, 27–36.Google ScholarCross Ref
17. Karni, Z., and Gotsman, C. 2000. Spectral compression of mesh geometry. In SIGGRAPH ’00, 279–286. Google ScholarDigital Library
18. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3, 509–518. Google ScholarDigital Library
19. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4, 1442–1461. Google ScholarDigital Library
20. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1, 114–129.Google ScholarCross Ref
21. Levy, B. 2006. Laplace-Beltrami eigenfunctions towards an algorithm that “understands” geometry. In Proc. of SMI 2006, 13. Google ScholarDigital Library
22. Li, H., Lo, K.-Y., Leung, M.-K., and Fu, C.-W. 2008. Dual Poisson-disk tiling: An efficient method for distributing features on arbitrary surfaces. IEEE TVCG 14, 5, 982–998. Google ScholarDigital Library
23. Li, H., Wei, L.-Y., Sander, P., and Fu, C.-W. 2010. Anisotropic blue noise sampling. ACM Trans. Graph. 29, 5, to appear. Google ScholarDigital Library
24. Lloyd, S. 1982. Least squares quantization in pcm. IEEE Transactions on Information Theory 28, 2, 129–137.Google ScholarDigital Library
25. McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. In Graphics Interface ’92, 94–105. Google ScholarDigital Library
26. Meier, B. J. 1996. Painterly rendering for animation. In SIGGRAPH ’96, 477–484. Google ScholarDigital Library
27. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH ’87, 65–72. Google ScholarDigital Library
28. Nehab, D., and Shilane, P. 2004. Stratified point sampling of 3D models. In Proc. of PBG, 49–56. Google ScholarDigital Library
29. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23, 3, 488–495. Google ScholarDigital Library
30. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Trans. Graph. 26, 3, 78:1–6. Google ScholarDigital Library
31. Pastor, O. M., Freudenberg, B., and Strothotte, T. 2003. Real-time animated stippling. IEEE CG&A 23, 4, 62–68. Google ScholarDigital Library
32. Praun, E., Hoppe, H., and Finkelstein, A. 1999. Robust mesh watermarking. In SIGGRAPH ’99, 49–56. Google ScholarDigital Library
33. Qu, L., and Meyer, G. W. 2006. Perceptually driven interactive geometry remeshing. In I3D ’06, 199–206. Google ScholarDigital Library
34. Ritschel, T., Engelhardt, T., Grosch, T., Seidel, H.-P., Kautz, J., and Dachsbacher, C. 2009. Micro-rendering for scalable, parallel final gathering. ACM Trans. Graph. 28, 5, 132:1–8. Google ScholarDigital Library
35. Sethian, J. A. 1995. A fast marching level set method for monotonically advancing fronts. In Proc. Nat. Acad. Sci, 1591–1595.Google Scholar
36. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553–560. Google ScholarDigital Library
37. Turk, G. 1992. Re-tiling polygonal surfaces. In SIGGRAPH ’92, 55–64. Google ScholarDigital Library
38. Turk, G. 2001. Texture synthesis on surfaces. In SIGGRAPH ’01, 347–354. Google ScholarDigital Library
39. Ulichney, R. 1987. Digital halftoning. MIT Press, Cambridge, MA. Google ScholarDigital Library
40. Vallet, B., and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. Comput. Graph. Forum 27, 2, 251–260.Google ScholarCross Ref
41. Vanderhaeghe, D., Barla, P., Thollot, J., and Sillion, F. X. 2007. Dynamic point distribution for stroke-based rendering. In EGSR’07, 139–146. Google ScholarDigital Library
42. Wei, L.-Y., and Levoy, M. 2001. Texture synthesis over arbitrary manifold surfaces. In SIGGRAPH ’01, 355–360. Google ScholarDigital Library
43. Wei, L.-Y. 2008. Parallel Poisson disk sampling. ACM Trans. Graph. 27, 3, 20:1–9. Google ScholarDigital Library
44. White, K., Cline, D., and Egbert, P. 2007. Poisson disk point sets by hierarchical dart throwing. In Symposium on Interactive Ray Tracing, 129–132. Google ScholarDigital Library
45. Yu, Q., Neyret, F., Bruneton, E., and Holzschuch, N. 2009. Scalable real-time animation of rivers. Comput. Graph. Forum 28, 2, 239–248.Google ScholarCross Ref
