“Consequences of stratified sampling in graphics” by Mitchell

  • ©Don Mitchell




    Consequences of stratified sampling in graphics



    Antialiased pixel values are often computed as the mean of N point samples. Using uniformly distributed random samples, the central limit theorem predicts a variance of the mean of O(N-1). Stratified sampling can further reduce the variance of the mean. This paper investigates how and why stratification effects the convergence to mean value of image pixels, which are observed to converge from N-2 to N-1, with a rate of about N-3/2 in pixels containing edges. This is consistent with results from the theory of discrepancy. The result is generalized to higher dimensions, as encountered with distributed ray tracing or form-factor computation.


    1. J. Beck and W. W. L. Chen. Irregularities of Distribution, Cambridge University Press, 1987.
    2. R. L. Cook, Stochastic sampling in computer graphics. ACM Trans. Graphics 5:1 (1986) 51-72.
    3. R. A. Cross. Sampling Patterns Optimized for Uniform Distributed Edges. Graphics Gems V, Academic Press, 1995, 359-363.
    4. M.A.Z. Dippe and E. H. Wold. Antialiasing through stochastic sampling. Computer Graphics 19:3 (1985) 69-78.
    5. D. P. Dobkin and D. P. Mitchell. Random-edge discrepancy of supersampling patterns. Graphic Interface, York, Ontario (1993).
    6. D. P. Dobkin, D. Eppstein and D. P. Mitchell. Computing the Discrepancy with Applications to Supersampling Patterns. Trans. Graphics (to appear).
    7. J. H. Halton. A retrospective and prospective survey of the Monte Carlo method. SIAM Review 12 (1970) 1-63.
    8. J. M. Hammersley and D. C. Handscomb. Monte Carlo Methods. Methuen & Co., London, 1964.
    9. J. T. Kajiya. The Rendering Equation. Computer Graphics 20 (1986) 143-150.
    10. M. Lee, R. A. Redner, and S. P. Uselton. Statistically optimized sampling for distributed ray tracing. Computer Graphics 19:3 (1985) 61-67.
    11. D. P. Mitchell. Generating antialiased images at low sampling densities. Computer Graphics 21:4 (1987) 65-72.
    12. J. Painter and K. Sloan. Antialiased ray tracing by adaptive progressive refinement. Computer Graphics 23:3 (1989) 281-288.
    13. W. Purgathofer. A statistical model for adaptive stochastic sampling. Proc. Eurographics (1986) 145- 152.
    14. P. Shirley. Discrepancy as a quality measure for sample distributions. Proc. Eurographics (1991) 183-193.
    15. J. Spanier and E. M. Gelbard. Monte Carlo Principles and Neutron Transport Problems. Addison-Wesley, Reading, MA, 1969.

ACM Digital Library Publication: