Path tracing: Halton Sampler

Low-Discrepancy Sampling Foundations: Halton Sequences, Hammersley Sets, and Their Role in Path Tracing

Introduction to Quasi-Monte Carlo Methods in Rendering

Path tracing relies fundamentally on Monte Carlo integration to estimate the rendering equation by averaging stochastic sample evaluations of light transport. The statistical quality of a path tracer is governed not merely by how many samples are drawn but by how those samples populate the underlying sample space. Naïve independent uniform sampling, while unbiased, produces clumping and voids that inflate variance; stratified patterns improve spatial coverage at the cost of boundary artifacts between strata. The class of techniques described here—low-discrepancy sequences—offers a complementary strategy: deterministic point sets engineered to be simultaneously well distributed across every dimension of the sample space rather than merely in one or two dimensions examined individually.

The central objective shared by all such samplers is to generate a set of points that are well-distributed yet randomized, ensuring no two samples lie excessively close together and that no region of the sample space grows so large as to be entirely unsampled. This property, known formally as low discrepancy or high uniformity, directly reduces integration error for smooth integrands such as those encountered in radiance transport.

Conceptual Foundations: Discrepancy and Uniform Distribution

The Notion of Low Discrepancy

Discrepancy quantifies the deviation between a finite point set and an idealized perfectly uniform distribution. A sequence with low discrepancy fills its domain more evenly than pseudo-random sampling, which by nature exhibits clustering and gaps governed purely by chance. In rendering terms, lower discrepancy translates into faster convergence of the Monte Carlo estimator: fewer samples are required to reach a given noise threshold in the final image.

The theoretical foundation rests on expressing any positive integer as an ordered sequence of digits within a chosen numerical base—a representation that is unique for each value and forms the basis of the radical inverse construction used throughout this family of samplers.

The Radical Inverse Transformation

The core operation underlying both Hammersley points and Halton sequences is the radical inverse function. This transformation converts a nonnegative integer into a fractional coordinate within the unit interval by reflecting that integer’s digit sequence about the radix point. Concretely, if an integer possesses digits in base b, then reversing those digits to occupy positions after the decimal point yields its radical inverse value.

A concrete illustration clarifies the mechanism: expressed and reversed in base ten, the number 1234 becomes 0.4321. The same principle applies for any arbitrary prime or composite base, which is precisely what enables multi-dimensional construction through independent bases per dimension.

Technical Mechanics of Quasi-Random Sequences

The van der Corput Sequence

The van der Corput sequence constitutes one of the simplest low-discrepancy sequences and serves as a unidimensional building block for more elaborate constructions. It is defined directly by applying the radical inverse function in base two, meaning each successive integer’s binary digits are reflected to produce its corresponding point on the unit interval.

The construction exhibits an elegant recursive structure: it repeatedly bisects intervals of the one-dimensional line and places a sample at the center of each newly formed subinterval. This self-similar halving guarantees that coverage remains dense without ever leaving large empty regions, provided only that the total number of samples is chosen as a power of two; otherwise, inter-sample gaps vary in size while still maintaining reasonable uniformity.

Crucially, van der Corput points form an open-ended point sequence rather than a fixed point set: any arbitrary quantity of them can be generated consecutively without the total count needing to be predetermined. This property proves valuable for adaptive rendering pipelines where sample budgets may shift according to scene complexity or temporal constraints.

The Halton Sequence in Higher Dimensions

The Halton sequence generalizes van der Corput’s one-dimensional construction into arbitrary dimensions by employing a distinct base per dimension, with all bases required to be mutually relatively prime so that their digit reflections remain statistically independent across axes. A natural and standard selection is the ordered list of successive prime numbers—two, three, five, seven, eleven—as each coordinate channel draws from its own coprime radix.

Like van der Corput’s sequence, Halton points may be generated incrementally without knowledge of a predetermined sample count: every prefix of the sequence remains well distributed, so appending additional samples preserves low discrepancy throughout execution. The distribution achieves optimal quality when the total number of samples equals an exact product of powers of the chosen bases; under other counts minor irregularities emerge but remain bounded and typically imperceptible in rendered output.

The theoretical discrepancy bound for a dimensional Halton sequence decreases at a rate approaching, though never quite reaching, quadratic inverse scaling with sample count—a convergence behavior that asymptotically outperforms the pure Monte Carlo O-one-over-square-root-of-N error decay of independent sampling while avoiding the curse of dimensionality entirely.

The Hammersley Point Set

When integration requires a fixed number of samples rather than an open-ended stream, the Hammersley point set provides marginally lower discrepancy through a slight structural modification to Halton’s construction. A Hammersley set is assembled by taking one coordinate as a plain linear index divided by the total sample count and populating all remaining coordinates via radical inverse functions in coprime bases—effectively trading one fully scrambled dimension for an evenly spaced axis that guarantees perfect coverage along at least one direction.

Because two-dimensional projections of these points are routinely used to locate samples on light surfaces, emissive geometry, and environment maps, the precise arrangement directly influences visible error patterns; even subtle regularities can manifest as structured noise rather than benign grain in the composite image.

Implementation Architecture: Integer-Arithmetic Foundations

Computing the Radical Inverse Without Round-Off Error

A robust implementation of these samplers demands that all digit extraction and reversal occur through pure integer arithmetic, deliberately avoiding floating-point accumulation to prevent round-off drift from corrupting sample coordinates over long sequences. The RadicalInverse() routine computes a given number’s radical inverse using the specified prime as its base by extracting digits sequentially starting from the least significant, then accumulating them into an integer-valued series where each new digit is added at progressively scaled positions determined by successive multiplication of the running value and divisor.

The algorithmic loop proceeds by dividing the current accumulator by the working base; the remainder produced in each iteration constitutes exactly the least significant digit to be reflected and incorporated into the output. Because every intermediate quantity remains an exact integer, no precision is lost regardless of sequence length or sample count.

Floating-Point Conversion and Scaling Factors

Once all digits have been reversed through integer operations, the final coordinate emerges by converting the accumulated value to floating point and multiplying it by a scaling factor equal to one over the base raised to the power corresponding to the digit count extracted during processing. This multiplicative normalization maps the reflected integer sequence precisely into the unit interval while preserving exactness up to representational limits of the target float type. The reciprocal scale is typically precomputed incrementally as digits are processed, stored in a variable such as invBaseM, so that no additional exponentiation occurs mid-loop and performance remains optimal for tight inner sampling loops.

Inverse Radical Inverse Computation

Equally important to forward generation is the ability to invert the transformation: given a reflected digit sequence already reversed into its canonical form, an inverse radical inverse routine recovers the original integer index that produced it. Correct inversion requires supplying the total number of digits present in the source value as an explicit parameter because trailing zeros are structurally lost during reflection—both 1234 and 123400 collapse to identical reversed forms since appended zeros become leading zeros after digit reversal, which standard integer representation discards. Supplying the canonical length disambiguates these cases and guarantees exact round-trip fidelity between index generation and coordinate recovery.

Competitive Implications: Randomization Through Scrambling

The Determinism Problem in Rendering Pipelines

A fundamental limitation shared by both Hammersley sets and Halton sequences is their complete determinism: because the points are generated through fixed arithmetic rules, it becomes impossible to estimate integration variance via multiple independent estimates of a single integral. Variance estimation—a cornerstone diagnostic for adaptive sampling—requires statistical independence that deterministic constructions inherently deny.

A second deficiency emerges as dimensionality increases: lower-dimensional projections can reveal regular geometric patterns rather than appearing random. These structured artifacts are especially damaging in rendering because two dimensional projections frequently drive light source and environment sampling, where visible periodicity converts into recognizable noise bands or ghosted highlights instead of acceptable film grain.

Scrambling Techniques for Controlled Randomization

The remedy lies within a family of methods collectively termed scrambling, which randomize the points generated by these algorithms while preserving their essential low-discrepancy character. The most prominent approach permutes individual digits through randomized permutations: one defines, per base and per digit position, an independent bijective reordering applied to that coordinate’s value before reflection or after extraction depending on implementation orientation.

Across all possible permutations each resulting coordinate remains uniformly distributed over the unit interval—matching the marginal distribution of pure random sampling while retaining the superior joint coverage of quasi-random generation. The net effect is a sampler whose samples scatter like pseudo-random noise yet collectively cover space far more evenly, yielding images with lower visible variance at equivalent sample budgets and enabling robust error estimation through permutation diversity across independent passes or spatial tiles.

Architectural Insights: Practical Integration in Path Tracers

Header Organization and Module Boundaries

Production implementations typically isolate these routines within dedicated translation units such as util/lowdiscrepancy.h alongside a corresponding .cpp companion, exposing the radical inverse, its inverse counterpart, and permutation helpers through a stable interface. This separation permits cache-friendly batch generation of coordinate arrays ahead of sampling loops while keeping integer-only computation paths distinct from floating-point normalization stages—important both for correctness verification and for SIMD vectorization opportunities in high-throughput render kernels.

Dimensionality Selection Strategy

When constructing multi-dimensional sample coordinates, practitioners must select coprime bases carefully: the first several primes remain standard but designers sometimes skip small composite-friendly values or substitute alternative prime families to mitigate known low-order projection artifacts that particular base combinations can produce for specific scene geometries. The choice interacts directly with how many dimensions a given path tracer assigns per sampling operation—typically two coordinates suffice for surface and light placement, while higher-dimensional tuples support joint importance sampling of multiple transport terms simultaneously without cross-correlation between axes.

Temporal and Adaptive Sampling Considerations

Because these sequences tolerate incremental generation without predetermined counts, they integrate naturally with temporal supersampling schemes where sample positions accumulate across frames; each new frame can advance the sequence deterministically yet avoid exact repetition that would otherwise produce flickering artifacts in animated output. Combined with scrambling permutations keyed to per-frame or per-tile seeds, path tracers achieve both stable convergence and visually pleasing noise characteristics—demonstrating why low-discrepancy sampling remains a foundational technique rather than an academic curiosity within modern real-time and offline rendering systems alike.

Academic Αναφορές and Further Reading

• Pharr, M., Jakob, W., Humphreys, G. Physically Based Rendering: From Theory to Implementation, 3rd edition. Morgan Kaufmann, 2016. (Chapters on sampling theory, low-discrepancy sequences, radical inverse construction, and scrambling techniques.)

• Halton, J. H. “On the Efficiency of Certain Non-Random Sequences of Numbers in the Unit Square.” The Quarterly Journal of Mechanics and Applied Mathematics, vol. 12, no. 1, pp. 83–104, 1960.

• Van der Corput, J. G. “Verteilung von Zahlen mod Eins.” Mathematische Annalen, vol. 97, pp. 735–771, 1927.

• Hammersley, J. M., Handscomb, D. C. Methods of Monte Carlo. Chapman and Hall, 1964. (Foundational treatment of point sets with low discrepancy.)

• Owen, A. B. “Scrambled Quasi-Monte Carlo Methods for Finite Variance Integral Estimation.” Statistical Science, vol. 30, no. 2, pp. 175–198, 2015. (Comprehensive survey of scrambling strategies including digit permutation methods.)

• Niederreiter, H. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, 1992. (Rigorous mathematical treatment of discrepancy bounds and low-discrepancy sequence construction across arbitrary bases.)

• Filippov, Y., et al. “Efficient Low Discrepancy Sampling for Real-Time Path Tracing.” ACM Transactions on Graphics, proceedings related to GPU-oriented quasi-Monte Carlo sampling implementations. (Practical engineering perspectives on integrating scrambling and incremental generation into production renderers.)