“k-d Darts: Sampling by k-Dimensional Flat Searches” by Ebeida

  • ©

Conference:


Type(s):


Title:

    k-d Darts: Sampling by k-Dimensional Flat Searches

Session/Category Title:   Points & Reconstruction

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    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 useful for exploring a function’s properties, such as estimating its integral, or finding an exemplar above a threshold. We describe a recipe for converting some algorithms from point sampling to k-d dart sampling, if the function can be evaluated along a k-d flat. We demonstrate that k-d darts are more efficient than point-wise samples in high dimensions, depending on the characteristics of the domain: for example, the subregion of interest has small volume and evaluating the function along a flat is not too expensive. We present three concrete applications using line darts (1-d darts): relaxed maximal Poisson-disk sampling, high-quality rasterization of depth-of-field blur, and estimation of the probability of failure from a response surface for uncertainty quantification. Line darts achieve the same output fidelity as point sampling in less time. For Poisson-disk sampling, we use less memory, enabling the generation of larger point distributions in higher dimensions. Higher-dimensional darts provide greater accuracy for a particular volume estimation problem.

References:


    1. C. B. Barber, D. P. Dobkin, and H. T. Huhdanpaa. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469–483.
    2. R. L. Cook. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72.
    3. M. A. Z. Dippé and E. H. Wold. 1985. Antialiasing through stochastic sampling. In Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’85). 69–78.
    4. M. S. Ebeida and S. A. Mitchell. 2011. Uniform random voronoi meshes. In Proceedings of the 20th International Meshing Roundtable. 258–275.
    5. M. S. Ebeida, S. A. Mitchell, A. Patney, A. A. Davidson, and J. D. Owens. 2012. A simple algorithm for maximal Poisson-disk sampling in high dimensions. Comput. Graph. Forum 31, 2, 785–794.
    6. M. S. Ebeida, A. Patney, S. A. Mitchell, A. Davidson, P. M. Knupp, and J. D. Owens. 2011. Efficient maximal Poisson-disk sampling. ACM Trans. Graph. 30, 4, 49:1–49:12.
    7. M. N. Gamito and S. C. Maddock. 2009. Accurate multidimensional Poisson-disk sampling. ACM Trans. Graph. 29, 1, 8:1–8:19.
    8. P. W. Glynn and D. L. Iglehart. 1989. Importance sampling for stochastic simulations. Manag. Sci. 35, 11, 1367–1392.
    9. C. J. Gribel, R. Barringer, and T. Akenine-Möller. 2011. High quality spatio-temporal rendering using semi-analytical visibility. ACM Trans. Graph. 30, 54:1–54:11.
    10. C. J. Gribel, M. Doggett, and T. Akenine-Möller. 2010. Analytical motion blur rasterization with compression. In Proceedings of Conference on High Performance Graphics (HPG’10). 163–172.
    11. P. E. Haeberli and K. Akeley. 1990. The accumulation buffer: Hardware support for high-quality rendering. In Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’90). 309–318.
    12. A. Hall. 1873. On an experimental determination of π. Messenger Math. 2, 113–114.
    13. E. Hammon Jr. 2008. Practical post-process depth of field. In GPU Gems 3, H. Nguyen, Ed., Addison-Wesley, 583–605.
    14. W. Jarosz, D. Nowrouzezahrai, I. Sadeghi, and H. W. Jensen. 2011. A comprehensive theory of volumetric radiance estimation using photon points and beams. ACM Trans. Graph. 30, 1, 5:1–5:19.
    15. H. W. Jensen and P. H. Christensen. 1998. Efficient simulation of light transport in scenes with participating media using photon maps. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’98). 311–320.
    16. T. R. Jones and D. R. Karger. 2011. Linear-time Poisson-disk patterns. J. Graph. GPU Game Tools 15, 3, 177–182.
    17. T. R. Jones and R. N. Perry. 2000. Antialiasing with line samples. In Proceedings of the Eurographics Workshop on Rendering Techniques. Springer, 197–206.
    18. A. Lagae and P. Dutré. 2008. A comparison of methods for generating Poisson disk distributions. Comput. Graph. Forum 27, 1, 114–129.
    19. J. Lehtinen, T. Aila, J. Chen, S. Laine, and F. Durand. 2011. Temporal light field reconstruction for rendering distribution effects. ACM Trans.Graph. 30, 4, 55:1–55:12.
    20. Y.-S. Liu, J.-H. Yong, H. Zhang, D.-M. Yan, and J.-G. Sun. 2006. A quasi-Monte Carlo method for computing areas of point-sampled surfaces. Comput.-Aided Des. 38, 1, 55–68.
    21. N. L. Max. 1990. Antialiasing scan-line data. IEEE Comput. Graph. Appl. 10, 1, 18–30.
    22. M. D. McKay, R. J. Beckman, and W. J. Conover. 1979. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, 2, 239–245.
    23. D. P. Mitchell. 1987. Generating antialiased images at low sampling densities. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’87). 65–72.
    24. G. Nebe and N. Sloane. 2012. A catalogue of lattices. http://www.math.rwth-achen.de/∼Gabriele.Nebe/LATTICES/index.html.
    25. A. B. Owen. 1992. A central limit theorem for Latin hypercube sampling. J. Royal Statist. Soc. Series B (Methodological) 54, 2, 541–551.
    26. J. F. Ramaley. 1969. Buffon’s noodle problem. Amer. Math. Monthly 76, 8, 916–918.
    27. J. Rovira, P. Wonka, F. Castro, and M. Sbert. 2005. Point sampling with uniformly distributed lines. In Proceedings of the 2nd Eurographics/IEEE VGTC Conference on Point-Based Graphics (SPBG’05). Eurographics Association, 109–118.
    28. T. Schlömer. 2011. PSA point set analysis. http://code.google.com/p/psa/.
    29. J. Spanier. 1966. Two pairs of families of estimators for transport problems. J. SIAM Appl. Math. 14, 702–713.
    30. X. Sun, K. Zhou, S. Lin, and B. Guo. 2010. Line space gathering for single scattering in large scenes. ACM Trans. Graph. 29, 4, 54:1–54:8.
    31. S. Tzeng, A. Patney, A. Davidson, M. S. Ebeida, S. A. Mitchell, and J. D. Owens. 2012. High-quality parallel depth-of-field using line samples. In Proceedings of the Conference on High Performance Graphics (HPG’12). 23–31.
    32. E. Veach and L. J. Guibas. 1997. Metropolis light transport. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’97). 65–76.
    33. L.-Y. Wei. 2008. Parallel Poisson disk sampling. ACM Trans. Graph. 27, 3, 20:1–20:9.
    34. K. B. White, D. Cline, and P. K. Egbert. 2007. Poisson disk point sets by hierarchical dart throwing. In Proceedings of the IEEE Symposium on Interactive Ray Tracing (RT’07). 129–132.

ACM Digital Library Publication:


Overview Page: