Я внедряю raytracer, и я занимаюсь реализацией сэмплеров. Сэмплер - это генератор случайных точек над квадратом x = 0: 1, y = 0: 1. Каждый сэмплер содержит несколько наборов «случайных» сэмплов, и каждый набор содержит заданное количество сэмплов.
Теперь, один из семплеров - NRooks. Он делит поверхность на блоки n x n, выбирает блоки по диагонали, в каждом диагональном блоке выделяет случайную точку и, наконец, перетасовывает сначала x между собой, затем y.
Это все красиво и чисто. Однако, когда пришло время извлечь точки, книга, за которой я следую, предлагает эти дополнительные требования, чтобы нарушить корреляции между последующими пикселями и выборками.
Первое требование заключается в том, что каждый раз, когда набор исчерпан, новый набор выборок выбирается случайным образом. Код, реализованный для достижения этой цели, следующий:
Point2D Sampler::sample_unit_square(void) {
if (count % num_samples == 0) jump = (rand_int() % num_sets) * num_samples;
return (samples[jump + count++ % num_samples]
}
, где samples - это вектор Point2D размером num_samples*num_sets (линеаризован). Каждый раз, когда делается один пиксель (число делится на num_samples), новый переход извлекается и используется для указания линейного массива для начала нового набора.
Поскольку я использую python, моя стратегия использует итераторы:
def __iter__(self):
while True:
for sample_set in random.choice(self._samples_sets):
for sample in sample_set:
yield sample
Это тривиально, и работает нормально.
Вторая необходимость - перетасовать индексы, и вот где мой вопрос. Книга пересматривает код следующим образом
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]]
}
где перетасованные индексы - это массив, вычисляемый следующим образом
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]);
}
}
}
, который является очень C ++ способом взять список чисел от 1 до n и перемешать их. Я хотел реализовать следующий код в 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
Я мог бы также реализовать случайный итератор, который выполняет итерации на множестве, сохраняя копию списка, но это не главное. Мой вопрос возникает из следующей фразы в книге:
... Еще одна возможность [удалить корреляцию] состоит в том, чтобы использовать конечный случайный порядок на выборках каждого набора, но это разрушает условие n-rooks [...]. Лучшим способом является случайное перемешивание индексов, используемых в sample_unit_square, для каждого набора, но при этом гарантируется, что используются все образцы.
Что я не понимаю, так это: почему это говорит о том, что окончательное перемешивание на сэмплах каждого набора разбивает n-ладьи? Дело в том, что он использует косвенное индексирование в массив точек. Этот косвенный индекс создается путем перестановки всех индексов от 1 до количества наборов, но это эквивалентно перемешиванию на всех выборках в каждом наборе. Будучи ИМХО эквивалентным, я не понимаю, почему первая формулировка должна сломать n-ладьи, а вторая - нет.
Книга, для протокола: «Трассировка луча с нуля», Кевин Сафферн.