Многие девелоперы часто сталкиваются с задаче получения красиво зашумлённой поверхности.
На Хабре часто встречаются подобные статьи: https://habrahabr.ru/post/183986/ https://habrahabr.ru/post/313420/ https://habrahabr.ru/post/322504/
Очевидно, если генерировать поверхность совершенно случайно, то результат будет не соответствовать ожиданиям программиста -- получится обычный "псевдобелый шум". Проблему такой генерации поверхности можно решать разными способами.
1. Наивно генерировать равномерную поверхность и затем случайным образом на случайную высоту выдавливать эту поверхность.
Этот способ обладает огромной вычислительной сложностью, поскольку придётся многократно итерировать по массиву точек поверхности.
Реализовав подобное, я получил 6 минут генерации тестовой поверхности 768х768 пикселов.
Результат получился не впечатляющий:
![](/documents/33644/0/XGwgkRf.jpeg/11d8ea12-6244-4b1c-b1c8-93f3bd5d27c4?t=1513771944930)
2. Использовать математические и алгоритмические решения: популярный шум Перлина или его модификацию -- сплайновый шум, который быстрее рассчитывается за счёт меньшего числа опорных точек.
Но этот способ потребует для каждой точки вычислять градиент до всех (или ближайших) опорных точек поверхности, что приводит к большому количеству операций с плавающей точкой.
А также эти подходы обладают известным недостатком -- полученная поверхность имеет сильную пространственную направленность.
![](https://hsto.org/files/fb1/dd6/703/fb1dd67034ea406f8194a494998ce424.jpg)
3. Поэтому я предлагаю подход, основанный на случайных сглаженных ключевых кривых.
Этот подход заключается в следующем:
- генерируем сглаженную случайную кривую;
- вычисляем наибольшее расхождение по высоте поверхности с предыдущей ключевой кривой, попутно сохраняя разницу;
- вычисляем количество шагов, требуемых для линейной трансформации предыдущей ключевой кривой с только что сгенерированой на основании наибольшего расхождения;
- линейно интерполируем все точки поверхности междву ключевыми кривыми, шаг интерполяции при этом равен отношению i-расхождения к наибольшему расхождению;
- заполняем промежуточные точки поверхности, попутно запоминая абсолютные максимумы и минимумы высот;
- повторяем алгоритм до получения поверхности нужного размера;
- проходим по всем точкам сгенерированой поверхности, нормализуя их в требуемых пределах: вычитаем абсолютный минимум, делим на абсолютный максимум и умножаем на нормирующий коэффициент.
В результате получился эффективный способ генерировать неразрывные сглаженные поверхности, которые в последствии можно много где использовать.
![](/documents/33644/0/4wk7V0X.jpeg/8c11ec4c-3a11-4ff7-bf35-dbd9017b76a4?t=1513771765786)
Программная реализация алгоритма доступа на моём GitHub-е по ссылке: https://github.com/zhmylove/itmmorgue/blob/terra/scripts/gen_surface.pl