facett-core/src/render/cpu/faces.rs
//! **The lit-face painter** — the shared "scissor → reject degenerates → emit one
//! mesh" tail every CPU-lit 3D pane draws through, plus its data oracles.
//!
//! ## Why this exists (the clipping bug it fixes)
//!
//! A CPU-lit 3D pane (`facett-graph3d::RabbitLogo3D`, `facett-model3d::Model3D`, …)
//! projects its mesh, back-face culls, depth-sorts and then hands each surviving
//! face to the painter. The obvious way to do that last step —
//! `egui::Shape::convex_polygon(pts, col, Stroke::NONE)` per face — is **unsound for
//! projected 3D geometry**: `epaint`'s tessellator feathers every filled path with a
//! *miter join* (`epaint::tessellator::Path::add_line_loop`, `normal / length_sq`).
//! For a near-degenerate face — a silhouette sliver, or a face seen edge-on, both of
//! which a rotating solid produces at almost every pose — the two edge normals at a
//! corner are nearly antiparallel, `length_sq → 0`, and the miter normal **explodes**.
//! The emitted vertex is flung `0.5 · feathering / sqrt(length_sq)` pixels away: a
//! thin bright **spoke** that shoots across (and far out of) the widget rect.
//!
//! Measured on the bundled Avocado at a 1264×444 pane, 24 yaw poses: the *raw*
//! projected geometry never left the rect (0 escapes at every pose), yet the
//! *tessellated* geometry escaped by up to **7799 px** — ~17 widget-widths — at 22
//! of the 24 poses. The `ui.painter_at(rect)` clip rect merely *crops* the spoke at
//! the pane edge; the ink still crosses the whole pane. That is the clipping bug.
//!
//! ## What this does instead
//!
//! [`paint_faces`] emits **one flat [`egui::Mesh`]** — three coloured vertices per
//! triangle, fan-triangulated from the *scissored* polygon — so the feathering path
//! is never entered and no spoke can be born. On the way it:
//!
//! 1. **depth-sorts** far→near (painter's algorithm; the one place that order lives),
//! 2. **rejects degenerate faces** whose |2·signed area| is below
//! [`MIN_FACE_AREA2_PX`] (they carry no ink and are exactly the ones that used to
//! blow up),
//! 3. **scissors** every face to the rect with the shared
//! [`clip_poly_to_rect`](super::scissor::clip_poly_to_rect), so geometry is
//! confined *before* it becomes vertices — not merely cropped afterwards,
//! 4. reports [`FaceStats`] measured on the vertices it **actually emitted**.
//!
//! [`FaceStats::ink_outside_rect`] is therefore the real bug oracle
//! (`ink_outside_rect == 0`), not a re-derivation of what the painter *might* have
//! done. It uses the same names + the same `lit` heuristic as `facett-map3d`'s
//! `RenderStats` so the two lanes speak one vocabulary.
//!
//! ## Trade
//! A flat mesh has no edge anti-aliasing — the same deal the `facett-map3d` CPU lane
//! (software z-buffer + blit) already takes. Spoke-free and rect-confined beats
//! feathered-and-exploding; and one mesh replaces N shapes, so it is also cheaper.
use egui::{Color32, Painter, Pos2, Rect};
use super::scissor::clip_poly_to_rect;
/// One shaded, already-projected triangle: `(painter depth, 3 screen points,
/// colour)`. Larger depth = nearer (the convention both 3D panes project with).
pub type ShadedFace = (f32, [Pos2; 3], Color32);
/// A shaded, projected triangle carrying **per-vertex** depth — what
/// [`raster_zbuffer`] needs to resolve occlusion per *pixel* instead of per face.
/// Larger `vz` = nearer (the orthographic view-space convention both 3D panes
/// project with).
///
/// The per-face `depth` a painter's-algorithm sort uses is only the *mean* of `vz`,
/// and that mean is exactly what tears: two surfaces that interleave in depth (a
/// cut model's outer skin against the interior right behind it; two extruded shells
/// that intersect) get a stable but **wrong** order, and the seam between them
/// breaks into a triangle-wide sawtooth. `vz` keeps the information needed to do it
/// properly.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct ShadedTri {
/// The three screen-space points (logical points, not physical pixels).
pub pts: [Pos2; 3],
/// View-space depth per vertex; larger = nearer.
pub vz: [f32; 3],
/// The shaded, already-lit colour.
pub col: Color32,
}
impl ShadedTri {
/// The mean depth — the painter's-algorithm sort key (and the lossy quantity the
/// z-buffer exists to stop relying on).
#[must_use]
pub fn depth(&self) -> f32 {
(self.vz[0] + self.vz[1] + self.vz[2]) / 3.0
}
/// The lean oracle tuple ([`ShadedFace`]) — drops the per-vertex depth.
#[must_use]
pub fn face(&self) -> ShadedFace {
(self.depth(), self.pts, self.col)
}
}
/// Minimum |2 · signed area| in px² for a face to be worth emitting. Below this a
/// triangle contributes no visible ink *and* is precisely the degenerate case that
/// detonates `epaint`'s miter join, so dropping it is both free and load-bearing.
pub const MIN_FACE_AREA2_PX: f32 = 1.0e-3;
/// How far outside the rect (px) an emitted vertex may sit before it counts as an
/// escape. Matches `facett-map3d`'s scissor oracle epsilon.
const ESCAPE_EPS: f32 = 1e-2;
/// The **data oracles** a CPU-lit face pass reports — the same conformance surface
/// (and the same field names) as `facett-map3d::RenderStats`, measured here on the
/// vertices actually written into the [`egui::Mesh`].
/// **The "lit" threshold: the sum of a face's three colour channels.**
///
/// A face counts as lit when `r + g + b` exceeds this. The ambient floor is `0.30`, so
/// a genuinely shaded face clears it comfortably while a near-black one does not.
///
/// It is a named constant because it was **two copies of `90`** — one here and one in
/// `facett-map3d`'s `RenderStats` — under a comment saying *"same heuristic + threshold
/// as facett-map3d's RenderStats, so the two lanes agree on the word"*. A comment asking
/// two literals to agree is a guard that watches, not a rule that holds: `lit_fraction`
/// is compared BETWEEN the two lanes by the backend-conformance test, so the day one
/// number moved the conformance check would have failed on a difference that was not a
/// rendering difference at all (lane ST, gfx3d-S3).
pub const LIT_THRESHOLD: u32 = 90;
/// **Is this shaded colour "lit"?** — the ONE writer of the [`LIT_THRESHOLD`] rule, so
/// the CPU lane and `facett-map3d`'s `RenderStats` cannot answer differently.
///
/// Takes the three channels rather than a colour type on purpose: the two call sites
/// hold DIFFERENT colour types (`egui::Color32` here, `vello_cpu`'s `PremulRgba8` in
/// `facett-map3d`), and a shared rule that only one of them can call is not a shared
/// rule. Channels are the common denominator, and the alpha is deliberately not part of
/// it — a transparent face is not an unlit one.
#[must_use]
pub fn is_lit(r: u8, g: u8, b: u8) -> bool {
u32::from(r) + u32::from(g) + u32::from(b) > LIT_THRESHOLD
}
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FaceStats {
/// Faces that survived degeneracy rejection **and** the scissor, i.e. that put
/// ink on the pane. `0` with a non-empty input means the pose framed nothing.
pub visible_triangles: usize,
/// Faces dropped for being degenerate (|2·area| < [`MIN_FACE_AREA2_PX`]) — the
/// spoke sources. Advisory; a healthy solid drops a handful per pose.
pub degenerate_dropped: usize,
/// Faces dropped for lying wholly outside the rect (the scissor's real work).
pub offscreen_dropped: usize,
/// Fraction `0..1` of emitted faces whose shaded colour is not near-black.
pub lit_fraction: f32,
/// **The bug oracle** — emitted mesh vertices that still land outside the rect.
/// MUST be `0`: no ink escapes the component.
pub ink_outside_rect: usize,
/// Worst signed distance (px) any *raw* (pre-scissor) face vertex poked past a
/// rect edge. A correct projection + fit drives this to ~0; the scissor makes it
/// harmless either way.
pub raw_overshoot_px: f32,
/// Whether the emitted order is monotone far→near (correct painter occlusion).
pub depth_monotone: bool,
/// Worst emitted face extent in px — bounded by the rect diagonal by
/// construction; a spoke would blow this up.
pub max_extent_px: f32,
}
impl FaceStats {
/// The one-line summary a `testmatrix` emitter carries as its detail string.
#[must_use]
pub fn detail(&self) -> String {
format!(
"visible_triangles={} ink_outside_rect={} lit_fraction={:.2} max_extent_px={:.1} \
raw_overshoot_px={:.1} depth_monotone={} degenerate_dropped={} offscreen_dropped={}",
self.visible_triangles,
self.ink_outside_rect,
self.lit_fraction,
self.max_extent_px,
self.raw_overshoot_px,
self.depth_monotone,
self.degenerate_dropped,
self.offscreen_dropped,
)
}
}
/// Twice the signed area of a triangle (positive = CCW in screen space).
#[inline]
fn area2(p: &[Pos2; 3]) -> f32 {
(p[1].x - p[0].x) * (p[2].y - p[0].y) - (p[1].y - p[0].y) * (p[2].x - p[0].x)
}
/// **Scissor + reject + tessellate** a shaded face list into one flat
/// [`egui::Mesh`], reporting the [`FaceStats`] oracles. Pure — no `Ui`, no painter,
/// no device — so a headless pose sweep asserts exactly what the live pane draws.
///
/// `faces` is sorted in place far→near (painter's algorithm); callers need not
/// pre-sort. Never panics, and never emits a vertex outside `rect`.
#[must_use]
pub fn tessellate_faces(faces: &mut [ShadedFace], rect: Rect) -> (egui::Mesh, FaceStats) {
faces.sort_by(|l, r| l.0.partial_cmp(&r.0).unwrap_or(std::cmp::Ordering::Equal));
let mut mesh = egui::Mesh::default();
mesh.reserve_vertices(faces.len() * 3);
mesh.reserve_triangles(faces.len());
let mut stats = FaceStats { depth_monotone: true, ..FaceStats::default() };
let mut lit = 0usize;
let mut last_depth = f32::NEG_INFINITY;
for (depth, pts, col) in faces.iter() {
if *depth < last_depth - 1e-3 {
stats.depth_monotone = false;
}
last_depth = *depth;
// How far the RAW projection poked out — reported even though the scissor
// then confines it, so a bad fit is still visible in the oracles.
for p in pts {
let over = (rect.left() - p.x).max(p.x - rect.right()).max(rect.top() - p.y).max(p.y - rect.bottom());
if over > stats.raw_overshoot_px {
stats.raw_overshoot_px = over;
}
}
if !pts.iter().all(|p| p.x.is_finite() && p.y.is_finite()) {
stats.degenerate_dropped += 1;
continue;
}
if area2(pts).abs() < MIN_FACE_AREA2_PX {
stats.degenerate_dropped += 1;
continue;
}
let poly = clip_poly_to_rect(pts, rect);
if poly.len() < 3 {
stats.offscreen_dropped += 1;
continue;
}
// Fan-triangulate the clipped convex polygon straight into the mesh. Flat
// vertex colours, `WHITE_UV` — no path, no feathering, no miter, no spoke.
let base = mesh.vertices.len() as u32;
let (mut lo, mut hi) = (poly[0], poly[0]);
for p in &poly {
mesh.colored_vertex(*p, *col);
lo = Pos2::new(lo.x.min(p.x), lo.y.min(p.y));
hi = Pos2::new(hi.x.max(p.x), hi.y.max(p.y));
}
for i in 1..poly.len() as u32 - 1 {
mesh.add_triangle(base, base + i, base + i + 1);
}
stats.visible_triangles += 1;
let extent = (hi.x - lo.x).max(hi.y - lo.y);
if extent > stats.max_extent_px {
stats.max_extent_px = extent;
}
if is_lit(col.r(), col.g(), col.b()) {
lit += 1;
}
}
stats.lit_fraction =
if stats.visible_triangles == 0 { 0.0 } else { lit as f32 / stats.visible_triangles as f32 };
// The bug oracle, measured on what we actually emitted.
for v in &mesh.vertices {
let over = (rect.left() - v.pos.x)
.max(v.pos.x - rect.right())
.max(rect.top() - v.pos.y)
.max(v.pos.y - rect.bottom());
if over > ESCAPE_EPS {
stats.ink_outside_rect += 1;
}
}
(mesh, stats)
}
/// [`tessellate_faces`] + the actual draw: paint the confined, spoke-free mesh
/// through `painter` and hand back the oracles. The painter's-algorithm lane —
/// correct for a scene with no interpenetrating surfaces; see
/// [`paint_tris_zbuffered`] for the per-pixel-depth lane the 3D model panes use.
pub fn paint_faces(painter: &Painter, rect: Rect, faces: &mut [ShadedFace]) -> FaceStats {
let (mesh, stats) = tessellate_faces(faces, rect);
if !mesh.is_empty() {
painter.add(egui::Shape::mesh(mesh));
}
stats
}
// ── the software z-buffer (per-PIXEL depth, not per-face order) ──────────────────
/// **Rasterise shaded triangles with a per-pixel depth test** into a straight-RGBA
/// buffer of `width × height` physical pixels, `origin` being the rect's top-left in
/// logical points and `ppp` the points→pixels scale. Uncovered pixels stay
/// transparent, so whatever the pane painted underneath shows through.
///
/// Depth is interpolated **linearly** in view space (these viewers project
/// orthographically, so `z` is already linear in screen space — no `1/z` needed) and
/// the test keeps the **larger** `z` (nearer). This is what replaces the
/// painter's-algorithm centroid sort, which cannot order interpenetrating surfaces:
/// it tore the cut Avocado's skin against its interior into a triangle-wide sawtooth
/// and split the rabbit logo's ears from its head along the shells' intersection.
///
/// Ink cannot escape the buffer by construction — every write is bounds-clamped —
/// so this lane satisfies `ink_outside_rect == 0` structurally.
#[must_use]
pub fn raster_zbuffer(
tris: &[ShadedTri],
width: usize,
height: usize,
origin: Pos2,
ppp: f32,
) -> Vec<Color32> {
let mut color = vec![Color32::TRANSPARENT; width * height];
if width == 0 || height == 0 {
return color;
}
// Depth buffer: larger = nearer, start at -inf (nothing written yet).
let mut zbuf = vec![f32::NEG_INFINITY; width * height];
let (fw, fh) = (width as f32, height as f32);
for t in tris {
let px = [
(t.pts[0].x - origin.x) * ppp,
(t.pts[1].x - origin.x) * ppp,
(t.pts[2].x - origin.x) * ppp,
];
let py = [
(t.pts[0].y - origin.y) * ppp,
(t.pts[1].y - origin.y) * ppp,
(t.pts[2].y - origin.y) * ppp,
];
let area = (px[1] - px[0]) * (py[2] - py[0]) - (px[2] - px[0]) * (py[1] - py[0]);
if !area.is_finite() || area.abs() < 1e-6 {
continue; // degenerate: no ink, and it would divide by ~0
}
let inv_area = 1.0 / area;
let minx = px.iter().copied().fold(f32::MAX, f32::min).floor().clamp(0.0, fw - 1.0) as usize;
let maxx = px.iter().copied().fold(f32::MIN, f32::max).ceil().clamp(0.0, fw - 1.0) as usize;
let miny = py.iter().copied().fold(f32::MAX, f32::min).floor().clamp(0.0, fh - 1.0) as usize;
let maxy = py.iter().copied().fold(f32::MIN, f32::max).ceil().clamp(0.0, fh - 1.0) as usize;
for y in miny..=maxy {
for x in minx..=maxx {
let (sx, sy) = (x as f32 + 0.5, y as f32 + 0.5);
let w0 = ((px[1] - sx) * (py[2] - sy) - (px[2] - sx) * (py[1] - sy)) * inv_area;
let w1 = ((px[2] - sx) * (py[0] - sy) - (px[0] - sx) * (py[2] - sy)) * inv_area;
let w2 = 1.0 - w0 - w1;
if w0 < -1e-4 || w1 < -1e-4 || w2 < -1e-4 {
continue; // outside the triangle
}
let d = w0 * t.vz[0] + w1 * t.vz[1] + w2 * t.vz[2];
let idx = y * width + x;
if d > zbuf[idx] {
zbuf[idx] = d;
color[idx] = t.col;
}
}
}
}
color
}
/// Compute the [`FaceStats`] oracles for a `ShadedTri` list against `rect`, using the
/// same scissor + degeneracy rules as [`tessellate_faces`]. Pure; no raster, no
/// paint — the headless oracle a pose sweep asserts.
#[must_use]
pub fn tri_stats(tris: &mut [ShadedTri], rect: Rect) -> FaceStats {
let mut faces: Vec<ShadedFace> = tris.iter().map(ShadedTri::face).collect();
let stats = tessellate_faces(&mut faces, rect).1;
// Keep the caller's list in the same far→near order the oracle assumed.
tris.sort_by(|l, r| l.depth().partial_cmp(&r.depth()).unwrap_or(std::cmp::Ordering::Equal));
stats
}
/// **The z-buffered draw.** Rasterise `tris` with a per-pixel depth test into a
/// one-frame texture sized to `rect` in physical pixels, blit it over `rect`, and
/// hand back the [`FaceStats`] oracles.
///
/// `key` names the one-frame texture; give each pane its own (two model viewers can
/// share a screen — the demo's `SplitPane` hosts exactly that). egui applies the
/// texture `set` before painting and the `free` (on handle drop) after, within one
/// `paint_and_update_textures`, so a per-frame upload is safe — a software renderer
/// re-uploads every frame anyway.
#[allow(clippy::ptr_arg)] // public signature (model3d, graph3d logo call it): kept as is
pub fn paint_tris_zbuffered(
ui: &mut egui::Ui,
rect: Rect,
key: &str,
tris: &mut Vec<ShadedTri>,
) -> FaceStats {
let stats = tri_stats(tris, rect);
if tris.is_empty() {
return stats;
}
let ppp = ui.ctx().pixels_per_point().max(0.1);
let w = ((rect.width() * ppp).round() as usize).clamp(1, 8192);
let h = ((rect.height() * ppp).round() as usize).clamp(1, 8192);
let pixels = raster_zbuffer(tris, w, h, rect.min, ppp);
let image = egui::ColorImage::new([w, h], pixels);
let tex = frame_texture(ui, key, image, egui::TextureOptions::LINEAR);
ui.painter_at(rect).image(
tex,
rect,
Rect::from_min_max(Pos2::new(0.0, 0.0), Pos2::new(1.0, 1.0)),
Color32::WHITE,
);
stats
}
/// **A texture re-uploaded every frame, under one stable id.** The handle lives in the
/// context's temp memory under `key`, so frame N+1 `set`s the same texture instead of
/// allocating a new one and freeing the old (the handle drop of a one-frame
/// `load_texture`).
///
/// Why it exists (egui 0.36, lane H2, 2026-10-02): `egui_kittest` 0.36's wgpu renderer
/// applies a frame's texture **frees in `handle_delta`, before it renders**
/// (`egui_kittest-0.36.2/src/wgpu.rs:140`), where 0.35 only applied the sets. A texture
/// loaded and dropped inside one frame is therefore gone by the time a kittest
/// screenshot is drawn — the rabbit logo and the map3d CPU raster rendered blank
/// (MEASURED on the t14s Radeon: `rabbit3d_snapshot` content 0.36 %, main 100 %
/// green). eframe (native `egui-wgpu/src/winit.rs:744`, web
/// `web_painter_wgpu.rs:395`) still frees after submit, so a real host never saw it —
/// and it also saves the per-frame alloc/free there.
///
/// Keyed by `key` AND the calling `Ui`'s id, so two panes passing the same `key` keep
/// two textures (a one-frame texture always got a fresh id).
pub fn frame_texture(
ui: &egui::Ui,
key: &str,
image: egui::ColorImage,
options: egui::TextureOptions,
) -> egui::TextureId {
let ctx = ui.ctx();
let id = ui.id().with(("facett-frame-texture", key));
if let Some(mut tex) = ctx.data(|d| d.get_temp::<egui::TextureHandle>(id)) {
tex.set(image, options);
return tex.id();
}
let tex = ctx.load_texture(key, image, options);
let tid = tex.id();
ctx.data_mut(|d| d.insert_temp(id, tex));
tid
}
/// **The pose-invariant fit.** The projection scale (px per design unit) that makes
/// a solid of bounding-sphere `radius` (about its own pivot) exactly fill `rect`
/// with `margin` (`0..1`, fraction of the half-extent kept as breathing room) — at
/// **every** yaw/tilt, because a sphere is rotation-invariant.
///
/// This replaces the "`rect.size().min_elem() * 0.42`" magic that both 3D panes used
/// to hard-code: that number only *happened* to fit the meshes shipped at the time
/// and silently amputates any model whose corners reach further. Feeding the mesh's
/// own [`bounding_radius`] here makes "the model is never cut off" a property of the
/// geometry rather than a coincidence.
#[must_use]
pub fn fit_scale(rect: Rect, radius: f32, margin: f32) -> f32 {
let half = rect.size().min_elem() * 0.5;
let r = radius.max(1e-6);
(half * margin.clamp(0.0, 1.0) / r).max(0.0)
}
/// The bounding-sphere radius of a point cloud about the origin — the pose-invariant
/// half-extent [`fit_scale`] wants. (`0` for an empty cloud.)
#[must_use]
pub fn bounding_radius<'a>(points: impl IntoIterator<Item = &'a [f32; 3]>) -> f32 {
points
.into_iter()
.map(|p| (p[0] * p[0] + p[1] * p[1] + p[2] * p[2]).sqrt())
.fold(0.0_f32, f32::max)
}
/// Count the **boundary edges** of an indexed triangle mesh: directed edges whose
/// opposite twin is absent. `0` ⇒ the shell is **closed** (watertight) and may be
/// back-face culled safely. Anything else ⇒ it is an **open** shell and culling
/// makes it see-through — see [`is_watertight`].
///
/// Position-welded, so a mesh that splits vertices for normals/UVs (every glTF
/// export does) is judged on its geometry, not its attribute seams. Coordinates are
/// quantised to `1e-5` design units before welding.
#[must_use]
pub fn boundary_edge_count(positions: &[[f32; 3]], indices: &[u32]) -> usize {
use std::collections::{HashMap, HashSet};
let key = |p: [f32; 3]| {
[(p[0] * 1e5).round() as i64, (p[1] * 1e5).round() as i64, (p[2] * 1e5).round() as i64]
};
let mut weld: HashMap<[i64; 3], u32> = HashMap::new();
let mut id: Vec<u32> = Vec::with_capacity(positions.len());
for p in positions {
let n = weld.len() as u32;
id.push(*weld.entry(key(*p)).or_insert(n));
}
let mut dir: HashSet<(u32, u32)> = HashSet::with_capacity(indices.len());
for t in indices.as_chunks::<3>().0 {
let (a, b, c) = (id[t[0] as usize], id[t[1] as usize], id[t[2] as usize]);
for e in [(a, b), (b, c), (c, a)] {
dir.insert(e);
}
}
dir.iter().filter(|(a, b)| !dir.contains(&(*b, *a))).count()
}
/// Is the shell **closed** (every edge shared by two triangles)? A closed shell can
/// be back-face culled — you can never see its inside. An **open** shell must be
/// drawn **two-sided**: culling its back faces leaves you looking straight through
/// the model to the background, which reads as "the model is cut away".
///
/// This is not hypothetical: the bundled CC0 Khronos *Avocado* is a **half**
/// avocado, an open shell whose 41-edge (position-welded) cut rim lies on a flat plane. Back-face
/// culled, the entire inside of the far half vanished and the pane showed background
/// through the fruit — the reported clipping. See
/// [`Model3D`](https://docs.rs/facett-model3d)'s two-sided path.
#[must_use]
pub fn is_watertight(positions: &[[f32; 3]], indices: &[u32]) -> bool {
boundary_edge_count(positions, indices) == 0
}
/// Does every triangle's **geometric** normal agree with its authored **vertex**
/// normal? Returns the count that do **not** — the "inside-out triangles" oracle.
/// A consistently-wound, outward-facing mesh reports `0`; anything else will be
/// back-face culled exactly where it should be drawn (and lit backwards where it is).
///
/// This is the fence that catches a mis-wound generator: the extruded rabbit logo
/// once reported `528` here (both ears, extruded from clockwise silhouette loops)
/// and rendered as hollow troughs.
#[must_use]
pub fn inside_out_triangles(positions: &[[f32; 3]], normals: &[[f32; 3]], indices: &[u32]) -> usize {
let mut bad = 0usize;
for t in indices.as_chunks::<3>().0 {
let (i0, i1, i2) = (t[0] as usize, t[1] as usize, t[2] as usize);
let (Some(p), Some(q), Some(r)) = (positions.get(i0), positions.get(i1), positions.get(i2))
else {
continue;
};
let u = [q[0] - p[0], q[1] - p[1], q[2] - p[2]];
let v = [r[0] - p[0], r[1] - p[1], r[2] - p[2]];
let fnm = [u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0]];
// Average the three authored normals so a single split vertex cannot swing it.
let mut vn = [0.0f32; 3];
for i in [i0, i1, i2] {
if let Some(n) = normals.get(i) {
for c in 0..3 {
vn[c] += n[c];
}
}
}
if fnm[0] * vn[0] + fnm[1] * vn[1] + fnm[2] * vn[2] < 0.0 {
bad += 1;
}
}
bad
}
// ── the robot pose sweep (shared by every CPU-lit 3D pane) ───────────────────────
/// One pose in a sweep: an orientation plus the viewport it is framed in. Mirrors
/// the shape of `facett-map3d`'s 360°×zoom×tilt robot sweep, lifted to the
/// orthographic model viewers (where "zoom" is the pane the model is fitted to).
#[derive(Clone, Debug, PartialEq)]
pub struct Pose {
/// Orbit yaw (radians).
pub yaw: f32,
/// Tilt about X (radians).
pub tilt: f32,
/// The viewport the model is fitted + centred on.
pub viewport: Rect,
/// Human-readable id, e.g. `"yaw 185° · tilt 0.60 · 1264x444"`.
pub label: String,
}
/// Build the canonical **360° × zoom × tilt** pose grid: `yaw_steps` yaws evenly
/// around a full turn, crossed with every `tilt` and every `viewport` (the zoom
/// axis — a model viewer zooms by changing how much pane it is fitted to).
#[must_use]
pub fn pose_grid(yaw_steps: usize, tilts: &[f32], viewports: &[Rect]) -> Vec<Pose> {
let mut out = Vec::with_capacity(yaw_steps * tilts.len() * viewports.len());
for i in 0..yaw_steps.max(1) {
let yaw = i as f32 * std::f32::consts::TAU / yaw_steps.max(1) as f32;
for &tilt in tilts {
for &viewport in viewports {
out.push(Pose {
yaw,
tilt,
viewport,
label: format!(
"yaw {:3.0}° · tilt {tilt:+.2} · {:.0}x{:.0}",
yaw.to_degrees(),
viewport.width(),
viewport.height()
),
});
}
}
}
out
}
/// What a [`sweep`] found — the worst offender per oracle, each carrying the pose
/// that produced it so a failure names the exact camera state.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct SweepReport {
/// How many poses were driven.
pub poses: usize,
/// Worst `ink_outside_rect` seen, and where. MUST be `(0, _)`.
pub worst_ink: (usize, String),
/// Fewest `visible_triangles` seen, and where — the "did a pose lose geometry
/// it should have kept" oracle.
pub min_visible: (usize, String),
/// Worst `max_extent_px` seen, and where — a spoke blows this up.
pub worst_extent: (f32, String),
/// Worst pre-scissor overshoot seen, and where — a bad fit shows up here even
/// though the scissor makes it harmless.
pub worst_raw_overshoot: (f32, String),
/// How many poses reported a non-monotone painter order.
pub non_monotone_poses: usize,
/// Lowest `lit_fraction` seen, and where — a pose that went dark.
pub min_lit_fraction: (f32, String),
}
impl SweepReport {
/// The one-line summary a `testmatrix` emitter carries.
#[must_use]
pub fn detail(&self) -> String {
format!(
"poses={} worst_ink_outside_rect={} (at {}) min_visible_triangles={} (at {}) \
worst_max_extent_px={:.1} (at {}) worst_raw_overshoot_px={:.1} min_lit_fraction={:.2} \
non_monotone_poses={}",
self.poses,
self.worst_ink.0,
self.worst_ink.1,
self.min_visible.0,
self.min_visible.1,
self.worst_extent.0,
self.worst_extent.1,
self.worst_raw_overshoot.0,
self.min_lit_fraction.0,
self.non_monotone_poses,
)
}
}
/// Drive `poses` through `stats_of` (the pane's own project→clip pipeline) and
/// reduce the per-pose [`FaceStats`] into a [`SweepReport`]. Pure and headless — the
/// sweep a robot-UI test asserts.
pub fn sweep(poses: &[Pose], mut stats_of: impl FnMut(&Pose) -> FaceStats) -> SweepReport {
let mut r = SweepReport {
poses: poses.len(),
min_visible: (usize::MAX, String::new()),
min_lit_fraction: (f32::MAX, String::new()),
..SweepReport::default()
};
for p in poses {
let s = stats_of(p);
if s.ink_outside_rect > r.worst_ink.0 {
r.worst_ink = (s.ink_outside_rect, p.label.clone());
}
if s.visible_triangles < r.min_visible.0 {
r.min_visible = (s.visible_triangles, p.label.clone());
}
if s.max_extent_px > r.worst_extent.0 {
r.worst_extent = (s.max_extent_px, p.label.clone());
}
if s.raw_overshoot_px > r.worst_raw_overshoot.0 {
r.worst_raw_overshoot = (s.raw_overshoot_px, p.label.clone());
}
if s.lit_fraction < r.min_lit_fraction.0 {
r.min_lit_fraction = (s.lit_fraction, p.label.clone());
}
if !s.depth_monotone {
r.non_monotone_poses += 1;
}
}
if r.min_visible.0 == usize::MAX {
r.min_visible = (0, "no poses".into());
}
if r.min_lit_fraction.0 == f32::MAX {
r.min_lit_fraction = (0.0, "no poses".into());
}
r
}
#[cfg(test)]
mod tests {
use super::*;
use egui::pos2;
fn rect() -> Rect {
Rect::from_min_max(pos2(0.0, 0.0), pos2(100.0, 100.0))
}
/// RED-when-broken: a face sprawling far past the rect is *confined* — every
/// emitted vertex sits inside, so the bug oracle reads 0. Delete the scissor and
/// this fails.
#[test]
fn sprawling_face_is_confined_and_leaks_no_ink() {
let mut faces: Vec<ShadedFace> =
vec![(0.0, [pos2(-900.0, 40.0), pos2(40.0, -900.0), pos2(900.0, 900.0)], Color32::WHITE)];
let (mesh, st) = tessellate_faces(&mut faces, rect());
assert_eq!(st.ink_outside_rect, 0, "no emitted vertex escapes the rect");
assert_eq!(st.visible_triangles, 1, "the crossing face still draws");
assert!(!mesh.is_empty(), "it produced real geometry");
assert!(st.max_extent_px <= 100.0 + 1e-3, "extent is bounded by the rect: {}", st.max_extent_px);
assert!(st.raw_overshoot_px > 100.0, "the RAW face really did poke out: {}", st.raw_overshoot_px);
}
/// RED-when-broken: the exact shape that used to detonate `epaint`'s miter join —
/// a zero-area sliver — is rejected, not emitted.
#[test]
fn degenerate_slivers_are_rejected() {
// Three collinear points: |2·area| == 0.
let mut faces: Vec<ShadedFace> =
vec![(0.0, [pos2(10.0, 50.0), pos2(50.0, 50.0), pos2(90.0, 50.0)], Color32::WHITE)];
let (mesh, st) = tessellate_faces(&mut faces, rect());
assert_eq!(st.degenerate_dropped, 1, "the collinear sliver is dropped");
assert_eq!(st.visible_triangles, 0);
assert!(mesh.is_empty(), "nothing is emitted for a zero-area face");
}
/// A wholly-outside face is dropped by the scissor; an inside face is kept whole.
#[test]
fn offscreen_dropped_and_inside_kept() {
let mut faces: Vec<ShadedFace> = vec![
(0.0, [pos2(300.0, 300.0), pos2(340.0, 300.0), pos2(320.0, 340.0)], Color32::WHITE),
(1.0, [pos2(10.0, 10.0), pos2(90.0, 10.0), pos2(50.0, 90.0)], Color32::WHITE),
];
let (_m, st) = tessellate_faces(&mut faces, rect());
assert_eq!(st.offscreen_dropped, 1);
assert_eq!(st.visible_triangles, 1);
assert_eq!(st.ink_outside_rect, 0);
assert!(st.depth_monotone, "the pass sorts far→near itself");
assert!((st.lit_fraction - 1.0).abs() < 1e-6, "a white face is lit");
}
/// The fit is pose-invariant: a unit-radius solid at any rotation stays inside.
#[test]
fn fit_scale_keeps_a_unit_sphere_inside_the_rect() {
let r = Rect::from_min_max(pos2(0.0, 0.0), pos2(400.0, 200.0));
let s = fit_scale(r, 1.0, 0.94);
// Worst case: a vertex at radius 1 in ANY direction.
assert!(s * 1.0 <= r.size().min_elem() * 0.5 + 1e-3, "scale {s} keeps radius 1 inside");
assert!(s > 0.0);
// A fatter solid gets proportionally smaller.
assert!((fit_scale(r, 2.0, 0.94) - s * 0.5).abs() < 1e-3);
}
/// RED-when-broken: the z-buffer resolves by **pixel depth**, not face order.
/// Two interpenetrating triangles — the exact case a painter's-algorithm
/// centroid sort gets wrong — each win the half of the overlap they are nearer
/// in, whichever order they arrive in.
#[test]
fn zbuffer_resolves_interpenetrating_faces_either_way_round() {
let red = Color32::from_rgb(255, 0, 0);
let blue = Color32::from_rgb(0, 0, 255);
// Two big quads-as-triangles covering the same 10x10 area, tilted so RED is
// nearer on the left and BLUE is nearer on the right. Equal MEAN depth, so a
// centroid sort has no information at all — only per-pixel depth can do it.
let a = ShadedTri {
pts: [pos2(0.0, 0.0), pos2(10.0, 0.0), pos2(0.0, 10.0)],
vz: [1.0, -1.0, 0.0],
col: red,
};
let b = ShadedTri {
pts: [pos2(0.0, 0.0), pos2(10.0, 0.0), pos2(0.0, 10.0)],
vz: [-1.0, 1.0, 0.0],
col: blue,
};
assert!((a.depth() - b.depth()).abs() < 1e-6, "equal mean depth: a sort cannot help");
// Row-major index of pixel (x, y) in the 10-wide buffer.
let at = |x: usize, y: usize| y * 10 + x;
for (order, tris) in [("a,b", vec![a, b]), ("b,a", vec![b, a])] {
let px = raster_zbuffer(&tris, 10, 10, pos2(0.0, 0.0), 1.0);
// Near the left edge RED is in front; near the right edge BLUE is.
assert_eq!(px[at(0, 1)], red, "order {order}: left column is the nearer (red) face");
assert_eq!(px[at(8, 0)], blue, "order {order}: right column is the nearer (blue) face");
}
}
/// The raster never writes outside its own buffer, however far the geometry
/// sprawls — `ink_outside_rect == 0` structurally on this lane.
#[test]
fn zbuffer_raster_confines_a_sprawling_triangle() {
let t = ShadedTri {
pts: [pos2(-9000.0, 40.0), pos2(40.0, -9000.0), pos2(9000.0, 9000.0)],
vz: [0.0, 0.0, 0.0],
col: Color32::WHITE,
};
let px = raster_zbuffer(&[t], 32, 32, pos2(0.0, 0.0), 1.0);
assert_eq!(px.len(), 32 * 32, "the buffer is exactly the rect");
assert!(px.iter().any(|c| *c != Color32::TRANSPARENT), "and it did draw inside it");
}
/// RED-when-broken: a closed tetrahedron is watertight and outward-wound; open
/// it (drop a face) and the boundary shows; invert a face and the inside-out
/// oracle names it.
#[test]
fn watertight_and_inside_out_oracles_are_sensitive() {
// Unit tetrahedron, all faces wound CCW seen from outside.
let pos = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]];
let closed: Vec<u32> = vec![0, 2, 1, 0, 1, 3, 0, 3, 2, 1, 2, 3];
assert_eq!(boundary_edge_count(&pos, &closed), 0, "a closed tetrahedron has no boundary");
assert!(is_watertight(&pos, &closed));
// Outward vertex normals = the vertex directions from the centroid.
let c = [0.25f32, 0.25, 0.25];
let nrm: Vec<[f32; 3]> = pos.iter().map(|p| [p[0] - c[0], p[1] - c[1], p[2] - c[2]]).collect();
assert_eq!(inside_out_triangles(&pos, &nrm, &closed), 0, "outward-wound: nothing inside-out");
// Drop one face → an open shell with a 3-edge boundary.
let open: Vec<u32> = closed[..9].to_vec();
assert_eq!(boundary_edge_count(&pos, &open), 3, "the missing face leaves a 3-edge rim");
assert!(!is_watertight(&pos, &open), "an open shell is NOT watertight");
// Flip one face → exactly one inside-out triangle.
let mut flipped = closed.clone();
flipped.swap(0, 1);
assert_eq!(inside_out_triangles(&pos, &nrm, &flipped), 1, "the flipped face is named");
}
#[test]
fn bounding_radius_is_the_farthest_point() {
let pts = [[0.0, 0.0, 0.0], [3.0, 4.0, 0.0], [1.0, 1.0, 1.0]];
assert!((bounding_radius(pts.iter()) - 5.0).abs() < 1e-5);
assert_eq!(bounding_radius(std::iter::empty()), 0.0);
}
/// The grid really is 360° × tilts × viewports, and the reducer reports the
/// WORST pose by name (not an average that hides one bad frame).
#[test]
fn sweep_reports_the_worst_pose_by_name() {
let vps = [Rect::from_min_max(pos2(0.0, 0.0), pos2(100.0, 100.0))];
let poses = pose_grid(8, &[0.0, 0.5], &vps);
assert_eq!(poses.len(), 16, "8 yaws × 2 tilts × 1 viewport");
assert!(poses[0].label.contains("yaw 0°"), "{}", poses[0].label);
// One deliberately-bad pose in the middle: the reducer must surface IT.
let bad = poses[5].label.clone();
let r = sweep(&poses, |p| FaceStats {
visible_triangles: if p.label == bad { 1 } else { 40 },
ink_outside_rect: usize::from(p.label == bad) * 7,
max_extent_px: if p.label == bad { 900.0 } else { 30.0 },
depth_monotone: p.label != bad,
lit_fraction: 1.0,
..FaceStats::default()
});
assert_eq!(r.poses, 16);
assert_eq!(r.worst_ink, (7, bad.clone()), "the leaking pose is named");
assert_eq!(r.min_visible, (1, bad.clone()), "the geometry-losing pose is named");
assert_eq!(r.worst_extent.0, 900.0);
assert_eq!(r.non_monotone_poses, 1);
}
}