ACM Trans. Graph. (Proceedings of SIGGRAPH Asia 2023)

Analysis and Synthesis of Digital Dyadic Sequences

Abdalla G. M. Ahmed       Mikhail Skopenkov       Markus Hadwiger       Peter Wonka

KAUST, KSA

Generating matrices, points, and periodograms of various digital dyadic sequences. The first $2^m$ points of the sequences are shown for $m=0,\dots,9$ in separate squares of increasing sizes. The digital dyadic sequences in (b) and (c) are obtained by reordering the known digital dyadic nets with the same names; such reordering is one of the main discoveries of the paper. The sequence in (d) is obtained from a $256$-point Gray net by first reordering it into a sequence and then extending the sequence in one of the possible ways. The sequence in (e) represents a new class of self-similar sequences introduced in the paper.

Abstract

We explore the space of matrix-generated $(0, m, 2)$-nets and $(0, 2)$-sequences in base 2, also known as digital dyadic nets and sequences. In computer graphics, they are arguably leading the competition for use in rendering. We provide a complete characterization of the design space and count the possible number of constructions with and without considering possible reorderings of the point set. Based on this analysis, we then show that every digital dyadic net can be reordered into a sequence, together with a corresponding algorithm. Finally, we present a novel family of self-similar digital dyadic sequences, to be named ξ-sequences, that spans a subspace with fewer degrees of freedom. Those $\xi$-sequences are extremely efficient to sample and compute, and we demonstrate their advantages over the classic Sobol $(0, 2)$-sequence.

Interactive Demo

In this demo we see actual plots of ξ-sequences. The top-left plot is the main, origin-anchored sequence, the bottom-right plot shows xor-scrambled variants with shifted origin, The bottom-left section shows dithering patterns of the sequence, using sample indices as thresholds, compared to dithering with Sobol, Bayer, and Ulichney's VnC masks. The matrices are for the x and y components, the z (or Morton) ordering index, and the inversion from z index to sequence number. The following controls are available:

• Roll the mouse wheel, or pinch-zoom the plot, or set 'm' to increase or decrease the number of samples.
• Drag the main plot to move point #1, shown in red, to set the primary parameter 'a' of the sequence.
• Drag the variants plot to position point #0, the secondary parameter of the sequence. Please note how the images of point #1 at different scales move relative to point #0.
• Drag the slider to adjust the dragging speed, click or tap the button to reset to default speed, which is the visual dragging speed.
• Edit the value directly in the 'a' and 'p0' fields, observing the displayed format. Please note that 'a' should be at least 0.5, or 0x80000000 in our 32-bit fixed-point representation.
• Toggle the stratification grid on and off.
• Toggle the check button to outline the domain at different scales, and highlight sub-quadrant 1, the one that opposes point #0.
• Display and threshold (fixed tone option) the dither matrix, and use the slider, or the mouse wheel over the dither plot, to adjust the threshold. The increment is 256 points, and the reset button adjusts the slider to 50% of the 512x512 dither matrix.
• Thresholded dither matrix may be seen as an efficient way of seeing a large number of points from the sequence. The smallest threshold corresponds to "m = 8" in the p0 plot!

Since scrolling/dragging is used in the plots, please use the matrices pane to scroll/drag the page.

Downloads

	Preprint PDF (14.1 MB)
	Source Code ZIP (11 KB)

Bibtex

@article{Ahmed23DigitalSequences,
    author      = {Ahmed, Abdalla G. M.
                   and Skopenkov, Mikhail
                   and Hadwiger, Markus
                   and Wonka, Peter},
    title       = {{Analysis and Synthesis of Digital Dyadic Sequences}},
    year        = {2023},
    issue_date  = {December 2021},
    publisher   = {ACM},
    volume      = {42},
    number      = {6},
    url         = {},
    doi         = {10.1145/3618308},
    journal     = {ACM Trans. Graph.},
    month       = dec,
    articleno   = {218},
    numpages    = {17},
    keywords    = {sampling, nets, digital nets, dyadic nets, Sobol sequence,
                   Faure sequence, quasi-Monte Carlo, low-discrepancy sequences,
                   self-similar}
}

Acknowledgments

We are grateful to F. Pillichshammer for bringing earlier proofs of Theorems 3.1 and 3.3 (which we conceived independently) to our attention.
Thanks to Mohanad Ahmed for his insightful discussions.