Good way to procedurally generate a "blob" graphic in 2D

I'm looking to create a "blob" in a computationally fast manner. A blob here is defined as a collection of pixels that could be any shape, but all connected. Examples:

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

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


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

Where . is dead space and o is a marked pixel. I only care about "binary" generation - a pixel is either ON or OFF. So for instance these would look like some imaginary blob of ketchup or fictional bacterium or whatever organic substance.

What kind o开发者_开发百科f algorithm could achieve this? I'm really at a loss

David Thonley's comment is right on, but I'm going to assume you want a blob with an 'organic' shape and smooth edges. For that you can use metaballs. Metaballs is a power function that works on a scalar field. Scalar fields can be rendered efficiently with the marching cubes algorithm. Different shapes can be made by changing the number of balls, their positions and their radius.

See here for an introduction to 2D metaballs: https://web.archive.org/web/20161018194403/https://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html

And here for an introduction to the marching cubes algorithm: https://web.archive.org/web/20120329000652/http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

Note that the 256 combinations for the intersections in 3D is only 16 combinations in 2D. It's very easy to implement.

EDIT:

I hacked together a quick example with a GLSL shader. Here is the result by using 50 blobs, with the energy function from hkankaan's homepage.

Here is the actual GLSL code, though I evaluate this per-fragment. I'm not using the marching cubes algorithm. You need to render a full-screen quad for it to work (two triangles). The vec3 uniform array is simply the 2D positions and radiuses of the individual blobs passed with 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;
}

Here's an approach where we first generate a piecewise-affine potato, and then smooth it by interpolating. The interpolation idea is based on taking the DFT, then leaving the low frequencies as they are, padding with zeros at high frequencies, and taking an inverse DFT.

Here's code requiring only standard Python libraries:

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):
    pi = 3.14
    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.

This generates something like this (the initial points, and the interpolation):

Here's another attempt:

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

These have kinks and concavities occasionally. Such is the nature of this family of blobs.

Note that SciPy has convex hull and FFT, so the above functions could be substituted by them.

You could probably design algorithms to do this that are minor variants of a range of random maze generating algorithms. I'll suggest one based on the union-find method.

The basic idea in union-find is, given a set of items that is partitioned into disjoint (non-overlapping) subsets, to identify quickly which partition a particular item belongs to. The "union" is combining two disjoint sets together to form a larger set, the "find" is determining which partition a particular member belongs to. The idea is that each partition of the set can be identified by a particular member of the set, so you can form tree structures where pointers point from member to member towards the root. You can union two partitions (given an arbitrary member for each) by first finding the root for each partition, then modifying the (previously null) pointer for one root to point to the other.

You can formulate your problem as a disjoint union problem. Initially, every individual cell is a partition of its own. What you want is to merge partitions until you get a small number of partitions (not necessarily two) of connected cells. Then, you simply choose one (possibly the largest) of the partitions and draw it.

For each cell, you will need a pointer (initially null) for the unioning. You will probably need a bit vector to act as a set of neighbouring cells. Initially, each cell will have a set of its four (or eight) adjacent cells.

For each iteration, you choose a cell at random, then follow a pointer chain to find its root. In the details from the root, you find its neighbours set. Choose a random member from that, then find the root for that, to identify a neighbouring region. Perform the union (point one root to the other, etc) to merge the two regions. Repeat until you're happy with one of the regions.

When merging partitions, the new neighbour set for the new root will be the set symmetric difference (exclusive or) of the neighbour sets for the two previous roots.

You'll probably want to maintain other data as you grow your partitions - e.g. the size - in each root element. You can use this to be a bit more selective about going ahead with a particular union, and to help decide when to stop. Some measure of the scattering of the cells in a partition may be relevant - e.g. a small deviance or standard deviation (relative to a large cell count) probably indicates a dense roughly-circular blob.

When you finish, you just scan all cells to test whether each is a part of your chosen partition to build a separate bitmap.

In this approach, when you randomly choose a cell at the start of an iteration, there's a strong bias towards choosing the larger partitions. When you choose a neighbour, there's also a bias towards choosing a larger neighbouring partition. This means you tend to get one clearly dominant blob quite quickly.