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

ABSTRACT

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.

REFERENCES

• 1: Aurenhammer, F., Hoffmann, F., and Aronov, B. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1, 61--76.
• 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.
• 3: Chen, L. 2004. Mesh smoothing schemes based on optimal Delaunay triangulations. In Proceedings of the 13th International Meshing Roundtable, 109--120.
• 4: Robert L. Cook, Stochastic sampling in computer graphics, ACM Transactions on Graphics (TOG), v.5 n.1, p.51-72, Jan. 1986 [doi>10.1145/7529.8927]
• 5: Mark A. Z. Dippé , Erling Henry Wold, Antialiasing through stochastic sampling, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.69-78, July 1985
• 6: Du, Q., and Emelianenko, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numerical Linear Algebra with Applications 13, 2--3, 173--192.
• 7: Qiang Du , Vance Faber , Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, v.41 n.4, p.637-676, Dec. 1999 [doi>10.1137/S0036144599352836]
• 8: Daniel Dunbar , Greg Humphreys, A spatial data structure for fast Poisson-disk sample generation, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 9: Halton, J. H. 1970. A retrospective and perspective survey of the Monte Carlo method. SIAM Review 12, 1, 1--63.
• 10: Stefan Hiller , Oliver Deussen , Alexander Keller, Tiled Blue Noise Samples, Proceedings of the Vision Modeling and Visualization Conference 2001, p.265-272, November 21-23, 2001
• 11: Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics Tools 11, 2, 27--36.
• 12: Thomas Kollig , Alexander Keller, Efficient illumination by high dynamic range images, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
• 13: Johannes Kopf , Daniel Cohen-Or , Oliver Deussen , Dani Lischinski, Recursive Wang tiles for real-time blue noise, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 14: Ares Lagae , Philip Dutré, An alternative for Wang tiles: colored edges versus colored corners, ACM Transactions on Graphics (TOG), v.25 n.4, p.1442-1459, October 2006 [doi>10.1145/1183287.1183296]
• 15: Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1, 114--129.
• 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.
• 17: Lloyd, S. P. 1982. Least square quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129--137.
• 18: Michael McCool , Eugene Fiume, Hierarchical Poisson disk sampling distributions, Proceedings of the conference on Graphics interface '92, p.94-105, September 1992, Vancouver, British Columbia, Canada
• 19: Don P. Mitchell, Generating antialiased images at low sampling densities, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.65-72, August 1987
• 20: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 21: Victor Ostromoukhov , Charles Donohue , Pierre-Marc Jodoin, Fast hierarchical importance sampling with blue noise properties, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 22: Victor Ostromoukhov, Sampling with polyominoes, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 23: Matt Pharr , Greg Humphreys, Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 24: Adrian Secord, Weighted Voronoi stippling, Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, June 03-05, 2002, Annecy, France [doi>10.1145/508530.508537]
• 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.
• 26: P. G. Szabó , M. Cs. Markót , T. Csendes , E. Specht , L. G. Casado , I. Garcãa, New Approaches to Circle Packing in a Square: With Program Codes (Springer Optimization and Its Applications), Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 27: Robert Ulichney, Digital halftoning, MIT Press, Cambridge, MA, 1987
• 28: Li-Yi Wei, Parallel Poisson disk sampling, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 29: Kenric B. White , David Cline , Parris K. Egbert, Poisson Disk Point Sets by Hierarchical Dart Throwing, Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, p.129-132, September 10-12, 2007 [doi>10.1109/RT.2007.4342600]
• 30: Yellott, Jr., J. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 12, 1, 382--385.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.1 Digitization and Image Capture
          Subjects: Sampling

Keywords:
Lloyd's method, Poisson disk point sets, Voronoi tessellations, blue noise, capacity constraint, importance sampling