The set function involves doing the same, except an array of all previous offsets areneed to be recorded, so that if a branch is inserted or deleted in the middle of the tree, the indices in parent branches can be updated when the memory is shift to make more space or to fill the gap.
typedef struct Octree {
Ptr data; // Definition of Ptr and Node8 are not relevant to this question
uint8_t data_alloc, set_alloc;
uint16_t data_size, set_size, base;
Node8 set[];
} Octree;
static uint_fast8_t octree_index(const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y, const uint_fast8_t level) {
return (x>>level&1)|(z>>level&1)<<1|(y>>level&1)<<2;
}
uint16_t octree_get(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) { // Gets the value at a certain position in the octree
uint_fast16_t set = 0;
uint_fast8_t level = 5;
uint16_t node = octree->base;
while (node&0x8000 && level--)
node = ((uint16_t *)octree->set)[(set += node&0x7FFF)<<3|octree_index(x, y, z, level)];
return node;
}
Octree *octree_set(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y, const uint16_t new) { // Gets the value at a certain position in the octree
uint_fast16_t set = 0, stack[5]; // Note the new `stack` variable
uint_fast8_t level = 5;
uint16_t node = octree->base;
while (node&0x8000 && level--)
node = ((uint16_t *)octree->set)[stack[level] = (set += node&0x7FFF)<<3|octree_index(x, y, z, level)];
// The only difference in the above line is the `stack[level] = ` before `(set += ...`
if (node != new) {
if (level) {
// Subdivide and insert
} else {
// Set and merge if necessary
}
}
return octree;
}
typedef struct Stack {
uint16_t node;
uint_fast8_t level;
uint_fast16_t offset[5];
} Stack;
Stack octree_get(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) {
uint_fast16_t set = 0;
Stack stack = {octree->base, 5};
while (stack.node&0x8000 && stack.level--)
stack.node = ((uint16_t *)octree->set)[stack.offset[stack.level] = (set += stack.node&0x7FFF)<<3|octree_index(x, y, z, stack.level)];
return stack;
} // Returning a struct in and of itself may or may not be optimal but that is arguably a separate question
Octree *octree_set(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y, const uint16_t new) {
Stack stack = octree_get(octree, x, y, z);
if (stack.node != new) {
if (stack.level) {
// Subdivide and insert
} else {
// Set and merge if necessary
}
}
return octree;
}
