Skip to content

Instantly share code, notes, and snippets.

@longde123

longde123/Main.hx

Forked from deltaluca/Main.hx
Created September 27, 2021 04:17
Show Gist options
  • Save longde123/b81693493240c2584dd5ea5a398f1f6d to your computer and use it in GitHub Desktop.
Save longde123/b81693493240c2584dd5ea5a398f1f6d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @deltaluca deltaluca created this gist Feb 18, 2014.
    476 changes: 476 additions & 0 deletions Main.hx
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,476 @@
    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();
    });
    }
    }