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

research-article

Analysis and synthesis of point distributions based on pair correlation

Authors:

A. Cengiz Öztireli,

Markus GrossAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 31, Issue 6

Article No.: 170, Pages 1 - 10

https://doi.org/10.1145/2366145.2366189

Published: 01 November 2012 Publication History

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.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[7]

Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast poisson-disk sample generation. ACM Trans. Graph. 25 (July), 503--508.

Digital Library

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

Digital Library

[9]

Fattal, R. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 4 (July), 48:1--48:12.

Digital Library

[10]

Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional poisson-disk sampling. ACM Trans. Graph. 29 (December), 8:1--8:19.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[21]

Lloyd, S. 1982. Least squares quantization in pcm. Information Theory, IEEE Transactions on 28, 2 (mar), 129--137.

Digital Library

[22]

Ma, C., Wei, L.-Y., and Tong, X. 2011. Discrete element textures. ACM Trans. Graph. 30, 4 (Aug.), 62:1--62:10.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

[36]

Wei, L.-Y. 2008. Parallel poisson disk sampling. ACM Trans. Graph. 27 (August), 20:1--20:9.

Digital Library

[37]

Wei, L.-Y. 2010. Multi-class blue noise sampling. ACM Trans. Graph. 29 (July), 79:1--79:8.

Digital Library

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

Digital Library

Cited By

Yang BMould D(2025)Anisotropic Point Synthesis by ExampleAdvances in Visual Computing10.1007/978-3-031-77392-1_7(87-98)Online publication date: 22-Jan-2025
https://doi.org/10.1007/978-3-031-77392-1_7
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
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
Show More Cited By

Index Terms

Analysis and synthesis of point distributions based on pair correlation
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

k-d Darts: Sampling by k-dimensional flat searches

We formalize sampling a function using k-d darts. A k-d Dart is a set of independent, mutually orthogonal, k-dimensional hyperplanes called k-d flats. A dart has d choose k flats, aligned with the coordinate axes for efficiency. We show k-d darts are ...
Simple General Approximations for a Random Variable and its Inverse Distribution Function Based on Linear Transformations of a Nonskewed Variate

Linear transformations of a nonskewed random variable are employed to derive simple general approximations for a random variable having known cumulants. Introducing the unit normal variate, these become linear normal approximations.Some nonskewed ...
Sampling algorithms for generating joint uniform distributions using the vine-copula method

An n-dimensional joint uniform distribution is defined as a distribution whose one-dimensional marginals are uniform on some interval I. This interval is taken to be [0,1] or, when more convenient [-12,12]. The specification of joint uniform ...

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 31, Issue 6

November 2012

794 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2366145

Issue’s Table of Contents

Copyright © 2012 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: 01 November 2012

Published in TOG Volume 31, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Swiss National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
794
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)4

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang BMould D(2025)Anisotropic Point Synthesis by ExampleAdvances in Visual Computing10.1007/978-3-031-77392-1_7(87-98)Online publication date: 22-Jan-2025
https://doi.org/10.1007/978-3-031-77392-1_7
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
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
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
Ahmed AWonka P(2021)Optimizing dyadic netsACM Transactions on Graphics10.1145/3450626.345988040:4(1-17)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459880
van Onzenoodt CSingh GRopinski TRitschel T(2021)Blue Noise PlotsComputer Graphics Forum10.1111/cgf.14264440:2(425-433)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142644
Muniraju GKailkhura BThiagarajan JBremer PTepedelenlioglu CSpanias A(2021)Coverage-Based Designs Improve Sample Mining and Hyperparameter OptimizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2020.298293632:3(1241-1253)Online publication date: Mar-2021
https://doi.org/10.1109/TNNLS.2020.2982936
Ahmed AWonka P(2020)Screen-space blue-noise diffusion of monte carlo sampling error via hierarchical ordering of pixelsACM Transactions on Graphics10.1145/3414685.341788139:6(1-15)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417881
Reddy PGuerrero PFisher MLi WMitra N(2020)Discovering pattern structure using differentiable compositingACM Transactions on Graphics10.1145/3414685.341783039:6(1-15)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417830
Guehl PAllègre RDischler JBenes BGalin E(2020)Semi‐Procedural Textures Using Point Process Texture Basis FunctionsComputer Graphics Forum10.1111/cgf.1406139:4(159-171)Online publication date: 20-Jul-2020
https://doi.org/10.1111/cgf.14061
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents