Skip to content

Instantly share code, notes, and snippets.

@ALLAH-2
Last active June 18, 2023 03:03
Show Gist options
  • Save ALLAH-2/0d7fa750da019b785bc18165cea6628d to your computer and use it in GitHub Desktop.
Save ALLAH-2/0d7fa750da019b785bc18165cea6628d to your computer and use it in GitHub Desktop.
marcelo codget octree [ the best one]
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]));
@Nobonet
Copy link

Nobonet commented Jun 9, 2023

7

@ALLAH-2
Copy link
Author

ALLAH-2 commented Jun 18, 2023

7

bruh

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment