Abstract
We review our recent progress on efficient algorithms for generating well-spaced samples of high dimensional data, and for exploring and characterizing these data, the underlying domain, and functions over the domain. To our knowledge, these techniques have not yet been applied to computational topology, but the possible connections are worth considering. In particular, computational topology problems often have difficulty in scaling efficiently, and these sampling techniques have the potential to drastically reduce the size of the data over which these computational topology algorithms must operate. We summarize the definition of these sample distributions; algorithms for generating them in low, moderate, and high dimensions; and applications in mesh generation, rendering, motion planning and simulation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdelkader, A., Mitchell, S.A., Ebeida, M.S.: Steiner point reduction in planar Delaunay meshes. In: ACM Symposium on Computational Geometry. Young Researchers Forum (2014) http://www.computational-geometry.org/YRF/cgyrf2014.pdf and http://www.cs.sandia.gov/~samitch/bibliography_2007.html#steiner-reduction
Bolander Jr., J.E., Saito, S.: Fracture analyses using spring networks with random geometry. Eng. Fract. Mech. 61(5–6), 569–591 (1998)
Bowers, J., Wang, R., Wei, L.-Y., Maletz, D.: Parallel Poisson disk sampling with spectrum analysis on surfaces. In: SIGGRAPH Asia ’10, pp. 166:1–10 (2010)
Chew, L.P.: Guaranteed-quality mesh generation for curved surfaces. In: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 274–280 (1993)
Dunbar, D., Humphreys, G.: A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graph. 25(3), 503–508 (July 2006)
Ebeida, M.S., Awad, M.A., Ge, X., Mahmoud, A.H., Mitchell, S.A., Knupp, P.M., Wei, L.-Y.: Improving spatial coverage while preserving the blue noise of point sets. Computer-Aided Design 46, 25–36 (2014)
Ebeida, M.S., Knupp, P.M., Leung, V.J., Bishop, J.E., Martinez, M.J.: Mesh generation for modeling and simulation of carbon sequestration process. In: DOE Scientific Discovery Through Advanced Computing (SciDAC) (2011)
Ebeida, M.S., Mitchell, S.A.: Uniform random Voronoi meshes. In: 20th International Meshing Roundtable, pp. 273–290. Springer, Berlin (October 2011)
Ebeida, M.S., Mahmoud, A.H., Awad, M.A., Mohammed, M.A., Mitchell, S.A., Rand, A., Owens, J.D.: Sifted disks. Comput. Graph. Forum 32(2 Pt 4), 509–518 (2013)
Ebeida, M.S., Mitchell, S.A., Davidson, A.A., Patney, A., Knupp, P.M., Owens, J.D.: Efficient and good Delaunay meshes from random points. Comput. Aided Design 43(11), 1506–1515 (2011)
Ebeida, M.S., Mitchell, S.A., Patney, A., Davidson, A.A., Owens, J.D.: A simple algorithm for maximal Poisson-disk sampling in high dimensions. Comput. Graph. Forum 31(2), 785–794 (May 2012)
Ebeida, M.S., Patney, A., Mitchell, S.A., Davidson, A., Knupp, P.M., Owens, J.D.: Efficient maximal Poisson-disk sampling. ACM Trans. Graph. 30(4), 49:1–49:12 (July 2011)
Ebeida, M.S., Patney, A., Mitchell, S.A., Dalbey, K.R., Davidson, A.A., Owens, J.D.: k-d darts: Sampling by k-dimensional flat searches. ACM Trans. Graph. 33(1), 3:1–3:16 (2014). doi: 10.1145/2522528. http: //doi.acm.org/10.1145/2522528
Heck, D., Schlömer, T., Deussen, O.: Blue noise sampling with controlled aliasing. ACM Trans. Graph. (TOG) 32(3), 25 (2013)
Jones, T.R.: Efficient generation of Poisson-disk sampling patterns. J. Graph. Tools 11(2), 27–36 (2006)
Mitchell, S.A., Rand, A., Ebeida, M.S., Bajaj, C.: Variable radii Poisson-disk sampling. In: Canadian Conference on Computational Geometry, vol. 24, pp. 185–190 (2012)
Nehab, D., Hoppe, H.: A fresh look at generalized sampling. Found. Trends Comput. Graph. Vis. 8(1), 1–84 (2014)
Pharr, M., Humphreys, G.: Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann (2010)
Park, C., Pan, J., Manocha, D.: RealTime GPU-based motion planning for task executions. In: IEEE International Conference on Robotics and Automation Workshop on Combining Task and Motion Planning (May 2013)
Schlömer, T.: PSA Point Set Analysis. Version 0.2.2. http://code.google.com/p/psa/ (2011)
Tzeng, S., Patney, A., Davidson, A., Ebeida, M.S., Mitchell, S.A., Owens, J.D.: High-quality parallel depth-of-field using line samples. In: Proceedings of High Performance Graphics, pp. 23–31 (June 2012)
Acknowledgements
The UC Davis authors thank the National Science Foundation (grant # CCF-1017399), Sandia LDRD award #13-0144, UC Lab Fees Research Program Award #12-LR-238449, NVIDIA and Intel Graduate Fellowships, and the Intel Science and Technology Center for Visual Computing for supporting this work.
Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ebeida, M.S. et al. (2015). Exercises in High-Dimensional Sampling: Maximal Poisson-Disk Sampling and k-d Darts. In: Bennett, J., Vivodtzev, F., Pascucci, V. (eds) Topological and Statistical Methods for Complex Data. Mathematics and Visualization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44900-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-662-44900-4_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44899-1
Online ISBN: 978-3-662-44900-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)