Skip to content

Instantly share code, notes, and snippets.

@deltaluca
Created February 18, 2014 08:34
Show Gist options
  • Save deltaluca/9066929 to your computer and use it in GitHub Desktop.
Save deltaluca/9066929 to your computer and use it in GitHub Desktop.
Occlusion culling minecraft 2d
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();
});
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment