marcelo codget octree [ the best one]

marceloOctree.js

var octantVecs = [
    [-1, -1, -1],
    [-1, -1,  1],
    [-1,  1, -1],
    [-1,  1,  1],
    [1,  -1, -1],
    [1,  -1,  1],
    [1,   1, -1],
    [1,   1,  1]
];

function vectorAdd(a, b, c){
    for(var i = 0; i<3; ++i)
        a[i] += b[i]*c;
    return a;
}

function getOctant(a, b){
    return (a[0]<b[0] ? 1 : 0)
        + (a[1]<b[1] ? 2 : 0)
        + (a[2]<b[2] ? 4 : 0);
}

function octree(radius){
    this.root = {
        position: [0,0,0],
        radius: radius
    };
}

octree.prototype.query = function(position){
    var root = this.root;
    var rootRadius = root.radius;
    var rootPos = [0, 0, 0];
    while(root){
        var octant = getOctant(rootPos, position);
        if(!root[octant])
            return;
        else if(root[octant].value)
            return root[octant].value;
        else {
            vectorAdd(rootPos, octantVecs[octant], rootRadius>>=1);
            root = root[octant];
        }
    }
}

octree.prototype.insert = function(position, value){
    var root = this.root;

    var rootRadius = root.radius;
    var rootPos = [0, 0, 0];

    while(root){
        var octant = getOctant(rootPos, position);
        if(!root[octant]){
            return root[octant] = {
                position: position,
                value: value
            };
        } else if(root[octant].value){
            var leafPos = root[octant].position;
            var leaf = root[octant].value;
            root[octant].position = null;
            root[octant].value = null;

            for(var i = 0; i<11; ++i){
                var left = getOctant(rootPos, leafPos);
                var right = getOctant(rootPos, position); 
                if(left != right){
                    root[left] = {value: leaf, position: leafPos};
                    return root[right] = {value: value, position: position};
                } else {
                    var newRoot = {};
                    root[left] = newRoot;
                    root = newRoot;

                    vectorAdd(rootPos, octantVecs[left], rootRadius>>=1);
                }
            }

            console.error("Points are either the same, or octree radius is too large");
        } else {
            vectorAdd(rootPos, octantVecs[octant], rootRadius>>=1);
            root = root[octant];
        }
    }
}

// the tests
var oct = new octree(69);
oct.insert([1, 0, 0], -1);
oct.insert([0, 0, 10], -1);
oct.insert([10, 20, 0], -1);
oct.insert([30, -40, 30], "alla");
oct.insert([-5, 33, 20], "oh my goodness gracious");
oct.insert([-5, 33.1, 20], "oh my goodness gracious2");

console.log(oct.query([-5,33.1,20]));

7

7

bruh