Sobol' Sequences with Guaranteed-Quality 2D Projections
ACM Transactions on Graphics · 01.08.2025 · 44 (4) · 1-16
DOI: 10.1145/3730821 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 27.07.2025. Verfasst von Nicolas Bonneel und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 30 Literaturangaben. Gefördert von: Agence Nationale de la Recherche.
Abstract (Originalsprache)
Low-discrepancy sequences, and more particularly Sobol' sequences are gold standard for drawing highly uniform samples for quasi-Monte Carlo applications. They produce so-called ( t,s )-sequences, that is, sequences of s -dimensional samples whose uniformity is controlled by a non-negative integer quality factor t. The Monte Carlo integral estimator has a convergence rate that improves as t decreases. Sobol' construction in base 2 also provides extremely fast sampling point generation using efficient xor-based arithmetic. Computer graphics applications, such as rendering, often require high uniformity in consecutive 2D projections and in higher-dimensional projections at the same time. However, it can be shown that, in the classical Sobol' construction, only a single 2D sequence of points (up to scrambling), constructed using irreducible polynomials x and x + 1, achieves the ideal t = 0 property. Reusing this sequence in projections necessarily loses high dimensional uniformity. We prove the existence and construct many 2D Sobol' sequences having t = 1 using irreducible polynomials p and p 2 + p + 1. They can be readily combined to produce higher-dimensional low discrepancy sequences with a high-quality t = 1, guaranteed in consecutive pairs of dimensions. We provide the initialization table that can be directly used with any existing Sobol' implementation, along with the corresponding generator matrices, for an optimized 692-dimensional Sobol' construction. In addition to guaranteeing the (1, 2)-sequence property for all consecutive pairs, we ensure that t ≤ 4 for consecutive 4D projections up to 2 15 points.
Förderung
- Agence Nationale de la Recherche
Zitieren
APA
Bonneel, N., Coeurjolly, D., Iehl, J., & Ostromoukhov, V. (2025). Sobol' Sequences with Guaranteed-Quality 2D Projections. ACM Transactions on Graphics, 44(4), 1-16. https://doi.org/10.1145/3730821
Vancouver
Bonneel N, Coeurjolly D, Iehl J, Ostromoukhov V. Sobol' Sequences with Guaranteed-Quality 2D Projections. ACM Transactions on Graphics. 2025;44(4):1-16. doi:10.1145/3730821
BibTeX
@article{Bonneel2025,
author = {Bonneel, Nicolas and Coeurjolly, David and Iehl, Jean-Claude and Ostromoukhov, Victor},
title = {Sobol' Sequences with Guaranteed-Quality 2D Projections},
journal = {ACM Transactions on Graphics},
year = {2025},
volume = {44},
number = {4},
pages = {1--16},
doi = {10.1145/3730821}
}
EUVIMED