Random access (quasi-?)random sequence

Question

Fix a dimension $d \ge 1$. Is there an efficiently computable sequence $f : \mathbb{N} \to [0,1]^d$ such that

1. $f$ is either random or quasirandom (e.g., similar to Sobol sequences).

2. Given $n \in \mathbb{N}$ and a box $S = [a_0,b_0] \times \cdots \times [a_{d-1},b_{d-1}]$, one can find the subset $f_{S,n} = \{f_k | k<n, f_k \in S\}$ in output sensitive time $O(\operatorname{poly}(\log n +|f_{S,n}|))$.

The motivation is that such a sequence would provide a nice way to use non-jittery, low-noise sampling when zooming around in an image.

Answer 1

There's a paper by Gruenschloss about enumerating Sobol points falling within some elementary intervals: https://github.com/lgruen/sample-enum

This is used in pbrt with the global sampler in order to figure out which samples correspond to which pixel, namely the part about getIndexForSample. You can find it for Sobol here: https://github.com/mmp/pbrt-v3/blob/master/src/samplers/sobol.cpp and the SobolIntervalToIndex can be found here: https://github.com/mmp/pbrt-v3/blob/master/src/core/lowdiscrepancy.h