Шум Перлина (Perlin Noise)

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

Многим людям приходилось использовать генератор случайных чисел в программах для создания непредсказуемости, чтобы сделать движение и поведение объектов более натуральными или генерировать текстуры. Генераторы случайных чисел, конечно, имеют свои области применения, но иногда их выход может быть слишком «жесткий», чтобы казаться естественным. В этой статье мы представляем функцию, которая имеет очень широкий спектр применения, больше, чем я мог бы думать, но в основном везде, где вам нужно чтобы что-то выглядело естественного происхождения. К тому же вывод может быть легко настроен под ваши нужды.

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

Для создания функции шума Перлина, вам нужны две вещи, функции шума и функция интерполяции.

Функция шума

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

Вот график, показывающий пример функции шума.Случайное значение от 0 до 1 присваивается каждой точки на оси X.

По плавной интерполяции между значениями, мы можем определить непрерывную функцию, которая принимает не целое в качестве параметра.

Различные способы интерполяции значений будут позже в этой статье.

Определения

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

Синусоидальная волна

(amplitude — амплитуда, wavelength — длина волны, frequency — частота)
Длина волны — это расстояние от одной вершины к другой. Амплитуда — это высота волны. Частота определяется как 1/(длина волны).

Шумовая волна

На графике этой функции шума, например, красные пятна указывают на случайные значения, определенные по измерению функции.
В этом случае амплитуда — это разница между минимальным и максимальным значениями которые у функции могут быть. Длина волны — это есть расстояние от одного красного пятна к другому. Опять же частота определяется как 1/(длина волны).

Создание функции шума Перлина

Теперь, если вы возьмёте много таких гладких функций, с различной частотой и амплитудой, вы можете добавить их все вместе, чтобы создать хорошо зашумленную функцию. Это функция шума Перлина.
Возьмите следующие функции шума

Сопоставьте их вместе и вот что вы получите в итоге.

Вы видите, что эта функция имеет крупные, средние и небольшие вариации. Вы даже можете себе представить, что это выглядит немного как горный хребет. На самом деле многие компьютерные пейзажи выполнены с использованием этого метода. Конечно они используют 2D-шум, который я получил на в данный момент.
Вы, конечно же, проделать тоже самое для двух измерений. Некоторые функции шума в 2D

Складывая все эти функции вместе получаем шумовую картину.

Стойкость(Persistence)

Когда вы добавляете вместе эти функции шума, вы можете задаться вопросом, какая именно амплитуда и частота использована каждого из них. В одномерном примере использованы два раза частоты и половины амплитуды для каждой последующей добавляемой функции шума. Это довольно распространенное явление. Таким образом, фактически, многие люди даже не рассматриваю возможность использования всего остального. Тем не менее, вы можете создать шум функции Перлина с различными характеристиками и с использованием других частот и амплитуд на каждом шагу. Например, чтобы создать гладкие холмы, вы можете использовать функции шума Перлина с большими амплитудами на низких частотах, и очень малой амплитудой на высоких частотах. Или вы могли бы сделать пологую, но очень скалистую плоскость выбором малых амплитуд для низких частот.
Чтобы сделать это проще, и, чтобы избежать повторения слов, амплитуда и частота все время, единственное число используется для определения каждой амплитуды и каждой частоты. Эта величина называется настойчивостью(Persistence). Существует некоторая неопределенность относительно его точного смысла. Этот термин был изначально придуман Мандельбротом, один из тех кто стоит за открытием фракталов. Он определил шум с большим количеством высоких частот, имеющих низкую стойкость. Мой друг Мэтт также выступил с концепцией настойчивости, но определил его наоборот. Честно говоря, я предпочитаю определение Мэтта.
Извините, Мандельброт.
Таким образом, наше определение настойчивости заключается в следующем:

frequency(частота) = 2^i 
amplitude(амплитуда) = persistence(стойкость)^i

Где i -это i-тая добавленная функция шума.
Чтобы проиллюстрировать эффект настойчисовти на выходе шума Перлина, взгляните на диаграммы внизу.
Они показывают компонент шума функции, который добавляется, эффект сохранения значения, и, как следствие функции шума Перлина.

стойкость = 1/4

частоты: 1, 2, 4, 8, 16, 32
=
Амплитуды: 1, 1/4, 1/16, 1/64, 1/256, 1/1024

стойкость = 1/2

частоты: 1, 2, 4, 8, 16, 32
=
Амплитуды: 1, 1/2, 1/4, 1/8, 1/16, 1/32

стойкость = 1/root2

частоты: 1, 2, 4, 8, 16, 32
=
Амплитуды: 1, 1/1.414, 1/2, 1/2.828, 1/4, 1/5.656

стойкость = 1

частоты: 1, 2, 4, 8, 16, 32
=
Амплитуды: 1, 1, 1, 1, 1, 1

Октавы

Каждую добавленную последующую шумовую функцию называют октавой. Причиной этого является то, что каждая функция шума имеет частоту в два раза большую чем предыдущая. В музыке октава также обладают этим свойством.
То, сколько октав вы будете складывать целиком зависит от вас. Вы можете добавить их так много или так мало, как вы хотите. Однако, позвольте мне дать вам несколько советов. Если вы используете функции шума Перлина для рендеринга изображения на экран, наступит момент, когда октава может имеет слишком высокую частоту, чтобы быть отображаемой. Там просто может не быть достаточно пикселей на экране, чтобы воспроизводить все мелкие детали на очень высокой функции шума. Некоторые реализации шума Перлина автоматически складываются из шумовых функций, до тех пор пока пределы разрешения экрана(или другой среды) не будут достигнуты.
Кроме того, разумно остановиться при добавлении шумовой функции, когда их амплитуда становится слишком мала, чтобы воспроизводиться. Когда именно это произойдет, зависит от уровня стойкости, общей амплитуды функции Перлина и бита разрешения экрана (или чего то ещё).

Создание шумовой функции

Что мы ищем в шумовой функции? По существу — генератора случайных чисел. Однако, в отличие от других генераторов случайных чисел встречаемых вами в программах, которые дают вам различные случайные числа каждый раз, когда вы их вызываете, эти шумовые функции поставлять случайное число рассчитывается из одного или нескольких параметров. То есть каждый раз, когда вы вводите то же число, шумовая функция будет отвечать тем же числом, что и раньше для этого числа. Но вводя другое число, она и вернет другое число.
Ну, я не знаю много о генераторов случайных чисел, поэтому я начал искать, и вот один я нашел. Он выглядел, довольно хорошо. Он возвращает числа с плавающей точкой от -1,0 до 1,0.

 function IntNoise(32-bit integer: x)			 

    x = (x<<13) ^ x;
    return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);    

  end IntNoise function

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

#include <stdlib.h>
#include <iostream.h>
#include <math.h>

inline long sqrt(long i)
{
	long r,rnew=1,rold=r;
	do
	{
		rold=r;
		r=rnew;
		rnew = (r+(i/r));
		rnew >>= 1;
	}
	while(rold != rnew);
	return rnew;
}

inline int isprime(long i)
{
	long si,j;
	si = sqrt(i);
	for (j=2; (j<=si); j++)
	{
		if (i%j == 0)
			return 0;
	}
	return 1;
}

void main(int argc, char *argv[])
{
	long i,i1,i2,f=0;
	if (argc < 2)
	{
		cout << endl << endl;
		cout << "Prime number finder: Hugo Elias 1998" << endl << "http://freespace.virgin.net/hugo.elias" << endl << endl;
		cout << "Usage:" << endl << "  primes a b > primes.txt" << endl << endl;
		cout << "will find all primes between a and b" << endl << "and will write the results to the file PRIMES.TXT" << endl;
		return;
	}
	i1 = atol(argv[1]);
	i2 = atol(argv[2]);
	for (i=i1; i<i2; i++)
		if (isprime(i))
		{
			f++;
			if (f==16)
			{
				cout << endl;
				f=0;
			}
			cout << i << " ";
		}

}

Интерполяция

После создания вашей шумовой функции, необходимо сгладить значения, которые она возвращает. Опять же, вы можете выбрать любой способ, который вам нравится, но некоторые выглядят лучше, чем другие. Стандартные функции интерполяции имеют три входа, a, b, значения для интерполяции между ними, и х, который принимает значения от 0 до 1. Интерполяции функция возвращает значение между a и b в зависимости от значения х. Если х равен 0, то возвращается a, и при х = 1, то возвращается b. Если х находится между 0 и 1, то возвращает некоторое значение между a и b.

Линейная интерполяция

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

function Linear_Interpolate(a, b, x)
	return  a*(1-x) + b*x
  end of function

Косинусоидальная интерполяция

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

function Cosine_Interpolate(a, b, x)
	ft = x * 3.1415927
	f = (1 - cos(ft)) * .5
	return  a*(1-f) + b*f
  end of function

Кубическая интерполяция

Этот метод дает очень гладкие результаты, конечно, но вы платите за это в скорости. Честно говоря, я не уверен, что это дать значительно лучшие результаты, чем косинусоидальная интерполяции, но здесь это все равно, если вы этого хотите. Это немного сложнее, так что будьте внимательны. Если раньше, интерполяции функции ушло три входа, кубическая интерполяция принимает пять. Вместо того чтобы просто a и b, теперь нужно v0, v1, v2 и v3, вместе с х, как раньше.

v0 = точка до a
v1 = точка a
v2 = точка b
v3 = точка полсе b

  function Cubic_Interpolate(v0, v1, v2, v3,x)
	P = (v3 - v2) - (v0 - v1)
	Q = (v0 - v1) - P
	R = v2 - v0
	S = v1

	return Px3 + Qx2 + Rx + S
  end of function

Сглаженный шум

Помимо интерполяции, вы также можете сгладить выход шумовой функции, чтобы сделать его менее случайно выглядящим, а также меньше площади в 2D и 3D версии. Сглаживание сделает больше чем вы ожидаете, и каждый, кто написал сглаживающий фильтр, или алгоритм огоня уже должны быть знакомы с этим процессом. Вместо того чтобы просто принимать значения шумовой функции в одной координат, вы можете взять среднее от значения и значения в соседних координатах. Если это непонятно, то взглянуть на псевдокод ниже.
На маленькой диаграмме, проиллюстрированы различия между сглаженной шумовой функцией и ту же функцию шума без сглаживания.
Вы можете видеть, что гладкая шумовая функция сглажена, никогда не достигает крайностей не сглаженным шумовой функции и частота оказывается примерно в два раза меньше. Существует мало смысла сглаживать 1 мерный шум, так как это действительно единственный эффект. Сглаживание становится более полезным в 2 или трех измерениях, где эффект заключается в снижении прямоугольности шума.
К сожалению, это также уменьшает контрастность. Чем сглаженнее вы сделаете это, очевидно, более плоским будет шум.

1-размерный сглаженный шум

  function Noise(x)
    .
    .
  end function

  function SmoothNoise_1D(x)
    return Noise(x)/2  +  Noise(x-1)/4  +  Noise(x+1)/4
  end function

2-размерный сглаженный шум

  function Noise(x, y)
    .
    .
  end function

  function SmoothNoise_2D(x>, y)    
    corners = ( Noise(x-1, y-1)+Noise(x+1, y-1)+Noise(x-1, y+1)+Noise(x+1, y+1) ) / 16
    sides   = ( Noise(x-1, y)  +Noise(x+1, y)  +Noise(x, y-1)  +Noise(x, y+1) ) /  8
    center  =  Noise(x, y) / 4
    return corners + sides + center
  end function

Собираем все вместе

Теперь вы знаете все, так что пришло время собрать воедино все, что вы узнали и создать функцию шума Перлина. Помните, что это всего лишь несколько интерполяций шума функции складываются. Так шум Перлина это просто функция. Вы передаете это один или несколько параметров, а он отвечает числом.
Итак, вот простая 1 мерная функция Перлина. Основная часть функции Перлина это цикл. Каждая итерация цикла добавляет еще одну октаву с удвоенной частотой. Каждая итерация вызывает различные функции шума, обозначается Noise_i. Теперь вам не нужно на самом деле писать много функций шума, по одному для каждой октавы, как предполагается в псевдокоде. Поскольку все функции шума практически одинаковы, за исключением значения этих трех больших простых чисел, вы можете сохранить тот же код, а просто использовать другой набор простых чисел для каждого.

1-размерный шум Перлина (псевдокод)

 function Noise1(integer x)
    x = (x<<13) ^ x;
    return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);    
  end function


  function SmoothedNoise_1(float x)
    return Noise(x)/2  +  Noise(x-1)/4  +  Noise(x+1)/4
  end function


  function InterpolatedNoise_1(float x)
      integer_X    = int(x)
      fractional_X = x - integer_X
      v1 = SmoothedNoise1(integer_X)
      v2 = SmoothedNoise1(integer_X + 1)
      return Interpolate(v1 , v2 , fractional_X)
  end function


  function PerlinNoise_1D(float x)
      total = 0
      p = persistence
      n = Number_Of_Octaves - 1
      loop i from 0 to n
          frequency = 2i
          amplitude = pi
          total = total + InterpolatedNoisei(x * frequency) * amplitude
      end of i loop
      return total
  end function

Теперь можно легко применить тот же код, чтобы создать 2 или более мерной функции шума Перлина.

2-размерный шум Перлина (псевдокод)

function Noise1(integer x, integer y)
    n = x + y * 57
    n = (n<<13) ^ n;
    return ( 1.0 - ( (n * (n * n * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);    
  end function

  function SmoothNoise_1(float x, float y)
    corners = ( Noise(x-1, y-1)+Noise(x+1, y-1)+Noise(x-1, y+1)+Noise(x+1, y+1) ) / 16
    sides   = ( Noise(x-1, y)  +Noise(x+1, y)  +Noise(x, y-1)  +Noise(x, y+1) ) /  8
    center  =  Noise(x, y) / 4
    return corners + sides + center
  end function

  function InterpolatedNoise_1(float x, float y)
      integer_X    = int(x)
      fractional_X = x - integer_X
      integer_Y    = int(y)
      fractional_Y = y - integer_Y
      v1 = SmoothedNoise1(integer_X,     integer_Y)
      v2 = SmoothedNoise1(integer_X + 1, integer_Y)
      v3 = SmoothedNoise1(integer_X,     integer_Y + 1)
      v4 = SmoothedNoise1(integer_X + 1, integer_Y + 1)
      i1 = Interpolate(v1 , v2 , fractional_X)
      i2 = Interpolate(v3 , v4 , fractional_X)
      return Interpolate(i1 , i2 , fractional_Y)
  end function


  function PerlinNoise_2D(float x, float y)
      total = 0
      p = persistence
      n = Number_Of_Octaves - 1
      loop i from 0 to n
          frequency = 2i
          amplitude = pi
          total = total + InterpolatedNoisei(x * frequency, y * frequency) * amplitude
      end of i loop
      return total
  end function

В конце оригинальной статьи есть дополнительные материалы, кому будет интересно думаю не затруднительно будет перейти.

Ссылки:
Собственно сама статья.
Cайт Кена Перлина

ps: Уважаемые минусующие, а мотивировать минус уже не принято?

Автор: GoldKeeper