Хороший способ процедурно генерировать «блоб» графику в 2D

Question

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

.ooo....  
..oooo..  
....oo..  
.oooooo.
..o..o..  

...ooooooooooooooooooo...  
..........oooo.......oo..  
.....ooooooo..........o..  
.....oo..................  


......ooooooo....  
...ooooooooooo...  
..oooooooooooooo.  
..ooooooooooooooo  
..oooooooooooo...  
...ooooooo.......  
....oooooooo.....  
.....ooooo.......  
.......oo........  

Где. является мертвым пространством, а o является отмеченным пикселем. Я забочусь только о «двоичном» поколении - пиксель включен или выключен. Так, например, они будут выглядеть как воображаемый шарик кетчупа, вымышленной бактерии или любого другого органического вещества.

Какой алгоритм может этого добиться? Я действительно в растерянности

Answer 1

Комментарий Дэвида Тонли прав, но я собираюсь предположить, что вам нужен шарик с «органической» формой и гладкими краями. Для этого вы можете использовать metaballs. Metaballs - это степенная функция, которая работает на скалярном поле. Скалярные поля можно эффективно визуализировать с помощью алгоритма марширующих кубов. Различные формы могут быть сделаны путем изменения количества шариков, их положения и радиуса.

Смотрите здесь введение в 2D метаболлы: http://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html

А вот для ознакомления с алгоритмом марширующих кубов: http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

Обратите внимание, что 256 комбинаций для пересечений в 3D - это только 16 комбинаций в 2D. Это очень легко реализовать.

EDIT:

Я собрал быстрый пример с шейдером GLSL. Вот результат использования 50 капель с функцией энергии с домашней страницы hkankaan.

Вот фактический код GLSL, хотя я оцениваю этот фрагмент. Я не использую алгоритм марширующих кубов. Вам нужно отрендерить полноэкранный квад для того, чтобы он работал (два треугольника). Равномерный массив vec3 - это просто 2D-позиции и радиусы отдельных капель, передаваемые с помощью 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;
}

Answer 2

Вот подход, в котором мы сначала генерируем кусочно-аффинный картофель, а затем сглаживаем его путем интерполяции.Идея интерполяции основана на использовании ДПФ, затем оставлении низких частот такими, какие они есть, заполнении нулями на высоких частотах и ​​использовании обратного ДПФ.

Вот код, требующий только стандартные библиотеки Python:

import cmath
from math import atan2
from random import random

def convexHull(pts):    #Graham's scan.
    xleftmost, yleftmost = min(pts)
    by_theta = [(atan2(x-xleftmost, y-yleftmost), x, y) for x, y in pts]
    by_theta.sort()
    as_complex = [complex(x, y) for _, x, y in by_theta]
    chull = as_complex[:2]
    for pt in as_complex[2:]:
        #Perp product.
        while ((pt - chull[-1]).conjugate() * (chull[-1] - chull[-2])).imag < 0:
            chull.pop()
        chull.append(pt)
    return [(pt.real, pt.imag) for pt in chull]


def dft(xs):
    return [sum(x * cmath.exp(2j*pi*i*k/len(xs)) 
                for i, x in enumerate(xs))
            for k in range(len(xs))]

def interpolateSmoothly(xs, N):
    """For each point, add N points."""
    fs = dft(xs)
    half = (len(xs) + 1) // 2
    fs2 = fs[:half] + [0]*(len(fs)*N) + fs[half:]
    return [x.real / len(xs) for x in dft(fs2)[::-1]]

pts = convexHull([(random(), random()) for _ in range(10)])
xs, ys = [interpolateSmoothly(zs, 100) for zs in zip(*pts)]   #Unzip.

Это генерирует что-то вроде этого (начальные точки и интерполяция):

Вот еще одна попытка:

pts = [(random() + 0.8) * cmath.exp(2j*pi*i/7) for i in range(7)]
pts = convexHull([(pt.real, pt.imag ) for pt in pts])
xs, ys = [interpolateSmoothly(zs, 30) for zs in zip(*pts)]

Иногда они имеют изгибы и вогнутости.Такова природа этого семейства BLOB-объектов.

Обратите внимание, что SciPy имеет выпуклый корпус и БПФ, поэтому вышеуказанные функции могут быть заменены ими.

Answer 3

Возможно, вы могли бы разработать для этого алгоритмы, которые являются второстепенными вариантами ряда алгоритмов генерации случайных лабиринтов.Я предлагаю один, основанный на методе union-find .

Основная идея в union-find заключается в том, чтобы задавать набор элементов, которые разбиты на непересекающиеся (не перекрывающиеся) подмножества., чтобы быстро определить, к какому разделу принадлежит конкретный элемент.«Объединение» объединяет два непересекающихся набора вместе, чтобы сформировать больший набор, «поиск» определяет, к какому разделу принадлежит конкретный член.Идея состоит в том, что каждый раздел набора может быть идентифицирован конкретным членом набора, поэтому вы можете формировать древовидные структуры, в которых указатели указывают от элемента к элементу в направлении корня.Вы можете объединить два раздела (учитывая произвольный элемент для каждого), сначала найдя корень для каждого раздела, а затем изменив (ранее нулевой) указатель для одного корня, чтобы он указывал на другой.

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

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

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

При объединении разделов новый набор соседей для нового корня будет представлять собой набор симметричной разности (исключая или) наборов соседей для двух предыдущих корней.

Вы, вероятно, захотите сохранить другие данные по мере увеличения ваших разделов - например, размер - в каждом корневом элементе.Вы можете использовать это, чтобы быть более избирательным в отношении продолжения работы с конкретным объединением и помочь решить, когда остановиться.Может иметь значение некоторая мера рассеяния ячеек в разделе - например, небольшое отклонение или стандартное отклонение (относительно большого числа ячеек), вероятно, указывает на плотное приблизительно круглое пятно.

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

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