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]));

Feast on my works. Ye mighty and despair!!

Wow! Thanks for the Oc Tree Allah 2. Can You Make the Octagonapus bouding volune hirearky from brick aids 7? Would be apprediated

Ok

7

7

bruh