Un bon moyen de générer un graphique la procédure « blob » en 2D

Question

Je cherche à créer un « blob » de manière rapide informatiquement. Une goutte ici est défini comme un ensemble de pixels qui pourrait avoir une forme quelconque, mais tous connectés. Exemples:

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

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


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

Où. est un espace mort et o est un pixel marqué. Je me soucie seulement de la génération « binaire » - un pixel est soit ON ou OFF. Ainsi, par exemple ceux-ci ressembleraient une blob imaginaire de bactérie ketchup ou de fiction ou tout autre substance organique.

Quel type d'algorithme pourrait y parvenir? Je suis vraiment à une perte

Answer 1

Le commentaire de David Thonley est juste, mais je vais supposer que vous voulez un blob avec une forme « organique » et lisser les bords. Pour cela, vous pouvez utiliser metaballs. Metaballs est une fonction de puissance qui fonctionne sur un champ scalaire. champs scalaires peuvent être rendus efficacement avec l'algorithme de cubes de marche. Différentes formes peuvent être faites en changeant le nombre de balles, leurs positions et leur rayon.

Voir ici pour une introduction à 2D METABALLS: http: // www. niksula.hut.fi/~hkankaan/Homepages/metaballs.html

Et ici pour une introduction aux cubes de marche algorithme: http: / /local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

Notez que les 256 combinaisons pour les intersections en 3D est seulement 16 combinaisons en 2D. Il est très facile à mettre en œuvre.

EDIT:

Je piraté ensemble un exemple rapide avec un shader GLSL. Voici le résultat en utilisant 50 blobs, avec la fonction d'énergie à partir de la page d'accueil de hkankaan.

Voici le code GLSL réelle, bien que j'évalue ce par fragment. Je ne suis pas en utilisant l'algorithme de cubes de marche. Vous devez rendre un quad plein écran pour que cela fonctionne (deux triangles). La matrice uniforme vec3 est simplement les positions 2D et les rayons de gouttes individuelles transmises avec 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

Voici une approche où nous avons d'abord générons un affines par morceaux de pommes de terre, puis lisser par interpoler. L'idée d'interpolation est basée sur la prise de la TFD, puis en laissant les fréquences basses telles qu'elles sont, rembourrage avec des zéros à des fréquences élevées, et en prenant une DFT inverse.

Code de nécessite les bibliothèques Python ne standards:

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.

Cela génère quelque chose comme ça (les points initiaux, et l'interpolation):

Voici une autre tentative:

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

Ceux-ci ont Kinks et concavités de temps en temps. Telle est la nature de cette famille de blobs.

Notez que SciPy a coque convexe et FFT, de sorte que les fonctions ci-dessus peuvent être substitués par eux.

Answer 3

Vous pourriez probablement concevoir des algorithmes pour ce faire que des variantes mineures d'une gamme d'algorithmes de génération de labyrinthe aléatoire. Je suggère un basé sur le union-find méthode.

L'idée de base dans l'union-find est, étant donné un ensemble d'éléments qui est divisé en sous-ensembles disjoints (sans chevauchement), d'identifier rapidement la partition d'un élément particulier appartient. Le « union » combine deux ensembles disjoints ensemble pour former un ensemble plus large, le « trouver » est de déterminer quelle partition un membre particulier appartient. L'idée est que chaque partition de l'ensemble peut être identifié par un membre particulier de l'ensemble, de sorte que vous pouvez former des structures d'arbres où des pointeurs pointent d'un membre à vers la racine. Vous pouvez union de deux partitions (étant donné un élément arbitraire pour chacun) en trouvant d'abord la racine de chaque partition, en modifiant ensuite le pointeur pour une racine à un point (précédemment null) à l'autre.

Vous pouvez formuler votre problème comme un problème de disjointe. Dans un premier temps, chaque cellule individuelle est une partition de son propre. Ce que vous voulez est de fusionner des partitions jusqu'à ce que vous obtenez un petit nombre de partitions (pas nécessairement deux) des cellules connectées. Ensuite, vous choisissez simplement un (peut-être le plus grand) des partitions et dessiner.

Pour chaque cellule, vous aurez besoin d'un pointeur (initialement null) pour la unioning. Vous aurez probablement besoin d'un vecteur de bits pour agir comme un ensemble de cellules voisines. Dans un premier temps, chaque cellule aura un ensemble de quatre (ou huit) des cellules adjacentes.

Pour chaque itération, vous choisissez une cellule au hasard, puis suivre une chaîne de pointeur pour trouver sa racine. Dans les détails de la racine, vous trouverez ses voisins fixés. Choisissez un membre aléatoire de cela, puis trouver la racine pour que, d'identifier une région voisine. Effectuez l'union (point une racine à l'autre, etc.) pour fusionner les deux régions. Répétez jusqu'à ce que vous êtes satisfait de l'une des régions.

Lors de la fusion des partitions, le nouveau jeu de voisin pour la nouvelle racine sera l'ensemble différence symétrique (exclusive ou) des ensembles voisins pour les deux racines antérieures.

Vous aurez probablement besoin de maintenir d'autres données que vous cultivez vos partitions - par exemple la taille - dans chaque élément racine. Vous pouvez l'utiliser pour être un peu plus sélectif à aller de l'avant avec un syndicat particulier, et pour aider à décider quand arrêter. Une certaine mesure de la dispersion des cellules dans une partition peut être pertinent - par exemple, une petite déviation ou l'écart type (par rapport à un grand nombre de cellules) indique probablement une goutte plus ou moins dense circulaire.

Lorsque vous avez terminé, vous suffit de scanner toutes les cellules pour vérifier si chacun est une partie de votre partition choisie pour construire un bitmap séparé.

Dans cette approche, lorsque vous choisissez au hasard une cellule au début d'une itération, il y a une forte tendance à choisir les partitions plus grandes. Lorsque vous choisissez un voisin, il y a aussi un biais vers le choix d'une partition voisine plus grande. Cela signifie que vous ont tendance à obtenir un blob clairement dominant assez rapidement.