I have been attempting to implement a voxel octree for a game, and this issue has completely stumped me.
My octree is stored linearly as a hashmap of octree indices and nodes (see "Implicit node representations" under https://geidav.wordpress.com/2014/08/18/advanced-octrees-2-node-representations/). In my insert function, I add the node to the hashmap, and then I recursively split parent nodes until the voxel to be inserted fits in the octree, generating the seven other nodes with the parent's voxel type. If there is no direct parent, I recursively make new parents.
A quick rundown of the octree indexing system I'm using: for each level of the octree, three bits are appended to determine the position relative to the parent node. The very root node is of index 1, which allows for the depth of any subtree to be computed.
Somehow, the voxel to be inserted gets added to the hashmap twice, as well as the other 7 on the same level, and that overwrites the voxel with the wrong type.
My main function is as follows:
fn main() {
let mut octree = Octree::new(Voxel::Air);
octree.insert(0b1010110, Voxel::Dirt);
}
and it outputs:
inserted at 1010110: Leaf(Dirt)
inserted at 1010: Leaf(Air)
inserted at 1000: Leaf(Air)
inserted at 1001: Leaf(Air)
inserted at 1011: Leaf(Air)
inserted at 1100: Leaf(Air)
inserted at 1101: Leaf(Air)
inserted at 1110: Leaf(Air)
inserted at 1111: Leaf(Air)
inserted at 1010000: Leaf(Air)
inserted at 1010001: Leaf(Air)
inserted at 1010010: Leaf(Air)
inserted at 1010011: Leaf(Air)
inserted at 1010100: Leaf(Air)
inserted at 1010101: Leaf(Air)
inserted at 1010110: Leaf(Air) // duplicate
inserted at 1010111: Leaf(Air)
inserted at 1010001: Leaf(Air) // duplicate
inserted at 1010010: Leaf(Air) // duplicate
inserted at 1010011: Leaf(Air) // duplicate
inserted at 1010100: Leaf(Air) // duplicate
inserted at 1010101: Leaf(Air) // no 1010110 duplicate here (my if-condition at least works here)
inserted at 1010111: Leaf(Air) // duplicate
Below is all the octree implementation code (copy + paste to replicate):
use std::collections::HashMap;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
#[repr(u16)]
pub enum Voxel {
#[default]
Air,
Stone,
Dirt,
Grass,
}
// max depth: 5 (log2(1_xyz_xyz_x-yz_xyz_xyz) / 3)
pub type OctreeIndex = u16;
#[derive(Clone, Debug)]
pub struct Octree {
pub nodes: HashMap<OctreeIndex, OctreeNode>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct OctreeNode {
pub index: OctreeIndex,
pub data: Option<Voxel>, // Some = leaf, None = branch
}
impl Octree {
pub fn new(voxel: Voxel) -> Self {
let mut octree = Self {
nodes: HashMap::new(),
};
let node = OctreeNode {
index: 1,
data: Some(voxel),
};
octree.nodes.insert(1, node);
octree
}
pub fn insert(&mut self, index: OctreeIndex, voxel: Voxel) -> OctreeNode {
let node = OctreeNode {
index,
data: Some(voxel),
};
self.nodes.insert(index, node);
println!("inserted at {:b}: {:?}", index, self.nodes[&index].data);
let parent = match self.get_parent_node_mut(&node) {
Some(parent) => parent,
None if index != 1 => &mut self.insert(index >> 3, self.get_closest_voxel(&node, 0)),
None => return node,
};
let p_index = parent.index;
if let Some(v) = parent.data {
parent.data = None;
for i in 0..8 {
let current_index = (p_index << 3) + i;
if i != index - (p_index << 3) {
self.insert(current_index, v);
}
}
}
node
}
pub fn get_closest_voxel(&self, node: &OctreeNode, depth: u8) -> Voxel {
match self.nodes[&(node.index >> ((node.get_depth() - depth) * 3))].data {
Some(v) => v,
None => self.get_closest_voxel(node, depth + 1),
}
}
pub fn get_parent_node_mut(&mut self, node: &OctreeNode) -> Option<&mut OctreeNode> {
self.nodes.get_mut(&(node.index >> 3))
}
}
impl OctreeNode {
fn get_depth(&self) -> u8 {
(self.index as f32).log2() as u8 / 3
}
}
I tried moving around the hashmap insertion point, I tried to alter the condition for generating nodes, but nothing prevented the duplication. Most of the time was honestly spent trying to even conceptualize what was going on.
If there is something completely outrageous about the way that I implemented this, please let me know (anything to improve the surely atrocious runtime complexity).
Using
&mut self.insert(index >> 3, self.get_closest_voxel(&node, 0))
as parent is wrong, the intention seems to be able to mutate the parent node that is in the HashMap. But you're not mutating the real, inserted parent with it, instead you're mutating the copy that insert returned.
So the data of the real parent within the HashMap is never set to None to begin with and that causes a duplicate insertion of nodes because if let Some(v) = parent.data { still matches.
It's often problematic to take references of parts of self, like node: &OctreeNode in
fn get_closest_voxel(&self, node: &OctreeNode, depth: u8)
and often also the one in get_parent_node_mut. Instead I recommend you switch to indices:
impl Octree {
pub fn new(voxel: Voxel) -> Self {
let mut octree = Self {
nodes: HashMap::new(),
};
let node = OctreeNode {
index: 1,
data: Some(voxel),
};
octree.nodes.insert(1, node);
octree
}
pub fn insert(&mut self, index: OctreeIndex, voxel: Voxel) -> OctreeIndex {
let node = OctreeNode {
index,
data: Some(voxel),
};
self.nodes.insert(index, node);
eprintln!("inserted at {:b}: {:?}", index, self.nodes[&index].data);
let parent_index = match self.get_parent_node_mut(index) {
Some(parent) => parent.index,
None if index != 1 => self.insert(index >> 3, self.get_closest_voxel(index, 0)),
None => return index,
};
if let Some(v) = self.nodes[&parent_index].data {
self.nodes.get_mut(&parent_index).unwrap().data = None;
for i in 0..8 {
let current_index = (parent_index << 3) + i;
if i != index - (parent_index << 3) {
self.insert(current_index, v);
}
}
}
index
}
pub fn get_closest_voxel(&self, node_index: OctreeIndex, depth: u8) -> Voxel {
let node = &self.nodes[&node_index];
match self.nodes[&(node.index >> ((node.get_depth() - depth) * 3))].data {
Some(v) => v,
None => self.get_closest_voxel(node.index, depth + 1),
}
}
pub fn get_parent_node_mut(&mut self, node_index: OctreeIndex) -> Option<&mut OctreeNode> {
self.nodes.get_mut(&(node_index >> 3))
}
}
With this applied there also do not appear any duplicate inserts any more.