Skip to main content

qualia_core_db/container_10d/
cluster_dag_section.rs

1//! Section 23 (`CDAG`): Nanite-Style Hierarchical Meshlet Cluster DAG Section.
2//!
3//! Encodes a continuous level-of-detail (CLOD) directed acyclic graph of 64-byte
4//! cache-line-aligned meshlet clusters (`MeshletClusterNode`) preceded by a 32-byte
5//! header (`ClusterDagMiniHeader`).
6//!
7//! Each cluster stores its own bounding sphere and quadric error (`lod_error_self`)
8//! alongside its parent group's bounding sphere and error (`lod_error_parent`),
9//! satisfying the monotonic DAG cut invariant `lod_error_parent >= lod_error_self`.
10//! At runtime, GPU compute or CPU zero-heap traversal selects the cut where:
11//! `projected_error(self) <= threshold_px < projected_error(parent)`.
12
13use bytemuck::{bytes_of, pod_read_unaligned, Pod, Zeroable};
14
15/// 4-byte ASCII magic for `.10d` Cluster DAG sections (`"CDAG"`).
16pub const MAGIC_CDAG: [u8; 4] = *b"CDAG";
17
18/// Current format version of the `CDAG` section.
19pub const CLUSTER_DAG_SECTION_VERSION: u16 = 1;
20
21/// Fixed byte size of [`ClusterDagMiniHeader`].
22pub const CLUSTER_DAG_HEADER_SIZE: usize = 32;
23
24/// Fixed byte size of [`MeshletClusterNode`].
25pub const MESHLET_CLUSTER_NODE_SIZE: usize = 64;
26
27/// Maximum vertices allowed in a single hardware meshlet cluster.
28pub const MAX_MESHLET_VERTICES: u8 = 64;
29
30/// Maximum triangles allowed in a single hardware meshlet cluster.
31pub const MAX_MESHLET_TRIANGLES: u8 = 124;
32
33/// Maximum cluster nodes admitted in a single `CDAG` section.
34pub const MAX_CLUSTER_DAG_NODES: usize = 262_144;
35
36/// Cluster border vertices were seam-locked during hierarchical QEM simplification.
37pub const FLAG_CDAG_SEAM_LOCKED: u32 = 1 << 0;
38
39/// Normal cone axis and cutoff are populated for backface cluster culling.
40pub const FLAG_CDAG_CONE_CULLED: u32 = 1 << 1;
41
42/// 32-byte POD mini-header for `SectionType::ClusterDag` (`CDAG`).
43#[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/// 64-byte cache-line-aligned POD node representing one meshlet in the Cluster DAG.
76#[repr(C, align(64))]
77#[derive(Debug, Clone, Copy, PartialEq, Pod, Zeroable)]
78pub struct MeshletClusterNode {
79    /// Bounding sphere `[cx, cy, cz, radius]` in local meters (16B).
80    pub bounding_sphere: [f32; 4],
81    /// Parent cluster-group bounding sphere `[px, py, pz, parent_radius]` (16B).
82    pub parent_error_sphere: [f32; 4],
83    /// World-space QEM geometric error of this cluster in meters (4B).
84    pub lod_error_self: f32,
85    /// Monotonic parent group error (`>= lod_error_self`; `f32::INFINITY` for roots) (4B).
86    pub lod_error_parent: f32,
87    /// Octahedral normal cone axis in `snorm16` (4B).
88    pub cone_axis_oct16: [i16; 2],
89    /// Quantized cone cutoff `cos(half_angle + pi/2)` in `snorm16` (2B).
90    pub cone_cutoff_snorm16: i16,
91    /// Hierarchy level (`0` = finest leaf meshlet) (1B).
92    pub lod_level: u8,
93    /// Vertex count in this meshlet (`<= 64`) (1B).
94    pub vertex_count: u8,
95    /// Triangle count in this meshlet (`<= 124`) (1B).
96    pub triangle_count: u8,
97    /// Material binding slot index (1B).
98    pub material_slot: u8,
99    /// First child cluster group index (`0xFFFF` for leaf clusters) (2B).
100    pub child_group_first: u16,
101    /// Offset into the meshlet vertex index stream (4B).
102    pub vertex_data_offset: u32,
103    /// Offset into the meshlet local triangle micro-index stream (4B).
104    pub triangle_data_offset: u32,
105    /// Hashed `did:q42:` anatomical/mechanical subpart identifier (4B).
106    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/// Errors emitted by the `CDAG` section codec and zero-heap LOD cut selector.
113#[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/// Compute exact byte length for a `CDAG` section with `cluster_count` nodes.
197#[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/// Encode a unit 3D direction into `[i16; 2]` octahedral `snorm16` coordinates.
209#[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/// Decode `[i16; 2]` octahedral `snorm16` coordinates back into a unit 3D vector.
233#[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
297/// Encode a `CDAG` section into a caller-provided byte slice without heap allocation.
298pub 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
337/// Decode and validate a `CDAG` section into caller-provided `MeshletClusterNode` storage (Zero-Heap).
338pub 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/// Project a world-space geometric error `world_error` at `sphere` into screen-space pixels.
387#[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
405/// Select the active continuous-LOD cut into `out_cluster_indices` without heap allocation.
406///
407/// A cluster is selected iff `projected_error(self) <= error_threshold_px < projected_error(parent)`.
408pub 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            // Leaf 0 (LOD 0): self error 0.0m, parent error 0.02m
468            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            // Leaf 1 (LOD 0): self error 0.0m, parent error 0.02m
485            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            // Root (LOD 1): simplified parent group, self error 0.02m, parent error +inf
502            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        // Camera close (z = 4.0m): parent error (0.02m) projects > 1.0px -> selects leaves [0, 1]
553        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        // Camera far (z = 50.0m): parent error (0.02m) projects < 1.0px -> selects root [2]
565        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}