Buena manera de generar procesalmente un gráfico “blob” en 2D

Question

Estoy mirando para crear una "burbuja" de manera computacionalmente rápida. Un BLOB aquí se define como una colección de píxeles que podría ser 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 el espacio muerto y o es un píxel marcado. Sólo me importa generación "binario" - un píxel es SI o NO. Así, por ejemplo, éstos se vería como una burbuja imaginaria de la salsa de tomate o una bacteria ficción o cualquier sustancia orgánica.

¿Qué tipo de algoritmo podría lograr esto? Estoy realmente en una pérdida

Answer 1

El comentario de David Thonley está justo en, pero voy a suponer que desea una masa con una forma 'orgánica' y suavizar los bordes. Para que pueda utilizar metaballs. Metaballs es una función de potencia que funciona en un campo escalar. Los campos escalares pueden ser prestados de manera eficiente con el algoritmo de marching cubes. Diferentes formas se pueden realizar 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. Este es el resultado mediante el uso de 50 gotas, con la función de energía a partir de la página principal del hkankaan.

Este es el código GLSL real, aunque evalúo por este fragmento. No estoy usando el algoritmo de marching cubes. Es necesario para hacer un quad de pantalla completa para que funcione (dos triángulos). La matriz vec3 uniforme es simplemente el 2D posiciones y radios de las gotas individuales pasaron 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

Aquí hay 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 la consideración de la DFT, a continuación, dejando las frecuencias bajas como son, rellenando con ceros a altas frecuencias, y tomando una DFT inversa.

A continuación del código que requiere solamente las bibliotecas estándar de 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.

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

Este es 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 torceduras y concavidades de vez en cuando. Tal es la naturaleza de esta familia de manchas.

Nota que SciPy tiene casco convexo y FFT, por lo que las funciones anteriores podrían ser sustituidos por los mismos.

Answer 3

Probablemente se podría diseñar algoritmos para hacer esto que son variantes menores de una serie de algoritmos de generación de laberintos al azar. Voy a sugerir una basada en la unión- método.

La idea básica de unión-es, dado un conjunto de elementos que se divide en subconjuntos disjuntos (no superpuestos), para identificar rápidamente qué partición de un artículo en particular pertenece. La "unión" es la combinación de dos conjuntos disjuntos entre sí para formar un conjunto más grande, el "encontrar" es determinar qué partición un miembro en particular pertenece. La idea es que cada partición del conjunto puede ser identificado por un miembro particular del conjunto, por lo que puede formar estructuras de árbol, donde los punteros apuntan de un miembro a hacia la raíz. Puede unión de dos particiones (dado un miembro de arbitraria para cada uno) por encontrar primero la raíz de cada partición, a continuación, modificar el puntero (anteriormente nulo) de una raíz a punto al otro.

Se puede formular el problema como un problema de unión de la desunión. Inicialmente, cada célula individual es una partición de su propia. Lo que se quiere es fusionar particiones hasta obtener un pequeño número de particiones (no necesariamente dos) de las células conectadas. A continuación, sólo tiene que elegir uno (posiblemente el más grande) de las particiones y dibuja.

Para cada celda, se necesita un puntero (inicialmente nulo) para la unificante. Es probable que necesite un vector de bits para actuar como un conjunto de células vecinas. Inicialmente, cada célula tendrá un conjunto de sus cuatro (u ocho) de las células adyacentes.

Para cada iteración, se elige un celular al azar, a continuación, seguir una cadena de puntero para encontrar su raíz. En los detalles de la raíz, se encuentra establecen sus vecinos. Elegir un miembro de azar de que, a continuación, encontrar la raíz para eso, para identificar una región vecina. Realizar la unión (punto de una raíz a la otra, etc) para fusionar las dos regiones. Repita hasta que esté satisfecho con una de las regiones.

Cuando la fusión de particiones, el nuevo conjunto de vecinos de la nueva raíz será el conjunto diferencia simétrica (o exclusiva) de los conjuntos vecinos de las dos raíces anteriores.

Usted probablemente querrá mantener otros datos a medida que crecen sus particiones - por ejemplo, el tamaño - en cada elemento raíz. Usted puede usar esto para ser un poco más selectivos acerca de seguir adelante con una unión en particular, y para ayudar a decidir cuándo parar. Algunos medida de la dispersión de las células en una partición puede ser relevante - por ejemplo, una pequeña desviación o la desviación estándar (en relación con un gran número de células), probablemente indica una densa mancha más o menos circular.

Cuando termine, que acaba de escanear todas las células para probar si cada uno es una parte de su partición elegida para construir un mapa de bits independiente.

En este enfoque, cuando se elige al azar una célula en el inicio de una iteración, hay un fuerte sesgo hacia la elección de las particiones más grandes. Cuando se elige un vecino, también hay un sesgo hacia la elección de una partición vecina más grande. Esto significa que tienden a conseguir una mancha claramente dominante con bastante rapidez.