Равномерное распределение точек на сфере

aa_dav

Прикольный способ - я вот до него не допер Главное - простой. Чем-то похож на метод Монте-Карло вычисления чиста пи


Booster

Доказательства нет - интуиция

А вообще рассуждения были примерно такие: первый поворот как раз и портит все распределение, если угол распределен линейно. Линейное распределение угла дает косинусное распределение координаты Z. Вспомнилась формула - как вычислить случайную величину, если есть ее функция распределение и линейная rnd -> [0; 1] (через обратную функцию). Сложил все в кучу и пишла идея - нужно сменить линейное распределение на синусное/косинусное. Ну и далее - взял арксинус и derive, и подогнал график

[edit]

Да, и собственно интуиция подсказала, что точки лягут равномерно, если будет равномерное распределение относительно координаты z. От этого и шел.

 

Pavia

Ты z не используешь, а изначальная проблема как раз и кроется в распределении z.

 

aa_dav
Откуда там будет сгущение, если идём всегда по медиане? По-сути первая точка рендомит вторую систему координат. Её можно и не считать, а просто взять случайную матрицу поворота.

 

_DEN_
Z я использую. Просто у меня проекция такая что z направленно в глубь монитора. Поэтому она неучаствует.
А ты попробуй и проверь все будет корректно.

 

Pavia

Тоже неправильный подход. У тебя нижнее полушарие будет густым, а верхнее - редким. Направив ось в зрителя ты этого в 2д не увидишь.

 

псевдокод. предполагается что сфера радиуса R и центр её находится в центре координат.

Код (Text):

1. z = random( -R, +R )
2. phi = random( 0, 2 * Pi )
3. rz = sqrt( R^2 -z^2 )
4. x = rz * sin( phi )
5. y = rz * cos( phi )

на выходе (x,y,z) - координаты нашей точки.

2 Booster

Раз не было возражений по моему пониманию твоего метода, значит я прав, значит будут сгущения. Если считаешь иначе - сравни с моим псевдокодом свой алгоритм и поясни где они одинаковы.

 

_DEN_
Оно не редкое оно пустое. =) Заменил на the:=arccos(2*Random-1). Повертел шарик все впорядке.

 

Pavia

Ну теперь да Арккосинус ведь так же леко выражается через арксинус как и косинус через синус. Ну или наоброт

 

_DEN_
Оно не редкое оно пустое. =) Заменил на the:=arccos(2*Random-1). Повертел шарик все впорядке.

 

Да, не прокотило моё предположение. Сделал так: Рендомнул точку на окружности, потом нашёл 3 рендомных матрицы вращений по трём осям, перемножил их. Умножил точку на результат умножения трёх матриц.

50 000 точек.

 

Booster

Хмм... Это что? Очень похоже на равномерно раскиданные точки, но на ортогональную проекцию.

 

_DEN_
В смысле на ортогональную проекцию?

 

Хех... =) Прикольно что именно этот метод (а это 3 случайных угла Эйлера) я пытался продвигать в той теме про которую писал. И тоже ошибся. Изначально просто звучало предложение про 2 угла Эйлера (а это, как я понял, именно то что ты писал). Но два угла Эйлера давали сгущение на полюсах. Тогда я подумал что просто все забыли про третий угол Эйлера и ввёл его в алгоритм (тут похожее уже постили на первой или второй странице) и сгущения проявились не на полюсах, а на экваторе.

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

 

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

 

Booster

Ну сгущение есть, а перспективного искажения нет. Как будто ортогональная проекция (FoV -> 0).

 

_DEN_
Как это ты определил? FOV = 45%. И где сгущения?

 

Booster

Я прогнал, у тебя все правильно.

 

В принципе причина сгущения точек у полюсов при равномерном распределении углов - понятна, и соотв-но как с ней бороться - тоже. Равные площади сечений - это чересчур "круто" и все можно объяснить проще. Каждому значению вертикального угла на сфере соответствует окружность (параллель) радиуса R*cos и соотв-но длина окружности уменьшается от экватора к полюсам. Для того, чтобы точки равномерно заполняли поверхность сферы нужно чтобы кол-во точек на каждой параллели было пропорционально ее длине, т.е. пропорционально R*cos (т.е. к экватору больше, к полюсам меньше). Добиться этого можно несколькими способами. Например в лоб (алгоритмически) - для кажого равномерно распределенного вертикального угла генерировать не одну точку (одно значение азимутального угла), а N точек, где N пропорционально косинусу данного верт.угла (аналогично можно и децимацию прикрутить по Booster-y). Или же выдавать по 2 независимых угла на каждой итерации, но тогда распределение вертик.угла должно быть не равномерным, а таким, чтобы распределение R*cos было равномерным, откуда "после несложных" преобразований получаем, что можно либо генерить случайный верт.угол по закону арксинуса (_DEN_), либо вместо угла - равномерно распределенную координату z = R*sin (aa_dav)

 

leo

Длина окружности, по мере движения к плюсу уменьшается, но площадь сегментов нет ^)
Я пока нашёл объяснение феномена сгущений, в том, что на втором угле Эйлера, вероятность точек повышается к полюсу ввиду того, что окружности на них банально сходятся, на картинке это должно быть более понятно.

1D-полюс.

Если же добавить ещё один угол, то как раз получается сгущение по-экватору, так как добавилось ещё одно измерение, полюса размазались по окружности. Это легко понять, если представить, что первая окружность, задаваемая первым углом начинает вращаться в одном измерении, а значит и сгустки тоже вращаются в плоскости.

С добавлением же ещё одного угла, сгущения равномерно размазываются по всей поверхности шара.

Для рандомизации точек на поверхности шара достаточно двух углов, но в этом случае добавляются две области сгущения. В свою очередь эти области сгущения рандомизируются с помощью ещё двух углов.

_DEN_
Зря ты эту тему в хип, мне понравилась. ^)

 

Booster

А "банальная сходимость" меридианов чем по твоему обусловлена ? Именно уменьшением длины окружности параллели при приближении к полюсам. Т.е. одинаковым угловым расстояниям phi между меридианами соответствуют разные линейные расстояния phi*R*cos(B) в зависимости от вертикального угла B - чем меньше, тем реже, чем больше, тем гуще.
Поэтому если мы задаем равномерное распределение по двум углам, то на каждой параллели в среднем оказывается одинаковое число точек, но из-за разных длин окружностей на полюсах точки будут лежать гуще, чем на экваторе

Смотря каких сегментов. При равномерном шаге по вертик.углу - площадь ес-но уменьшается, т.к. длина элемента дуги меридиана остается фиксированой, а длина окружности уменьшается. А вот при равномерном шаге по оси Z - остается постоянной, т.к. при этом уменьшение радиуса параллели компенсируется увеличением длины дуги меридиана