use crate::storage::spatial_page::{BoundingBox, SpatialPage};
use anyhow::{bail, Context, Result};
use std::collections::BTreeMap;
use std::fs::OpenOptions;
use std::io::{Read, Seek, Write};
use std::path::Path;
#[derive(Debug, Clone)]
pub enum OctreeNode {
Internal {
bbox: BoundingBox,
children: Box<[OctreeNode; 8]>,
depth: u8,
},
Leaf {
bbox: BoundingBox,
page_indices: Vec<usize>,
morton_prefix: u64,
morton_bits: u8,
},
}
impl OctreeNode {
pub fn leaf_from_page(
bbox: BoundingBox,
page_idx: usize,
morton_prefix: u64,
morton_bits: u8,
) -> Self {
OctreeNode::Leaf {
bbox,
page_indices: vec![page_idx],
morton_prefix,
morton_bits,
}
}
pub fn bbox(&self) -> &BoundingBox {
match self {
OctreeNode::Internal { bbox, .. } => bbox,
OctreeNode::Leaf { bbox, .. } => bbox,
}
}
pub fn is_leaf(&self) -> bool {
matches!(self, OctreeNode::Leaf { .. })
}
pub fn collect_leaves(&self) -> Vec<&OctreeNode> {
let mut out = vec![];
self.collect_leaves_into(&mut out);
out
}
fn collect_leaves_into<'a>(&'a self, out: &mut Vec<&'a OctreeNode>) {
match self {
OctreeNode::Internal { children, .. } => {
for ch in children.iter() {
ch.collect_leaves_into(out);
}
}
leaf @ OctreeNode::Leaf { .. } => out.push(leaf),
}
}
pub fn collect_page_indices(&self) -> Vec<usize> {
let mut out = vec![];
self.collect_page_indices_into(&mut out);
out
}
fn collect_page_indices_into(&self, out: &mut Vec<usize>) {
match self {
OctreeNode::Internal { children, .. } => {
for ch in children.iter() {
ch.collect_page_indices_into(out);
}
}
OctreeNode::Leaf { page_indices, .. } => out.extend(page_indices.iter().copied()),
}
}
}
pub fn build_octree(
pages: &[SpatialPage],
max_depth: u8,
max_pages_per_leaf: usize,
) -> Option<OctreeNode> {
if pages.is_empty() {
return None;
}
let mut gb = pages[0].header.bbox();
for p in &pages[1..] {
gb.expand(&p.header.bbox());
}
let refs: Vec<(usize, &SpatialPage)> = pages.iter().enumerate().collect();
_build(&refs, &gb, 0, max_depth, max_pages_per_leaf)
}
fn _build(
refs: &[(usize, &SpatialPage)],
bbox: &BoundingBox,
depth: u8,
max_depth: u8,
max_per_leaf: usize,
) -> Option<OctreeNode> {
if refs.is_empty() {
return None;
}
if depth >= max_depth || refs.len() <= max_per_leaf {
let prefix = if refs.len() == 1 {
refs[0].1.header.morton_prefix
} else {
common_prefix(refs)
};
let bits = if refs.len() == 1 {
refs[0].1.header.morton_shift
} else {
depth * 3
};
return Some(OctreeNode::Leaf {
bbox: *bbox,
page_indices: refs.iter().map(|(i, _)| *i).collect(),
morton_prefix: prefix,
morton_bits: bits,
});
}
let mx = (bbox.min_x + bbox.max_x) / 2.0;
let my = (bbox.min_y + bbox.max_y) / 2.0;
let mz = (bbox.min_z + bbox.max_z) / 2.0;
let octants = [
BoundingBox::new(bbox.min_x, mx, bbox.min_y, my, bbox.min_z, mz),
BoundingBox::new(mx, bbox.max_x, bbox.min_y, my, bbox.min_z, mz),
BoundingBox::new(bbox.min_x, mx, my, bbox.max_y, bbox.min_z, mz),
BoundingBox::new(mx, bbox.max_x, my, bbox.max_y, bbox.min_z, mz),
BoundingBox::new(bbox.min_x, mx, bbox.min_y, my, mz, bbox.max_z),
BoundingBox::new(mx, bbox.max_x, bbox.min_y, my, mz, bbox.max_z),
BoundingBox::new(bbox.min_x, mx, my, bbox.max_y, mz, bbox.max_z),
BoundingBox::new(mx, bbox.max_x, my, bbox.max_y, mz, bbox.max_z),
];
let mut groups: [Vec<(usize, &SpatialPage)>; 8] = Default::default();
for r in refs {
let pb = r.1.header.bbox();
let cx = (pb.min_x + pb.max_x) / 2.0;
let cy = (pb.min_y + pb.max_y) / 2.0;
let cz = (pb.min_z + pb.max_z) / 2.0;
let idx = octant_index(cx, cy, cz, mx, my, mz);
groups[idx as usize].push(*r);
}
let maybe_child = |g: &[(usize, &SpatialPage)], b: &BoundingBox| {
_build(g, b, depth + 1, max_depth, max_per_leaf)
.map(Box::new)
.unwrap_or_else(|| {
Box::new(OctreeNode::Leaf {
bbox: *b,
page_indices: vec![],
morton_prefix: 0,
morton_bits: depth * 3,
})
})
};
Some(OctreeNode::Internal {
bbox: *bbox,
children: Box::new([
*maybe_child(&groups[0], &octants[0]),
*maybe_child(&groups[1], &octants[1]),
*maybe_child(&groups[2], &octants[2]),
*maybe_child(&groups[3], &octants[3]),
*maybe_child(&groups[4], &octants[4]),
*maybe_child(&groups[5], &octants[5]),
*maybe_child(&groups[6], &octants[6]),
*maybe_child(&groups[7], &octants[7]),
]),
depth,
})
}
fn octant_index(x: f32, y: f32, z: f32, mx: f32, my: f32, mz: f32) -> u8 {
(if x >= mx { 1 } else { 0 }) + (if y >= my { 2 } else { 0 }) + (if z >= mz { 4 } else { 0 })
}
fn common_prefix(refs: &[(usize, &SpatialPage)]) -> u64 {
if refs.is_empty() {
return 0;
}
let mut p = refs[0].1.header.morton_prefix;
for (_, page) in &refs[1..] {
p &= page.header.morton_prefix;
}
p
}
pub fn range_query(node: &OctreeNode, query: &BoundingBox) -> Vec<usize> {
let mut out = vec![];
_range(node, query, &mut out);
out
}
fn _range(node: &OctreeNode, query: &BoundingBox, out: &mut Vec<usize>) {
match node {
OctreeNode::Internal { bbox, children, .. } => {
if !bbox.intersects(query) {
return;
}
for ch in children.iter() {
_range(ch, query, out);
}
}
OctreeNode::Leaf {
bbox, page_indices, ..
} => {
if bbox.intersects(query) {
out.extend(page_indices.iter().copied());
}
}
}
}
pub fn point_query(node: &OctreeNode, x: f32, y: f32, z: f32) -> Vec<usize> {
let mut out = vec![];
_point(node, x, y, z, &mut out);
out
}
fn _point(node: &OctreeNode, x: f32, y: f32, z: f32, out: &mut Vec<usize>) {
match node {
OctreeNode::Internal { bbox, children, .. } => {
if !bbox.contains_point(x, y, z) {
return;
}
for ch in children.iter() {
_point(ch, x, y, z, out);
}
}
OctreeNode::Leaf {
bbox, page_indices, ..
} => {
if bbox.contains_point(x, y, z) {
out.extend(page_indices.iter().copied());
}
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DualEdgeType {
Face,
Edge,
Corner,
}
#[derive(Debug, Clone)]
pub struct DualVertex {
pub leaf_idx: usize,
pub bbox: BoundingBox,
pub page_indices: Vec<usize>,
}
#[derive(Debug, Clone)]
pub struct DualGraph {
pub vertices: Vec<DualVertex>,
pub adjacency: Vec<Vec<(usize, DualEdgeType)>>,
}
impl DualGraph {
pub fn from_octree(octree: &OctreeNode) -> Self {
let leaves = octree.collect_leaves();
let n = leaves.len();
let vertices: Vec<DualVertex> = leaves
.iter()
.enumerate()
.map(|(i, leaf)| match leaf {
OctreeNode::Leaf {
bbox, page_indices, ..
} => DualVertex {
leaf_idx: i,
bbox: *bbox,
page_indices: page_indices.clone(),
},
_ => unreachable!(),
})
.collect();
let mut adjacency: Vec<Vec<(usize, DualEdgeType)>> = vec![vec![]; n];
for i in 0..n {
for j in (i + 1)..n {
if let Some(et) = adjacency_type(&vertices[i].bbox, &vertices[j].bbox) {
adjacency[i].push((j, et));
adjacency[j].push((i, et));
}
}
}
DualGraph {
vertices,
adjacency,
}
}
pub fn bfs(&self, start_idx: usize) -> Vec<usize> {
use std::collections::{HashSet, VecDeque};
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
if start_idx < self.vertices.len() {
visited.insert(start_idx);
queue.push_back(start_idx);
}
while let Some(cur) = queue.pop_front() {
for (nbr, _) in &self.adjacency[cur] {
if visited.insert(*nbr) {
queue.push_back(*nbr);
}
}
}
visited.into_iter().collect()
}
pub fn connected_components(&self) -> Vec<Vec<usize>> {
let mut visited = vec![false; self.vertices.len()];
let mut comps = vec![];
for i in 0..self.vertices.len() {
if !visited[i] {
let comp = self.bfs(i);
for &v in &comp {
visited[v] = true;
}
comps.push(comp);
}
}
comps
}
}
fn adjacency_type(a: &BoundingBox, b: &BoundingBox) -> Option<DualEdgeType> {
use crate::storage::spatial_page::overlaps;
let dims = overlaps(a, b);
if dims == 3 {
Some(DualEdgeType::Face)
} else if dims == 2 {
Some(DualEdgeType::Edge)
} else if dims == 1 {
Some(DualEdgeType::Corner)
} else {
None
}
}
#[derive(Debug, Clone)]
pub struct OctreePageStore {
pub pages: Vec<SpatialPage>,
pub octree: OctreeNode,
pub dual_graph: DualGraph,
pub morton_index: BTreeMap<u64, usize>,
}
impl OctreePageStore {
pub fn new(pages: Vec<SpatialPage>, max_depth: u8, max_pages_per_leaf: usize) -> Self {
let mut morton_index = BTreeMap::new();
for (i, page) in pages.iter().enumerate() {
morton_index.insert(page.header.morton_prefix, i);
}
let octree = build_octree(&pages, max_depth, max_pages_per_leaf).unwrap_or_else(|| {
OctreeNode::Leaf {
bbox: BoundingBox::new(0.0, 1.0, 0.0, 1.0, 0.0, 1.0),
page_indices: (0..pages.len()).collect(),
morton_prefix: 0,
morton_bits: 0,
}
});
let dual_graph = DualGraph::from_octree(&octree);
Self {
pages,
octree,
dual_graph,
morton_index,
}
}
pub fn get_page(&self, idx: usize) -> Option<&SpatialPage> {
self.pages.get(idx)
}
pub fn find_by_morton_prefix(&self, prefix: u64) -> Option<&SpatialPage> {
self.morton_index
.get(&prefix)
.and_then(|idx| self.pages.get(*idx))
}
pub fn range_query(&self, query: &BoundingBox) -> Vec<usize> {
range_query(&self.octree, query)
}
pub fn point_query(&self, x: f32, y: f32, z: f32) -> Vec<usize> {
point_query(&self.octree, x, y, z)
}
pub fn total_nodes(&self) -> usize {
self.pages.iter().map(|p| p.nodes.len()).sum()
}
pub fn leaf_count(&self) -> usize {
self.octree.collect_leaves().len()
}
pub fn dual_vertex_count(&self) -> usize {
self.dual_graph.vertices.len()
}
pub fn dual_edge_count(&self) -> usize {
self.dual_graph.adjacency.iter().map(|v| v.len()).sum()
}
pub fn save<P: AsRef<Path>>(&self, path: P) -> Result<()> {
let path = path.as_ref();
let tmp = path.with_extension("tmp");
self.save_inner(&tmp)?;
std::fs::rename(&tmp, path)
.with_context(|| format!("Failed to rename {:?} to {:?}", tmp, path))?;
Ok(())
}
fn save_inner(&self, path: &Path) -> Result<()> {
let mut file = OpenOptions::new()
.write(true)
.create(true)
.truncate(true)
.open(path)
.with_context(|| format!("Failed to open spatial store for writing: {:?}", path))?;
file.write_all(&OCTREE_STORE_MAGIC.to_le_bytes())?; file.write_all(&OCTREE_STORE_VERSION.to_le_bytes())?; file.write_all(&(0u64).to_le_bytes())?; file.write_all(&(0u64).to_le_bytes())?; file.write_all(&(0u64).to_le_bytes())?;
let page_count = self.pages.len() as u64;
let mut page_offsets: Vec<(u64, u32)> = Vec::with_capacity(self.pages.len());
for page in &self.pages {
let packed = page.pack()?;
let len = packed.len() as u32;
let offset = file.stream_position()?;
file.write_all(&len.to_le_bytes())?;
file.write_all(&packed)?;
page_offsets.push((offset, len));
}
let octree_offset = file.stream_position()?;
let mut octree_buf = Vec::with_capacity(4096); write_octree(&mut octree_buf, &self.octree);
file.write_all(&octree_buf)?;
file.seek(std::io::SeekFrom::Start(8))?;
file.write_all(&page_count.to_le_bytes())?;
file.write_all(&octree_offset.to_le_bytes())?;
file.sync_all()?;
Ok(())
}
pub fn open<P: AsRef<Path>>(
path: P,
_max_depth: u8,
_max_pages_per_leaf: usize,
) -> Result<Self> {
let path = path.as_ref();
let mut file = OpenOptions::new()
.read(true)
.open(path)
.with_context(|| format!("Failed to open spatial store for reading: {:?}", path))?;
let mut header = [0u8; 32];
file.read_exact(&mut header)?;
let magic = u32::from_le_bytes(header[0..4].try_into().unwrap());
let version = u32::from_le_bytes(header[4..8].try_into().unwrap());
if magic != OCTREE_STORE_MAGIC {
bail!(
"Invalid spatial store magic: expected {:#x}, got {:#x}",
OCTREE_STORE_MAGIC,
magic
);
}
if version != OCTREE_STORE_VERSION {
bail!(
"Unsupported spatial store version: expected {}, got {}",
OCTREE_STORE_VERSION,
version
);
}
let page_count = u64::from_le_bytes(header[8..16].try_into().unwrap());
let octree_offset = u64::from_le_bytes(header[16..24].try_into().unwrap());
let mut pages = Vec::with_capacity(page_count as usize);
let mut morton_index = BTreeMap::new();
for i in 0..page_count {
let offset = file.stream_position()?;
if offset >= octree_offset {
break;
}
let mut len_bytes = [0u8; 4];
file.read_exact(&mut len_bytes)?;
let len = u32::from_le_bytes(len_bytes);
let mut packed = vec![0u8; len as usize];
file.read_exact(&mut packed)?;
let page = SpatialPage::unpack(&packed)
.with_context(|| format!("Failed to unpack spatial page {}", i))?;
morton_index.insert(page.header.morton_prefix, pages.len());
pages.push(page);
}
let remaining = file.metadata()?.len() - octree_offset;
let mut octree_bytes = vec![0u8; remaining as usize];
file.seek(std::io::SeekFrom::Start(octree_offset))?;
file.read_exact(&mut octree_bytes)?;
let mut slice = octree_bytes.as_slice();
let octree = read_octree_slice(&mut slice)?;
let dual_graph = DualGraph::from_octree(&octree);
Ok(Self {
pages,
octree,
dual_graph,
morton_index,
})
}
}
const OCTREE_STORE_MAGIC: u32 = 0x5350_4744; const OCTREE_STORE_VERSION: u32 = 1;
fn write_octree(buf: &mut Vec<u8>, node: &OctreeNode) {
match node {
OctreeNode::Internal {
bbox,
children,
depth,
} => {
buf.push(0u8); write_bbox_to_buf(buf, bbox);
buf.push(*depth);
for child in children.iter() {
write_octree(buf, child);
}
}
OctreeNode::Leaf {
bbox,
page_indices,
morton_prefix,
morton_bits,
} => {
buf.push(1u8); write_bbox_to_buf(buf, bbox);
buf.extend_from_slice(&morton_prefix.to_le_bytes());
buf.push(*morton_bits);
let count = page_indices.len() as u32;
buf.extend_from_slice(&count.to_le_bytes());
for &idx in page_indices {
buf.extend_from_slice(&(idx as u64).to_le_bytes());
}
}
}
}
fn write_bbox_to_buf(buf: &mut Vec<u8>, bbox: &BoundingBox) {
let BoundingBox {
min_x,
max_x,
min_y,
max_y,
min_z,
max_z,
} = bbox;
buf.extend_from_slice(&min_x.to_le_bytes());
buf.extend_from_slice(&max_x.to_le_bytes());
buf.extend_from_slice(&min_y.to_le_bytes());
buf.extend_from_slice(&max_y.to_le_bytes());
buf.extend_from_slice(&min_z.to_le_bytes());
buf.extend_from_slice(&max_z.to_le_bytes());
}
fn read_octree_slice(bytes: &mut &[u8]) -> Result<OctreeNode> {
if bytes.is_empty() {
bail!("Unexpected EOF reading octree node");
}
let tag = bytes[0];
*bytes = &bytes[1..];
let bbox = read_bbox_from_slice(bytes)?;
if tag == 0 {
if bytes.is_empty() {
bail!("Unexpected EOF reading depth");
}
let depth = bytes[0];
*bytes = &bytes[1..];
let children = Box::new([
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
read_octree_slice(bytes)?,
]);
Ok(OctreeNode::Internal {
bbox,
children,
depth,
})
} else {
if bytes.len() < 8 {
bail!("Unexpected EOF reading morton_prefix");
}
let morton_prefix = u64::from_le_bytes(bytes[0..8].try_into().unwrap());
*bytes = &bytes[8..];
if bytes.is_empty() {
bail!("Unexpected EOF reading morton_bits");
}
let morton_bits = bytes[0];
*bytes = &bytes[1..];
if bytes.len() < 4 {
bail!("Unexpected EOF reading page count");
}
let count = u32::from_le_bytes(bytes[0..4].try_into().unwrap()) as usize;
*bytes = &bytes[4..];
if bytes.len() < count * 8 {
bail!("Unexpected EOF reading page_indices");
}
let mut page_indices = Vec::with_capacity(count);
for i in 0..count {
let b = &bytes[i * 8..i * 8 + 8];
page_indices.push(u64::from_le_bytes(b.try_into().unwrap()) as usize);
}
*bytes = &bytes[count * 8..];
Ok(OctreeNode::Leaf {
bbox,
page_indices,
morton_prefix,
morton_bits,
})
}
}
fn read_bbox_from_slice(bytes: &mut &[u8]) -> Result<BoundingBox> {
if bytes.len() < 24 {
bail!("Unexpected EOF reading bbox");
}
let min_x = f32::from_le_bytes(bytes[0..4].try_into().unwrap());
let max_x = f32::from_le_bytes(bytes[4..8].try_into().unwrap());
let min_y = f32::from_le_bytes(bytes[8..12].try_into().unwrap());
let max_y = f32::from_le_bytes(bytes[12..16].try_into().unwrap());
let min_z = f32::from_le_bytes(bytes[16..20].try_into().unwrap());
let max_z = f32::from_le_bytes(bytes[20..24].try_into().unwrap());
*bytes = &bytes[24..];
Ok(BoundingBox::new(min_x, max_x, min_y, max_y, min_z, max_z))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::storage::data_structures::NodeRec;
use crate::storage::spatial_page::SpatialPageHeader;
use std::collections::HashMap;
fn make_page(nodes: Vec<NodeRec>, morton_prefix: u64) -> SpatialPage {
let mut page = SpatialPage {
header: SpatialPageHeader {
magic: crate::storage::spatial_page::SPATIAL_PAGE_MAGIC,
version: crate::storage::spatial_page::SPATIAL_PAGE_VERSION,
morton_prefix,
morton_shift: 0,
node_count: nodes.len() as u16,
_pad1: [0; 5],
min_x: f32::MAX,
max_x: f32::MIN,
min_y: f32::MAX,
max_y: f32::MIN,
min_z: f32::MAX,
max_z: f32::MIN,
_pad2: [0; 8],
property_block_offset: 0,
property_block_len: 0,
edge_cluster_offset: 0,
edge_cluster_len: 0,
_reserved: [0; 16],
},
nodes,
properties: HashMap::new(),
edges: vec![],
};
let mut bbox = BoundingBox::from_node(&page.nodes[0]);
for n in &page.nodes[1..] {
bbox.expand(&BoundingBox::from_node(n));
}
page.header.min_x = bbox.min_x;
page.header.max_x = bbox.max_x;
page.header.min_y = bbox.min_y;
page.header.max_y = bbox.max_y;
page.header.min_z = bbox.min_z;
page.header.max_z = bbox.max_z;
page
}
fn make_node(id: u64, morton: u64, x: f32, y: f32, z: f32) -> NodeRec {
NodeRec {
id,
morton_code: morton,
x,
y,
z,
edge_off: 0,
edge_len: 0,
flags: 0,
begin_ts: 1,
end_ts: 0,
tx_id: 1,
visibility: 1,
_padding: [0; 7],
}
}
#[test]
fn test_octree_build_empty() {
let store = OctreePageStore::new(vec![], 3, 1);
assert_eq!(store.pages.len(), 0);
assert_eq!(store.leaf_count(), 1);
assert_eq!(store.dual_vertex_count(), 1);
}
#[test]
fn test_octree_build_single_page() {
let nodes = vec![
make_node(1, 0, 0.1, 0.1, 0.1),
make_node(2, 0, 0.2, 0.2, 0.2),
];
let page = make_page(nodes, 0);
let store = OctreePageStore::new(vec![page], 3, 1);
assert_eq!(store.pages.len(), 1);
assert_eq!(store.total_nodes(), 2);
}
#[test]
fn test_octree_build_multiple_pages() {
let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
let page2 = make_page(vec![make_node(2, 0, 0.9, 0.9, 0.9)], 0);
let store = OctreePageStore::new(vec![page1, page2], 4, 1);
assert_eq!(store.pages.len(), 2);
assert_eq!(store.dual_vertex_count(), store.leaf_count());
}
#[test]
fn test_range_query() {
let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
let page2 = make_page(vec![make_node(2, 0, 0.9, 0.9, 0.9)], 0);
let store = OctreePageStore::new(vec![page1, page2], 4, 1);
let q1 = BoundingBox::new(0.0, 0.49, 0.0, 0.49, 0.0, 0.49);
let r1 = store.range_query(&q1);
assert_eq!(r1.len(), 1);
assert_eq!(store.get_page(r1[0]).unwrap().nodes[0].id, 1);
let q2 = BoundingBox::new(0.0, 1.0, 0.0, 1.0, 0.0, 1.0);
let r2 = store.range_query(&q2);
assert_eq!(r2.len(), 2);
}
#[test]
fn test_point_query() {
let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
let page2 = make_page(vec![make_node(2, 0, 0.8, 0.8, 0.8)], 0);
let store = OctreePageStore::new(vec![page1, page2], 4, 1);
let r = store.point_query(0.1, 0.1, 0.1);
assert_eq!(r.len(), 1);
assert_eq!(store.get_page(r[0]).unwrap().nodes[0].id, 1);
}
#[test]
fn test_dual_graph_connected_components() {
let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0);
let page2 = make_page(vec![make_node(2, 0, 0.9, 0.9, 0.9)], 0);
let store = OctreePageStore::new(vec![page1, page2], 1, 1); let comps = store.dual_graph.connected_components();
assert_eq!(comps.len(), 1, "Full octree dual graph is connected");
}
#[test]
fn test_dual_graph_bfs() {
let nodes1 = vec![make_node(1, 0, 0.1, 0.1, 0.1)];
let nodes2 = vec![make_node(2, 0, 0.6, 0.1, 0.1)];
let nodes3 = vec![make_node(3, 0, 0.9, 0.9, 0.9)];
let page1 = make_page(nodes1, 0);
let page2 = make_page(nodes2, 0);
let page3 = make_page(nodes3, 0);
let store = OctreePageStore::new(vec![page1, page2, page3], 1, 1);
let leaf = store
.dual_graph
.vertices
.iter()
.position(|v| v.page_indices.contains(&0))
.unwrap();
let visited = store.dual_graph.bfs(leaf);
let leaf_count = store.leaf_count();
assert_eq!(
visited.len(),
leaf_count,
"BFS should reach all leaves in connected dual graph"
);
}
#[test]
fn test_morton_index_lookup() {
let page1 = make_page(vec![make_node(1, 0, 0.1, 0.1, 0.1)], 0x1234);
let store = OctreePageStore::new(vec![page1], 2, 1);
assert!(store.find_by_morton_prefix(0x1234).is_some());
assert!(store.find_by_morton_prefix(0x9999).is_none());
}
#[test]
fn test_save_open_roundtrip_multiple_pages() {
let mut pages = Vec::new();
for i in 0..100 {
let mut page = SpatialPage::new((i as u64) << 8, 8);
page.header.node_count = 2;
page.header.min_x = i as f32 * 0.1;
page.header.max_x = i as f32 * 0.1 + 0.1;
page.header.min_y = 0.0;
page.header.max_y = 0.1;
page.header.min_z = 0.0;
page.header.max_z = 0.1;
page.nodes = vec![
make_node(i as u64 * 2, 0, i as f32 * 0.1, 0.0, 0.0),
make_node(i as u64 * 2 + 1, 0, i as f32 * 0.1 + 0.05, 0.0, 0.0),
];
pages.push(page);
}
let store = OctreePageStore::new(pages, 4, 1);
let tempdir = tempfile::tempdir().unwrap();
let path = tempdir.path().join("spatial_store_multi.bin");
store.save(&path).expect("save should succeed");
let loaded = OctreePageStore::open(&path, 4, 1).expect("open should succeed");
assert_eq!(loaded.pages.len(), store.pages.len());
assert_eq!(
loaded.pages[100 - 1].nodes.len(),
store.pages[100 - 1].nodes.len()
);
assert_eq!(loaded.octree.is_leaf(), store.octree.is_leaf());
}
#[test]
fn bench_save_open_roundtrip() {
let counts = [100_usize, 1000, 5000];
for &count in &counts {
let mut pages = Vec::with_capacity(count);
for i in 0..count {
let x = (i % 100) as f32 * 0.01;
let y = ((i / 100) % 100) as f32 * 0.01;
let z = 0.0f32;
let mut page = SpatialPage::new(i as u64, 8);
page.header.node_count = 2;
page.header.min_x = x;
page.header.max_x = x + 0.01;
page.header.min_y = y;
page.header.max_y = y + 0.01;
page.header.min_z = z;
page.header.max_z = z + 0.01;
page.nodes = vec![
make_node(i as u64 * 2, 0, x, y, z),
make_node(i as u64 * 2 + 1, 0, x + 0.005, y + 0.005, z),
];
pages.push(page);
}
let store = OctreePageStore::new(pages, 4, 1);
let tempdir = tempfile::tempdir().unwrap();
let path = tempdir.path().join("spatial_bench.bin");
let t0 = std::time::Instant::now();
store.save(&path).unwrap();
let save_us = t0.elapsed().as_micros() as f64;
let t1 = std::time::Instant::now();
let loaded = OctreePageStore::open(&path, 4, 1).unwrap();
let open_us = t1.elapsed().as_micros() as f64;
assert_eq!(loaded.pages.len(), store.pages.len());
let total_nodes = count * 2;
println!(
"[BENCH] {} pages ({} nodes) save: {:>8.1} us ({:.1} M nodes/s) open: {:>8.1} us ({:.1} M nodes/s)",
count, total_nodes,
save_us, total_nodes as f64 / (save_us / 1_000_000.0) / 1_000_000.0,
open_us, total_nodes as f64 / (open_us / 1_000_000.0) / 1_000_000.0,
);
}
}
}