“Line segment sampling with blue-noise properties” by Sun, Zhou, Guo, Xie, Pan, et al. …

  • ©Xin Sun, Kun Zhou, Jie Guo, Guofu Xie, Jingui Pan, and Wencheng Wang




    Line segment sampling with blue-noise properties

Session/Category Title:   Sampling



    Line segment sampling has recently been adopted in many rendering algorithms for better handling of a wide range of effects such as motion blur, defocus blur and scattering media. A question naturally raised is how to generate line segment samples with good properties that can effectively reduce variance and aliasing artifacts observed in the rendering results. This paper studies this problem and presents a frequency analysis of line segment sampling. The analysis shows that the frequency content of a line segment sample is equivalent to the weighted frequency content of a point sample. The weight introduces anisotropy that smoothly changes among point samples, line segment samples and line samples according to the lengths of the samples. Line segment sampling thus makes it possible to achieve a balance between noise (point sampling) and aliasing (line sampling) under the same sampling rate. Based on the analysis, we propose a line segment sampling scheme to preserve blue-noise properties of samples which can significantly reduce noise and aliasing artifacts in reconstruction results. We demonstrate that our sampling scheme improves the quality of depth-of-field rendering, motion blur rendering, and temporal light field reconstruction.


    1. Akenine-Möller, T., Munkberg, J., and Hasselgren, J. 2007. Stochastic rasterization using time-continuous triangles. In GH, 7–16. Google ScholarDigital 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 (July), 86:1–86:8. Google ScholarDigital Library
    3. Barringer, R., Gribel, C. J., and Akenine-Möller, T. 2012. High-quality curve rendering using line sampled visibility. ACM Trans. Graph. 31, 6 (Nov.), 162:1–162:10. Google ScholarDigital Library
    4. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graph. 29, 6 (Dec.), 166:1–166:10. Google ScholarDigital Library
    5. Bridson, R. 2007. Fast poisson disk sampling in arbitrary dimensions. In ACM SIGGRAPH 2007 sketches, ACM, New York, NY, USA, SIGGRAPH ’07. Google ScholarDigital Library
    6. Cheslack-Postava, E., Wang, R., Akerlund, O., and Pellacini, F. 2008. Fast, realistic lighting and material design using nonlinear cut approximation. ACM Trans. Graph. 27, 5 (Dec.), 128:1–128:10. Google ScholarDigital Library
    7. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. Graph. 22, 3 (July), 287–294. Google ScholarDigital Library
    8. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (Jan.), 51–72. Google ScholarDigital Library
    9. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast poisson-disk sample generation. ACM Trans. Graph. 25, 3 (July), 503–508. Google ScholarDigital Library
    10. Durand, F., Holzschuch, N., Soler, C., Chan, E., and Sillion, F. X. 2005. A frequency analysis of light transport. ACM Trans. Graph. 24, 3 (July), 1115–1126. Google ScholarDigital Library
    11. Ebeida, M. S., Davidson, A. A., Patney, A., Knupp, P. M., Mitchell, S. A., and Owens, J. D. 2011. Efficient maximal poisson-disk sampling. ACM Trans. Graph. 30, 4 (July), 49:1–49:12. Google ScholarDigital Library
    12. Ebeida, M. S., Mitchell, S. A., Patney, A., Davidson, A. A., and Owens, J. D. 2012. A simple algorithm for maximal poisson-disk sampling in high dimensions. Comp. Graph. Forum 31, 2pt4 (May), 785–794. Google ScholarDigital Library
    13. Egan, K., Tseng, Y.-T., Holzschuch, N., Durand, F., and Ramamoorthi, R. 2009. Frequency analysis and sheared reconstruction for rendering motion blur. ACM Trans. Graph. 28, 3 (July), 93:1–93:13. Google ScholarDigital Library
    14. Egan, K., Hecht, F., Durand, F., and Ramamoorthi, R. 2011. Frequency analysis and sheared filtering for shadow light fields of complex occluders. ACM Trans. Graph. 30, 2 (Apr.), 9:1–9:13. Google ScholarDigital Library
    15. Fattal, R. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 4 (July), 48:1–48:12. Google ScholarDigital Library
    16. Gribel, C. J., Doggett, M., and Akenine-Möller, T. 2010. Analytical motion blur rasterization with compression. In HPG, 163–172. Google ScholarDigital Library
    17. Gribel, C. J., Barringer, R., and Akenine-Möller, T. 2011. High-quality spatio-temporal rendering using semi-analytical visibility. ACM Trans. Graph. 30, 4 (July), 54:1–54:12. Google ScholarDigital Library
    18. Hachisuka, T., Jarosz, W., Weistroffer, R. P., Dale, K., Humphreys, G., Zwicker, M., and Jensen, H. W. 2008. Multidimensional adaptive sampling and reconstruction for ray tracing. ACM Trans. Graph. 27, 3 (Aug.), 33:1–33:10. Google ScholarDigital Library
    19. Havran, V., Bittner, J., Herzog, R., and Seidel, H.-P. 2005. Ray maps for global illumination. In EGSR, 43–54. Google ScholarDigital Library
    20. Jarosz, W., Zwicker, M., and Jensen, H. W. 2008. The beam radiance estimate for volumetric photon mapping. Comp. Graph. Forum 27, 2 (Apr.), 557–566.Google ScholarCross Ref
    21. Jarosz, W., Nowrouzezahrai, D., Sadeghi, I., and Jensen, H. W. 2011. A comprehensive theory of volumetric radiance estimation using photon points and beams. ACM Trans. Graph. 30, 1 (Feb.), 5:1–5:19. Google ScholarDigital Library
    22. Jarosz, W., Nowrouzezahrai, D., Thomas, R., Sloan, P. P., and Zwicker, M. 2011. Progressive photon beams. ACM Trans. Graph. 30, 6 (Dec.). Google ScholarDigital Library
    23. Jensen, H. W., and Buhler, J. 2002. A rapid hierarchical rendering technique for translucent materials. ACM Trans. Graph. 21, 3 (July), 576–581. Google ScholarDigital Library
    24. Jones, T. R., and Perry, R. N. 2000. Antialiasing with line samples. In EGRW, 197–206. Google ScholarDigital Library
    25. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3 (July), 509–518. Google ScholarDigital Library
    26. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4 (Oct.), 1442–1461. Google ScholarDigital Library
    27. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1 (March), 114–129.Google ScholarCross Ref
    28. Lehtinen, J., Aila, T., Chen, J., Laine, S., and Durand, F. 2011. Temporal light field reconstruction for rendering distribution effects. ACM Trans. Graph. 30, 4 (July), 55:1–55:12. Google ScholarDigital Library
    29. 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. Google ScholarDigital Library
    30. Lloyd, S. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2 (May), 85–91.Google ScholarCross Ref
    31. McCool, M., and Fiume, E. 1992. Hierarchical poisson disk sampling distributions. In GI, 94–105. Google ScholarDigital Library
    32. Mehta, S. U., Wang, B., and Ramamoorthi, R. 2012. Axis-aligned filtering for interactive sampled soft shadows. ACM Trans. Graph. 31, 6 (Nov.), 163:1–163:10. Google ScholarDigital Library
    33. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. SIGGRAPH Comput. Graph. 21, 4 (Aug.), 65–72. Google ScholarDigital Library
    34. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. SIGGRAPH Comput. Graph. 25, 4 (July), 157–164. Google ScholarDigital Library
    35. Nehab, D., and Shilane, P. 2004. Stratified point sampling of 3D models. In PBG, 49–56. Google ScholarDigital Library
    36. Novák, J., Nowrouzezahrai, D., Dachsbacher, C., and Jarosz, W. 2012. Progressive virtual beam lights. Comp. Graph. Forum 31, 4 (June), 1407–1413. Google ScholarDigital Library
    37. Novák, J., Nowrouzezahrai, D., Dachsbacher, C., and Jarosz, W. 2012. Virtual ray lights for rendering scenes with participating media. ACM Trans. Graph. 31, 4 (July), 60:1–60:11. Google ScholarDigital Library
    38. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23, 3 (Aug.), 488–495. Google ScholarDigital Library
    39. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
    40. Öztireli, A. C., and Gross, M. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. 31, 6 (Nov.), 170:1–170:10. Google ScholarDigital Library
    41. Öztireli, A. C., Alexa, M., and Gross, M. 2010. Spectral sampling of manifolds. ACM Trans. Graph. 29, 6 (Dec.), 168:1–168:8. Google ScholarDigital Library
    42. Pang, W.-M., Qu, Y., Wong, T.-T., Cohen-Or, D., and Heng, P.-A. 2008. Structure-aware halftoning. ACM Trans. Graph. 27, 3 (Aug.), 89:1–89:8. Google ScholarDigital Library
    43. Ramamoorthi, R., Mahajan, D., and Belhumeur, P. 2007. A first-order analysis of lighting, shading, and shadows. ACM Trans. Graph. 26, 1 (Jan.). Google ScholarDigital Library
    44. Soler, C., Subr, K., Durand, F., Holzschuch, N., and Sillion, F. 2009. Fourier depth of field. ACM Trans. Graph. 28, 2 (May), 18:1–18:12. Google ScholarDigital Library
    45. Sun, X., Zhou, K., Lin, S., and Guo, B. 2010. Line space gathering for single scattering in large scenes. ACM Trans. Graph. 29, 4 (July), 54:1–54:8. Google ScholarDigital Library
    46. Tzeng, S., Patney, A., Davidson, A., Ebeida, M. S., Mitchell, S. A., and Owens, J. D. 2012. High-quality parallel depth-of-field using line samples. In HPG, 23–31. Google ScholarDigital Library
    47. Wei, L.-Y., and Wang, R. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. 30, 4 (July), 50:1–50:10. Google ScholarDigital Library
    48. Wei, L.-Y. 2008. Parallel poisson disk sampling. ACM Trans. Graph. 27, 3 (Aug.), 20:1–20:9. Google ScholarDigital Library
    49. Wei, L.-Y. 2010. Multi-class blue noise sampling. ACM Trans. Graph. 29 (July), 79:1–79:8. Google ScholarDigital Library
    50. White, K. B., Cline, D., and Egbert, P. K. 2007. Poisson disk point sets by hierarchical dart throwing. In RT, 129–132. Google ScholarDigital Library
    51. Zhou, Y., Huang, H., Wei, L.-Y., and Wang, R. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. 31, 4 (July), 76:1–76:11. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: