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

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

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

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

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

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

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

  • случайный
  • униформа
  • быстрый
  • просто

Спасибо!

РЕДАКТИРОВАТЬ:
Мне нужен быстрый метод, а не только правильный. Вот почему я спрашиваю о Монте-Карло. Предоставленные ответы верны, но не быстро. Метод с тетраэдром быстрый, но не очень "случайный" => некорректный.
Мне действительно нужно что-то более подходящее.


random 3d montecarlo
person avp    schedule 03.12.2009    source источник

Ответы (5)


arrow_upward
10
arrow_downward

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

person David Norman    schedule 03.12.2009
comment
Ответы только по ссылкам не приветствуются - person Floris; 10.03.2020

arrow_upward
5
arrow_downward

Вот реализация 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};
}
person finnw    schedule 24.01.2011
comment
@DouglasZare, если d2 < MIN_NORMAL, то 1.0 / d2 может переполниться - person finnw; 25.07.2014

arrow_upward
4
arrow_downward

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

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

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

Вот реализация Python для ZCW.

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

person mrossi    schedule 31.10.2011

arrow_upward
2
arrow_downward

Для сферических секций создайте свой угол равномерно в 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 из линии Дэвида Нормана.

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

person dmckee --- ex-moderator kitten    schedule 03.12.2009

arrow_upward
2
arrow_downward

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

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

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

person Andrew Butts    schedule 05.12.2009