More Web Proxy on the site http://driver.im/

research-article

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

Authors:

Michael Balzer,

Thomas Schlömer,

Oliver DeussenAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 28, Issue 3

Article No.: 86, Pages 1 - 8

https://doi.org/10.1145/1531326.1531392

Published: 27 July 2009 Publication History

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.

Supplementary Material

JPG File (tps089_09.jpg)

Download
13.26 KB

Zip (86-196.zip)

CONTACT The full paper can be obtained from the ACM Digital Library or as a preliminary draft from our website http://graphics.uni-konstanz.de. Feel free to contact us via e-mail: [email protected] and [email protected].

Download
166.18 MB

MP4 File (tps089_09.mp4)

Download
44.85 MB

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]

Cook, R. L. 1986. Stochastic sampling in computer graphics. In Computer Graphics (Proceedings of SIGGRAPH 86), ACM, vol. 5, 51--72.

Digital Library

[5]

Dipp&#233;, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Computer Graphics (Proceedings of SIGGRAPH 85), ACM, vol. 19, 69--78.

Digital 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.

[7]

Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review 41, 4, 637--676.

Digital 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.

Digital Library

[9]

Halton, J. H. 1970. A retrospective and perspective survey of the Monte Carlo method. SIAM Review 12, 1, 1--63.

Digital 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.

Digital Library

[11]

Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics Tools 11, 2, 27--36.

[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.

Digital 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.

Digital Library

[14]

Lagae, A., and Dutr&#233;, P. 2006. An alternative for Wang tiles: Colored edges versus colored corners. ACM Transactions on Graphics 25, 4, 1442--1459.

Digital Library

[15]

Lagae, A., and Dutr&#233;, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1, 114--129.

[16]

Liu, Y., Wang, W., L&#233;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.

Digital Library

[18]

McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. Graphics Interface '92, 94--105.

Digital 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.

Digital 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.

[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.

Digital Library

[22]

Ostromoukhov, V. 2007. Sampling with polyominoes. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007), ACM, vol. 26, 78.

Digital Library

[23]

Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann.

Digital Library

[24]

Secord, A. 2002. Weighted Voronoi stippling. In Proceedings of the Second International Symposium on Non-photorealistic Animation and Rendering, ACM, 37--43.

Digital 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.

[26]

Szab&#243;, P. G., Mark&#243;t, M. C., Csendes, T., Specht, E., Casado, L. G., and Garc&#237;a, I. 2007. New Approaches to Circle Packing in a Square. Springer.

Digital Library

[27]

Ulichney, R. 1987. Digital halftoning. MIT Press.

Digital Library

[28]

Wei, L.-Y. 2008. Parallel Poisson disk sampling. In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2008), ACM, vol. 27, 1--9.

Digital 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.

Digital Library

[30]

Yellott, Jr., J. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 12, 1, 382--385.

Cited By

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Genest BCourty NCoeurjolly D(2024)Non‐Euclidean Sliced Optimal Transport SamplingComputer Graphics Forum10.1111/cgf.1502043:2Online publication date: 30-Apr-2024
https://doi.org/10.1111/cgf.15020
Chen SHsu K(2024)An efficient approach of meshless node placement in three-dimensional subsurface flow modelingEngineering Analysis with Boundary Elements10.1016/j.enganabound.2024.105997169(105997)Online publication date: Dec-2024
https://doi.org/10.1016/j.enganabound.2024.105997
Show More Cited By

Index Terms

Capacity-constrained point distributions: a variant of Lloyd's method
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
  2. Computer graphics
    1. Image manipulation
    2. Rendering

Recommendations

On centroidal voronoi tessellation—energy smoothness and fast computation

Centroidal Voronoi tessellation (CVT) is a particular type of Voronoi tessellation that has many applications in computational sciences and engineering, including computer graphics. The prevailing method for computing CVT is Lloyd's method, which has ...
Fast capacity constrained Voronoi tessellation
I3D '10: Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games

Capacity constrained Voronoi tessellation (CCVT) [Balzer et al. 2009] addresses a crucial quality issue of Lloyd relaxation but at the expense of slower computation, which could hinder its potential wide adoption. We present a fast capacity constrained ...
Capacity-constrained point distributions: a variant of Lloyd's method
SIGGRAPH '09: ACM SIGGRAPH 2009 papers

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 28, Issue 3

August 2009

750 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1531326

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2009

Published in TOG Volume 28, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

158
Total Citations
View Citations
1,532
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)7

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Genest BCourty NCoeurjolly D(2024)Non‐Euclidean Sliced Optimal Transport SamplingComputer Graphics Forum10.1111/cgf.1502043:2Online publication date: 30-Apr-2024
https://doi.org/10.1111/cgf.15020
Chen SHsu K(2024)An efficient approach of meshless node placement in three-dimensional subsurface flow modelingEngineering Analysis with Boundary Elements10.1016/j.enganabound.2024.105997169(105997)Online publication date: Dec-2024
https://doi.org/10.1016/j.enganabound.2024.105997
Wang YXing YZhang J(2023)Voronoi treemap in Manhattan distance and Chebyshev distanceInformation Visualization10.1177/1473871623116718122:3(246-264)Online publication date: 20-Apr-2023
https://doi.org/10.1177/14738716231167181
Doignies BBonneel NCoeurjolly DDigne JPaulin LIehl JOstromoukhov V(2023)Example-Based Sampling with Diffusion ModelsSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618243(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618243
Bærentzen JFrisvad JMartínez J(2023)Curl Noise JitteringSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618163(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618163
Huang XRitschel TSeidel HMemari PSingh G(2023)Patternshop: Editing Point Patterns by Image ManipulationACM Transactions on Graphics10.1145/359241842:4(1-14)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592418
Zhao YLi MBerger M(2023)Graphical Perception of Saliency-based Model ExplanationsProceedings of the 2023 CHI Conference on Human Factors in Computing Systems10.1145/3544548.3581320(1-15)Online publication date: 19-Apr-2023
https://dl.acm.org/doi/10.1145/3544548.3581320
Krahmer FVeselovska A(2023)Enhanced Digital Halftoning via Weighted Sigma-Delta ModulationSIAM Journal on Imaging Sciences10.1137/22M151786X16:3(1727-1761)Online publication date: 29-Aug-2023
https://doi.org/10.1137/22M151786X
Ahmed ARen JWonka P(2022)Gaussian Blue NoiseACM Transactions on Graphics10.1145/3550454.355551941:6(1-15)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555519
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents