Rust 中的八叉树实现：为什么插入函数会重复插入，我该如何解决这个问题？

Question

我一直在尝试为游戏实现体素八叉树，这个问题完全难住了我。

我的八叉树线性存储为八叉树索引和节点的哈希图（请参阅https://geidav.wordpress.com/2014/08/18/advanced-octrees-2-node-representations/下的“隐式节点表示”） ）。在我的插入函数中，我将节点添加到哈希图中，然后递归地分割父节点，直到要插入的体素适合八叉树，从而生成具有父体体素类型的其他七个节点。如果没有直接父母，我会递归地创建新父母。

我正在使用的八叉树索引系统的快速概述：对于八叉树的每个级别，附加三个位来确定相对于父节点的位置。最根节点的索引为 1，这允许计算任何子树的深度。

不知何故，要插入的体素被添加到哈希图中两次，以及同一级别的其他 7 个体素，这会用错误的类型覆盖体素。

我的主要功能如下：

fn main() {
    let mut octree = Octree::new(Voxel::Air);
    octree.insert(0b1010110, Voxel::Dirt);
}

它输出：

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

以下是所有八叉树实现代码（复制+粘贴复制）：

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
    }
}

我尝试移动哈希图插入点，尝试改变生成节点的条件，但没有什么可以阻止重复。大部分时间都诚实地花在尝试概念化正在发生的事情上。

如果我的实现方式有什么完全令人无法容忍的地方，请告诉我（任何可以改善肯定是残酷的运行时复杂性的事情）。

Answer 1

&mut self.insert(index >> 3, self.get_closest_voxel(&node, 0))

显然是错误的，因为你没有改变真实的、插入的

parent

，而是改变了返回的 copy

insert

。

fn get_closest_voxel(&self, node: &OctreeNode, depth: u8)

引用

self

的部分内容通常会出现问题（比如

node: &OctreeNode

肯定在

get_closest_voxel

中，而且通常也在

get_parent_node_mut

中），我建议您改用索引：

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: u16, voxel: Voxel) -> u16 {
        let node = OctreeNode {
            index,
            data: Some(voxel),
        };

        self.nodes.insert(index, node);
        //dbg!(&self, format!("{index:b}"), &voxel);
        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) {
                    eprintln!("child insert");
                    self.insert(current_index, v);
                }
            }
        }
        index
    }

    pub fn get_closest_voxel(&self, node_index: u16, 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: u16) -> Option<&mut OctreeNode> {
        self.nodes.get_mut(&(node_index >> 3))
    }
}

应用此功能后，也不再出现任何重复插入。