Равномерное случайное (монте-карло) распределение на единичной сфере

Question

Мне нужно разъяснение с алгоритмом генерации случайных значений для моего питомца трассировщик лучей.
Я излучаю лучи из одной точки. И у меня есть проблема с распределением этих лучей: мне нужно, чтобы распределение было равномерным, но это не ...

Проблема, с которой я сейчас сталкиваюсь, заключается в том, что распределение, которое изначально было однородным, не является равномерным после моих искажений пространства результатов.

Так, например, я генерирую r и t углы, если полярная система координат. Распределение не является равномерным и не может быть равномерным: пространство вблизи каждого полюса имеет гораздо большую плотность результатов, чем, скажем, близко к экватору. Причина довольно ясна: я преобразовываю равномерно распределенные точки из цилиндрического пространства в сферические. И я искажаю результаты. Та же проблема, если я нормализую точки, сгенерированные случайным образом в кубе.

Моя идея теперь такова: я хочу создать тетраэдр, нормализовать его вершины, разделить каждую грань (треугольник) точкой в ​​середине, нормализовать ее и повторять рекурсивно, пока у меня не будет достаточно точек. Затем я немного «искажаю» эти моменты. Затем я снова их нормализую. Вот и все.

Я понимаю, что этот метод не является чисто математическим методом Монте-Карло, потому что я не использую случайное распределение ни на одном этапе, кроме последнего. И мне не нравится это решение для этой сложности.

Может кто-нибудь предложить что-нибудь более простое, но все же

• случайные
• равномерная
• быстро
• простой

Спасибо!

EDIT:
Мне нужен быстрый метод, а не только правильный. Вот почему я спрашиваю о Монте-Карло. Ответы предоставлены правильные, но не быстрые. Метод с тетраэдром быстрый, но не очень «случайный» => неверный.
Мне действительно нужно что-то более подходящее.

Answer 1

Вот алгоритм, который позволяет генерировать точки, случайно распределенные на единичной сфере.

Answer 2

Вот реализация Java, которую я использовал в прошлом:

public static double[] randomPointOnSphere(Random rnd)
{
    double x, y, z, d2;
    do {
        x = rnd.nextGaussian();
        y = rnd.nextGaussian();
        z = rnd.nextGaussian();
        d2 = x*x + y*y + z*z;
    } while (d2 <= Double.MIN_NORMAL);
    double s = Math.sqrt(1.0 / d2);
    return new double[] {x*s, y*s, z*s};
}

Answer 3

Вам действительно нужно случайное распределение или равномерное распределение по сфере?

Тогда я бы предложил углы ZCW, которые равномерно распределены по всей сфере и быстро рассчитываются. Другими методами являются TheSydneyOperaHouse (SOPHE) и Repulsion. (поиск по repulsion.c) Метод отталкивания довольно хороший, но медленный: он итеративно распределяет точки равномерно по сфере. К счастью, это нужно сделать только один раз.

Это используется в кристаллографии и ЯМР, потому что для порошковых структур быстрее использовать равномерное распределение по сравнению со случайным (вам нужно меньше точек).

Здесь - реализация Python для ZCW.

Подробнее в этих статьях:

• Исследования неслучайного численного метода для многомерного интегрирования , Ченг, Вера Б. и Генри Х. Сузукава-младший и Вольфсберг, Макс

• Компьютерное моделирование в твердотельном ЯМР. III. Усреднение порошка , Матиас Эден

Answer 4

Если вы не трассируете лучи только тривиальными сценами, будет ли время вашего рендеринга действительно зависеть от времени выборки? Если нет, то, вероятно, оптимизировать пока не стоит, хотя стоит прочитать и понять методы единообразной выборки, приведенные в других ответах.

Кроме того, ваши выборки не должны быть очень случайными, чтобы получить хорошую оценку любой функции, которую вы выбираете. Вы можете исследовать, используя последовательность квазислучайных чисел, такую ​​как последовательность Хэлтона . Ваша идея подразделения тетраэдра неплохая. Это должно привести к хорошим хорошо распределенным точкам, которые должны быть лучше, чем однородные псевдослучайные выборки для большинства сцен, хотя в некоторых случаях могут привести к ужасным артефактам.

В любом случае, вам действительно следует обратиться к форумам на ompf.org. Там есть супер-хардкорные ботаники с лучевой трассировкой.

Answer 5

Для сферических сечений генерируйте ваш угол равномерно в phi (полярный угол) и cos(theta) (для тета азимутального угла) между вашими пределами.

В псевдокоде:

phi = phi_low_limit        + rand()*(phi_high_limit       - phi_low_limit)
ct = cos(theta_high_limit) + rand()*(cos(theta_low_limit) - cos(theta_high_limit))
// The order is inverted here because cos heads down for increasing theta
theta = arccos(ct)

Это особый случай правила, которое гласит: инвертировать якобиан и генерировать в этом пространстве равномерно эти координаты.

Примечание: обратите внимание, что я использую противоположное соглашение для phi и theta из линии Дэвида Нормана.

Примечание также: на самом деле это не самый быстрый метод, а скорее тот, который иллюстрирует общий принцип.