Simple BSP Compiler

bsp.js

var dot = function(x1, y1, x2, y2) {
    return x1 * x2 + y1 * y2;
};

var Plane = function(x, y, d) {
    this.x = x;
    this.y = y;
    this.d = d;
};

Plane.prototype.distance = function(x, y) {
    return dot(x, y, this.x, this.y) + this.d;
};

Plane.prototype.print = function() {
    print("[" + this.x + "," + this.y + "," + this.d + "]");
};

var Line = function(x1, y1, x2, y2) {
    this.c = color(random(255), random(255), random(255));
    this.x1 = x1;
    this.y1 = y1;
    this.x2 = x2;
    this.y2 = y2;
};

Line.prototype.draw = function() {
    stroke(this.c);
    line(this.x1, this.y1, this.x2, this.y2);
};

Line.prototype.createPlane = function() {
    /**
     * Output: plane
     * Returns the plane of the line.
     **/
    var normal = [this.y1 - this.y2, this.x2 - this.x1];
    var len = dist(0, 0, normal[0], normal[1]);
    normal[0] /= len;
    normal[1] /= len;

    var distance = dot(normal[0], normal[1], this.x1, this.y1);

    return new Plane(normal[0], normal[1], -distance);
};

Line.prototype.split = function(plane) {
    /**
     * Input: plane
     * 
     * Output: [front line, back line]
     * Note that either line may be null.
     **/
    var d1 = plane.distance(this.x1, this.y1);
    var d2 = plane.distance(this.x2, this.y2);
    if(d1 === 0) {
        d1 = 0.0001;
    }
    if(d2 === 0) {
        d2 = 0.0001;
    }
    if(d1 > 0 && d2 > 0) {
        return [this, null];
    }
    if(d1 < 0 && d2 < 0) {
        return [null, this];
    }
    var intersection = -d1 / dot(this.x2 - this.x1, this.y2 - this.y1, plane.x, plane.y);
    var intersectionX = lerp(this.x1, this.x2, intersection);
    var intersectionY = lerp(this.y1, this.y2, intersection);
    if(d1 > 0) {
        return [new Line(this.x1, this.y1, intersectionX, intersectionY), new Line(this.x2, this.y2, intersectionX, intersectionY)];
    } else {
        return [new Line(this.x2, this.y2, intersectionX, intersectionY), new Line(this.x1, this.y1, intersectionX, intersectionY)];
    }
};

Line.prototype.print = function() {
    print("new Line(" + this.x1 + "," + this.y1 + "," + this.x2 + "," + this.y2 + ")");
};

Line.prototype.distance = function(x, y) {
    var plane = this.createPlane();
    var planeDistance = plane.distance(x, y);
    var v1d = dist(this.x1, this.y1, x, y);
    var v2d = dist(this.x2, this.y2, x, y);
    return abs(planeDistance) + min(v1d, v2d);
};

var BSP = function(lines) {
    this.plane = lines[0].createPlane();
    this.line = lines[0];
    this.front = null;
    this.back = null;
    if(lines.length > 1) {
        var frontLines = [];
        var backLines = [];
        for(var i = 1; i < lines.length; i++) {
            var splitted = lines[i].split(this.plane);
            if(splitted[0] !== null) {
                frontLines.push(splitted[0]);
            }
            if(splitted[1] !== null) {
                backLines.push(splitted[1]);
            }
        }
        if(frontLines.length > 0) {
            this.front = new BSP(frontLines);
        }
        if(backLines.length > 0) {
            this.back = new BSP(backLines);
        }
    }
};

BSP.prototype.draw = function(x, y) {
    var front = this.front;
    var back = this.back;
    if(this.plane.distance(x, y) < 0) {
        front = this.back;
        back = this.front;
    }
    if(front !== null) {
        front.draw(x, y);
    }
    this.line.draw();
    if(back !== null) {
        back.draw(x, y);
    }
};

BSP.prototype.print = function() {
    print("{plane:");
    this.plane.print();
    print(",line:");
    this.line.print();
    if(this.front !== null) {
        print(",front:");
        this.front.print();
    }
    if(this.back !== null) {
        print(",back:");
        this.back.print();
    }
    print("}");
};