1use bytemuck::{bytes_of, pod_read_unaligned, Pod, Zeroable};
14
15pub const MAGIC_CDAG: [u8; 4] = *b"CDAG";
17
18pub const CLUSTER_DAG_SECTION_VERSION: u16 = 1;
20
21pub const CLUSTER_DAG_HEADER_SIZE: usize = 32;
23
24pub const MESHLET_CLUSTER_NODE_SIZE: usize = 64;
26
27pub const MAX_MESHLET_VERTICES: u8 = 64;
29
30pub const MAX_MESHLET_TRIANGLES: u8 = 124;
32
33pub const MAX_CLUSTER_DAG_NODES: usize = 262_144;
35
36pub const FLAG_CDAG_SEAM_LOCKED: u32 = 1 << 0;
38
39pub const FLAG_CDAG_CONE_CULLED: u32 = 1 << 1;
41
42#[repr(C)]
44#[derive(Debug, Clone, Copy, PartialEq, Eq, Pod, Zeroable)]
45pub struct ClusterDagMiniHeader {
46 pub magic: [u8; 4],
47 pub version: u16,
48 pub max_lod_depth: u16,
49 pub cluster_count: u32,
50 pub group_count: u32,
51 pub total_meshlet_vertices: u32,
52 pub total_meshlet_triangles: u32,
53 pub root_cluster_offset: u32,
54 pub flags: u32,
55}
56
57const _: () = assert!(core::mem::size_of::<ClusterDagMiniHeader>() == CLUSTER_DAG_HEADER_SIZE);
58
59impl Default for ClusterDagMiniHeader {
60 fn default() -> Self {
61 Self {
62 magic: MAGIC_CDAG,
63 version: CLUSTER_DAG_SECTION_VERSION,
64 max_lod_depth: 0,
65 cluster_count: 0,
66 group_count: 0,
67 total_meshlet_vertices: 0,
68 total_meshlet_triangles: 0,
69 root_cluster_offset: 0,
70 flags: FLAG_CDAG_SEAM_LOCKED | FLAG_CDAG_CONE_CULLED,
71 }
72 }
73}
74
75#[repr(C, align(64))]
77#[derive(Debug, Clone, Copy, PartialEq, Pod, Zeroable)]
78pub struct MeshletClusterNode {
79 pub bounding_sphere: [f32; 4],
81 pub parent_error_sphere: [f32; 4],
83 pub lod_error_self: f32,
85 pub lod_error_parent: f32,
87 pub cone_axis_oct16: [i16; 2],
89 pub cone_cutoff_snorm16: i16,
91 pub lod_level: u8,
93 pub vertex_count: u8,
95 pub triangle_count: u8,
97 pub material_slot: u8,
99 pub child_group_first: u16,
101 pub vertex_data_offset: u32,
103 pub triangle_data_offset: u32,
105 pub semantic_subpart_id: u32,
107}
108
109const _: () = assert!(core::mem::size_of::<MeshletClusterNode>() == 64);
110const _: () = assert!(core::mem::align_of::<MeshletClusterNode>() == 64);
111
112#[derive(Debug, Clone, PartialEq)]
114pub enum ClusterDagSectionError {
115 PayloadTooShort {
116 need: usize,
117 have: usize,
118 },
119 BadMagic([u8; 4]),
120 UnsupportedVersion(u16),
121 TooManyClusters {
122 count: usize,
123 max: usize,
124 },
125 PayloadLengthMismatch {
126 declared_clusters: u32,
127 payload_bytes: usize,
128 },
129 BufferTooSmall {
130 need: usize,
131 have: usize,
132 },
133 NonMonotonicError {
134 cluster_index: usize,
135 self_error: f32,
136 parent_error: f32,
137 },
138 InvalidBoundingSphere {
139 cluster_index: usize,
140 },
141 MeshletLimitExceeded {
142 cluster_index: usize,
143 vertices: u8,
144 triangles: u8,
145 },
146 InvalidCameraParameters,
147}
148
149impl core::fmt::Display for ClusterDagSectionError {
150 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
151 match self {
152 Self::PayloadTooShort { need, have } => {
153 write!(f, "CDAG payload too short: have {have}, need {need}")
154 }
155 Self::BadMagic(m) => write!(f, "CDAG bad magic: {m:?}"),
156 Self::UnsupportedVersion(v) => write!(f, "CDAG unsupported version: {v}"),
157 Self::TooManyClusters { count, max } => {
158 write!(f, "CDAG cluster count {count} exceeds max {max}")
159 }
160 Self::PayloadLengthMismatch {
161 declared_clusters,
162 payload_bytes,
163 } => write!(
164 f,
165 "CDAG payload length {payload_bytes} does not match {declared_clusters} clusters"
166 ),
167 Self::BufferTooSmall { need, have } => {
168 write!(f, "CDAG buffer too small: have {have}, need {need}")
169 }
170 Self::NonMonotonicError {
171 cluster_index,
172 self_error,
173 parent_error,
174 } => write!(
175 f,
176 "CDAG cluster[{cluster_index}] violates monotonic error: self={self_error} > parent={parent_error}"
177 ),
178 Self::InvalidBoundingSphere { cluster_index } => {
179 write!(f, "CDAG cluster[{cluster_index}] has invalid bounding sphere")
180 }
181 Self::MeshletLimitExceeded {
182 cluster_index,
183 vertices,
184 triangles,
185 } => write!(
186 f,
187 "CDAG cluster[{cluster_index}] exceeds meshlet limits: {vertices} verts, {triangles} tris"
188 ),
189 Self::InvalidCameraParameters => write!(f, "CDAG invalid viewport or FOV parameters"),
190 }
191 }
192}
193
194impl std::error::Error for ClusterDagSectionError {}
195
196#[inline]
198pub const fn cluster_dag_encoded_len(cluster_count: usize) -> Option<usize> {
199 if cluster_count > MAX_CLUSTER_DAG_NODES {
200 return None;
201 }
202 match cluster_count.checked_mul(MESHLET_CLUSTER_NODE_SIZE) {
203 Some(body) => CLUSTER_DAG_HEADER_SIZE.checked_add(body),
204 None => None,
205 }
206}
207
208#[inline]
210pub fn encode_oct16_normal(dir: [f32; 3]) -> [i16; 2] {
211 let len = (dir[0] * dir[0] + dir[1] * dir[1] + dir[2] * dir[2]).sqrt();
212 let (mut x, mut y, z) = if len > 1e-6 && len.is_finite() {
213 (dir[0] / len, dir[1] / len, dir[2] / len)
214 } else {
215 (0.0, 0.0, 1.0)
216 };
217 let l1 = (x.abs() + y.abs() + z.abs()).max(1e-6);
218 x /= l1;
219 y /= l1;
220 if z < 0.0 {
221 let ox = (1.0 - y.abs()) * if x >= 0.0 { 1.0 } else { -1.0 };
222 let oy = (1.0 - x.abs()) * if y >= 0.0 { 1.0 } else { -1.0 };
223 x = ox;
224 y = oy;
225 }
226 [
227 (x.clamp(-1.0, 1.0) * 32767.0).round() as i16,
228 (y.clamp(-1.0, 1.0) * 32767.0).round() as i16,
229 ]
230}
231
232#[inline]
234pub fn decode_oct16_normal(oct: [i16; 2]) -> [f32; 3] {
235 let mut x = (oct[0] as f32 / 32767.0).clamp(-1.0, 1.0);
236 let mut y = (oct[1] as f32 / 32767.0).clamp(-1.0, 1.0);
237 let z = 1.0 - x.abs() - y.abs();
238 if z < 0.0 {
239 let old_x = x;
240 x = (1.0 - y.abs()) * if old_x >= 0.0 { 1.0 } else { -1.0 };
241 y = (1.0 - old_x.abs()) * if y >= 0.0 { 1.0 } else { -1.0 };
242 }
243 let len = (x * x + y * y + z * z).sqrt();
244 if len > 1e-6 {
245 [x / len, y / len, z / len]
246 } else {
247 [0.0, 0.0, 1.0]
248 }
249}
250
251fn validate_cluster_node(
252 index: usize,
253 node: &MeshletClusterNode,
254) -> Result<(), ClusterDagSectionError> {
255 let r_self = node.bounding_sphere[3];
256 let r_parent = node.parent_error_sphere[3];
257 if !node.bounding_sphere[0].is_finite()
258 || !node.bounding_sphere[1].is_finite()
259 || !node.bounding_sphere[2].is_finite()
260 || !r_self.is_finite()
261 || r_self <= 0.0
262 || !node.parent_error_sphere[0].is_finite()
263 || !node.parent_error_sphere[1].is_finite()
264 || !node.parent_error_sphere[2].is_finite()
265 || !r_parent.is_finite()
266 || r_parent < r_self
267 {
268 return Err(ClusterDagSectionError::InvalidBoundingSphere {
269 cluster_index: index,
270 });
271 }
272 if !node.lod_error_self.is_finite()
273 || node.lod_error_self < 0.0
274 || node.lod_error_parent.is_nan()
275 || node.lod_error_parent < node.lod_error_self
276 {
277 return Err(ClusterDagSectionError::NonMonotonicError {
278 cluster_index: index,
279 self_error: node.lod_error_self,
280 parent_error: node.lod_error_parent,
281 });
282 }
283 if node.vertex_count == 0
284 || node.vertex_count > MAX_MESHLET_VERTICES
285 || node.triangle_count == 0
286 || node.triangle_count > MAX_MESHLET_TRIANGLES
287 {
288 return Err(ClusterDagSectionError::MeshletLimitExceeded {
289 cluster_index: index,
290 vertices: node.vertex_count,
291 triangles: node.triangle_count,
292 });
293 }
294 Ok(())
295}
296
297pub fn encode_cluster_dag_section(
299 header: &ClusterDagMiniHeader,
300 nodes: &[MeshletClusterNode],
301 out: &mut [u8],
302) -> Result<usize, ClusterDagSectionError> {
303 if header.magic != MAGIC_CDAG {
304 return Err(ClusterDagSectionError::BadMagic(header.magic));
305 }
306 if header.version != CLUSTER_DAG_SECTION_VERSION {
307 return Err(ClusterDagSectionError::UnsupportedVersion(header.version));
308 }
309 let needed = cluster_dag_encoded_len(nodes.len()).ok_or(
310 ClusterDagSectionError::TooManyClusters {
311 count: nodes.len(),
312 max: MAX_CLUSTER_DAG_NODES,
313 },
314 )?;
315 if out.len() < needed {
316 return Err(ClusterDagSectionError::BufferTooSmall {
317 need: needed,
318 have: out.len(),
319 });
320 }
321 for (idx, node) in nodes.iter().enumerate() {
322 validate_cluster_node(idx, node)?;
323 }
324
325 let mut canonical_header = *header;
326 canonical_header.cluster_count = nodes.len() as u32;
327 out[..CLUSTER_DAG_HEADER_SIZE].copy_from_slice(bytes_of(&canonical_header));
328
329 let mut offset = CLUSTER_DAG_HEADER_SIZE;
330 for node in nodes {
331 out[offset..offset + MESHLET_CLUSTER_NODE_SIZE].copy_from_slice(bytes_of(node));
332 offset += MESHLET_CLUSTER_NODE_SIZE;
333 }
334 Ok(needed)
335}
336
337pub fn decode_cluster_dag_section(
339 payload: &[u8],
340 out_nodes: &mut [MeshletClusterNode],
341) -> Result<(ClusterDagMiniHeader, usize), ClusterDagSectionError> {
342 if payload.len() < CLUSTER_DAG_HEADER_SIZE {
343 return Err(ClusterDagSectionError::PayloadTooShort {
344 need: CLUSTER_DAG_HEADER_SIZE,
345 have: payload.len(),
346 });
347 }
348 let header: ClusterDagMiniHeader = pod_read_unaligned(&payload[..CLUSTER_DAG_HEADER_SIZE]);
349 if header.magic != MAGIC_CDAG {
350 return Err(ClusterDagSectionError::BadMagic(header.magic));
351 }
352 if header.version != CLUSTER_DAG_SECTION_VERSION {
353 return Err(ClusterDagSectionError::UnsupportedVersion(header.version));
354 }
355 let count = header.cluster_count as usize;
356 let needed_bytes = cluster_dag_encoded_len(count).ok_or(
357 ClusterDagSectionError::TooManyClusters {
358 count,
359 max: MAX_CLUSTER_DAG_NODES,
360 },
361 )?;
362 if payload.len() != needed_bytes {
363 return Err(ClusterDagSectionError::PayloadLengthMismatch {
364 declared_clusters: header.cluster_count,
365 payload_bytes: payload.len(),
366 });
367 }
368 if out_nodes.len() < count {
369 return Err(ClusterDagSectionError::BufferTooSmall {
370 need: count,
371 have: out_nodes.len(),
372 });
373 }
374
375 let mut offset = CLUSTER_DAG_HEADER_SIZE;
376 for (idx, slot) in out_nodes[..count].iter_mut().enumerate() {
377 let node: MeshletClusterNode =
378 pod_read_unaligned(&payload[offset..offset + MESHLET_CLUSTER_NODE_SIZE]);
379 validate_cluster_node(idx, &node)?;
380 *slot = node;
381 offset += MESHLET_CLUSTER_NODE_SIZE;
382 }
383 Ok((header, count))
384}
385
386#[inline]
388pub fn project_sphere_error_px(
389 sphere: [f32; 4],
390 world_error: f32,
391 camera_pos: [f32; 3],
392 proj_scale: f32,
393) -> f32 {
394 if world_error.is_infinite() {
395 return f32::INFINITY;
396 }
397 let dx = sphere[0] - camera_pos[0];
398 let dy = sphere[1] - camera_pos[1];
399 let dz = sphere[2] - camera_pos[2];
400 let center_dist = (dx * dx + dy * dy + dz * dz).sqrt();
401 let surface_dist = (center_dist - sphere[3]).max(1e-4);
402 (world_error * proj_scale) / surface_dist
403}
404
405pub fn select_cut_clusters_zero_heap(
409 nodes: &[MeshletClusterNode],
410 camera_pos: [f32; 3],
411 viewport_height_px: f32,
412 fov_y_rad: f32,
413 error_threshold_px: f32,
414 out_cluster_indices: &mut [u32],
415) -> Result<usize, ClusterDagSectionError> {
416 if !viewport_height_px.is_finite()
417 || viewport_height_px <= 0.0
418 || !fov_y_rad.is_finite()
419 || fov_y_rad <= 0.0
420 || fov_y_rad >= core::f32::consts::PI
421 || !error_threshold_px.is_finite()
422 || error_threshold_px < 0.0
423 {
424 return Err(ClusterDagSectionError::InvalidCameraParameters);
425 }
426 let half_tan = (0.5 * fov_y_rad).tan();
427 if !(half_tan > 1e-6) || !half_tan.is_finite() {
428 return Err(ClusterDagSectionError::InvalidCameraParameters);
429 }
430 let proj_scale = viewport_height_px / (2.0 * half_tan);
431
432 let mut selected = 0usize;
433 for (idx, node) in nodes.iter().enumerate() {
434 let err_self = project_sphere_error_px(
435 node.bounding_sphere,
436 node.lod_error_self,
437 camera_pos,
438 proj_scale,
439 );
440 let err_parent = project_sphere_error_px(
441 node.parent_error_sphere,
442 node.lod_error_parent,
443 camera_pos,
444 proj_scale,
445 );
446 if err_self <= error_threshold_px && err_parent > error_threshold_px {
447 if selected >= out_cluster_indices.len() {
448 return Err(ClusterDagSectionError::BufferTooSmall {
449 need: selected + 1,
450 have: out_cluster_indices.len(),
451 });
452 }
453 out_cluster_indices[selected] = idx as u32;
454 selected += 1;
455 }
456 }
457 Ok(selected)
458}
459
460#[cfg(test)]
461mod tests {
462 use super::*;
463
464 fn sample_dag_nodes() -> [MeshletClusterNode; 3] {
465 let axis = encode_oct16_normal([0.0, 0.0, 1.0]);
466 [
467 MeshletClusterNode {
469 bounding_sphere: [-0.5, 0.0, 0.0, 1.0],
470 parent_error_sphere: [0.0, 0.0, 0.0, 2.0],
471 lod_error_self: 0.0,
472 lod_error_parent: 0.02,
473 cone_axis_oct16: axis,
474 cone_cutoff_snorm16: 0,
475 lod_level: 0,
476 vertex_count: 64,
477 triangle_count: 120,
478 material_slot: 0,
479 child_group_first: 0xFFFF,
480 vertex_data_offset: 0,
481 triangle_data_offset: 0,
482 semantic_subpart_id: 0x1001,
483 },
484 MeshletClusterNode {
486 bounding_sphere: [0.5, 0.0, 0.0, 1.0],
487 parent_error_sphere: [0.0, 0.0, 0.0, 2.0],
488 lod_error_self: 0.0,
489 lod_error_parent: 0.02,
490 cone_axis_oct16: axis,
491 cone_cutoff_snorm16: 0,
492 lod_level: 0,
493 vertex_count: 64,
494 triangle_count: 120,
495 material_slot: 0,
496 child_group_first: 0xFFFF,
497 vertex_data_offset: 64,
498 triangle_data_offset: 360,
499 semantic_subpart_id: 0x1002,
500 },
501 MeshletClusterNode {
503 bounding_sphere: [0.0, 0.0, 0.0, 2.0],
504 parent_error_sphere: [0.0, 0.0, 0.0, 2.0],
505 lod_error_self: 0.02,
506 lod_error_parent: f32::INFINITY,
507 cone_axis_oct16: axis,
508 cone_cutoff_snorm16: 0,
509 lod_level: 1,
510 vertex_count: 64,
511 triangle_count: 120,
512 material_slot: 0,
513 child_group_first: 0,
514 vertex_data_offset: 128,
515 triangle_data_offset: 720,
516 semantic_subpart_id: 0x1000,
517 },
518 ]
519 }
520
521 #[test]
522 fn cdag_layout_and_roundtrip() {
523 assert_eq!(core::mem::size_of::<ClusterDagMiniHeader>(), 32);
524 assert_eq!(core::mem::size_of::<MeshletClusterNode>(), 64);
525
526 let nodes = sample_dag_nodes();
527 let header = ClusterDagMiniHeader {
528 max_lod_depth: 1,
529 cluster_count: 3,
530 group_count: 1,
531 total_meshlet_vertices: 192,
532 total_meshlet_triangles: 360,
533 root_cluster_offset: 2,
534 ..ClusterDagMiniHeader::default()
535 };
536 let mut buf = [0u8; 32 + 3 * 64];
537 let written = encode_cluster_dag_section(&header, &nodes, &mut buf).unwrap();
538 assert_eq!(written, buf.len());
539
540 let mut decoded = [MeshletClusterNode::zeroed(); 3];
541 let (dec_hdr, count) = decode_cluster_dag_section(&buf, &mut decoded).unwrap();
542 assert_eq!(count, 3);
543 assert_eq!(dec_hdr, header);
544 assert_eq!(decoded, nodes);
545 }
546
547 #[test]
548 fn cdag_cut_selection_transitions_between_leaf_and_root() {
549 let nodes = sample_dag_nodes();
550 let mut cut = [0u32; 4];
551
552 let near_count = select_cut_clusters_zero_heap(
554 &nodes,
555 [0.0, 0.0, 4.0],
556 1080.0,
557 core::f32::consts::FRAC_PI_3,
558 1.0,
559 &mut cut,
560 )
561 .unwrap();
562 assert_eq!(&cut[..near_count], &[0, 1]);
563
564 let far_count = select_cut_clusters_zero_heap(
566 &nodes,
567 [0.0, 0.0, 50.0],
568 1080.0,
569 core::f32::consts::FRAC_PI_3,
570 1.0,
571 &mut cut,
572 )
573 .unwrap();
574 assert_eq!(&cut[..far_count], &[2]);
575 }
576}