Un buon modo per generare proceduralmente un'immagine "blob" in 2D

Question

Sto cercando di creare un "blob" in modo computazionalmente veloce. Un blob qui è definito come una raccolta di pixel che potrebbe essere di qualsiasi forma, ma tutti collegati. Esempi:

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

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


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

Dove. è lo spazio morto e o è un pixel marcato. Mi interessa solo della generazione "binaria": un pixel è ON o OFF. Quindi, per esempio, questi sembrerebbero un po 'di blob immaginario di ketchup o di un batterio immaginario o di qualunque sostanza organica.

Che tipo di algoritmo potrebbe raggiungere questo? Sono davvero in perdita

Answer 1

Il commento di David Thonley è corretto, ma assumerò che tu voglia un blob con una forma "organica" e bordi lisci. Per questo è possibile utilizzare metaball. Metaballs è una funzione di potenza che funziona su un campo scalare. I campi scalari possono essere resi in modo efficiente con l'algoritmo dei cubi in marcia. Forme diverse possono essere fatte cambiando il numero di palline, le loro posizioni e il loro raggio.

Vedi qui per un'introduzione al 2D METABALLS: http://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html

E qui per un'introduzione alla algoritmo di cubetti di marcia: http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

Nota che le 256 combinazioni per gli incroci in 3D è solo 16 combinazioni in 2D . È molto facile da implementare.

EDIT:

ho messo insieme un esempio veloce con uno shader GLSL. Ecco il risultato usando 50 blob, con la funzione energetica dalla homepage di hkankaan.

Questo è il codice GLSL effettivo, sebbene valuti questo frammento. Non sto usando l'algoritmo dei cubi marching. È necessario rendere un quad a schermo intero per farlo funzionare (due triangoli). L'array uniforme vec3 è semplicemente le posizioni 2D e i raggi dei singoli BLOB passati 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

Probabilmente potresti progettare algoritmi per fare questo che sono varianti minori di una serie di algoritmi casuali di generazione di labirinti. Ne suggerirò uno basato sul metodo union-find.

L'idea di base in unione-trova è, dato un insieme di elementi che è partizionato in sottoinsiemi disgiunti (non sovrapposti), per identificare rapidamente a quale partizione appartiene un particolare oggetto. La "unione" sta combinando insieme due insiemi disgiunti per formare un insieme più grande, il "ritrovamento" sta determinando a quale partizione appartiene un particolare membro. L'idea è che ogni partizione dell'insieme può essere identificata da un particolare membro del set, in modo da poter formare strutture ad albero in cui i puntatori puntano da un membro all'altro verso la radice. È possibile unire due partizioni (dato un membro arbitrario per ciascuna) individuando prima la radice per ogni partizione, quindi modificando il puntatore (precedentemente null) per una radice in modo che punti all'altro.

È possibile formulare il problema come un problema sindacale disgiunto. Inizialmente, ogni singola cella è una partizione a sé stante. Quello che vuoi è unire le partizioni fino a ottenere un piccolo numero di partizioni (non necessariamente due) di celle connesse. Quindi, devi semplicemente scegliere uno (possibilmente il più grande) delle partizioni e disegnarlo.

Per ogni cella, è necessario un puntatore (inizialmente nullo) per l'unione. Probabilmente avrai bisogno di un vettore bit per agire come un insieme di celle vicine. Inizialmente, ogni cella avrà un insieme delle sue quattro (o otto) celle adiacenti.

Per ogni iterazione, si sceglie una cella a caso, quindi si segue una catena di puntatori per trovare la sua radice. Nei dettagli dalla radice, trovi i suoi vicini impostati. Scegli un membro a caso da quello, quindi trova la radice per quello, per identificare una regione vicina. Esegui l'unione (punta una radice all'altra, ecc.) Per unire le due regioni. Ripeti finché non sei soddisfatto di una delle regioni.

Quando si uniscono le partizioni, il nuovo insieme di vicini per la nuova radice sarà la differenza simmetrica impostata (esclusiva o) degli insiemi vicini per le due radici precedenti.

Probabilmente vorrai mantenere altri dati man mano che cresci le tue partizioni - ad es. la dimensione - in ogni elemento radice. Puoi usare questo per essere un po 'più selettivo sull'andare avanti con un particolare sindacato e per aiutare a decidere quando fermarti. Una certa misura della dispersione delle celle in una partizione può essere rilevante - ad es. una piccola deviazione o deviazione standard (relativa a un numero elevato di cellule) probabilmente indica un denso blob approssimativamente circolare.

Al termine, è sufficiente eseguire la scansione di tutte le celle per verificare se ciascuna è una parte della partizione scelta per creare una bitmap separata.

In questo approccio, quando si sceglie casualmente una cella all'inizio di un'iterazione, c'è un forte pregiudizio verso la scelta delle partizioni più grandi. Quando si sceglie un vicino, c'è anche un pregiudizio verso la scelta di una partizione vicina più grande. Ciò significa che tendi a ottenere un blob chiaramente dominante piuttosto rapidamente.

Answer 3

Ecco un approccio in cui abbiamo prima generiamo una patata a tratti affine, e poi liscia mediante interpolazione. L'idea di interpolazione si basa sul prendere la DFT, quindi lasciare le basse frequenze come sono, riempire di zeri alle alte frequenze e prendere una DFT inversa.

Ecco il codice che richiede librerie Python solo standard:

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. 

Questo genera qualcosa di simile (i punti iniziali, e l'interpolazione):

Ecco un altro tentativo:

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

Questi hanno nodi e concavità occasionalmente. Questa è la natura di questa famiglia di blob.

Nota che SciPy ha lo scafo convesso e la FFT, quindi le funzioni di cui sopra potrebbero essere sostituite da esse.