barajando y preservación de restricción NRooks

Question

Estoy implementando un raytracer, y estoy en el medio de implementar muestreadores. Una muestra es un generador de puntos aleatorios sobre un cuadrado x = 0: 1, y = 0: 1. Cada muestra contiene múltiples conjuntos de muestras "aleatorias", y cada conjunto contiene una cantidad dada de muestras.

Ahora, uno de los Samplers es el NRooks. Divide la superficie en bloques n x n, elige los bloques a lo largo de la diagonal, en cada bloque diagonal extrae un punto aleatorio y finalmente mezcla primero el x entre sí, luego el y.

Todo esto es agradable y limpio. Sin embargo, cuando llega el momento de extraer los puntos, el libro que estoy siguiendo propone estos requisitos adicionales para romper las correlaciones entre los píxeles posteriores y los muestreos. El primer requisito es que cada vez que se agote un conjunto, se elija un nuevo conjunto de muestras al azar. El código implementado para lograr esto es la siguiente:

Point2D Sampler::sample_unit_square(void) { 
    if (count % num_samples == 0) jump = (rand_int() % num_sets) * num_samples; 
    return (samples[jump + count++ % num_samples] 
} 

donde samples es un vector de Point2D de tamaño num_samples*num_sets (es linealizado). Cada vez que se realiza un píxel (el recuento es divisible por num_samples) se extrae un nuevo salto y se utiliza para indicizar el conjunto lineal para el inicio de un nuevo conjunto.

Desde que estoy usando Python, mi estrategia hace uso de iteradores:

def __iter__(self): 

    while True: 
     for sample_set in random.choice(self._samples_sets): 
      for sample in sample_set: 
       yield sample 

Esto es trivial, y funciona bien.

La segunda necesidad es mezclar los índices, y aquí es donde está mi pregunta. El libro revisa el código como sigue

Point2D Sampler::sample_unit_square(void) { 
    if (count % num_samples == 0) jump = (rand_int() % num_sets) * num_samples; 
    return (samples[jump + shuffled_indices[ jump + count++ % num_samples]] 
} 

donde índices barajadas es una matriz calcula como sigue

void Sampler::setup_shuffled_indices(void) { 
    shuffled_indices.reserve(num_samples*num_sets); 
    vector<int> indices; 

    for (int j=0; j<num_samples; j++) indices.push_back(j); 

    for (int p=0; p<num_sets; p++) { 
      random_shuffle(indices.begin(), indices.end()); 
      for (int j=0; j<num_samples; j++) { 
       shuffled_indices.push_back(indices[j]); 
      } 
    } 
} 

que es una forma muy C++ de tomar una lista de números de 1 a n y arrastrando los pies ellos. Quería poner en práctica el siguiente código en Python

def __iter__(self): 

    while True: 
     sample_set = random.choice(self._samples_sets): 
     shuffled_set = sample_set[:] 
     random.shuffle(shuffled_set) 
     for sample in shuffled_set: 
      yield sample 

También podría implementar un iterador que itera al azar en el set, guardar la copia lista, pero este no es el punto. Mi pregunta surge de la siguiente frase en el libro:

... Otra posibilidad [para eliminar la correlación] es utilizar un shuffle de final sobre las muestras de cada conjunto, pero esto destruye la N-torres condición [. ..]. La mejor manera es barajar aleatoriamente los índices utilizados en sample_unit_square, para cada conjunto, pero garantizar que se utilicen todas las muestras.

Lo que no entiendo es: ¿por qué dice que la mezcla final en las muestras de cada conjunto rompe los novatos? el punto es que está usando la indexación indirecta en la matriz de puntos. Este índice indirecto se crea a partir de una mezcla de todos los índices del 1 al número de conjuntos, pero esto es equivalente a una mezcla en todas las muestras en cada conjunto. Al ser en mi humilde opinión equivalente, no veo por qué la primera formulación debe romper los torres nórdicas y por qué la segunda no.

El libro, para el registro, es "Ray Tracing from the ground up", de Kevin Suffern.

Answer 1

A mi me parece como

... utilizar una reproducción aleatoria final sobre las muestras de cada conjunto ..

está sugiriendo que barajar cada juego de forma independiente después de la puesta se barajan.

def __iter__(self): 

    while True: 
     for sample_set in random.choice(self._samples_sets): 
      for sample in random.choice(sample_set): 
       yield sample 

Like so. No soy un experto en Python, así que perdona cualquier error de código. Esto rompería los novatos, aunque podría ser simplemente una mala idea. Depende de lo que estés buscando.