Una buena forma de generar un gráfico "blob" en 2D 2D

Question

Estoy buscando crear un "blob" de manera computacionalmente rápida. Aquí, una burbuja se define como una colección de píxeles que podrían tener cualquier forma, pero todos conectados. Ejemplos:

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

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


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

Dónde. es espacio muerto y o es un pixel marcado. Solo me importa la generación "binaria": un píxel está activado o desactivado. Así que, por ejemplo, estos se verían como una mancha imaginaria de ketchup o bacteria ficticia o cualquier sustancia orgánica.

¿Qué tipo de algoritmo podría lograr esto? Estoy realmente perdido

Answer 1

El comentario de David Thonley es correcto, pero supongo que quieres un blob con una forma 'orgánica' y bordes suaves. Para eso puedes usar metaballs. Metaballs es una función de potencia que funciona en un campo escalar. Los campos escalares se pueden representar de manera eficiente con el algoritmo de cubos de marcha. Se pueden crear diferentes formas cambiando el número de bolas, sus posiciones y su radio.

Vea aquí para una introducción a 2D METABALLS: http://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html

Y aquí para una introducción al algoritmo de marching cubes: http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

Tenga en cuenta que las 256 combinaciones de las intersecciones en 3D es sólo 16 combinaciones en 2D . Es muy fácil de implementar.

EDIT:

I hackeado juntos un ejemplo rápido con un sombreado GLSL. Aquí está el resultado al usar 50 blobs, con la función de energía de la página principal de hkankaan.

Aquí está el código GLSL real, aunque lo evalúo por fragmento. No estoy usando el algoritmo de los cubos de marcha. Necesita renderizar un quad de pantalla completa para que funcione (dos triángulos). El conjunto de vectores vec3 es simplemente las posiciones 2D y los radios de los blobs individuales pasados ​​con 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

Probablemente puedas diseñar algoritmos para hacer esto que sean variantes menores de una gama de algoritmos de generación de laberintos aleatorios. Sugeriré uno basado en el método union-find.

La idea básica en union-find es, dado un conjunto de elementos que se particiona en subconjuntos disjuntos (no superpuestos), identificar rápidamente a qué partición pertenece un elemento en particular. La "unión" combina dos conjuntos disjuntos para formar un conjunto más grande, el "buscar" determina a qué partición pertenece un miembro en particular. La idea es que cada partición del conjunto pueda ser identificada por un miembro particular del conjunto, de modo que pueda formar estructuras de árbol donde los punteros apuntan de miembro a miembro hacia la raíz. Puede unir dos particiones (dado un miembro arbitrario para cada una) encontrando primero la raíz para cada partición, luego modificando el puntero (previamente nulo) para que una raíz apunte a la otra.

Puede formular su problema como un problema de unión disjunta. Inicialmente, cada celda individual es una partición propia. Lo que quiere es fusionar particiones hasta que obtenga una pequeña cantidad de particiones (no necesariamente dos) de celdas conectadas. Luego, simplemente elige una (posiblemente la más grande) de las particiones y la dibuja.

Para cada celda, necesitará un puntero (inicialmente nulo) para la unión. Probablemente necesitará un vector de bits para actuar como un conjunto de celdas vecinas. Inicialmente, cada celda tendrá un conjunto de sus cuatro (u ocho) celdas adyacentes.

Para cada iteración, elige una celda al azar, luego sigue una cadena de punteros para encontrar su raíz. En los detalles de la raíz, encuentras sus vecinos establecidos. Elija un miembro aleatorio a partir de eso, luego encuentre la raíz para eso, para identificar una región vecina. Realice la unión (señale una raíz a la otra, etc.) para unir las dos regiones. Repita hasta que esté satisfecho con una de las regiones.

Al fusionar particiones, el nuevo conjunto vecino para la nueva raíz será la diferencia simétrica establecida (exclusiva o) de los conjuntos vecinos para las dos raíces anteriores.

Es probable que desee mantener otros datos a medida que vaya ampliando sus particiones, p. el tamaño - en cada elemento raíz. Puede usar esto para ser un poco más selectivo sobre seguir adelante con una unión en particular y ayudar a decidir cuándo detenerse. Alguna medida de la dispersión de las celdas en una partición puede ser relevante, por ej. una pequeña desviación o desviación estándar (en relación con un recuento de células grandes) probablemente indica una mancha densamente circular.

Cuando termine, simplemente escanee todas las celdas para probar si cada una es parte de la partición elegida para construir un mapa de bits separado.

En este enfoque, cuando elige al azar una celda al comienzo de una iteración, hay un fuerte sesgo hacia la elección de las particiones más grandes. Cuando elige un vecino, también hay un sesgo hacia la elección de una partición vecina más grande. Esto significa que usted tiende a obtener una mancha claramente dominante bastante rápido.

Answer 3

Aquí es un enfoque en el primero generamos una patata a trozos afín, y luego alisarlo por interpolación. La idea de interpolación se basa en tomar el DFT, luego dejar las frecuencias bajas tal como están, rellenar con ceros a altas frecuencias y tomar un DFT inverso.

Aquí está el código que requiere bibliotecas Python único estándar:

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. 

Esto genera algo como esto (los puntos iniciales, y la interpolación):

Aquí hay otro intento:

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)] 

Estos tienen dobleces y concavidades de vez en cuando. Tal es la naturaleza de esta familia de blobs.

Tenga en cuenta que SciPy tiene casco convexo y FFT, por lo que las funciones anteriores podrían ser sustituidas por ellos.