oxiphysics_geometry/signed_distance_field/
octree.rs

1// Copyright 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3
4//! Adaptive octree SDF storage.
5
6// ─────────────────────────────────────────────────────────────────────────────
7// Octree SDF Storage
8// ─────────────────────────────────────────────────────────────────────────────
9
10/// Node in an octree used to store SDF values adaptively.
11#[derive(Debug, Clone)]
12pub enum OctreeNode {
13    /// Leaf node storing the SDF value at the cell centre.
14    Leaf {
15        /// SDF value at the centre.
16        value: f64,
17        /// Cell centre position.
18        centre: [f64; 3],
19        /// Half-size of the cell.
20        half_size: f64,
21    },
22    /// Internal node with 8 children.
23    Internal {
24        /// Cell centre.
25        centre: [f64; 3],
26        /// Half-size.
27        half_size: f64,
28        /// Child nodes (octants).
29        children: Box<[OctreeNode; 8]>,
30    },
31}
32
33impl OctreeNode {
34    /// Approximate SDF value at `p` by descending the octree.
35    pub fn evaluate(&self, p: [f64; 3]) -> f64 {
36        match self {
37            OctreeNode::Leaf { value, .. } => *value,
38            OctreeNode::Internal {
39                centre,
40                children,
41                half_size: _,
42            } => {
43                let ix = if p[0] >= centre[0] { 1 } else { 0 };
44                let iy = if p[1] >= centre[1] { 1 } else { 0 };
45                let iz = if p[2] >= centre[2] { 1 } else { 0 };
46                let child_idx = ix + 2 * iy + 4 * iz;
47                children[child_idx].evaluate(p)
48            }
49        }
50    }
51
52    /// Half-size (radius) of this node's cell.
53    pub fn half_size(&self) -> f64 {
54        match self {
55            OctreeNode::Leaf { half_size, .. } => *half_size,
56            OctreeNode::Internal { half_size, .. } => *half_size,
57        }
58    }
59}
60
61/// Adaptive octree SDF storage.
62#[derive(Debug, Clone)]
63pub struct OctreeSdf {
64    /// Root node.
65    pub root: OctreeNode,
66    /// Maximum subdivision depth.
67    pub max_depth: usize,
68    /// Subdivision threshold: refine if SDF value is below this.
69    pub refine_threshold: f64,
70}
71
72impl OctreeSdf {
73    /// Build an octree SDF from function `f` centred at `centre` with `half_size`.
74    pub fn build<F>(
75        f: &F,
76        centre: [f64; 3],
77        half_size: f64,
78        max_depth: usize,
79        refine_threshold: f64,
80    ) -> Self
81    where
82        F: Fn([f64; 3]) -> f64,
83    {
84        let root = Self::build_node(f, centre, half_size, 0, max_depth, refine_threshold);
85        Self {
86            root,
87            max_depth,
88            refine_threshold,
89        }
90    }
91
92    fn build_node<F>(
93        f: &F,
94        centre: [f64; 3],
95        half_size: f64,
96        depth: usize,
97        max_depth: usize,
98        threshold: f64,
99    ) -> OctreeNode
100    where
101        F: Fn([f64; 3]) -> f64,
102    {
103        let value = f(centre);
104        if depth >= max_depth || value.abs() > threshold {
105            return OctreeNode::Leaf {
106                value,
107                centre,
108                half_size,
109            };
110        }
111        let hs = half_size * 0.5;
112        let children: [OctreeNode; 8] = std::array::from_fn(|k| {
113            let cx = centre[0] + if k & 1 != 0 { hs } else { -hs };
114            let cy = centre[1] + if k & 2 != 0 { hs } else { -hs };
115            let cz = centre[2] + if k & 4 != 0 { hs } else { -hs };
116            Self::build_node(f, [cx, cy, cz], hs, depth + 1, max_depth, threshold)
117        });
118        OctreeNode::Internal {
119            centre,
120            half_size,
121            children: Box::new(children),
122        }
123    }
124
125    /// Evaluate the octree SDF at point `p`.
126    pub fn evaluate(&self, p: [f64; 3]) -> f64 {
127        self.root.evaluate(p)
128    }
129
130    /// Count total number of leaf nodes.
131    pub fn count_leaves(&self) -> usize {
132        Self::count_leaves_node(&self.root)
133    }
134
135    fn count_leaves_node(node: &OctreeNode) -> usize {
136        match node {
137            OctreeNode::Leaf { .. } => 1,
138            OctreeNode::Internal { children, .. } => {
139                children.iter().map(Self::count_leaves_node).sum()
140            }
141        }
142    }
143}
oxiphysics_geometry/signed_distance_field/octree.rs

oxiphysics_geometry/signed_distance_field/
octree.rs
