Два усовершенствования алгоритма Роберта Бридсона по принципу «разделяй и властвуй».
Задний план
Простым и достаточно быстрым алгоритмом для создания шаблона выборки диска Пуассона является алгоритм Роберта Бридсона O (n). Основываясь на этом, я рассмотрю два способа использования потоков для ускорения алгоритма, чтобы мы могли генерировать больше точек за то же время. Оба подхода просты в реализации и довольно быстрые с визуально неотличимыми результатами.
Прежде чем идти дальше, я настоятельно рекомендую проверить алгоритм Роберта Бридсона, чтобы понять, как он работает. Вот анимация оригинального алгоритма в действии:
Все белые и красные точки - это образцы, которые были созданы на данный момент. Но красные точки являются частью активного списка. Желтая граница - это указанные границы.
Глядя на анимированный предварительный просмотр алгоритма выше, можно подумать об использовании нескольких потоков для заполнения отдельных областей. И это именно то, что делает первый подход.
Подход 1 - Ковши
В этом подходе мы разбиваем всю область на сегменты одинакового размера с их собственной хеш-сеткой. Мы запускаем алгоритм в каждом сегменте в отдельном потоке. Точки, расположенные очень близко к краям каждой корзины, возможно, придется проверять на пересечение с точками в другой корзине, и это может вызвать конкуренцию между потоками. Мы можем легко устранить это противоречие, добавив немного отступов в каждую корзину. И вот что мы получаем:
Затем соседние корзины и их хэш-сетки объединяются в новую корзину. Обратите внимание на пробел из-за добавленного отступа. Мы можем заполнить этот пробел большим количеством очков. Для этого мы добавляем образцы, близкие к объединенной границе, в новый активный список (красные точки):
Затем мы снова запускаем алгоритм в каждом сегменте, снова объединяем сегменты и снова генерируем. Мы повторяем эти фазы, пока не останется только одна область, которая является исходной областью, которую мы разбиваем:
Еще раз обратите внимание, что на каждом этапе ведра заполняются отдельными потоками. Таким образом, сначала будет заполнено 4 на 4 = 16 ведер, затем 8, затем 4 и так далее, пока у нас не останется только один. Последнее ведро завершено в основном потоке. И это дает нам ускорение примерно в 4 раза, как показано на графике ниже:
Подход 2 - Плитка
Дальнейшего ускорения можно достичь, предварительно сгенерировав несколько плиток, которые мы вставляем в ведра на первом этапе. Это ускоряет начальную фазу разделения и генерации.
Как только мы штампуем плитки, мы просто позволяем процессу работать как Bucket Approach, объединять-генерировать снова и снова.
Однако характеристики производительности этого подхода теперь зависят от гораздо большего числа факторов. Нравится размер и количество уникальных плиток. Когда размер плитки небольшой, на их объединение уходит много времени. Но по мере увеличения размеров плитки на их создание тратится больше времени. Методом проб и ошибок удается получить 32 плитки размером с 4 уникальных плитки, что дает наилучшую производительность. И, судя по моим экспериментам, он подходит для общей площади как 256 на 256, так и 512 на 512.
Вы можете сравнить окончательный результат двух подходов на изображении ниже. Мы видим разницу в количестве баллов. И этого следовало ожидать, поскольку на начальном этапе посева баллы в корзинах распределялись бы по-разному.
Теперь, сравнивая производительность с двумя другими методами, мозаичный подход в четыре раза быстрее, чем подход Bucket:
Вывод
Тайловый подход кажется вполне подходящим для создания множества точек выборки диска Пуассона. При визуальном осмотре отлично смотрится плиточный подход. Если внимательно присмотреться, можно заметить некоторое повторение. Мы можем добавить немного случайности, вращая и / или переворачивая плитки за счет немного более высоких накладных расходов на этапе штамповки.
Дополнительные замечания
Этот алгоритм был написан на C # для работы с игровым движком Unity. Все иллюстрации были сделаны на игровом движке Unity.
