Occlusion culling minecraft 2d

Main.hx

import nape.util.BitmapDebug;
import nape.geom.Vec2;

class Perlin3D {
    public static inline function noise(x:Float, y:Float = 0.0, z:Float = 0.0) {
        var X:Int = untyped __int__(x); x -= X; X &= 0xff;
        var Y:Int = untyped __int__(y); y -= Y; Y &= 0xff;
        var Z:Int = untyped __int__(z); z -= Z; Z &= 0xff;
        var u = fade(x); var v = fade(y); var w = fade(z);
        var A = p(X)  +Y; var AA = p(A)+Z; var AB = p(A+1)+Z;
        var B = p(X+1)+Y; var BA = p(B)+Z; var BB = p(B+1)+Z;
        return lerp(w, lerp(v, lerp(u, grad(p(AA  ), x  , y  , z   ),
                                       grad(p(BA  ), x-1, y  , z   )),
                               lerp(u, grad(p(AB  ), x  , y-1, z   ),
                                       grad(p(BB  ), x-1, y-1, z   ))),
                       lerp(v, lerp(u, grad(p(AA+1), x  , y  , z-1 ),
                                       grad(p(BA+1), x-1, y  , z-1 )),
                               lerp(u, grad(p(AB+1), x  , y-1, z-1 ),
                                       grad(p(BB+1), x-1, y-1, z-1 ))));
    }

    static inline function fade(t:Float) return t*t*t*(t*(t*6-15)+10);
    static inline function lerp(t:Float, a:Float, b:Float) return a + t*(b-a);
    static inline function grad(hash:Int, x:Float, y:Float, z:Float) {
        var h = hash&15;
        var u = h<8 ? x : y;
        var v = h<4 ? y : h==12||h==14 ? x : z;
        return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
    }

    static inline function p(i:Int) return perm[i];

    static var perm: haxe.ds.Vector<Int>;
    public static function initNoise() {
        perm = new haxe.ds.Vector<Int>(512);
        var p = [151,160,137,91,90,15,
            131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
            190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
            88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
            77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
            102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
            135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
            5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
            223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
            129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
            251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
            49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
            138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180];
        for(i in 0...256) {
            perm[i]     = p[i];
            perm[256+i] = p[i];
        }
    }
}

typedef Plane = Array<Float>;
typedef AABB = Array<Float>;

typedef Occluder = {
    aabb: AABB,
    distance: Float
};
enum Tree {
    ACell(aabb:AABB, l0: Null<Tree>, l1: Null<Tree>, l2: Null<Tree>, l3: Null<Tree>);
    ALeaf(aabb:AABB, v:Occluder);
}

class Main {
    static function main() {
        Perlin3D.initNoise();

        var perlinScale = 0.01;
        var threshold = 0.0;
        var dim = 16;
        var sw = 1024;
        var sh = 768;
        var w = Math.floor(sw / dim);
        var h = Math.floor(sh / dim);
        var chunks = [for (y in 0...h) for (x in 0...w) {
            var data = [for (j in 0...dim) for (i in 0...dim) {
                Perlin3D.noise((x * dim + i) * perlinScale,
                               (y * dim + j) * perlinScale,
                               1.5) < threshold;
            }];
            var opaque = [true, true, true, true]; // x+ x-, y+, y-
            for (i in 0...dim) {
                opaque[0] = opaque[0] && data[i * dim + (dim - 1)];
                opaque[1] = opaque[1] && data[i * dim];
                opaque[2] = opaque[2] && data[i + (dim - 1) * dim];
                opaque[3] = opaque[3] && data[i];
            }
            {
                opaque: opaque,
                data: data
            };
        }];

        var map = new flash.display.BitmapData(sw, sh, false, 0xffffff);
        for (y in 0...sh) for (x in 0...sw) {
            var chunkX = Std.int(x / dim);
            var chunkY = Std.int(y / dim);
            var blockX = x % dim;
            var blockY = y % dim;
            var chunk = chunks[chunkY * w + chunkX];
            if (chunk.data[blockY * dim + blockX])
                 map.setPixel(x, y, (chunkX + chunkY) % 2 == 0 ? 0xa0a0a0 : 0xb0b0b0);
            else map.setPixel(x, y, 0xffffff);

            if (blockX == (dim - 1) && chunk.opaque[0]) map.setPixel(x, y, 0xff8888);
            if (blockX == 0         && chunk.opaque[1]) map.setPixel(x, y, 0x88ffff);
            if (blockY == (dim - 1) && chunk.opaque[2]) map.setPixel(x, y, 0x88ff88);
            if (blockY == 0         && chunk.opaque[3]) map.setPixel(x, y, 0xff88ff);
        }
        var bit;
        flash.Lib.current.addChild(bit = new flash.display.Bitmap(map));
        bit.alpha = 0.5;

        var debug = new BitmapDebug(sw, sh, 0xffffff, true);
        flash.Lib.current.addChild(debug.display);

        function plane(u:Vec2, v:Vec2):Plane {
            var a = (v.y - u.y);
            var b = (u.x - v.x);
            var c = -(a * u.x + b * u.y);
            return [a, b, c];
        }

        function inside(v:Vec2, p:Plane) {
            return v.x * p[0] + v.y * p[1] + p[2] >= 0;
        }

        function aabbInside(aabb:AABB, frustum:Array<Plane>) {
            for (p in frustum) {
                if ((p[0] * (p[0] < 0 ? aabb[0] : aabb[2]) +
                     p[1] * (p[1] < 0 ? aabb[1] : aabb[3])) + p[2] < 0) {
                    return false;
                }
            }
            return true;
        }

        function clipAABB(aabb:AABB, frustum:Array<Plane>) {
            // check for each edge (face in 3d) of AABB, how far along the axis
            // can move 'all' points so that AABB is minimal, but covers the area of
            // aabb intersecting frustum.
            function clipX(i, p:Plane) {
                if (p[0] == 0) return;

                var d1 = p[0] * aabb[i] + p[1] * aabb[1] + p[2];
                var d2 = p[0] * aabb[i] + p[1] * aabb[3] + p[2];
                if (d1 < 0 && d2 < 0) { // can clip
                    var n0 = (-p[2] - p[1]*aabb[1]) / p[0] - aabb[i];
                    var n1 = (-p[2] - p[1]*aabb[3]) / p[0] - aabb[i];
                    var n = (n0 * n0 < n1 * n1 ? n0 : n1);
                    aabb[i] += n;
                }
            }
            function clipY(i, p:Plane) {
                if (p[1] == 0) return;

                var d1 = p[0] * aabb[0] + p[1] * aabb[i] + p[2];
                var d2 = p[0] * aabb[2] + p[1] * aabb[i] + p[2];
                if (d1 < 0 && d2 < 0) { // can clip
                    var n0 = (-p[2] - p[0]*aabb[0]) / p[1] - aabb[i];
                    var n1 = (-p[2] - p[0]*aabb[2]) / p[1] - aabb[i];
                    var n = (n0 * n0 < n1 * n1 ? n0 : n1);
                    aabb[i] += n;
                }
            }
            for (p in frustum) {
                clipX(0, p);
                clipX(2, p);
                clipY(1, p);
                clipY(3, p);
            }
        }

        function aabbTotallyInside(aabb:AABB, frustum:Array<Plane>) {
            for (p in frustum) {
                if ((p[0] * (p[0] > 0 ? aabb[0] : aabb[2]) +
                     p[1] * (p[1] > 0 ? aabb[1] : aabb[3])) + p[2] < 0) {
                    return false;
                }
            }
            return true;
        }

        // assumption made for this application, that y is 'smaller' than x in all cases
        function aabbContains(x:AABB, y:AABB) {
            return y[0] >= x[0] && y[1] >= x[1] && y[2] <= x[2] && y[3] <= x[3];
        }

        function drawFrustum(frustum:Array<Plane>, colour:Int) {
            function intersect(a: Plane, b: Plane) {
                var det = a[0] * b[1] - a[1] * b[0];
                if (det == 0) return null;
                var invDet = 1 / det;
                return Vec2.get(
                    (a[1]*b[2] - a[2]*b[1]) * invDet,
                    (a[2]*b[0] - a[0]*b[2]) * invDet
                );
            }

            for (p in frustum) {
                var list = [];

                var p0, p1;
                if (p[1] != 0) {
                    var y0 = -p[2]/p[1];
                    var y1 = (-p[2]-p[0]*sw)/p[1];
                    p0 = Vec2.get(0, y0);
                    p1 = Vec2.get(sw, y1);
                }
                else {
                    var x0 = -p[2]/p[0];
                    var x1 = (-p[2]-p[1]*sh)/p[0];
                    p0 = Vec2.get(x0, 0);
                    p1 = Vec2.get(x1, sh);
                }

                for (q in frustum) if (p != q) {
                    if (p0 != null && !inside(p0, q)) {
                        p0 = null;
                    }
                    if (p1 != null && !inside(p1, q)) {
                        p1 = null;
                    }
                    var int = intersect(p, q);
                    if (int != null) {
                        for (r in frustum) if (r != p && r != q) {
                            if (!inside(int, r)) {
                                int = null;
                                break;
                            }
                        }
                    }
                    if (int != null) {
                        list.push(int);
                    }
                }
                if (p0 != null) {
                    list.push(p0);
                }
                if (p1 != null) {
                    list.push(p1);
                }
                list.sort(function (a, b) {
                    var del = (a.x * p[1] - a.y * p[0]) - (b.x * p[1] - b.y * p[0]);
                    return del < 0 ? -1 : del > 0 ? 1 : 0;
                });
                debug.drawLine(list[0], list[list.length - 1], colour);
            }
        }

        function napeAABB(aabb:AABB) {
            return new nape.geom.AABB(aabb[0], aabb[1], aabb[2] - aabb[0], aabb[3] - aabb[1]);
        }

        function shadowFrustum(aabb:AABB, focus:Vec2):Array<Plane> {
            // voronoi region check, probably slower for 3d and missing a trick here.
            var p0, p1;
            if (focus.x < aabb[0] && focus.y < aabb[1]) {
                p0 = Vec2.get(aabb[2], aabb[1]);
                p1 = Vec2.get(aabb[0], aabb[3]);
            }
            else if (focus.x < aabb[0] && focus.y > aabb[3]) {
                p0 = Vec2.get(aabb[0], aabb[1]);
                p1 = Vec2.get(aabb[2], aabb[3]);
            }
            else if (focus.x > aabb[2] && focus.y < aabb[1]) {
                p0 = Vec2.get(aabb[2], aabb[3]);
                p1 = Vec2.get(aabb[0], aabb[1]);
            }
            else if (focus.x > aabb[2] && focus.y > aabb[3]) {
                p0 = Vec2.get(aabb[0], aabb[3]);
                p1 = Vec2.get(aabb[2], aabb[1]);
            }
            else if (focus.x < aabb[0]) {
                p0 = Vec2.get(aabb[0], aabb[1]);
                p1 = Vec2.get(aabb[0], aabb[3]);
            }
            else if (focus.x > aabb[2]) {
                p0 = Vec2.get(aabb[2], aabb[3]);
                p1 = Vec2.get(aabb[2], aabb[1]);
            }
            else if (focus.y < aabb[1]) {
                p0 = Vec2.get(aabb[2], aabb[1]);
                p1 = Vec2.get(aabb[0], aabb[1]);
            }
            else {
                p0 = Vec2.get(aabb[0], aabb[3]);
                p1 = Vec2.get(aabb[2], aabb[3]);
            }
            return [
                plane(p0, focus),
                plane(p0, p1),
                plane(focus, p1)
            ];
        }

        function chunkAABB(x, y):AABB {
            return [ x * dim, y * dim, (x + 1) * dim, (y + 1) * dim ];
        }

        var previousCamera:Vec2 = null;
        flash.Lib.current.stage.addEventListener(flash.events.MouseEvent.MOUSE_MOVE, function (_) {
            debug.clear();

            var camera = Vec2.get(flash.Lib.current.mouseX, flash.Lib.current.mouseY);
            if (previousCamera == null) {
                previousCamera = Vec2.get();
                previousCamera.set(camera);
                return;
            }

            var direction = camera.sub(previousCamera);
            previousCamera.addeq(camera.sub(previousCamera).muleq(0.04));
            if (direction.lsq() == 0 || direction.x == 0 || direction.y == 0) {
                return;
            }
            direction.length = 1;

            var fov = 70;
            var cameraFrustum = [];
            direction.angle -= fov / 2;
            cameraFrustum.push(plane(camera, camera.add(direction)));
            direction.angle += fov;
            cameraFrustum.push(plane(camera.add(direction), camera));
            direction.angle -= fov / 2;
            cameraFrustum.push(plane(
                camera.add(direction.mul(20)),
                camera.add(direction.perp()).add(direction.mul(20))));
            cameraFrustum.push(plane(
                camera.add(direction.perp()).add(direction.mul(400)),
                camera.add(direction.mul(400))));

            debug.drawCircle(camera, 2, 0xff0000);
            drawFrustum(cameraFrustum, 0xff0000);

            var visible = []; // list
            var occluders = []; // full xy
            for (y in 0...h) for (x in 0...w) {
                var chunk = chunks[y * w + x];
                var aabb = chunkAABB(x, y);
                if (aabbInside(aabb, cameraFrustum)) {
                    var orig = [aabb[0], aabb[1], aabb[2], aabb[3]];
                    clipAABB(aabb, cameraFrustum);
                    var v;
                    var occluder = true;
                    if (camera.x < aabb[0]) {
                        occluder = occluder && chunk.opaque[1];
                    }
                    if (camera.x > aabb[2]) {
                        occluder = occluder && chunk.opaque[0];
                    }
                    if (camera.y < aabb[1]) {
                        occluder = occluder && chunk.opaque[3];
                    }
                    if (camera.y > aabb[3]) {
                        occluder = occluder && chunk.opaque[2];
                    }
                    if (occluder)
                        occluders.push({
                            aabb: aabb,
                            distance: Math.pow(camera.x - (aabb[0] + aabb[2]) / 2, 2) +
                                      Math.pow(camera.y - (aabb[1] + aabb[3]) / 2, 2)
                        });
                    else
                        occluders.push(null);
                    visible.push({
                        aabb: aabb,
                        orig: orig,
                        renderable: true
                    });
                }
                else
                {
                    occluders.push(null);
                }
            }


            // Iterative combiner
            // Start at occluder closest to camera, and expand out from camera to find largest occluding rectangle
            // occluder does not have to be a covering, it can expand out into non-occluder territory as long as
            // such territory is hidden from the camera already.
            var ocs = [];
            for (o in occluders) if (o != null) ocs.push(o);
            ocs.sort(function (a, b) return a.distance < b.distance ? -1 : 1);

            var occ = [];
            while (ocs.length != 0) {
                var seed = ocs.shift().aabb;
                var x0 = Std.int((seed[0] + seed[2]) / (2 * dim));
                var y0 = Std.int((seed[1] + seed[3]) / (2 * dim));
                if (occluders[y0 * w + x0] == null) continue;

                var x1 = x0;
                var y1 = y0;
                // determine directions we should try and expand to given resultant frustum
                if (camera.x < seed[0] && camera.y < seed[1]) {
                    // search +x +y
                    while (x1 < w-1 && occluders[y0 * w + x1 + 1] != null) x1++;
                    while (y1 < h-1 && occluders[(y1 + 1) * w + x0] != null) y1++;
                }
                else if (camera.x < seed[0] && camera.y > seed[3]) {
                    // search +x -y
                    while (x1 < w-1 && occluders[y0 * w + x1 + 1] != null) x1++;
                    while (y0 > 0 && occluders[(y0 - 1) * w + x0] != null) y0--;
                }
                else if (camera.x > seed[2] && camera.y < seed[1]) {
                    // search -x +y
                    while (x0 > 0 && occluders[y0 * w + x0 - 1] != null) x0--;
                    while (y1 < h-1 && occluders[(y1 + 1) * w + x1] != null) y1++;
                }
                else if (camera.x > seed[2] && camera.y > seed[3]) {
                    // search -x -y
                    while (x0 > 0 && occluders[y0 * w + x0 - 1] != null) x0--;
                    while (y0 > 0 && occluders[(y0 - 1) * w + x1] != null) y0--;
                }
                else if (camera.x < seed[0] || camera.x > seed[2]) {
                    // search +-y
                    while (y0 > 0 && occluders[(y0 - 1) * w + x0] != null) y0--;
                    while (y1 < h-1 && occluders[(y1 + 1) * w + x1] != null) y1++;
                }
                else {
                    // search +-x
                    while (x0 > 0 && occluders[y0 * w + x0 - 1] != null) x0--;
                    while (x1 < w-1 && occluders[y0 * w + x1 + 1] != null) x1++;
                }
                occ.push({
                    aabb: ([x0 * dim, y0 * dim, x1 * dim + dim, y1 * dim + dim] : Array<Float>)
                });
                for (y in y0...y1+1) {
                    for (x in x0...x1+1) {
                        occluders[y * w + x] = null;
                    }
                }
            }

            var ocs = occ;
            for (k in 0...ocs.length) {
                var v = ocs[k];
                ocs[k] = null;
                if (v == null) continue;
                var frustum = shadowFrustum(v.aabb, camera);
                debug.drawAABB(napeAABB(v.aabb), 0xff00ff);
                var i = 0;
                while (i < visible.length) {
                    var q = visible[i];
                    if (aabbContains(v.aabb, q.aabb) || aabbTotallyInside(q.aabb, frustum)) {
                        q.renderable = false;
                        visible[i] = visible[visible.length - 1];
                        visible.pop();
                    }
                    else {
                        i++;
                    }
                }
                for (i in 0...ocs.length) {
                    if (ocs[i] != null && ocs[i] != v && aabbTotallyInside(ocs[i].aabb, frustum)) {
                        ocs[i] = null;
                    }
                }
            }

            for (v in visible) {
                if (v.renderable) {
                    debug.drawAABB(napeAABB([v.orig[0]+1,v.orig[1]+1,v.orig[2]-1,v.orig[3]-1]), 0xff0000);
                }
            }

            debug.flush();
        });
    }
}