nape.geom.MarchingSquares

Iso-surface extraction into polygons.

This class, with only one static method provides an interface to an algorithm which will, when given a function mapping each point in a given AABB to a scalar value extract approximated polygons which represent the region of the AABB where the function returns a negative value.

This function could be a mathematical function like the equation of a circle: function (x, y) return (x*x + y*y) - r*r
Or something more practical like the biased alpha value interpolated from a Bitmap:

function (x, y) {
   var ix = if (x < 0) 0 else if (x >= bitmap.width - 1) bitmap.width - 2 else Std.int(x);
   var iy = if (y < 0) 0 else if (y >= bitmap.height - 1) bitmap.height - 2 else Std.int(y);
   var fx = x - ix;
   var fy = y - iy;
   var gx = 1 - fx;
   var gy = 1 - fy;

   var a00 = bitmap.getPixel32(ix, iy) >>> 24;
   var a01 = bitmap.getPixel32(ix, iy + 1) >>> 24;
   var a10 = bitmap.getPixel32(ix + 1, iy) >>> 24;
   var a11 = bitmap.getPixel32(ix + 1, iy + 1) >>> 24;

   return 0x80 - (gx*gy*a00 + fx*gy*a10 + gx*fy*a01 + fx*fy*a11);
}

For 'flash', we must wrap this in an IsoFunction interface to be used by MarchingSquares for performance reasons:

class BitmapIsoFunction implements nape.geom.IsoFunction {
    public function iso(x:Float, y:Float):Float {
        ...
    }
}

This function is converted into a set of polygons by sampling along regular grid points, and then recursively interpolating along cell edges based on the function provided to find the point in space along that edge where the function is approximately 0.

From this we generate polygons in each grid cell, which are then by default combined into larger, weakly simply polygons suitable for use in the decomposition routines of GeomPoly like convexDecomposition!

The runtime of the algorithm is O(N+K) for N number of cells and K number of output vertices (A final pass is made to remove unnecessary vertices).