1use 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
64pub 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
149pub 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 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
257pub 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
352pub 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
415pub 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}