geometry_dag/
meshlet_builder.rs

1//! 贪心簇(meshlet)划分:按输入三角形序装箱,顶点/三角形双上限,flush 前移判定。
2//!
3//! 与 TS 权威实现(`packages/deep-engine/src/geometry/meshletBuilder.ts`)逐位对拍:
4//! 输出描述符布局、顶点表拼接序、局部三角形打包、包围体排布全部一致。
5
6use crate::bounds::{compute_meshlet_bounds, triangle_normal};
7use crate::error::{DagError, DagResult};
8use crate::local_triangle::pack_local_triangle;
9use crate::types::{
10    IndexedGeometry, MESHLET_BOUNDS_STRIDE, MESHLET_DESCRIPTOR_STRIDE, MESHLET_SCHEMA_VERSION,
11    OUTPUT_MESHLETS_BUDGET, PendingMeshlet,
12};
13use crate::validation::{budget, validate_input, ValidatedInput};
14
15/// 输出字节预算(TS `MESHLET_BUILD_BUDGETS.outputBytes`,512 MiB)。
16const OUTPUT_BYTES_BUDGET: u64 = 512 * 1024 * 1024;
17
18/// 单次簇划分输出(与 TS `MeshletBuildResult` 同构)。
19#[derive(Debug, Clone)]
20pub struct MeshletBuildResult {
21    /// schema 版本。
22    pub schema_version: u32,
23    /// 源顶点数。
24    pub source_vertex_count: usize,
25    /// 源三角形数。
26    pub source_triangle_count: usize,
27    /// 簇数。
28    pub meshlet_count: usize,
29    /// 本次构建采用的簇顶点上限。
30    pub max_vertices: u32,
31    /// 本次构建采用的簇三角形上限。
32    pub max_triangles: u32,
33    /// 簇描述符 `[vertexOffset, vertexCount, triangleOffset, triangleCount]` × n。
34    pub descriptors: Vec<u32>,
35    /// 拼接的全局顶点表(局部→全局映射)。
36    pub vertex_remap: Vec<u32>,
37    /// 打包局部三角形(低 24 位:三个 8-bit 局部索引)。
38    pub local_triangle_indices: Vec<u32>,
39    /// 包围体(16 f32 × n,布局见 [`crate::bounds::MeshletBounds::to_flat`])。
40    pub bounds: Vec<f32>,
41}
42
43impl MeshletBuildResult {
44    /// 簇 `i` 的输出三角形段 `[start, end)`,与簇序一致(descriptors 三角形数前缀和)。
45    ///
46    /// 返回长度为 `2 * meshlet_count` 的平铺段表。
47    #[must_use]
48    pub fn cluster_output_spans(&self) -> Vec<u32> {
49        let mut spans = Vec::with_capacity(self.meshlet_count * 2);
50        let mut start = 0u32;
51        for i in 0..self.meshlet_count {
52            let count = self.descriptors[i * MESHLET_DESCRIPTOR_STRIDE + 3];
53            spans.push(start);
54            spans.push(start + count);
55            start += count;
56        }
57        spans
58    }
59}
60
61/// 对索引化三角形网格做贪心簇划分。
62///
63/// 算法与 TS `buildMeshlets` 一致:按输入序逐三角形装箱;加入新三角形前先判
64/// `triangleCount >= maxTriangles || vertexCount + addedVertices > maxVertices`,
65/// 触顶即 flush;局部顶点按首次出现序编号。
66///
67/// # Errors
68/// 输入非法(见 [`validate_input`])或超出输出预算(簇数 / 总字节)时返回错误。
69pub fn build_meshlets(
70    geometry: &IndexedGeometry,
71    max_vertices: Option<u32>,
72    max_triangles: Option<u32>,
73) -> DagResult<MeshletBuildResult> {
74    let input: ValidatedInput = validate_input(geometry, max_vertices, max_triangles)?;
75    let positions: &[f32] = &input.geometry.positions;
76
77    let mut output = Accumulator::default();
78    let mut pending = PendingMeshlet::new();
79    let indices = &input.geometry.indices;
80    let mut offset = 0;
81    while offset < indices.len() {
82        let global = [indices[offset], indices[offset + 1], indices[offset + 2]];
83        let mut added_vertices = if pending.contains_global(global[0]) { 0 } else { 1 };
84        if global[1] != global[0] && !pending.contains_global(global[1]) {
85            added_vertices += 1;
86        }
87        if global[2] != global[0] && global[2] != global[1] && !pending.contains_global(global[2]) {
88            added_vertices += 1;
89        }
90        if pending.triangles.len() as u32 >= input.max_triangles
91            || pending.vertices.len() as u32 + added_vertices as u32 > input.max_vertices
92        {
93            output.flush(positions, &mut pending)?;
94        }
95        let local = [
96            pending.local_vertex(global[0]),
97            pending.local_vertex(global[1]),
98            pending.local_vertex(global[2]),
99        ];
100        pending
101            .triangles
102            .push(pack_local_triangle(local[0], local[1], local[2])?);
103        match triangle_normal(positions, global[0], global[1], global[2]) {
104            Some(normal) => pending.normals.push(normal),
105            None => pending.has_degenerate = true,
106        }
107        offset += 3;
108    }
109    output.flush(positions, &mut pending)?;
110
111    Ok(MeshletBuildResult {
112        schema_version: MESHLET_SCHEMA_VERSION,
113        source_vertex_count: input.geometry.vertex_count(),
114        source_triangle_count: input.geometry.triangle_count(),
115        meshlet_count: output.descriptors.len() / MESHLET_DESCRIPTOR_STRIDE,
116        max_vertices: input.max_vertices,
117        max_triangles: input.max_triangles,
118        descriptors: output.descriptors,
119        vertex_remap: output.remap,
120        local_triangle_indices: output.triangles,
121        bounds: output.bounds,
122    })
123}
124
125/// 输出累积器:把 `PendingMeshlet` 固化为描述符 + 顶点表 + 局部三角形 + 包围体,
126/// 并逐次执行簇数 / 字节预算护栏(与 TS `flush` + `assertOutputBudget` 等价)。
127#[derive(Default)]
128struct Accumulator {
129    descriptors: Vec<u32>,
130    remap: Vec<u32>,
131    triangles: Vec<u32>,
132    bounds: Vec<f32>,
133}
134
135impl Accumulator {
136    fn flush(&mut self, positions: &[f32], pending: &mut PendingMeshlet) -> DagResult<()> {
137        if pending.triangles.is_empty() {
138            return Ok(());
139        }
140        budget(
141            (self.descriptors.len() / MESHLET_DESCRIPTOR_STRIDE + 1) as u64,
142            OUTPUT_MESHLETS_BUDGET,
143            "output meshlets",
144        )?;
145        self.descriptors.extend_from_slice(&[
146            self.remap.len() as u32,
147            pending.vertices.len() as u32,
148            self.triangles.len() as u32,
149            pending.triangles.len() as u32,
150        ]);
151        self.remap.extend_from_slice(&pending.vertices);
152        self.triangles.extend_from_slice(&pending.triangles);
153        let meshlet_bounds =
154            compute_meshlet_bounds(positions, &pending.vertices, &pending.normals, pending.has_degenerate)?;
155        self.bounds.extend_from_slice(&meshlet_bounds.to_flat());
156        assert_output_budget(
157            self.descriptors.len(),
158            self.remap.len(),
159            self.triangles.len(),
160            self.bounds.len(),
161        )?;
162        *pending = PendingMeshlet::new();
163        Ok(())
164    }
165}
166
167/// TS `assertOutputBudget`:输出总量与布局对齐护栏。
168fn assert_output_budget(
169    descriptors: usize,
170    remap: usize,
171    triangles: usize,
172    bounds: usize,
173) -> DagResult<()> {
174    let bytes = (descriptors + remap + triangles + bounds) as u64 * 4;
175    if bytes > OUTPUT_BYTES_BUDGET {
176        return Err(DagError::budget_exceeded(
177            format!("Meshlet output exceeds {OUTPUT_BYTES_BUDGET} bytes"),
178            OUTPUT_BYTES_BUDGET,
179        ));
180    }
181    if !bounds.is_multiple_of(MESHLET_BOUNDS_STRIDE) {
182        return Err(DagError::overflow("Meshlet bounds layout is misaligned."));
183    }
184    Ok(())
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190    use crate::types::IndexedGeometry;
191
192    fn triangle_grid(triangles: usize) -> IndexedGeometry {
193        // 一串共享一条边的退化安全三角形(独立顶点,便于触发顶点上限)。
194        let mut positions = Vec::new();
195        let mut indices = Vec::new();
196        for t in 0..triangles {
197            let base = (t * 3) as u32;
198            positions.extend_from_slice(&[t as f32, 0.0, 0.0, t as f32 + 1.0, 0.0, 0.0, t as f32, 1.0, 0.0]);
199            indices.extend_from_slice(&[base, base + 1, base + 2]);
200        }
201        IndexedGeometry { positions, indices }
202    }
203
204    #[test]
205    fn empty_mesh_yields_zero_meshlets() {
206        let g = IndexedGeometry { positions: vec![], indices: vec![] };
207        let r = build_meshlets(&g, None, None).expect("empty ok");
208        assert_eq!(r.meshlet_count, 0);
209        assert!(r.descriptors.is_empty());
210        assert!(r.bounds.is_empty());
211    }
212
213    #[test]
214    fn single_triangle_single_meshlet() {
215        let g = triangle_grid(1);
216        let r = build_meshlets(&g, None, None).expect("build");
217        assert_eq!(r.meshlet_count, 1);
218        assert_eq!(r.descriptors, [0, 3, 0, 1]);
219        assert_eq!(r.vertex_remap, [0, 1, 2]);
220        assert_eq!(r.local_triangle_indices, [(1 << 8) | 2 << 16]);
221    }
222
223    #[test]
224    fn flushes_on_triangle_limit() {
225        // 独立顶点网格下 maxVertices=64 先触发(每簇 21 三角形);把 maxTriangles 压到 4,
226        // 使三角形上限成为约束,验证 flush-on-triangle-limit 路径本身。
227        let g = triangle_grid(200);
228        let r = build_meshlets(&g, None, Some(4)).expect("build");
229        assert_eq!(r.source_triangle_count, 200);
230        let counts: Vec<u32> = (0..r.meshlet_count).map(|i| r.descriptors[i * 4 + 3]).collect();
231        assert_eq!(counts.first(), Some(&4));
232        assert_eq!(counts.last(), Some(&4)); // 200 % 4 == 0,批批打满
233        assert_eq!(counts.iter().sum::<u32>(), 200);
234        assert_eq!(r.meshlet_count, 50);
235    }
236
237    #[test]
238    fn flushes_on_vertex_limit_with_independent_vertices() {
239        // 每三角形 3 个独立顶点:顶点上限 64 → 每簇 21 三角形(63 顶点,第 22 个超限)。
240        let g = triangle_grid(200);
241        let r = build_meshlets(&g, Some(64), Some(64)).expect("build");
242        let vertex_counts: Vec<u32> = (0..r.meshlet_count).map(|i| r.descriptors[i * 4 + 1]).collect();
243        assert!(vertex_counts.iter().all(|&c| c <= 64));
244        let tri_counts: Vec<u32> = (0..r.meshlet_count).map(|i| r.descriptors[i * 4 + 3]).collect();
245        assert_eq!(tri_counts.iter().sum::<u32>(), 200);
246        assert!(tri_counts.iter().all(|&c| c <= 21), "independent-vertex grid caps at 21 tris/cluster, got {tri_counts:?}");
247    }
248
249    #[test]
250    fn flushes_on_vertex_limit() {
251        // 每三角形 3 个独立顶点,maxVertices=8 → 每 2 个三角形 flush(6 顶点,第 3 个到 9)。
252        let g = triangle_grid(10);
253        let r = build_meshlets(&g, Some(8), Some(64)).expect("build");
254        let counts: Vec<u32> = (0..r.meshlet_count).map(|i| r.descriptors[i * 4 + 1]).collect();
255        assert!(counts.iter().all(|&c| c <= 8));
256        let tri_counts: Vec<u32> = (0..r.meshlet_count).map(|i| r.descriptors[i * 4 + 3]).collect();
257        assert_eq!(tri_counts.iter().sum::<u32>(), 10);
258        assert!(tri_counts.iter().all(|&c| c == 2), "expect 2 tris per cluster, got {tri_counts:?}");
259        assert_eq!(r.meshlet_count, 5);
260    }
261
262    #[test]
263    fn duplicate_vertices_share_local_index() {
264        // 两个三角形共享全部顶点(重合三角形):同一 meshlet 内局部索引复用。
265        let g = IndexedGeometry {
266            positions: vec![0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0],
267            indices: vec![0, 1, 2, 0, 1, 2],
268        };
269        let r = build_meshlets(&g, None, None).expect("build");
270        assert_eq!(r.meshlet_count, 1);
271        assert_eq!(r.descriptors, [0, 3, 0, 2]); // 3 顶点 2 三角形
272    }
273
274    #[test]
275    fn degenerate_triangle_disables_cone() {
276        // 共线三角形:法向锥必须禁用(cutoff = -1),包围体仍输出。
277        let g = IndexedGeometry {
278            positions: vec![0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 2.0, 0.0, 0.0],
279            indices: vec![0, 1, 2],
280        };
281        let r = build_meshlets(&g, None, None).expect("build");
282        assert_eq!(r.meshlet_count, 1);
283        let cone = &r.bounds[12..16];
284        assert_eq!(cone, [0.0, 0.0, 1.0, -1.0]);
285    }
286
287    #[test]
288    fn cluster_output_spans_prefix_sum() {
289        let g = triangle_grid(200);
290        let r = build_meshlets(&g, None, Some(64)).expect("build");
291        let spans = r.cluster_output_spans();
292        assert_eq!(spans.len(), r.meshlet_count * 2);
293        assert_eq!(spans[0], 0);
294        for i in 1..r.meshlet_count {
295            assert_eq!(spans[i * 2], spans[i * 2 - 1]);
296        }
297        assert_eq!(spans.last(), Some(&200));
298    }
299}
geometry_dag/meshlet_builder.rs

geometry_dag/
meshlet_builder.rs
