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

  • ©Michael Balzer, Thomas Schlömer, and Oliver Deussen




    Capacity-constrained point distributions: a variant of Lloyd's method



    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

ACM Digital Library Publication: