“Capacity-constrained point distributions: a variant of Lloyd’s method” by Balzer, Schlömer and Deussen

We present a new general-purpose method for optimizing existing point sets. The resulting distributions possess high-quality blue noise characteristics and adapt precisely to given density functions. Our method is similar to the commonly used Lloyd’s method while avoiding its drawbacks. We achieve our results by utilizing the concept of capacity, which for each point is determined by the area of its Voronoi region weighted with an underlying density function. We demand that each point has the same capacity. In combination with a dedicated optimization algorithm, this capacity constraint enforces that each point obtains equal importance in the distribution. Our method can be used as a drop-in replacement for Lloyd’s method, and combines enhancement of blue noise characteristics and density function adaptation in one operation.

1. Aurenhammer, F., Hoffmann, F., and Aronov, B. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1, 61–76.Google ScholarCross Ref
2. Balzer, M., and Heck, D. 2008. Capacity-constrained Voronoi diagrams in finite spaces. In Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering, vol. 2, 44–56.Google Scholar
3. Chen, L. 2004. Mesh smoothing schemes based on optimal Delaunay triangulations. In Proceedings of the 13th International Meshing Roundtable, 109–120.Google Scholar
4. Cook, R. L. 1986. Stochastic sampling in computer graphics. In Computer Graphics (Proceedings of SIGGRAPH 86), ACM, vol. 5, 51–72. Google ScholarDigital Library
5. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Computer Graphics (Proceedings of SIGGRAPH 85), ACM, vol. 19, 69–78. Google ScholarDigital Library
6. Du, Q., and Emelianenko, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numerical Linear Algebra with Applications 13, 2–3, 173–192.Google ScholarCross Ref
7. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review 41, 4, 637–676. Google ScholarDigital Library
8. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2006), ACM, vol. 25, 503–508. Google ScholarDigital Library
9. Halton, J. H. 1970. A retrospective and perspective survey of the Monte Carlo method. SIAM Review 12, 1, 1–63.Google ScholarDigital Library
10. Hiller, S., Deussen, O., and Keller, A. 2001. Tiled blue noise samples. In Proceedings of the Vision Modeling and Visualization Conference 2001, IOS Press, 265–272. Google ScholarDigital Library
11. Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics Tools 11, 2, 27–36.Google ScholarCross Ref
12. Kollig, T., and Keller, A. 2003. Efficient illumination by high dynamic range images. In Proceedings of the 14th Eurographics Workshop on Rendering, Eurographics Association, vol. 44, 45–50. Google ScholarDigital Library
13. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2006), ACM, vol. 25, 509–518. Google ScholarDigital Library
14. Lagae, A., and Dutré, P. 2006. An alternative for Wang tiles: Colored edges versus colored corners. ACM Transactions on Graphics 25, 4, 1442–1459. Google ScholarDigital Library
15. 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
16. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., and Yang, C. 2008. On centroidal Voronoi tessellation — energy smoothness and fast computation. Tech. rep., Hong-Kong University and INRIA-ALICE Project Team.Google Scholar
17. Lloyd, S. P. 1982. Least square quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129–137.Google ScholarDigital Library
18. McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. Graphics Interface ’92, 94–105. Google ScholarDigital Library
19. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Computer Graphics (Proceedings of SIGGRAPH 87), ACM, vol. 21, 65–72. Google ScholarDigital Library
20. Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed. John Wiley and Sons Ltd. Google ScholarCross Ref
21. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2004), ACM, vol. 23, 488–495. Google ScholarDigital Library
22. Ostromoukhov, V. 2007. Sampling with polyominoes. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007), ACM, vol. 26, 78. Google ScholarDigital Library
23. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann. Google ScholarDigital Library
24. Secord, A. 2002. Weighted Voronoi stippling. In Proceedings of the Second International Symposium on Non-photorealistic Animation and Rendering, ACM, 37–43. Google ScholarDigital Library
25. Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: A local parameterization approach. In Proceedings of the 12th International Meshing Roundtable, 215–224.Google Scholar
26. Szabó, P. G., Markót, M. C., Csendes, T., Specht, E., Casado, L. G., and García, I. 2007. New Approaches to Circle Packing in a Square. Springer. Google ScholarDigital Library
27. Ulichney, R. 1987. Digital halftoning. MIT Press. Google ScholarDigital Library
28. Wei, L.-Y. 2008. Parallel Poisson disk sampling. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2008), ACM, vol. 27, 1–9. Google ScholarDigital Library
29. White, K., Cline, D., and Egbert, P. 2007. Poisson disk point sets by hierarchical dart throwing. In Proceedings of the IEEE Symposium on Interactive Ray Tracing, 129–132. Google ScholarDigital Library
30. Yellott, Jr., J. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 12, 1, 382–385.Google ScholarCross Ref