1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Copyright 2026 COOLJAPAN OU (Team KitaSan)
// SPDX-License-Identifier: Apache-2.0
//! Axis-aligned voxel grid backed by a compact bit vector.
//!
//! Used by the V-HACD decomposer to rasterize triangle soups and compute
//! connected components.
#![allow(dead_code)]
use bitvec::prelude::*;
use std::collections::VecDeque;
/// Axis-aligned voxel grid stored as a bit vector (1 bit per voxel).
///
/// Coordinates are uniform: all three axes use the same `step`.
pub struct VoxelGrid {
/// Occupancy bits in x-major order: `index = ix + nx*(iy + ny*iz)`.
pub occupied: BitVec,
/// World-space minimum corner of the grid.
pub origin: [f64; 3],
/// Uniform voxel size (same for all three axes).
pub step: f64,
/// Grid dimensions `[nx, ny, nz]`.
pub dims: [usize; 3],
}
impl VoxelGrid {
/// Create a new, empty grid covering `[origin, origin + dims * step]`.
pub fn new(origin: [f64; 3], step: f64, dims: [usize; 3]) -> Self {
let n = dims[0] * dims[1] * dims[2];
Self {
occupied: bitvec![0; n],
origin,
step,
dims,
}
}
/// Linear index from voxel grid coordinates (x-major storage).
#[inline]
pub fn index(&self, ix: usize, iy: usize, iz: usize) -> usize {
ix + self.dims[0] * (iy + self.dims[1] * iz)
}
/// Mark voxel `(ix, iy, iz)` as occupied.
pub fn mark(&mut self, ix: usize, iy: usize, iz: usize) {
let idx = self.index(ix, iy, iz);
self.occupied.set(idx, true);
}
/// Return true if voxel `(ix, iy, iz)` is occupied.
pub fn is_occupied(&self, ix: usize, iy: usize, iz: usize) -> bool {
let idx = self.index(ix, iy, iz);
self.occupied
.get(idx)
.map(|b| *b)
.expect("voxel index must be in bounds")
}
/// World-space centre of voxel `(ix, iy, iz)`.
pub fn voxel_center(&self, ix: usize, iy: usize, iz: usize) -> [f64; 3] {
[
self.origin[0] + (ix as f64 + 0.5) * self.step,
self.origin[1] + (iy as f64 + 0.5) * self.step,
self.origin[2] + (iz as f64 + 0.5) * self.step,
]
}
/// Volume of a single voxel.
#[inline]
pub fn voxel_volume(&self) -> f64 {
self.step * self.step * self.step
}
/// Decompose linear index back into grid coordinates.
#[inline]
fn coords_from_index(&self, idx: usize) -> (usize, usize, usize) {
let iz = idx / (self.dims[0] * self.dims[1]);
let rem = idx % (self.dims[0] * self.dims[1]);
let iy = rem / self.dims[0];
let ix = rem % self.dims[0];
(ix, iy, iz)
}
/// 6-connectivity BFS connected components of **occupied** voxels.
///
/// Returns a `Vec` where each element is the list of linear indices belonging
/// to one connected component.
pub fn connected_components(&self) -> Vec<Vec<usize>> {
let n = self.dims[0] * self.dims[1] * self.dims[2];
let mut visited: BitVec = bitvec![0; n];
let mut components: Vec<Vec<usize>> = Vec::new();
for start in 0..n {
if !self.occupied[start] || visited[start] {
continue;
}
let mut component: Vec<usize> = Vec::new();
let mut queue: VecDeque<usize> = VecDeque::new();
queue.push_back(start);
visited.set(start, true);
while let Some(idx) = queue.pop_front() {
component.push(idx);
let (ix, iy, iz) = self.coords_from_index(idx);
// 6-connectivity: ±x, ±y, ±z
let neighbors: [(i64, i64, i64); 6] = [
(1, 0, 0),
(-1, 0, 0),
(0, 1, 0),
(0, -1, 0),
(0, 0, 1),
(0, 0, -1),
];
for (dx, dy, dz) in neighbors {
let nx = ix as i64 + dx;
let ny = iy as i64 + dy;
let nz = iz as i64 + dz;
if nx < 0
|| ny < 0
|| nz < 0
|| nx >= self.dims[0] as i64
|| ny >= self.dims[1] as i64
|| nz >= self.dims[2] as i64
{
continue;
}
let nidx = self.index(nx as usize, ny as usize, nz as usize);
if self.occupied[nidx] && !visited[nidx] {
visited.set(nidx, true);
queue.push_back(nidx);
}
}
}
components.push(component);
}
components
}
/// Total number of occupied voxels.
pub fn occupied_count(&self) -> usize {
self.occupied.count_ones()
}
}