Golden Ratio Sequences for Low-Discrepancy Sampling

Abstract

Most classical constructions of low-discrepancy point sets are based on generalizations of the one-dimensional binary van der Corput sequence, whose implementation requires nontrivial bit-operations. As an alternative, we introduce the quasi-regular golden ratio sequences, which are based on the fractional part of successive integer multiples of the golden ratio. By leveraging results from number theory, we show that point sets, which evenly cover the unit square or disc, can be computed by a simple incremental permutation of a generator golden ratio sequence. We compare ambient occlusion images generated with a Monte Carlo ray tracer based on random, Hammersley, blue noise, and golden ratio point sets. The source code of the ray tracer used for our experiments is available online at the address provided at the end of this article.

Notes

¹Number theorists have related the quality of approximations of a real number by rational numbers to the size of the coefficients that appear in its continued fraction expansion. Smaller coefficients in this expansion lead to reals with worse rational approximations. The golden section , with a continued fraction expansion with constant coefficients 1 (minimal), thus has the worst approximations.