Skip to main content

qualia_core_db/topology/
induce_intrinsic.rs

1//! Tier-2 cold induction of intrinsic graphs (`Primal1Skeleton`, `PoincareDual`, `BoundaryIncidence`,
2//! `CombinatorialDartMap`, `MetricProximity`) from `computational_geometry` complexes.
3//!
4//! Tier-2 Cold Bounded (`AGENTS.md` ยง0-A): every builder enforces an explicit caller-supplied
5//! `budget_bytes` before allocating scratch buffers and fails closed with [`TopologyError::BudgetExhausted`].
6
7use bytemuck::Zeroable;
8
9use crate::specialized_libs::computational_geometry::ddg_operators::{
10    boundary_of_boundary_is_zero, boundary_of_simplex, ChainTerm,
11};
12use crate::specialized_libs::computational_geometry::mixed_cell_topology::{
13    extract_boundary_faces, BoundaryFace, MixedCell, MixedTopologyError, CELL_KIND_HEX,
14    CELL_KIND_QUAD, CELL_KIND_TETRA, CELL_KIND_TRIANGLE,
15};
16use crate::specialized_libs::computational_geometry::{
17    build_face_adjacency_csr, build_vertex_adjacency_csr, half_edges_to_darts,
18    validate_combinatorial_map, CsrError, Dart, HalfEdge, INVALID_INDEX,
19};
20use crate::tensor::topology::TopologyClass;
21use crate::tensor::Tensor10D;
22use crate::topology::compactor::UnsealedGraphSpec;
23use crate::topology::header::{
24    AnchorDomain, CellAnchor, GraphEmbedRole, GraphMorphology, TopologyError, TopologyInvariants,
25};
26
27#[inline]
28fn derive_graph_id(geometry_id: u64, role: GraphEmbedRole) -> u64 {
29    let mut h = 0xcbf2_9ce4_8422_2325u64 ^ geometry_id;
30    h = (h ^ (role as u64)).wrapping_mul(0x0100_0000_01b3);
31    h
32}
33
34#[inline]
35fn derive_cell_hash(geometry_id: u64, domain: AnchorDomain, cell_index: u32) -> u64 {
36    let mut h = 0xcbf2_9ce4_8422_2325u64 ^ geometry_id;
37    h = (h ^ (domain as u64)).wrapping_mul(0x0100_0000_01b3);
38    h = (h ^ (cell_index as u64)).wrapping_mul(0x0100_0000_01b3);
39    h
40}
41
42#[inline]
43fn map_csr_err(err: CsrError, count: u32, he_count: u32) -> TopologyError {
44    match err {
45        CsrError::OffsetBufferTooSmall { .. } | CsrError::NeighbourBufferTooSmall { .. } => TopologyError::BufferTooSmall,
46        CsrError::HalfEdgeOutOfRange { index } => TopologyError::CellOutOfRange { domain: AnchorDomain::Cell1Edge as u8, index, count: he_count },
47        CsrError::EntityOutOfRange { index } => TopologyError::VertexOutOfRange { vertex: index, count },
48    }
49}
50
51#[inline]
52fn make_cell_anchors(geometry_id: u64, count: usize, domain: AnchorDomain) -> Vec<CellAnchor> {
53    (0..count)
54        .map(|idx| CellAnchor {
55            entity_hash: derive_cell_hash(geometry_id, domain, idx as u32),
56            cell_index: idx as u32,
57            anchor_domain: domain as u8,
58            orientation_sign: 1,
59            material_or_stratum: 0,
60        })
61        .collect()
62}
63
64/// Induce both the `Primal1Skeleton` (`Cell0Vertex โ†” Cell0Vertex`) and the `PoincareDual`
65/// (`Cell2Face โ†” Cell2Face`) harboured graphs from a half-edge surface mesh.
66pub fn induce_primal_and_dual_from_half_edges(
67    geometry_id: u64,
68    half_edges: &[HalfEdge],
69    num_vertices: usize,
70    num_faces: usize,
71    budget_bytes: usize,
72) -> Result<(UnsealedGraphSpec, UnsealedGraphSpec), TopologyError> {
73    let he_len = half_edges.len();
74    let scratch_bytes = (num_vertices + num_faces + 2).saturating_mul(4).saturating_add(he_len.saturating_mul(8));
75    let anchor_bytes = (num_vertices + num_faces).saturating_mul(core::mem::size_of::<CellAnchor>());
76    let requested = scratch_bytes.saturating_add(anchor_bytes).saturating_add(he_len.saturating_mul(36));
77    if requested > budget_bytes {
78        return Err(TopologyError::BudgetExhausted { requested, budget: budget_bytes });
79    }
80
81    let mut v_offsets = vec![0u32; num_vertices + 1];
82    let mut v_neighbours = vec![0u32; he_len];
83    build_vertex_adjacency_csr(num_vertices as u32, half_edges, &mut v_offsets, &mut v_neighbours)
84        .map_err(|e| map_csr_err(e, num_vertices as u32, he_len as u32))?;
85    let primal_anchors = make_cell_anchors(geometry_id, num_vertices, AnchorDomain::Cell0Vertex);
86
87    let mut primal_edges = Vec::with_capacity(he_len * 2);
88    for (he_idx, he) in half_edges.iter().enumerate() {
89        let u = he.origin;
90        let dst = half_edges.get(he.next as usize).ok_or(TopologyError::CellOutOfRange {
91            domain: AnchorDomain::Cell1Edge as u8, index: he.next, count: he_len as u32,
92        })?.origin;
93        primal_edges.push((u, dst, he_idx as u32));
94        if he.twin == INVALID_INDEX {
95            primal_edges.push((dst, u, he_idx as u32));
96        }
97    }
98    primal_edges.sort_unstable_by_key(|&(u, v, a)| (u, v, a));
99    primal_edges.dedup_by(|a, b| a.0 == b.0 && a.1 == b.1);
100
101    let mut f_offsets = vec![0u32; num_faces + 1];
102    let mut f_neighbours = vec![0u32; he_len];
103    build_face_adjacency_csr(num_faces as u32, half_edges, &mut f_offsets, &mut f_neighbours)
104        .map_err(|e| map_csr_err(e, num_faces as u32, he_len as u32))?;
105    let dual_anchors = make_cell_anchors(geometry_id, num_faces, AnchorDomain::Cell2Face);
106
107    let mut dual_edges = Vec::with_capacity(he_len);
108    let mut has_boundary = false;
109    for (he_idx, he) in half_edges.iter().enumerate() {
110        if he.twin == INVALID_INDEX {
111            has_boundary = true;
112        } else {
113            let nbr_face = half_edges[he.twin as usize].face;
114            dual_edges.push((he.face, nbr_face, he_idx as u32));
115        }
116    }
117    dual_edges.sort_unstable_by_key(|&(u, v, a)| (u, v, a));
118    dual_edges.dedup_by(|a, b| a.0 == b.0 && a.1 == b.1);
119
120    let dual_invariants = if !has_boundary && !half_edges.is_empty() {
121        TopologyInvariants::SYMMETRIC | TopologyInvariants::MANIFOLD_CLOSED
122    } else {
123        TopologyInvariants::SYMMETRIC
124    };
125
126    let primal = UnsealedGraphSpec {
127        graph_id: derive_graph_id(geometry_id, GraphEmbedRole::Primal1Skeleton),
128        embed_role: GraphEmbedRole::Primal1Skeleton,
129        morphology: GraphMorphology::SymmetricGraph,
130        invariants: TopologyInvariants::SYMMETRIC,
131        context_and_state_mask: 0,
132        anchors: primal_anchors,
133        edges: primal_edges,
134        edge_weights: None,
135    };
136    let dual = UnsealedGraphSpec {
137        graph_id: derive_graph_id(geometry_id, GraphEmbedRole::PoincareDual),
138        embed_role: GraphEmbedRole::PoincareDual,
139        morphology: GraphMorphology::SymmetricGraph,
140        invariants: dual_invariants,
141        context_and_state_mask: 0,
142        anchors: dual_anchors,
143        edges: dual_edges,
144        edge_weights: None,
145    };
146    Ok((primal, dual))
147}
148
149/// Induce a 3-cell `PoincareDual` graph (`AnchorDomain::Cell3Volume`) from a `MixedCell` complex.
150pub fn induce_mixed_cell_dual_graph(
151    geometry_id: u64,
152    cells: &[MixedCell],
153    budget_bytes: usize,
154) -> Result<UnsealedGraphSpec, TopologyError> {
155    let max_facets = cells.len().saturating_mul(6);
156    let requested = cells
157        .len()
158        .saturating_mul(core::mem::size_of::<CellAnchor>())
159        .saturating_add(max_facets.saturating_mul(core::mem::size_of::<BoundaryFace>() + 24));
160    if requested > budget_bytes {
161        return Err(TopologyError::BudgetExhausted {
162            requested,
163            budget: budget_bytes,
164        });
165    }
166
167    let mut boundary_scratch = vec![BoundaryFace::zeroed(); max_facets];
168    extract_boundary_faces(cells, &mut boundary_scratch).map_err(|e| match e {
169        MixedTopologyError::UnknownCellKind { kind, .. } => TopologyError::InvalidComplexKind(kind),
170        _ => TopologyError::BufferTooSmall,
171    })?;
172
173    // Extract canonical facets (count, sorted_verts, owner_cell) for cell-to-cell dual adjacency.
174    let mut facets: Vec<(u8, [u32; 4], u32)> = Vec::with_capacity(max_facets);
175    for (ci, cell) in cells.iter().enumerate() {
176        let owner = ci as u32;
177        let v = cell.vertices;
178        match cell.kind {
179            CELL_KIND_TETRA => {
180                for raw in [[v[0], v[2], v[1], 0], [v[0], v[1], v[3], 0], [v[1], v[2], v[3], 0], [v[2], v[0], v[3], 0]] {
181                    let mut key = raw;
182                    key[..3].sort_unstable();
183                    facets.push((3, key, owner));
184                }
185            }
186            CELL_KIND_HEX => {
187                for raw in [[v[0], v[1], v[2], v[3]], [v[4], v[7], v[6], v[5]], [v[0], v[4], v[5], v[1]], [v[1], v[5], v[6], v[2]], [v[2], v[6], v[7], v[3]], [v[3], v[7], v[4], v[0]]] {
188                    let mut key = raw;
189                    key.sort_unstable();
190                    facets.push((4, key, owner));
191                }
192            }
193            CELL_KIND_TRIANGLE => {
194                for (a, b) in [(v[0], v[1]), (v[1], v[2]), (v[2], v[0])] {
195                    facets.push((2, [a.min(b), a.max(b), 0, 0], owner));
196                }
197            }
198            CELL_KIND_QUAD => {
199                for (a, b) in [(v[0], v[1]), (v[1], v[2]), (v[2], v[3]), (v[3], v[0])] {
200                    facets.push((2, [a.min(b), a.max(b), 0, 0], owner));
201                }
202            }
203            other => return Err(TopologyError::InvalidComplexKind(other)),
204        }
205    }
206    facets.sort_unstable_by_key(|&(cnt, key, owner)| (cnt, key, owner));
207
208    let mut edges = Vec::new();
209    let mut i = 0usize;
210    let mut shared_facet_id = 0u32;
211    while i < facets.len() {
212        let (cnt, key, _) = facets[i];
213        let start = i;
214        while i < facets.len() && facets[i].0 == cnt && facets[i].1 == key {
215            i += 1;
216        }
217        if i - start >= 2 {
218            for a in start..i {
219                for b in (a + 1)..i {
220                    let ca = facets[a].2;
221                    let cb = facets[b].2;
222                    if ca != cb {
223                        edges.push((ca, cb, shared_facet_id));
224                        edges.push((cb, ca, shared_facet_id));
225                    }
226                }
227            }
228            shared_facet_id += 1;
229        }
230    }
231    edges.sort_unstable_by_key(|&(u, v, a)| (u, v, a));
232    edges.dedup_by(|a, b| a.0 == b.0 && a.1 == b.1);
233
234    let mut anchors = Vec::with_capacity(cells.len());
235    for (ci, cell) in cells.iter().enumerate() {
236        anchors.push(CellAnchor {
237            entity_hash: derive_cell_hash(geometry_id, AnchorDomain::Cell3Volume, ci as u32),
238            cell_index: ci as u32,
239            anchor_domain: AnchorDomain::Cell3Volume as u8,
240            orientation_sign: 1,
241            material_or_stratum: cell.material,
242        });
243    }
244
245    Ok(UnsealedGraphSpec {
246        graph_id: derive_graph_id(geometry_id, GraphEmbedRole::PoincareDual),
247        embed_role: GraphEmbedRole::PoincareDual,
248        morphology: GraphMorphology::SymmetricGraph,
249        invariants: TopologyInvariants::SYMMETRIC,
250        context_and_state_mask: 0,
251        anchors,
252        edges,
253        edge_weights: None,
254    })
255}
256
257/// Induce a Levi / Hasse `BoundaryIncidence` (`BipartiteFactor`) graph (`Cell2Face โ†’ Cell1Edge`)
258/// while verifying $\partial \circ \partial = 0$ on every 2-simplex via [`boundary_of_boundary_is_zero`].
259pub fn induce_simplicial_boundary_incidence(
260    geometry_id: u64,
261    triangles: &[[u32; 3]],
262    num_vertices: u32,
263    budget_bytes: usize,
264) -> Result<UnsealedGraphSpec, TopologyError> {
265    let f_count = triangles.len();
266    let max_edges = f_count.saturating_mul(3);
267    let requested = (f_count.saturating_add(max_edges))
268        .saturating_mul(core::mem::size_of::<CellAnchor>())
269        .saturating_add(max_edges.saturating_mul(16));
270    if requested > budget_bytes {
271        return Err(TopologyError::BudgetExhausted {
272            requested,
273            budget: budget_bytes,
274        });
275    }
276
277    let mut raw_incidences: Vec<(usize, (u32, u32), i8)> = Vec::with_capacity(max_edges);
278    let mut unique_edges: Vec<(u32, u32)> = Vec::with_capacity(max_edges);
279
280    for (f_idx, tri) in triangles.iter().enumerate() {
281        for &v in tri {
282            if v >= num_vertices {
283                return Err(TopologyError::VertexOutOfRange {
284                    vertex: v,
285                    count: num_vertices,
286                });
287            }
288        }
289        if tri[0] == tri[1] || tri[1] == tri[2] || tri[2] == tri[0] {
290            return Err(TopologyError::ChainBoundaryNotZero { non_zero_terms: 1 });
291        }
292        let simplex = ChainTerm {
293            dim: 2,
294            vertex_count: 3,
295            sign: 1,
296            vertices: [tri[0], tri[1], tri[2], 0],
297        };
298        if !boundary_of_boundary_is_zero(simplex) {
299            return Err(TopologyError::ChainBoundaryNotZero { non_zero_terms: 1 });
300        }
301        let mut faces_1 = [ChainTerm::zeroed(); 4];
302        let n = boundary_of_simplex(simplex, &mut faces_1)
303            .map_err(|_| TopologyError::BufferTooSmall)?;
304        for term in &faces_1[..n] {
305            let a = term.vertices[0];
306            let b = term.vertices[1];
307            let canon = (a.min(b), a.max(b));
308            let oriented_sign = if a < b {
309                term.sign as i8
310            } else {
311                -(term.sign as i8)
312            };
313            unique_edges.push(canon);
314            raw_incidences.push((f_idx, canon, oriented_sign));
315        }
316    }
317
318    unique_edges.sort_unstable();
319    unique_edges.dedup();
320    let e_count = unique_edges.len();
321
322    let mut anchors = make_cell_anchors(geometry_id, f_count, AnchorDomain::Cell2Face);
323    anchors.extend(make_cell_anchors(geometry_id, e_count, AnchorDomain::Cell1Edge));
324
325    let mut weighted_edges: Vec<(u32, u32, u32, f32)> = Vec::with_capacity(raw_incidences.len());
326    for (f_idx, canon, sign) in raw_incidences {
327        let e_idx = unique_edges.binary_search(&canon).unwrap();
328        let target_v = (f_count + e_idx) as u32;
329        anchors[target_v as usize].orientation_sign = sign;
330        weighted_edges.push((f_idx as u32, target_v, e_idx as u32, sign as f32));
331    }
332    weighted_edges.sort_unstable_by_key(|&(u, v, a, _)| (u, v, a));
333
334    let edges = weighted_edges
335        .iter()
336        .map(|&(u, v, a, _)| (u, v, a))
337        .collect();
338    let weights = weighted_edges.iter().map(|&(_, _, _, w)| w).collect();
339
340    Ok(UnsealedGraphSpec {
341        graph_id: derive_graph_id(geometry_id, GraphEmbedRole::BoundaryIncidence),
342        embed_role: GraphEmbedRole::BoundaryIncidence,
343        morphology: GraphMorphology::BipartiteFactor,
344        invariants: TopologyInvariants::CHAIN_BOUNDARY_EXACT | TopologyInvariants::ACYCLIC,
345        context_and_state_mask: 0,
346        anchors,
347        edges,
348        edge_weights: Some(weights),
349    })
350}
351
352/// Induce a `CombinatorialDartMap` (`InvolutionMap`, `AnchorDomain::Cell1Edge`) with $\beta_1$ and $\beta_2$ links.
353pub fn induce_combinatorial_dart_graph(
354    geometry_id: u64,
355    half_edges: &[HalfEdge],
356    budget_bytes: usize,
357) -> Result<UnsealedGraphSpec, TopologyError> {
358    let n = half_edges.len();
359    let requested = n
360        .saturating_mul(core::mem::size_of::<Dart>() + core::mem::size_of::<CellAnchor>() + 24);
361    if requested > budget_bytes {
362        return Err(TopologyError::BudgetExhausted {
363            requested,
364            budget: budget_bytes,
365        });
366    }
367
368    let mut darts = vec![Dart::default(); n];
369    half_edges_to_darts(half_edges, &mut darts).map_err(|_| TopologyError::BufferTooSmall)?;
370    validate_combinatorial_map(&darts).map_err(|_| TopologyError::CellOutOfRange {
371        domain: AnchorDomain::Cell1Edge as u8,
372        index: 0,
373        count: n as u32,
374    })?;
375
376    let mut anchors = Vec::with_capacity(n);
377    let mut edges = Vec::with_capacity(n * 2);
378    let mut all_twinned = !darts.is_empty();
379
380    for (d_idx, dart) in darts.iter().enumerate() {
381        anchors.push(CellAnchor {
382            entity_hash: derive_cell_hash(geometry_id, AnchorDomain::Cell1Edge, d_idx as u32),
383            cell_index: d_idx as u32,
384            anchor_domain: AnchorDomain::Cell1Edge as u8,
385            orientation_sign: 1,
386            material_or_stratum: 0,
387        });
388        edges.push((d_idx as u32, dart.beta1, 1));
389        if dart.beta2 != INVALID_INDEX {
390            edges.push((d_idx as u32, dart.beta2, 2));
391        } else {
392            all_twinned = false;
393        }
394    }
395    edges.sort_unstable_by_key(|&(u, v, a)| (u, v, a));
396
397    let invariants = if all_twinned {
398        TopologyInvariants::MANIFOLD_CLOSED
399    } else {
400        TopologyInvariants::EMPTY
401    };
402
403    Ok(UnsealedGraphSpec {
404        graph_id: derive_graph_id(geometry_id, GraphEmbedRole::CombinatorialDartMap),
405        embed_role: GraphEmbedRole::CombinatorialDartMap,
406        morphology: GraphMorphology::InvolutionMap,
407        invariants,
408        context_and_state_mask: 0,
409        anchors,
410        edges,
411        edge_weights: None,
412    })
413}
414
415/// Induce a 10D `MetricProximity` (`SymmetricGraph`) connecting `Tensor10D` nodes within `max_radius`.
416pub fn induce_metric_proximity_10d(
417    geometry_id: u64,
418    points: &[Tensor10D],
419    entity_hashes: &[u64],
420    max_radius: f32,
421    topology_class: TopologyClass,
422    budget_bytes: usize,
423) -> Result<UnsealedGraphSpec, TopologyError> {
424    let n = points.len();
425    let base_bytes = n.saturating_mul(core::mem::size_of::<CellAnchor>());
426    if base_bytes > budget_bytes {
427        return Err(TopologyError::BudgetExhausted {
428            requested: base_bytes,
429            budget: budget_bytes,
430        });
431    }
432
433    let mut anchors = Vec::with_capacity(n);
434    for i in 0..n {
435        let hash = entity_hashes.get(i).copied().unwrap_or(0);
436        let (entity_hash, domain) = if hash != 0 {
437            (hash, AnchorDomain::SemanticQuin)
438        } else {
439            (
440                derive_cell_hash(geometry_id, AnchorDomain::Cell0Vertex, i as u32),
441                AnchorDomain::Cell0Vertex,
442            )
443        };
444        anchors.push(CellAnchor {
445            entity_hash,
446            cell_index: i as u32,
447            anchor_domain: domain as u8,
448            orientation_sign: 1,
449            material_or_stratum: 0,
450        });
451    }
452
453    let mut weighted_edges: Vec<(u32, u32, u32, f32)> = Vec::new();
454    let mut edge_id = 0u32;
455    for i in 0..n {
456        let pi = (points[i].x, points[i].y, points[i].z);
457        for j in (i + 1)..n {
458            let pj = (points[j].x, points[j].y, points[j].z);
459            let dist = topology_class.calculate_distance(pi, pj);
460            if dist.is_finite() && dist <= max_radius {
461                let needed = base_bytes.saturating_add((weighted_edges.len() + 2).saturating_mul(16));
462                if needed > budget_bytes {
463                    return Err(TopologyError::BudgetExhausted {
464                        requested: needed,
465                        budget: budget_bytes,
466                    });
467                }
468                weighted_edges.push((i as u32, j as u32, edge_id, dist));
469                weighted_edges.push((j as u32, i as u32, edge_id, dist));
470                edge_id += 1;
471            }
472        }
473    }
474    weighted_edges.sort_unstable_by_key(|&(u, v, a, _)| (u, v, a));
475
476    let edges = weighted_edges
477        .iter()
478        .map(|&(u, v, a, _)| (u, v, a))
479        .collect();
480    let weights = weighted_edges.iter().map(|&(_, _, _, w)| w).collect();
481
482    Ok(UnsealedGraphSpec {
483        graph_id: derive_graph_id(geometry_id, GraphEmbedRole::MetricProximity),
484        embed_role: GraphEmbedRole::MetricProximity,
485        morphology: GraphMorphology::SymmetricGraph,
486        invariants: TopologyInvariants::SYMMETRIC | TopologyInvariants::SPATIAL_METRIC,
487        context_and_state_mask: 0,
488        anchors,
489        edges,
490        edge_weights: Some(weights),
491    })
492}