Хороший способ процедурно сгенерировать графику «BLOB-объектов» в 2D
Я собираюсь создать "blob" в быстром вычислительном смысле. BLOB-объект здесь определяется как набор пикселей, которые могут быть любой формы, но все связаны между собой. Примеры:
.ooo....
..oooo..
....oo..
.oooooo.
..o..o..
...ooooooooooooooooooo...
..........oooo.......oo..
.....ooooooo..........o..
.....oo..................
......ooooooo....
...ooooooooooo...
..oooooooooooooo.
..ooooooooooooooo
..oooooooooooo...
...ooooooo.......
....oooooooo.....
.....ooooo.......
.......oo........
Где. является мертвым пространством, а o является отмеченным пикселем. Я забочусь только о «двоичном» поколение - пиксель включен или выключен. Так, например, они будут выглядеть как воображаемый шарик кетчупа, вымышленной бактерии или любого другого органического вещества.
Какой алгоритм может этого добиться? Я действительно в растерянности
2 ответа
Комментарий Дэвида Тонли верен, но я предполагаю, что вы хотите каплю с «органической» формой и гладкими краями. Для этого вы можете использовать метаболы. Метабаллы — это степенная функция, работающая со скалярным полем. Скалярные поля можно эффективно визуализировать с помощью алгоритма марширующих кубов. Различные формы могут быть сделаны путем изменения количества шаров, их положения и их радиуса.
См. здесь введение в 2D-метаболы: http://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html
А здесь введение в алгоритм марширующих кубов: http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/
Обратите внимание, что 256 комбинаций для пересечений в 3D — это всего лишь 16 комбинаций в 2D. Это очень легко реализовать.
РЕДАКТИРОВАТЬ:
Я собрал быстрый пример с шейдером GLSL. Вот результат использования 50 больших двоичных объектов с функцией энергии с домашней страницы hkankaan.
Вот фактический код GLSL, хотя я оцениваю его пофрагментно. Я не использую алгоритм марширующих кубов. Вам нужно отрендерить полноэкранный четырехугольник, чтобы он работал (два треугольника). Униформ-массив vec3 — это просто двумерные позиции и радиусы отдельных BLOB-объектов, переданные с помощью glUniform3fv.
/* Trivial bare-bone vertex shader */
#version 150
in vec2 vertex;
void main()
{
gl_Position = vec4(vertex.x, vertex.y, 0.0, 1.0);
}
/* Fragment shader */
#version 150
#define NUM_BALLS 50
out vec4 color_out;
uniform vec3 balls[NUM_BALLS]; //.xy is position .z is radius
bool energyField(in vec2 p, in float gooeyness, in float iso)
{
float en = 0.0;
bool result = false;
for(int i=0; i<NUM_BALLS; ++i)
{
float radius = balls[i].z;
float denom = max(0.0001, pow(length(vec2(balls[i].xy - p)), gooeyness));
en += (radius / denom);
}
if(en > iso)
result = true;
return result;
}
void main()
{
bool outside;
/* gl_FragCoord.xy is in screen space / fragment coordinates */
outside = energyField(gl_FragCoord.xy, 1.0, 40.0);
if(outside == true)
color_out = vec4(1.0, 0.0, 0.0, 1.0);
else
discard;
}
Вы вероятно, могли бы разработать алгоритмы для этого, которые являются второстепенными вариантами ряда алгоритмов генерации случайных лабиринтов. Я предложу один, основанный на методе union-find.
Основная идея объединения-поиска состоит в том, чтобы, учитывая набор элементов, разделенных на непересекающиеся (непересекающиеся) подмножества, быстро определить, к какому разделу принадлежит конкретный элемент. «Объединение» объединяет два непересекающихся набора вместе, чтобы сформировать больший набор, «найти» определяет, к какому разделу принадлежит конкретный элемент. Идея состоит в том, что каждый раздел набора может быть идентифицирован конкретным элементом набора, поэтому вы можете формировать древовидные структуры, в которых указатели указывают от элемента к элементу к корню. Вы можете объединить два раздела (с произвольным элементом для каждого), сначала найдя корень для каждого раздела, а затем изменив (ранее нулевой) указатель для одного корня, чтобы он указывал на другой.
Вы можете сформулировать свою задачу как задачу о непересекающихся объединениях. Изначально каждая отдельная ячейка представляет собой отдельный раздел. Что вы хотите, так это объединять разделы, пока не получите небольшое количество разделов (не обязательно два) связанных ячеек. Затем вы просто выбираете один (возможно, самый большой) из разделов и рисуете его.
Для каждой ячейки вам понадобится указатель (изначально нулевой) для объединения. Вам, вероятно, понадобится битовый вектор, чтобы действовать как набор соседних ячеек.Первоначально каждая ячейка будет иметь набор из четырех (или восьми) соседних ячеек.
Для каждой итерации вы выбираете ячейку случайным образом, затем следуете по цепочке указателей, чтобы найти ее корень. В деталях из корня вы найдете набор его соседей. Выберите из него случайный элемент, затем найдите для него корень, чтобы идентифицировать соседний регион. Выполните объединение (укажите один корень на другой и т. д.), чтобы объединить две области. Повторяйте, пока не будете довольны одним из регионов.
При слиянии разделов новым набором соседей для нового корня будет установленная симметричная разность (исключающее ИЛИ) наборов соседей для двух предыдущих корней.
Вы, вероятно, захотите сохранить другие данные по мере расширения разделов, например. размер - в каждом корневом элементе. Вы можете использовать это, чтобы более избирательно относиться к конкретному союзу и помочь решить, когда остановиться. Некоторая мера рассеяния ячеек в разделе может иметь значение, например. небольшое отклонение или стандартное отклонение (относительно большого количества клеток), вероятно, указывает на плотное пятно примерно круглой формы.
Когда вы закончите, вы просто просканируете все ячейки, чтобы проверить, является ли каждая из них частью выбранного вами раздела, чтобы построить отдельное растровое изображение.
В этом подходе, когда вы случайным образом выбираете ячейку в начале итерации, существует сильное смещение в сторону выбора больших разделов. Когда вы выбираете соседний раздел, вы также склоняетесь к выбору большего соседнего раздела. Это означает, что вы, как правило, довольно быстро получаете одну явно доминирующую каплю.