“Analysis and synthesis of point distributions based on pair correlation” by Öztireli and Gross
Conference:
Type(s):
Title:
- Analysis and synthesis of point distributions based on pair correlation
Session/Category Title: Points and Vectors
Presenter(s)/Author(s):
Abstract:
Analyzing and synthesizing point distributions are of central importance for a wide range of problems in computer graphics. Existing synthesis algorithms can only generate white or blue-noise distributions with characteristics dictated by the underlying processes used, and analysis tools have not been focused on exploring relations among distributions. We propose a unified analysis and general synthesis algorithms for point distributions. We employ the pair correlation function as the basis of our methods and design synthesis algorithms that can generate distributions with given target characteristics, possibly extracted from an example point set, and introduce a unified characterization of distributions by mapping them to a space implied by pair correlations. The algorithms accept example and output point sets of different sizes and dimensions, are applicable to multi-class distributions and non-Euclidean domains, simple to implement and run in O(n) time. We illustrate applications of our method to real world distributions.
References:
1. Alliez, P., Meyer, M., and Desbrun, M. 2002. Interactive geometry remeshing. ACM Trans. Graph. 21, 3, 347–354.
2. 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.
3. Boutin, M., and Kemper, G. 2004. On reconstructing n-point configurations from the distribution of distances or areas. Adv. Appl. Math. 32, 709–735.
4. Boutin, M., and Kemper, G. 2007. Which point configurations are determined by the distribution of their pairwise distances? International Journal of Computational Geometry & Applications 17, 31–43.
5. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72.
6. Deussen, O., Hanrahan, P., Lintermann, B., Měch, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modeling and rendering of plant ecosystems. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH 98, 275–286.
7. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast poisson-disk sample generation. ACM Trans. Graph. 25 (July), 503–508.
8. Ebeida, M. S., Patney, A., Mitchell, S. A., Davidson, A., Knupp, P. M., and Owens, J. D. 2011. Efficient maximal poisson-disk sampling. ACM Trans. Graph. 30, 4.
9. Fattal, R. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 4 (July), 48:1–48:12.
10. Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional poisson-disk sampling. ACM Trans. Graph. 29 (December), 8:1–8:19.
11. Illian, J., Penttinen, A., Stoyan, H., and Stoyan, D., Eds. 2008. Statistical Analysis and Modelling of Spatial Point Patterns. John Wiley and Sons, Ltd.
12. Jodrey, W. S., and Tlory, E. M. 1985. Computer simulation of close random packing of equal spheres. Phys. Rev. A 32 (Oct), 2347–2351.
13. Jones, T. R. 2006. Efficient generation of poisson-disk sampling patterns. journal of graphics, gpu, and game tools 11, 2, 27–36.
14. Kerscher, M. 2001. Constructing, characterizing, and simulating gaussian and higher-order point distributions. Phys. Rev. E 64 (Oct), 056109.
15. Kim, T., Thürey, N., James, D., and Gross, M. 2008. Wavelet turbulence for fluid simulation. ACM Trans. Graph. 27, 3 (Aug.), 50:1–50:6.
16. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Trans. Graph. 25 (July), 509–518.
17. Lagae, A., and Dutré, P. 2006. Poisson sphere distributions. In Vision, Modeling, and Visualization 2006, Akademische Verlagsgesellschaft Aka GmbH, Berlin, L. Kobbelt, T. Kuhlen, T. Aach, and R. Westermann, Eds., 373–379.
18. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1 (March), 114–129.
19. Lewis, J. P. 1989. Algorithms for solid noise synthesis. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH 89, 263–270.
20. Li, H., Wei, L.-Y., Sander, P. V., and Fu, C.-W. 2010. Anisotropic blue noise sampling. ACM Trans. Graph. 29, 6 (Dec.), 167:1–167:12.
21. Lloyd, S. 1982. Least squares quantization in pcm. Information Theory, IEEE Transactions on 28, 2 (mar), 129–137.
22. Ma, C., Wei, L.-Y., and Tong, X. 2011. Discrete element textures. ACM Trans. Graph. 30, 4 (Aug.), 62:1–62:10.
23. McCool, M., and Fiume, E. 1992. Hierarchical poisson disk sampling distributions. In Proceedings of the conference on Graphics interface ’92, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 94–105.
24. Narain, R., Golas, A., Curtis, S., and Lin, M. C. 2009. Aggregate dynamics for dense crowd simulation. ACM Trans. Graph. 28, 5 (Dec.), 122:1–122:8.
25. Ohser, J., and Mücklich, F., Eds. 2000. Statistical Analysis of Microstructures in Materials Science. John Wiley and Sons, Ltd.
26. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23 (Aug.), 488–495.
27. Pfaff, T., Thuerey, N., Selle, A., and Gross, M. 2009. Synthetic turbulence using artificial boundary layers. ACM Trans. Graph. 28, 5 (Dec.), 121:1–121:10.
28. Pommerening, A. 2002. Approaches to quantifying forest structures. Forestry 75, 305–324.
29. Schlömer, T., Heck, D., and Deussen, O. 2011. Farthest-point optimized point sets with maximized minimum distance. In Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, ACM, New York, NY, USA, HPG ’11, 135–142.
30. Schmaltz, C., Gwosdek, P., Bruhn, A., and Weickert, J. 2010. Electrostatic halftoning. Computer Graphics Forum 29, 8, 2313–2327.
31. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. ACM Trans. Graph. 24, 3 (July), 910–914.
32. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. ACM Trans. Graph. 24, 3 (July), 910–914.
33. Torquato, S., Ed. 2002. Random Heterogenous Materials. Microstructure and Macroscopic Properties. Springer-Verlag, New York.
34. Ulichney, R. 1987. Digital halftoning. MIT Press, Cambridge, MA, USA.
35. Wei, L.-Y., and Wang, R. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. 30, 4 (July), 50:1–50:10.
36. Wei, L.-Y. 2008. Parallel poisson disk sampling. ACM Trans. Graph. 27 (August), 20:1–20:9.
37. Wei, L.-Y. 2010. Multi-class blue noise sampling. ACM Trans. Graph. 29 (July), 79:1–79:8.
38. White, K., Cline, D., and Egbert, P. 2007. Poisson disk point sets by hierarchical dart throwing. In Interactive Ray Tracing, 2007. RT ’07. IEEE Symposium on, 129–132.
