Шум Перлина на C#

09.06.2018 at 11:39

Шум Перлина — алгоритм генерации текстур, который придумал Кен Перлин в 1983 году. Позже он улучшил свой алгоритм, который теперь так и называется — улучшенный шум Перлина.
Особенность такой генерации в том, что шум Перлина генерирует случайные числа для любой точки пространства, но случайные значения отличаются незначительно для точек, находящихся недалеко друг от друга.

Рассмотрим реализаию для плоскости, т.е. у каждой точки 2 координаты.
Для начала всем точкам плоскости с целыми координатами сопоставляется случайный вектор. В оригинальном алгоритме это был любой вектор единичной длины, в улучшенной версии алгоритма то должен быть 1 из следующих векторов: (1, 0), (-1, 0), (0, 1), (0, -1).
В оригинальной версии алгоритма для этого использовалася хеш от координат, я же для простоты ограничиваю пространство и выбираю случайный вектор для каждой точки. Это неоптимально с точки зрения производительности, но проще в реализации.

Сначала определим класс вектора

private class FloatVector {
    public double X { get; set; }
    public double Y { get; set; }
    public FloatVector () { }
    public FloatVector (double x, double y) {
        this.X = x;
        this.Y = y;
    }
} 

и сгенерируем вектора для всех нужных точек. Я это сделал в конструкторе

private FloatVector[, ] grid;

private FloatVector[] availableGradients;

private Random random = new Random ();

public PerlinNoiseGenerator (int width, int height) {
    availableGradients = new FloatVector[] { 
        new FloatVector(1, 0), 
        new FloatVector(-1, 0), 
        new FloatVector(0, 1), 
        new FloatVector(0, -1) 
    };
    grid = new FloatVector[width, height];
    for (var i = 0; i < width; i++) {
        for (var j = 0; j < height; j++) {
            grid[i, j] = availableGradients[random.Next(3)];
        }
    }
}

При генерации значения для точки (x, y) находим ближайшие к ней точки с целочисленными координатами (x0, y0), (x0, y1), (x1, y0), (x1, y1).
Далее для каждой точки считаем скалярное произведение двух векторов: случайного, сгенерированного ранее, и вектора до точки (x, y).

int x0 = (int) x;
double dx = x - x0;
int y0 = (int) y;
double dy = y - y0;

var vx0y0 = grid[x0, y0];
var vx0y1 = grid[x0, y0 + 1];
var vx1y0 = grid[x0 + 1, y0];
var vx1y1 = grid[x0 + 1, y0 + 1];
var s = MultiplyVectors (vx0y0, 
    new FloatVector (x - x0, y - y0));
var t = MultiplyVectors (vx1y0, 
    new FloatVector (x - x0 - 1, y - y0));
var u = MultiplyVectors (vx0y1, 
    new FloatVector (x - x0, y - y0 - 1));
var v = MultiplyVectors (vx1y1, 
    new FloatVector (x - x0 - 1, y - y0 - 1));

функция скалярного произведения двух векторов выглядит так:

private double MultiplyVectors (FloatVector v1, FloatVector v2) {
    return v1.X * v2.X + v1.Y * v2.Y;
}

Мы получили случайные числа для каждой из соседних елочисленных точек. Теперь считаем средневзвешенное значение. В качестве веса используем расстояние до точки (x, y) по каждой из осей.

var a = GetWeightedAverage(s, t, dx);
var b = GetWeightedAverage(u, v, dx);
var c = GetWeightedAverage(a, b, dy);

private double GetWeightedAverage(double a, double b, double weight) {
    return a + Fade(weight) * (b - a);
}

Особенность этой реализации средневзвешенного в том, что вес дополнительно прогоняется через функцию Fade

private double Fade (double t) {
    return 6 * t * t * t * t * t - 15 * t * t * t * t + 10 * t * t * t;
}

Эта функция как бы прижимает значение к одному из краев отрезка [0, 1]. Т.е. если X близок к 0, то Fade(X) еще ближе к 0. При этом
Fade(0) == 0
Fade(1) == 1
Fade(0.5) == 0.5

Теперь осталось только вернуть нормализованное значение

return Normalize(c);

private double Normalize (double x) {
    return (x + 1) / 2;
}

Функция Normalize переводит отрезок [-1, 1] в [0, 1].

Получившийся код позволяет генерировать вот такие текстуры:



На обновления блога теперь можно подписаться Вконтакте