spatialrust_gpu/kernels/
voxel_segments.rs

1/// Sorted voxel cell segments derived from per-point grid keys.
2#[derive(Clone, Debug, PartialEq, Eq)]
3pub struct VoxelSegments {
4    /// Unique voxel keys in sorted order.
5    pub keys: Vec<(i64, i64, i64)>,
6    /// Point indices sorted by voxel key.
7    pub point_indices: Vec<u32>,
8    /// Start offset into `point_indices` for each cell.
9    pub cell_starts: Vec<u32>,
10    /// Number of points in each cell.
11    pub cell_counts: Vec<u32>,
12}
13
14impl VoxelSegments {
15    /// Returns the number of occupied voxel cells.
16    #[must_use]
17    pub fn len(&self) -> usize {
18        self.keys.len()
19    }
20
21    /// Returns whether no voxel cells were found.
22    #[must_use]
23    pub fn is_empty(&self) -> bool {
24        self.keys.is_empty()
25    }
26}
27
28/// Builds sorted voxel segments from per-point `(ix, iy, iz)` keys.
29#[must_use]
30pub fn build_voxel_segments(keys: &[(i64, i64, i64)]) -> VoxelSegments {
31    if keys.is_empty() {
32        return VoxelSegments {
33            keys: Vec::new(),
34            point_indices: Vec::new(),
35            cell_starts: Vec::new(),
36            cell_counts: Vec::new(),
37        };
38    }
39
40    let mut order: Vec<usize> = (0..keys.len()).collect();
41    order.sort_by_key(|&index| keys[index]);
42
43    let sorted_keys: Vec<(i64, i64, i64)> = order.iter().map(|&index| keys[index]).collect();
44    let sorted_indices: Vec<u32> = order.iter().map(|&index| index as u32).collect();
45    compact_voxel_segments_from_sorted(&sorted_keys, &sorted_indices)
46}
47
48/// Compacts already-sorted voxel keys and point indices into segment metadata.
49#[must_use]
50pub fn compact_voxel_segments_from_sorted(
51    sorted_keys: &[(i64, i64, i64)],
52    sorted_indices: &[u32],
53) -> VoxelSegments {
54    assert_eq!(sorted_keys.len(), sorted_indices.len());
55
56    if sorted_keys.is_empty() {
57        return VoxelSegments {
58            keys: Vec::new(),
59            point_indices: Vec::new(),
60            cell_starts: Vec::new(),
61            cell_counts: Vec::new(),
62        };
63    }
64
65    let mut segments = VoxelSegments {
66        keys: Vec::new(),
67        point_indices: Vec::with_capacity(sorted_indices.len()),
68        cell_starts: Vec::new(),
69        cell_counts: Vec::new(),
70    };
71
72    let mut cursor = 0usize;
73    while cursor < sorted_keys.len() {
74        let key = sorted_keys[cursor];
75        let cell_start = segments.point_indices.len() as u32;
76        let mut count = 0u32;
77
78        while cursor < sorted_keys.len() && sorted_keys[cursor] == key {
79            segments.point_indices.push(sorted_indices[cursor]);
80            count += 1;
81            cursor += 1;
82        }
83
84        segments.keys.push(key);
85        segments.cell_starts.push(cell_start);
86        segments.cell_counts.push(count);
87    }
88
89    for cell_index in 0..segments.len() {
90        let start = segments.cell_starts[cell_index] as usize;
91        let end = start + segments.cell_counts[cell_index] as usize;
92        segments.point_indices[start..end].sort_unstable();
93    }
94
95    segments
96}
97
98#[cfg(test)]
99mod tests {
100    use super::build_voxel_segments;
101
102    #[test]
103    fn groups_points_by_voxel_key() {
104        let keys = vec![(0, 0, 0), (1, 0, 0), (0, 0, 0), (1, 0, 0)];
105        let segments = build_voxel_segments(&keys);
106        assert_eq!(segments.len(), 2);
107        assert_eq!(segments.cell_counts, vec![2, 2]);
108        assert_eq!(segments.point_indices, vec![0, 2, 1, 3]);
109    }
110}
spatialrust_gpu/kernels/voxel_segments.rs

spatialrust_gpu/kernels/
voxel_segments.rs
