copc_core/
hierarchy.rs

1use crate::{Error, Result};
2
3pub const HIERARCHY_ENTRY_BYTES: usize = 32;
4
5/// COPC octree voxel key.
6#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
7pub struct VoxelKey {
8    pub level: i32,
9    pub x: i32,
10    pub y: i32,
11    pub z: i32,
12}
13
14impl VoxelKey {
15    pub const fn root() -> Self {
16        Self {
17            level: 0,
18            x: 0,
19            y: 0,
20            z: 0,
21        }
22    }
23
24    pub fn child(self, octant: u8) -> Result<Self> {
25        self.validate()?;
26        if octant > 7 {
27            return Err(Error::InvalidInput(format!(
28                "octant must be in 0..=7, got {octant}"
29            )));
30        }
31        let level = self
32            .level
33            .checked_add(1)
34            .ok_or_else(|| Error::InvalidInput("voxel level overflow".into()))?;
35        let child_axis = |axis: i32, bit: u8| {
36            axis.checked_mul(2)
37                .and_then(|axis| axis.checked_add(i32::from(bit)))
38                .ok_or_else(|| Error::InvalidInput("voxel axis overflow".into()))
39        };
40        let child = Self {
41            level,
42            x: child_axis(self.x, octant & 1)?,
43            y: child_axis(self.y, (octant >> 1) & 1)?,
44            z: child_axis(self.z, (octant >> 2) & 1)?,
45        };
46        child.validate()?;
47        Ok(child)
48    }
49
50    /// Validate this key against the EPT/COPC octree coordinate rules.
51    pub fn validate(self) -> Result<()> {
52        if self.level < 0 || self.x < 0 || self.y < 0 || self.z < 0 {
53            return Err(Error::InvalidData(format!(
54                "invalid negative COPC voxel key {self:?}"
55            )));
56        }
57        if self.level < 31 {
58            let axis_limit = 1i32 << self.level;
59            if self.x >= axis_limit || self.y >= axis_limit || self.z >= axis_limit {
60                return Err(Error::InvalidData(format!(
61                    "COPC voxel key {self:?} has an axis outside 0..{axis_limit}"
62                )));
63            }
64        }
65        Ok(())
66    }
67}
68
69/// One 32-byte COPC hierarchy entry.
70#[derive(Clone, Copy, Debug, PartialEq, Eq)]
71pub struct Entry {
72    pub key: VoxelKey,
73    pub offset: u64,
74    pub byte_size: i32,
75    pub point_count: i32,
76}
77
78/// Availability represented by a COPC hierarchy entry.
79#[derive(Clone, Copy, Debug, PartialEq, Eq)]
80pub enum EntryAvailability {
81    Empty,
82    PointData { point_count: u32 },
83    ChildPage,
84}
85
86impl Entry {
87    /// Validate invariants that do not depend on the containing file.
88    pub fn validate(self) -> Result<()> {
89        self.key.validate()?;
90        match self.availability()? {
91            EntryAvailability::Empty => {
92                if self.offset != 0 || self.byte_size != 0 {
93                    return Err(Error::InvalidData(format!(
94                        "empty hierarchy entry {:?} must have zero offset and byte size",
95                        self.key
96                    )));
97                }
98            }
99            EntryAvailability::PointData { .. } => {
100                if self.byte_size <= 0 {
101                    return Err(Error::InvalidData(format!(
102                        "point data entry {:?} has invalid byte size {}",
103                        self.key, self.byte_size
104                    )));
105                }
106            }
107            EntryAvailability::ChildPage => {
108                if self.byte_size <= 0 {
109                    return Err(Error::InvalidData(format!(
110                        "child hierarchy page {:?} has invalid byte size {}",
111                        self.key, self.byte_size
112                    )));
113                }
114            }
115        }
116        Ok(())
117    }
118
119    pub fn availability(self) -> Result<EntryAvailability> {
120        match self.point_count {
121            -1 => Ok(EntryAvailability::ChildPage),
122            0 => Ok(EntryAvailability::Empty),
123            count if count > 0 => {
124                let point_count = u32::try_from(count).map_err(|_| {
125                    Error::InvalidData(format!(
126                        "hierarchy entry {:?} point count {} is out of range",
127                        self.key, self.point_count
128                    ))
129                })?;
130                Ok(EntryAvailability::PointData { point_count })
131            }
132            _ => Err(Error::InvalidData(format!(
133                "hierarchy entry {:?} has invalid point count {}",
134                self.key, self.point_count
135            ))),
136        }
137    }
138
139    pub fn has_point_data(self) -> bool {
140        self.point_count > 0
141    }
142
143    pub fn is_empty(self) -> bool {
144        self.point_count == 0
145    }
146
147    pub fn is_child_page(self) -> bool {
148        self.point_count == -1
149    }
150
151    pub fn write_le(self, dst: &mut [u8]) -> Result<()> {
152        self.validate()?;
153        if dst.len() != HIERARCHY_ENTRY_BYTES {
154            return Err(Error::InvalidInput(format!(
155                "hierarchy entry destination is {} bytes, expected {}",
156                dst.len(),
157                HIERARCHY_ENTRY_BYTES
158            )));
159        }
160        dst[0..4].copy_from_slice(&self.key.level.to_le_bytes());
161        dst[4..8].copy_from_slice(&self.key.x.to_le_bytes());
162        dst[8..12].copy_from_slice(&self.key.y.to_le_bytes());
163        dst[12..16].copy_from_slice(&self.key.z.to_le_bytes());
164        dst[16..24].copy_from_slice(&self.offset.to_le_bytes());
165        dst[24..28].copy_from_slice(&self.byte_size.to_le_bytes());
166        dst[28..32].copy_from_slice(&self.point_count.to_le_bytes());
167        Ok(())
168    }
169
170    pub fn from_le(src: &[u8]) -> Result<Self> {
171        if src.len() != HIERARCHY_ENTRY_BYTES {
172            return Err(Error::InvalidData(format!(
173                "hierarchy entry is {} bytes, expected {}",
174                src.len(),
175                HIERARCHY_ENTRY_BYTES
176            )));
177        }
178        let entry = Self {
179            key: VoxelKey {
180                level: i32::from_le_bytes(src[0..4].try_into().expect("level width")),
181                x: i32::from_le_bytes(src[4..8].try_into().expect("x width")),
182                y: i32::from_le_bytes(src[8..12].try_into().expect("y width")),
183                z: i32::from_le_bytes(src[12..16].try_into().expect("z width")),
184            },
185            offset: u64::from_le_bytes(src[16..24].try_into().expect("offset width")),
186            byte_size: i32::from_le_bytes(src[24..28].try_into().expect("byte_size width")),
187            point_count: i32::from_le_bytes(src[28..32].try_into().expect("point_count width")),
188        };
189        entry.validate()?;
190        Ok(entry)
191    }
192}
193
194/// A COPC hierarchy page.
195#[derive(Clone, Debug, Default, PartialEq, Eq)]
196pub struct HierarchyPage {
197    entries: Vec<Entry>,
198}
199
200impl HierarchyPage {
201    pub fn new(entries: Vec<Entry>) -> Self {
202        Self { entries }
203    }
204
205    pub fn entries(&self) -> &[Entry] {
206        &self.entries
207    }
208
209    pub fn into_entries(self) -> Vec<Entry> {
210        self.entries
211    }
212
213    pub fn from_le_bytes(bytes: &[u8]) -> Result<Self> {
214        if !bytes.len().is_multiple_of(HIERARCHY_ENTRY_BYTES) {
215            return Err(Error::InvalidData(format!(
216                "hierarchy page is {} bytes, not a multiple of {}",
217                bytes.len(),
218                HIERARCHY_ENTRY_BYTES
219            )));
220        }
221        let entries = bytes
222            .chunks_exact(HIERARCHY_ENTRY_BYTES)
223            .map(Entry::from_le)
224            .collect::<Result<Vec<_>>>()?;
225        Ok(Self { entries })
226    }
227
228    pub fn write_le_bytes(&self) -> Result<Vec<u8>> {
229        let byte_len = self
230            .entries
231            .len()
232            .checked_mul(HIERARCHY_ENTRY_BYTES)
233            .ok_or_else(|| Error::InvalidInput("hierarchy page size overflows usize".into()))?;
234        let mut out = vec![0u8; byte_len];
235        for (entry, chunk) in self
236            .entries
237            .iter()
238            .copied()
239            .zip(out.chunks_exact_mut(HIERARCHY_ENTRY_BYTES))
240        {
241            entry.write_le(chunk)?;
242        }
243        Ok(out)
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use super::*;
250
251    #[test]
252    fn hierarchy_entry_round_trips() {
253        let entry = Entry {
254            key: VoxelKey {
255                level: 3,
256                x: 4,
257                y: 5,
258                z: 6,
259            },
260            offset: 123_456,
261            byte_size: 789,
262            point_count: 42,
263        };
264        let mut bytes = [0u8; HIERARCHY_ENTRY_BYTES];
265        entry.write_le(&mut bytes).unwrap();
266        assert_eq!(Entry::from_le(&bytes).unwrap(), entry);
267    }
268
269    #[test]
270    fn voxel_child_maps_octant_bits() {
271        let child = VoxelKey::root().child(0b101).unwrap();
272        assert_eq!(
273            child,
274            VoxelKey {
275                level: 1,
276                x: 1,
277                y: 0,
278                z: 1,
279            }
280        );
281        assert!(VoxelKey::root().child(8).is_err());
282    }
283
284    #[test]
285    fn voxel_key_validation_rejects_invalid_axes() {
286        VoxelKey::root().validate().unwrap();
287        VoxelKey {
288            level: 3,
289            x: 7,
290            y: 7,
291            z: 7,
292        }
293        .validate()
294        .unwrap();
295        assert!(VoxelKey {
296            level: 3,
297            x: 8,
298            y: 0,
299            z: 0,
300        }
301        .validate()
302        .is_err());
303        assert!(VoxelKey {
304            level: -1,
305            x: 0,
306            y: 0,
307            z: 0,
308        }
309        .validate()
310        .is_err());
311    }
312
313    #[test]
314    fn entry_availability_classifies_point_count() {
315        let key = VoxelKey::root();
316        assert_eq!(
317            Entry {
318                key,
319                offset: 0,
320                byte_size: 0,
321                point_count: 0
322            }
323            .availability()
324            .unwrap(),
325            EntryAvailability::Empty
326        );
327        assert_eq!(
328            Entry {
329                key,
330                offset: 64,
331                byte_size: 128,
332                point_count: 42
333            }
334            .availability()
335            .unwrap(),
336            EntryAvailability::PointData { point_count: 42 }
337        );
338        assert_eq!(
339            Entry {
340                key,
341                offset: 64,
342                byte_size: 128,
343                point_count: -1
344            }
345            .availability()
346            .unwrap(),
347            EntryAvailability::ChildPage
348        );
349    }
350}
copc_core/hierarchy.rs

copc_core/
hierarchy.rs
