Blobs / Metaballs

Apart from being a fun effect to watch, the metaball algorithm can be used to render liquid droplets. Thoguh a more interesting application is to interpolate elevation or heights between given maxima. The chosen threshold is then equivalent to a slice at a certain height. If you are interested in learning more about metaballs check out Jamie Wong's excellent blog post. on which this code is based on.

The core part of the algorithm:

var _cellTypeToCorners = {
    0: [],
    1: [ "W", "S" ],
    2: [ "E", "S" ],
    3: [ "W", "E" ],
    4: [ "N", "E" ],
    5: [ "N", "W", "S", "E" ],
    6: [ "N", "S" ],
    7: [ "N", "W" ],
    8: [ "N", "W" ],
    9: [ "N", "S" ],
    10: [ "N", "E", "S", "W" ],
    11: [ "N", "E" ],
    12: [ "E", "W" ],
    13: [ "E", "S" ],
    14: [ "S", "W" ],
    15: []
};

var _cellSize = 5;
var _circles = [];

//...
_circles.push( { x: x, y: y, radius: radius, radius2: radius * radius } );
//...

function metaballs( circles, threshold, cellSize )
{
    var i = 0;
    var j = 0;
    var cells = [];
    var rows = Math.ceil( _height / cellSize );
    var cols = Math.ceil( _width / cellSize );

    for( i = 0; i <= rows; i++ )
    {
        var y = i * cellSize;

        cells.push( [] );

        for( j = 0; j <= cols; j++ )
        {
            var x = j * cellSize;

            cells[ i ].push( { sum: sum( x, y, circles ) } );
        }
    }

    // draw circles
    for( i = 0; i < circles.length; i++ )
    {
        var circle = circles[ i ];
        _context.beginPath();
        _context.arc( circle.x, circle.y, 1, 0, 2 * Math.PI );
        _context.lineWidth = 0.8;
        _context.strokeStyle = circle.color;
        _context.stroke();
    }

    // draw blobs
    _context.strokeStyle = "white";
    _context.lineWidth = 1;

    for( i = 0; i < cells.length - 1; i++ )
    {
        for( j = 0; j < cells[ i ].length - 1; j++ )
        {
            // 4 corners of the current cell
            var NW = cells[ i ][ j ].sum;
            var NE = cells[ i ][ j + 1 ].sum;
            var SW = cells[ i + 1 ][ j ].sum;
            var SE = cells[ i + 1 ][ j + 1 ].sum;

            var type =
                    ((SW > threshold) << 0) +
                    ((SE > threshold) << 1) +
                    ((NE > threshold) << 2) +
                    ((NW > threshold) << 3);

            // offset from top or left that the line intersection should be
            var N = (type & 4) == (type & 8) ? 0.5 : lerp( NW, NE, 0, 1, threshold );
            var E = (type & 2) == (type & 4) ? 0.5 : lerp( NE, SE, 0, 1, threshold );
            var S = (type & 1) == (type & 2) ? 0.5 : lerp( SW, SE, 0, 1, threshold );
            var W = (type & 1) == (type & 8) ? 0.5 : lerp( NW, SW, 0, 1, threshold );

            var compassCorners = _cellTypeToCorners[ type ];
            var compassCoords = {
                "N": [ i, j + N ],
                "W": [ i + W, j ],
                "E": [ i + E, j + 1 ],
                "S": [ i + 1, j + S ]
            };

            if( compassCorners.length === 2 )
            {
                line( compassCoords[ compassCorners[ 0 ] ], compassCoords[ compassCorners[ 1 ] ], cellSize );
            }
            else if( compassCorners.length === 4 )
            {
                line( compassCoords[ compassCorners[ 0 ] ], compassCoords[ compassCorners[ 1 ] ], cellSize );
                line( compassCoords[ compassCorners[ 2 ] ], compassCoords[ compassCorners[ 3 ] ], cellSize );
            }
        }
    }
}

function line( a, b, cellSize )
{
    var x0 = Math.floor( a[ 1 ] * cellSize );
    var y0 = Math.floor( a[ 0 ] * cellSize );
    var x1 = Math.floor( b[ 1 ] * cellSize );
    var y1 = Math.floor( b[ 0 ] * cellSize );

    _context.beginPath();
    _context.moveTo( x0, y0 );
    _context.lineTo( x1, y1 );
    _context.stroke();
}

function sum( x, y, circles )
{
    var s = 0;
    var n = circles.length;

    while( --n > -1 )
    {
        var c = circles[ n ];

        var dx = x - c.x;
        var dy = y - c.y;

        s += c.radius2 / ( dx * dx + dy * dy );
    }

    return s;
}

function lerp( ax, bx, ay, by, t )
{
    return ( ax !== bx ) ? ay + (by - ay) * (t - ax) / (bx - ax) : 0;
}