include!("mc_table.rs");
pub(crate) const EDGE_LOWER: [[u8; 4]; 3] = [[0, 2, 4, 6], [0, 1, 4, 5], [0, 1, 2, 3]];
#[inline]
pub(crate) fn triangles(case: usize) -> &'static [[u8; 3]] {
&TRI_EDGES[TRI_OFFSET[case] as usize..TRI_OFFSET[case + 1] as usize]
}
#[inline]
pub(crate) const fn corner_offset(c: usize) -> [usize; 3] {
[c & 1, (c >> 1) & 1, (c >> 2) & 1]
}
#[inline]
pub(crate) const fn edge_axis_lower(e: usize) -> (usize, usize) {
(e / 4, EDGE_LOWER[e / 4][e % 4] as usize)
}
#[cfg(test)]
mod tests {
use super::*;
type P = [f64; 3];
fn sub(a: P, b: P) -> P {
[a[0] - b[0], a[1] - b[1], a[2] - b[2]]
}
fn dot(a: P, b: P) -> f64 {
a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
}
fn cross(a: P, b: P) -> P {
[
a[1] * b[2] - a[2] * b[1],
a[2] * b[0] - a[0] * b[2],
a[0] * b[1] - a[1] * b[0],
]
}
fn norm(a: P) -> f64 {
dot(a, a).sqrt()
}
fn corner_pos(c: usize) -> P {
corner_offset(c).map(|v| v as f64)
}
fn edge_corners(e: usize) -> (usize, usize) {
let (axis, lo) = edge_axis_lower(e);
(lo, lo | (1 << axis))
}
fn edge_mid(e: usize) -> P {
let (a, b) = edge_corners(e);
let (pa, pb) = (corner_pos(a), corner_pos(b));
[0, 1, 2].map(|i| 0.5 * (pa[i] + pb[i]))
}
fn edge_between(c0: usize, c1: usize) -> usize {
let axis = (c0 ^ c1).trailing_zeros() as usize;
let lo = c0.min(c1) as u8;
let k = EDGE_LOWER[axis].iter().position(|&c| c == lo).unwrap();
axis * 4 + k
}
fn face_corners(f: usize) -> [usize; 4] {
let (a, s) = (f / 2, f % 2);
let others: Vec<usize> = (0..3).filter(|&b| b != a).collect();
let (b, c) = (others[0], others[1]);
[(0, 0), (1, 0), (1, 1), (0, 1)].map(|(u, v)| (s << a) | (u << b) | (v << c))
}
fn face_normal(f: usize) -> P {
let mut n = [0.0; 3];
n[f / 2] = if f % 2 == 1 { 1.0 } else { -1.0 };
n
}
fn inside(case: usize, c: usize) -> bool {
(case >> c) & 1 == 1
}
fn face_segments(case: usize, f: usize) -> Vec<(usize, usize)> {
let cs = face_corners(f);
let edge = |i: usize| edge_between(cs[i % 4], cs[(i + 1) % 4]);
let crossing: Vec<usize> = (0..4)
.filter(|&i| inside(case, cs[i]) != inside(case, cs[(i + 1) % 4]))
.map(edge)
.collect();
let raw = match crossing.len() {
0 => Vec::new(),
2 => vec![(crossing[0], crossing[1])],
4 => (0..4)
.filter(|&i| inside(case, cs[i]))
.map(|i| (edge(i + 3), edge(i)))
.collect(),
_ => unreachable!(),
};
let n = face_normal(f);
raw.into_iter()
.map(|(p, q)| {
let t = cross(n, sub(edge_mid(q), edge_mid(p)));
let (lo, hi) = edge_corners(p);
let out = sub(corner_pos(hi), corner_pos(lo));
let s = if inside(case, lo) { 1.0 } else { -1.0 };
if dot(t, out) * s > 0.0 {
(p, q)
} else {
(q, p)
}
})
.collect()
}
fn min_angle(a: P, b: P, c: P) -> f64 {
let ang = |p: P, q: P, r: P| {
let (u, v) = (sub(q, p), sub(r, p));
(dot(u, v) / (norm(u) * norm(v))).clamp(-1.0, 1.0).acos()
};
ang(a, b, c).min(ang(b, c, a)).min(ang(c, a, b))
}
fn triangulations(i: usize, j: usize) -> Vec<Vec<[usize; 3]>> {
if j < i + 2 {
return vec![Vec::new()];
}
let mut all = Vec::new();
for k in i + 1..j {
for left in triangulations(i, k) {
for right in triangulations(k, j) {
let mut t = vec![[i, k, j]];
t.extend_from_slice(&left);
t.extend_from_slice(&right);
all.push(t);
}
}
}
all
}
fn best_triangulation(case: usize, ring: &[usize]) -> Vec<[usize; 3]> {
let n = ring.len();
type Scored = ((usize, f64, f64), Vec<[usize; 3]>);
let mut best: Option<Scored> = None;
for tri in triangulations(0, n - 1) {
let on_one_face = |a: usize, b: usize| {
(0..6).any(|f| face_edges(f).contains(&a) && face_edges(f).contains(&b))
};
let diagonal_on_face = tri.iter().any(|t| {
(0..3).any(|k| {
let (i, j) = (t[k].min(t[(k + 1) % 3]), t[k].max(t[(k + 1) % 3]));
let interior = j - i != 1 && !(i == 0 && j == n - 1);
interior && on_one_face(ring[i], ring[j])
})
});
if diagonal_on_face {
continue;
}
let tri: Vec<[usize; 3]> = tri.iter().map(|t| t.map(|k| ring[k])).collect();
let mut acc = [[0.0f64; 3]; 12];
let mut area = 0.0;
let mut angle = f64::INFINITY;
for &[a, b, c] in &tri {
let (pa, pb, pc) = (edge_mid(a), edge_mid(b), edge_mid(c));
let nrm = cross(sub(pb, pa), sub(pc, pa));
area += 0.5 * norm(nrm);
angle = angle.min(min_angle(pa, pb, pc));
for e in [a, b, c] {
for k in 0..3 {
acc[e][k] += nrm[k];
}
}
}
let bad = ring
.iter()
.filter(|&&e| {
let (lo, hi) = edge_corners(e);
let out = sub(corner_pos(hi), corner_pos(lo));
let s = if inside(case, lo) { 1.0 } else { -1.0 };
dot(acc[e], out) * s < 0.0
})
.count();
let score = (bad, (area * 1e9).round(), -angle);
let better = match &best {
None => true,
Some((b, _)) => {
score.0 < b.0
|| (score.0 == b.0
&& (score.1 < b.1 || (score.1 == b.1 && score.2 < b.2 - 1e-12)))
}
};
if better {
best = Some((score, tri));
}
}
best.expect("every loop has a triangulation without face diagonals")
.1
}
pub(super) fn generate() -> Vec<Vec<[u8; 3]>> {
(0..256)
.map(|case| {
let mut next = [usize::MAX; 12];
for f in 0..6 {
for (p, q) in face_segments(case, f) {
assert_eq!(next[p], usize::MAX, "case {case}: edge {p} starts twice");
next[p] = q;
}
}
let mut seen = [false; 12];
let mut tris = Vec::new();
for start in 0..12 {
if next[start] == usize::MAX || seen[start] {
continue;
}
let mut ring = Vec::new();
let mut e = start;
while !seen[e] {
seen[e] = true;
ring.push(e);
e = next[e];
assert_ne!(e, usize::MAX, "case {case}: open loop");
}
assert_eq!(e, start, "case {case}: loop does not close");
tris.extend(
best_triangulation(case, &ring)
.into_iter()
.map(|t| t.map(|e| e as u8)),
);
}
tris
})
.collect()
}
fn render(cases: &[Vec<[u8; 3]>]) -> String {
let mut offsets = vec![0usize];
for c in cases {
offsets.push(offsets.last().unwrap() + c.len());
}
let mut s = String::from(
"// sesmesh — Solvent Excluded Surface meshes for molecules\n\
// Copyright (c) 2026 Ugo Varetto\n\
// SPDX-License-Identifier: MIT OR Apache-2.0\n\n\
// @generated by `mesh::tables::tests::generate`; do not edit.\n\
// Regenerate: SESMESH_BLESS=1 cargo test -p sesmesh mc_table\n\n",
);
s += "#[rustfmt::skip]\nconst TRI_OFFSET: [u16; 257] = [\n";
for row in offsets.chunks(16) {
let items: Vec<String> = row.iter().map(ToString::to_string).collect();
s += &format!(" {},\n", items.join(", "));
}
s += "];\n\n";
let total = offsets.last().unwrap();
s += &format!("#[rustfmt::skip]\nconst TRI_EDGES: [[u8; 3]; {total}] = [\n");
for (case, tris) in cases.iter().enumerate() {
if tris.is_empty() {
continue;
}
let items: Vec<String> = tris
.iter()
.map(|t| format!("[{}, {}, {}]", t[0], t[1], t[2]))
.collect();
s += &format!(" {}, // {case}\n", items.join(", "));
}
s += "];\n";
s
}
#[test]
fn mc_table_matches_generator() {
let cases = generate();
let text = render(&cases);
let path = concat!(env!("CARGO_MANIFEST_DIR"), "/src/mesh/mc_table.rs");
if std::env::var_os("SESMESH_BLESS").is_some() {
std::fs::write(path, &text).unwrap();
}
for (case, tris) in cases.iter().enumerate() {
assert_eq!(triangles(case), &tris[..], "case {case}: stale mc_table.rs");
}
}
fn boundary(case: usize) -> Vec<(usize, usize)> {
let mut directed: Vec<(usize, usize)> = Vec::new();
for t in triangles(case) {
for i in 0..3 {
directed.push((t[i] as usize, t[(i + 1) % 3] as usize));
}
}
let mut out: Vec<(usize, usize)> = directed
.iter()
.copied()
.filter(|&(a, b)| !directed.contains(&(b, a)))
.collect();
out.sort_unstable();
out
}
fn face_edges(f: usize) -> [usize; 4] {
let cs = face_corners(f);
[0, 1, 2, 3].map(|i| edge_between(cs[i], cs[(i + 1) % 4]))
}
#[test]
fn cases_are_well_formed() {
for case in 0..256 {
let tris = triangles(case);
let mut used = [false; 12];
for t in tris {
assert!(t[0] != t[1] && t[1] != t[2] && t[0] != t[2], "case {case}");
for &e in t {
used[e as usize] = true;
}
}
for (e, &u) in used.iter().enumerate() {
let (a, b) = edge_corners(e);
assert_eq!(
u,
inside(case, a) != inside(case, b),
"case {case} edge {e}"
);
}
let mut directed: Vec<(u8, u8)> = Vec::new();
for t in tris {
for i in 0..3 {
let d = (t[i], t[(i + 1) % 3]);
assert!(!directed.contains(&d), "case {case}: repeated edge {d:?}");
directed.push(d);
}
}
for (a, b) in boundary(case) {
let faces: Vec<usize> = (0..6)
.filter(|&f| face_edges(f).contains(&a) && face_edges(f).contains(&b))
.collect();
assert_eq!(
faces.len(),
1,
"case {case}: boundary edge ({a},{b}) off faces"
);
}
if case == 0 || case == 255 {
assert!(tris.is_empty());
}
}
}
#[test]
fn interior_edges_leave_faces() {
for case in 0..256 {
let bnd = boundary(case);
for t in triangles(case) {
for k in 0..3 {
let (a, b) = (t[k] as usize, t[(k + 1) % 3] as usize);
if bnd.contains(&(a, b)) || bnd.contains(&(b, a)) {
continue;
}
let shared =
(0..6).any(|f| face_edges(f).contains(&a) && face_edges(f).contains(&b));
assert!(!shared, "case {case}: interior edge ({a},{b}) on a face");
}
}
}
}
fn on_face(case: usize, f: usize) -> Vec<(usize, usize)> {
let fe = face_edges(f);
boundary(case)
.into_iter()
.filter(|(a, b)| fe.contains(a) && fe.contains(b))
.collect()
}
#[test]
fn shared_faces_match() {
let mut checked = 0;
for a in 0..3 {
let bit = 1 << a;
let map = |e: usize| {
let (axis, lo) = edge_axis_lower(e);
let lo = lo ^ bit;
let hi = lo | (1 << axis);
edge_between(lo, hi)
};
for lower in 0..256usize {
let shared: usize = (0..8)
.filter(|c| c & bit != 0 && inside(lower, *c))
.map(|c| 1 << (c ^ bit))
.sum();
let free: Vec<usize> = (0..8).filter(|c| c & bit != 0).collect();
for m in 0..16 {
let upper = shared
+ free
.iter()
.enumerate()
.filter(|(i, _)| (m >> i) & 1 == 1)
.map(|(_, c)| 1 << c)
.sum::<usize>();
let mut mine: Vec<(usize, usize)> = on_face(lower, 2 * a + 1)
.into_iter()
.map(|(p, q)| (map(q), map(p)))
.collect();
mine.sort_unstable();
let theirs = on_face(upper, 2 * a);
assert_eq!(mine, theirs, "axis {a}: lower {lower} upper {upper}");
checked += 1;
}
}
}
assert_eq!(checked, 3 * 256 * 16);
}
#[test]
fn winding_faces_outside() {
for case in 1..255 {
let mut acc = [[0.0f64; 3]; 12];
for t in triangles(case) {
let [a, b, c] = t.map(|e| edge_mid(e as usize));
let n = cross(sub(b, a), sub(c, a));
for &e in t {
for i in 0..3 {
acc[e as usize][i] += n[i];
}
}
}
let mut flux = 0.0;
for (e, n) in acc.iter().enumerate() {
let (lo, hi) = edge_corners(e);
if inside(case, lo) == inside(case, hi) {
continue;
}
let out = sub(corner_pos(hi), corner_pos(lo));
let s = if inside(case, lo) { 1.0 } else { -1.0 };
let f = dot(*n, out) * s;
assert!(f >= 0.0, "case {case} edge {e}: normal {n:?}");
flux += f;
}
assert!(flux > 0.0, "case {case}");
}
}
#[test]
fn table_size() {
let max = (0..256).map(|c| triangles(c).len()).max().unwrap();
assert!(max <= 12, "{max}");
assert_eq!(triangles(1).len(), 1);
assert_eq!(triangles(0x0f).len(), 2);
}
}