Poisson Disk Generator (2 стр)

Прикольно)

Алексей Патрашов
> А Мерсен куда потерялся? Я полосатость видел только у совсем примитивных ГПСЧ.
> Я код посмотрел, а там болтается квадратный корень, что на скорость влияет
> отрицательно. Картина высокохудожественная где-нибудь есть для сравнения?
Дело не в полосатости - вот как выглядят точки при обычном рандоме:

Алексей Патрашов
> Объясните мне, тупому, в чём тут глубокий смысл и почему распределение Пуассона
> выглядит как равномерное двухмерное?
Если внимательно почитать, то понятно что настоящее равномерное не гарантирует что точки не будут слипаться в кластеры.
Что, например, для процедурной засейки травой и деревьями крайне неприятная штука.

Алексей Патрашов
> А Мерсен куда потерялся? Я полосатость видел только у совсем примитивных ГПСЧ.
Тут борятся не с полосатостью, а чтобы расстояние между точками было не менее определенного (в зависимости от плотности).

Я идею понял. Когда улучшу время попробую сделать алгоритм с учётом уже проставленных точек. У меня ещё была мысль о проходе ячейкой с рандомом по ячейке.

Алексей Патрашов
> алгоритм с учётом уже проставленных точек
Так там и сделано. Прочитай пейпер, чтобы велосипед не изобретать http://people.cs.ubc.ca/%7Erbridson/docs/bridson-siggraph07-poissondisk.pdf

о... ещё занятней...

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

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

Алексей Патрашов
> Вероятность пересчитывать на клетку и одновременно получаются и координаты в клетке.
Вот сравнение пересчёта на клетку (jittered grid) с пуассоном:

На клетках всё ещё получаются кластеры из 3 точек (а максимум может быть 4 рядом).

kipar
> Или у тебя гарантируется что две точки не могут оказаться рядом (при этом пустых полос нет)?
Я исходил из того, что у меня задаются по углам клетки значения в зависимости от соседних клеток и положения в них точек. Тогда можно уже не переделывать равномерное распределение в трапецию, а сравнивать с трапецией, то есть вместо обратного преобразования использовать функцию распределения, которая будет квадратичной в противовес квадратному корню функции преобразования.

Алексей Патрашов
Интересно посмотреть реализацию и результат.

Алексей Патрашов
А анизотропии между направлением по диагонали и по вертикали\горизонтали и вообще заметной клеточности точно не будет?

kipar
> А анизотропии между направлением по диагонали и по вертикали\горизонтали и вообще заметной клеточности точно не будет?
По идее не должно, доберусь до питона может в эти выходные и опробую, там хорошая библиотека для изображений. В глубокой теории можно применить вообще алгоритм перебора с предотвращением кластеризации, но у него O(N2) сложность и ну его нафиг. Если ячейки попиксельно бить на вероятности с выбором нижнего значения, то должно быть всё достаточно раскидано выглядеть.

В копилку: Point Sampling with General Noise Spectrum

Алексей Патрашов
> но у него O(N2)
У алгоритма из статьи сложность O(N*K). Зачем делать N^2?