spatialrust_lod/
index.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use spatialrust_math::Vec3;
4
5use crate::{LodError, LodResult};
6
7/// Stable LOD/index node identity.
8#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
9pub struct NodeId(pub u64);
10
11/// Finite axis-aligned node bounds.
12#[derive(Clone, Copy, Debug, PartialEq)]
13pub struct LodBounds {
14    /// Inclusive minimum corner.
15    pub min: Vec3<f32>,
16    /// Inclusive maximum corner.
17    pub max: Vec3<f32>,
18}
19
20impl LodBounds {
21    /// Creates ordered finite bounds.
22    pub fn try_new(min: Vec3<f32>, max: Vec3<f32>) -> LodResult<Self> {
23        if [min.x, min.y, min.z, max.x, max.y, max.z].iter().any(|value| !value.is_finite())
24            || min.x > max.x
25            || min.y > max.y
26            || min.z > max.z
27        {
28            return Err(LodError::InvalidIndex("node bounds must be finite and ordered".into()));
29        }
30        Ok(Self { min, max })
31    }
32
33    /// Bounds center.
34    #[must_use]
35    pub fn center(self) -> Vec3<f32> {
36        Vec3::new(
37            (self.min.x + self.max.x) * 0.5,
38            (self.min.y + self.max.y) * 0.5,
39            (self.min.z + self.max.z) * 0.5,
40        )
41    }
42
43    /// Radius of a sphere containing these bounds.
44    #[must_use]
45    pub fn radius(self) -> f32 {
46        let half = Vec3::new(
47            (self.max.x - self.min.x) * 0.5,
48            (self.max.y - self.min.y) * 0.5,
49            (self.max.z - self.min.z) * 0.5,
50        );
51        half.length()
52    }
53
54    /// Union of two bounds.
55    #[must_use]
56    pub fn union(self, other: Self) -> Self {
57        Self {
58            min: Vec3::new(
59                self.min.x.min(other.min.x),
60                self.min.y.min(other.min.y),
61                self.min.z.min(other.min.z),
62            ),
63            max: Vec3::new(
64                self.max.x.max(other.max.x),
65                self.max.y.max(other.max.y),
66                self.max.z.max(other.max.z),
67            ),
68        }
69    }
70}
71
72/// One node from a persisted spatial/COPC hierarchy.
73#[derive(Clone, Debug, PartialEq)]
74pub struct LodNode {
75    /// Stable identity.
76    pub id: NodeId,
77    /// Parent identity; root nodes have none.
78    pub parent: Option<NodeId>,
79    /// Child identities.
80    pub children: Vec<NodeId>,
81    /// World-space bounds.
82    pub bounds: LodBounds,
83    /// Conservative geometric error in world units.
84    pub geometric_error: f32,
85    /// Points materialized by this node.
86    pub point_count: u64,
87    /// Estimated host bytes needed to decode this node.
88    pub host_bytes: u64,
89    /// Estimated bytes uploaded for this node.
90    pub upload_bytes: u64,
91    /// GPU bytes retained after upload.
92    pub gpu_bytes: u64,
93}
94
95impl LodNode {
96    fn validate(&self) -> LodResult<()> {
97        if !self.geometric_error.is_finite()
98            || self.geometric_error < 0.0
99            || self.point_count == 0
100            || self.host_bytes == 0
101            || self.upload_bytes == 0
102            || self.gpu_bytes == 0
103        {
104            return Err(LodError::InvalidIndex(format!(
105                "node {} requires finite non-negative error and positive counts/bytes",
106                self.id.0
107            )));
108        }
109        let mut children = self.children.clone();
110        children.sort_unstable();
111        children.dedup();
112        if children.len() != self.children.len() || children.contains(&self.id) {
113            return Err(LodError::InvalidIndex(format!(
114                "node {} has duplicate or self child",
115                self.id.0
116            )));
117        }
118        Ok(())
119    }
120}
121
122/// Validated deterministic LOD hierarchy.
123#[derive(Clone, Debug, PartialEq)]
124pub struct LodIndex {
125    nodes: BTreeMap<NodeId, LodNode>,
126    roots: Vec<NodeId>,
127}
128
129impl LodIndex {
130    /// Validates nodes, reciprocal parent links, roots, reachability, and cycles.
131    pub fn try_new(nodes: impl IntoIterator<Item = LodNode>) -> LodResult<Self> {
132        let mut map = BTreeMap::new();
133        for mut node in nodes {
134            node.validate()?;
135            node.children.sort_unstable();
136            if map.insert(node.id, node).is_some() {
137                return Err(LodError::InvalidIndex("duplicate node ID".into()));
138            }
139        }
140        if map.is_empty() {
141            return Err(LodError::InvalidIndex("LOD index must not be empty".into()));
142        }
143        for node in map.values() {
144            if let Some(parent) = node.parent {
145                let parent_node = map.get(&parent).ok_or_else(|| {
146                    LodError::InvalidIndex(format!("missing parent {}", parent.0))
147                })?;
148                if !parent_node.children.contains(&node.id) {
149                    return Err(LodError::InvalidIndex(format!(
150                        "parent {} does not reference child {}",
151                        parent.0, node.id.0
152                    )));
153                }
154            }
155            for child in &node.children {
156                let child_node = map
157                    .get(child)
158                    .ok_or_else(|| LodError::InvalidIndex(format!("missing child {}", child.0)))?;
159                if child_node.parent != Some(node.id) {
160                    return Err(LodError::InvalidIndex(format!(
161                        "child {} has inconsistent parent",
162                        child.0
163                    )));
164                }
165            }
166        }
167        let roots: Vec<_> =
168            map.values().filter(|node| node.parent.is_none()).map(|node| node.id).collect();
169        if roots.is_empty() {
170            return Err(LodError::InvalidIndex("LOD index has no root".into()));
171        }
172        let mut visited = BTreeSet::new();
173        let mut active = BTreeSet::new();
174        for root in &roots {
175            visit(*root, &map, &mut visited, &mut active)?;
176        }
177        if visited.len() != map.len() {
178            return Err(LodError::InvalidIndex("LOD index contains unreachable nodes".into()));
179        }
180        Ok(Self { nodes: map, roots })
181    }
182
183    /// Finds a node.
184    #[must_use]
185    pub fn node(&self, id: NodeId) -> Option<&LodNode> {
186        self.nodes.get(&id)
187    }
188
189    /// Root IDs in deterministic order.
190    #[must_use]
191    pub fn roots(&self) -> &[NodeId] {
192        &self.roots
193    }
194
195    /// All nodes ordered by ID.
196    pub fn nodes(&self) -> impl ExactSizeIterator<Item = &LodNode> {
197        self.nodes.values()
198    }
199
200    /// Returns the nearest ancestor, including `id`, satisfying `predicate`.
201    pub(crate) fn nearest_ancestor(
202        &self,
203        id: NodeId,
204        mut predicate: impl FnMut(NodeId) -> bool,
205    ) -> Option<NodeId> {
206        let mut current = Some(id);
207        while let Some(node_id) = current {
208            if predicate(node_id) {
209                return Some(node_id);
210            }
211            current = self.nodes.get(&node_id).and_then(|node| node.parent);
212        }
213        None
214    }
215}
216
217fn visit(
218    id: NodeId,
219    nodes: &BTreeMap<NodeId, LodNode>,
220    visited: &mut BTreeSet<NodeId>,
221    active: &mut BTreeSet<NodeId>,
222) -> LodResult<()> {
223    if active.contains(&id) {
224        return Err(LodError::InvalidIndex("LOD hierarchy contains a cycle".into()));
225    }
226    if !visited.insert(id) {
227        return Ok(());
228    }
229    active.insert(id);
230    for child in &nodes[&id].children {
231        visit(*child, nodes, visited, active)?;
232    }
233    active.remove(&id);
234    Ok(())
235}
spatialrust_lod/index.rs

spatialrust_lod/
index.rs
