If the octree level is 0, then I have 8 nodes. Now, if the octree level is 1, then I have 72 nodes. But if I have (for example) 500 nodes, how do I calculate what the level would be?
To calculate the max number of nodes at level n you would calculate:
8**1 + 8**2 + 8**3 ... 8**n
So at level 2, that's 8 + 64
This can be generalized as:
((8 ** (h + 1)) - 1)/7 - 1
In javascript you might write:
function maxNodes(h){
return ((8 ** (h + 1)) - 1)/7 - 1
}
for (let i = 1; i < 4; i++){
console.log(maxNodes(i))
}To find the inverse you will need to use Log base 8 and some algebra and you'll arrive at a formula:
floor (log(base-8)(7 * n + 1))
In some languages like python you can calculate math.floor(math.log(7*n + 1, 8)), but javascript doesn't have logs to arbitrary bases so you need to depend on the identity:
Log(base-b)(n) == Log(n)/Log(b)
and calculate something like:
function height(n){
return Math.floor(Math.log(7 * n + 1)/Math.log(8))
}
console.log(height(8))
console.log(height(72)) // last on level 2
console.log(height(73)) // first on level 3
console.log(height(584)) // last on level 3
console.log(height(585)) // first on level 4