Некоторое время назад я опубликовал пост о воссоздании некоторого генеративного искусства, которое я видел в Интернете Эспеном Клюге, и дошел до точки в коде, где мне пришлось генерировать случайные точки на изображении. В то время я не придавал этому особого значения. Тем не менее, это оказывается действительно интересной темой в области разработки игр или генеративного искусства. Как вы распределяете точки внутри области, которая каждый раз будет отличаться, но более равномерно распределена по плоскости? Что я выяснил, так это то, что использование функции random не даст вам по-настоящему случайной выборки. Некоторые точки будут группироваться вместе в области, что не будет хорошим распределением по области изображения.
Случайность, Которая на Самом Деле не Случайна
Короткий ответ на этот вопрос заключается в том, что случайность, используемая Processing, P5 или Javascript, на самом деле не является случайным процессом. Он использует так называемый генератор псевдослучайных чисел. Различие (о котором я узнал здесь и здесь . По сути, компьютер будет использовать некоторое внутреннее начальное значение для генерации числа, и начальное значение будет меняться при каждом последующем запуске случайной функции. Это означает, что если бы мы знали состояние случайного начального значения, то случайная функция действительно была бы предсказуемой и определенной.
Фактически, в processing есть функция, позволяющая вам изначально задать начальное значение, так что функция random будет выдавать вам один и тот же результат каждый раз, когда вы запускаете функцию (см. here ).
Таким образом, random на самом деле даст вам шаблонный результат, а не плавное распределение. Вот тут-то и вступает в дело выборка по Пуассоновскому диску. Техника в алгоритме состоит в том, чтобы разделить область на сетку, отслеживать, какие точки вы заложили, и делать это за O (n) времени, где n – размер имеющихся у вас точек. Довольно больной!
Алгоритм
Я частично собираюсь пересказать то, что Дэн Шиффман рассказывает в своем видео с поездом по кодированию здесь и дать вам только основы алгоритма.
Высокоуровневый вид алгоритма заключается в разделении пространства на сетку, и каждая итерация случайным образом выбирает точку, ближайшую к последней, и проверяет, что эта точка не находится на определенном расстоянии от любой другой точки сетки. Я собираюсь специально сделать это в 2 измерениях, но это может быть расширено на любую произвольную величину.
Переменные
ширина и высота: Насколько велика область выборки. Они предоставляются нам бесплатно в p5 и обработке.
r: Минимальное расстояние, разделяющее каждую точку. Поскольку мы равномерно распределяем нашу выборку, алгоритм должен знать, на каком расстоянии друг от друга должна находиться каждая точка выборки.
k: Максимальное количество предположений, которые алгоритм может сделать, чтобы поместить точку, прежде чем двигаться дальше. Это останавливает попытку алгоритма разместить точку, которая находится слишком близко к соседним точкам.
сетка: Это одномерный массив, который содержит все точки пространства, в котором вы выполняете выборку. Используя вложенные циклы for, вы сможете получить доступ к элементам в массиве в соответствии с их положением в пространстве (подробнее об этом ниже).
активный: Это также одномерный массив, который содержит все точки в образце, которые были размещены. Это будет удобно для непрерывной генерации точек.
К Кодексу!
Я собираюсь использовать для этого processing и Java, поэтому типы каждой переменной будут:
import java.util.ArrayList; float k = 30; float r = 10; PVector[] grid; ArrayListactive = new ArrayList ();
Сетка существенно не изменится при ее запуске, поэтому нет необходимости использовать структуру данных ArrayList. Однако активный список требует выталкивания и выталкивания из массива, поэтому это должно изменяться повсюду.
Шаг 1: Создайте случайную точку в сетке
Алгоритм запускается путем случайного определения местоположения точки в пространстве выборки и добавления ее в активный список. Мой код выглядел следующим образом:
import java.util.ArrayList; float k = 30; float r = 10; int cols; int rows; float w = r / sqrt(2); PVector[] grid; ArrayListactive = new ArrayList (); void setup() { size(400,400); background(0); cols = floor(width / w); rows = floor(height / w); grid = new PVector[rows*cols]; for (int i = 0; i < cols * rows; i++) { grid[i] = null; } PVector point = new PVector(random(width), random(height)); int i = floor(point.x/w); int j = floor(point.y/w); grid[i + j * cols] = point; active.add(point); }
Помимо обычных настроек обработки, я инициализировал количество столбцов и строк, которые нам нужны, создал необходимое нам пространство в сетке, умножив столбцы на строки, и переменную, которая будет длиной окружности радиуса r, которая инкапсулирует квадрат. Видеть:
Это делает невозможным, чтобы две точки выборки находились в одной и той же ячейке сетки. Мы инициализируем вектор случайной точки в пространстве с помощью обработки и переводим эту точку в положение на сетке и добавляем эту точку в наш список активных точек.
Шаг 2: Попытайтесь разместить новую точку
Теперь самая сложная часть алгоритма. Мы циклически берем выборку из активного массива и пытаемся сгенерировать новую точку, которая находится на расстоянии не менее r, но меньше 2 * r. Мы проделаем это k раз, чтобы не застрять в бесконечном цикле. Вот код, который я написал для достижения этой цели:
void draw() {
background(0);
if (active.size() > 0) {
int i = floor(random(active.size()));
PVector pos = active.get(i);
for (int j = 0; j < k; j++) {
PVector sample = PVector.random2D();
float m = random(r, 2 * r);
sample.setMag(m);
sample.add(pos);
if (testSample(sample) == true) {
active.add(sample);
int x = floor(sample.x / w);
int y = floor(sample.y / w);
grid[x + y * cols] = sample;
break;
} else if (j == k - 1) {
active.remove(i);
}
}
}
}
Boolean testSample(PVector sample) {
int col = floor(sample.x / w);
int row = floor(sample.y / w);
//println(col, row, cols, rows, grid[col + row * cols]);
if (col > 0 && row > 0 && col < cols - 1 && row < rows - 1 && grid[col + row * cols] == null) {
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
int index = (col + i) + (row + j) * cols;
PVector neighbor = grid[index];
if (neighbor != null) {
float d = PVector.dist(sample, neighbor);
if (d < r) {
return false;
}
}
}
}
return true;
}
return false;
}
Я начну с самого верха и сейчас буду двигаться вниз. Итак, поскольку цикл рисования выполняется снова и снова, мы можем использовать его как цикл while. Таким образом, если активный массив пуст, у нас нет позиции для генерации выборок, а это значит, что мы бы сгенерировали все. Далее мы случайным образом захватим элемент в активном массиве. Мы случайным образом создадим 2D-вектор, установим его величину или длину в диапазоне от r до 2 * r, а затем добавим элемент, который мы генерируем вокруг этого нового вектора. Отчасти это связано с хорошими векторными атрибутами.
Как только мы получим наш сгенерированный вектор, мы должны проверить, не находится ли этот вектор на расстоянии r от другой точки. Это подводит нас к методу “testSample”, который я написал. Он берет образец, который мы сделали, и проверяет все соседние местоположения сетки вокруг него, чтобы увидеть, не находится ли он слишком близко к ним. Важно отметить, что отсутствие сетки означало бы, что нам пришлось бы проверять все точки, которые мы сгенерировали до сих пор. Назначение их местоположениям в сетке означает, что мы можем быстро проверить.
Мы будем перебирать между одним столбцом выше и ниже нашей выборки, а также одной строкой выше и ниже нашей выборки. Была какая-то странная обработка ошибок, которую нужно было выполнить, если мы находились в первой и последней строке и столбце, и если эта точка сетки уже была сгенерирована. Наконец, если мы сталкиваемся с соседом, и этот сосед находится слишком близко к нашей выборке, метод возвращает значение false. И если мы проверили все соседние ячейки сетки и нет красных флажков, то этот пункт хорош, и мы можем вернуть true.
if (testSample(sample) == true) {
active.add(sample);
int x = floor(sample.x / w);
int y = floor(sample.y / w);
grid[x + y * cols] = sample;
break;
} else if (j == k - 1) {
active.remove(i);
}
Итак, если этот протестированный образец хорош, мы находим его местоположение в сетке, добавляем точку в нашу сетку и добавляем ее в активный список, потому что затем она может генерировать еще одну. Однако, если мы не смогли сгенерировать точку, А переменная цикла j вот-вот выйдет из цикла (т.Е. Мы сгенерировали k точек), тогда мы вставляем точку, которую мы использовали для генерации выборок, потому что это не удалось в k испытаниях.
И БУМ, мы получили полный алгоритм выборки по пуассоновскому диску, готовый к работе. Если вы хотите вывести это из обработки, просто замените “if (active.size() > 1)” циклом while, и он должен работать просто отлично.
Оригинал: “https://dev.to/christiankastner/poisson-disc-sampling-and-generative-art-2fpd”