null

Эффективные подходы к генерации сглаженных двумерных распределений

Многие девелоперы часто сталкиваются с задаче получения красиво зашумлённой поверхности.

На Хабре часто встречаются подобные статьи: https://habrahabr.ru/post/183986/ https://habrahabr.ru/post/313420/ https://habrahabr.ru/post/322504/

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

1. Наивно генерировать равномерную поверхность и затем случайным образом на случайную высоту выдавливать эту поверхность.
Этот способ обладает огромной вычислительной сложностью, поскольку придётся многократно итерировать по массиву точек поверхности.
Реализовав подобное, я получил 6 минут генерации тестовой поверхности 768х768 пикселов.
Результат получился не впечатляющий:

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

 

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

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

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


Программная реализация алгоритма доступа на моём GitHub-е по ссылке: https://github.com/zhmylove/itmmorgue/blob/terra/scripts/gen_surface.pl

korg

 

Коротко о себе

Работаю в компании Tune-IT, администрирую инфраструктуру компании и вычислительную сеть кафедры Вычислительной ТехникиСПбНИУ ИТМО.

Интересы: администрирование UNIX и UNIX-like систем и активного сетевого оборудования, написание shell- и perl-скриптов, изучение технологий глобальных сетей.
Люблю собирать GNU/Linux и FreeBSD, использовать тайлинговые оконные менеджеры и писать системный софт.

Nothing has been found. n is 0