graphic design tool
git clone https://git.lucas.co/cce-designer.git
feat(phase3): develop, an incremental remesher, and a winding fix underneath both
Develop moves the surface along its point normals by an attribute — the step
that turns a field into a shape, and the thing every other Developer operator
exists to feed. It moves points and touches nothing else; a node that quietly
retriangulated while it displaced would make it impossible to tell which of the
two turned a simulation to mush.
Remesh is the counterweight, and it is its own module with its own tests
because the algorithm is worth reading on its own. Split edges over 4/3 of the
target, collapse under 4/5, flip toward valence 6, relax tangentially. The
thresholds are the paper's and they are not arbitrary: a narrower window lets a
split produce edges the next collapse undoes, and the mesh oscillates instead
of converging — which is what test_remesh_converges_rather_than_oscillating
holds it to.
It is careful with what the solver has been accumulating, because Phase 2 was
built for this: a split interpolates every attribute from the two endpoints, a
collapse keeps one endpoint's identity AND values rather than averaging into a
new point, and a new point joins a group only where both parents were members —
otherwise every group grows along its own boundary at every remesh.
Three bugs found by the tests, one serious:
The passes iterated a stale edge list. After one split, the triangle indices
recorded for later edges pointed at faces that no longer existed, and acting on
them tore the surface open. The edge LIST stays a snapshot — a pass decides up
front what it will consider — but the TRIANGLES are looked up at the moment of
the act, through a point-to-triangle incidence maintained as the mesh changes.
Reversing a quad moves its fan diagonal, so the first winding fix silently
retriangulated every band. The quads are now reversed but anchored on the same
corner: same two triangles, opposite facing.
And the one that was already there: THE NATIVE GENERATORS WOUND BACKWARDS.
Every normal on a native sphere pointed into it (0 of 42 outward), and every
face of a native box wound against the Norm attribute the same function
attached to it. The template meshes were always right — 362 of 362 — which is
why test_template_meshes_wind_ccw_outward and the overlay test both passed, and
a path tracer shades both sides so nothing ever looked wrong. Develop is the
first operator whose answer depends on it: it grew the surface inward. The
soup-equivalence test now compares triangles as an unordered set and asserts
the normals face out.
--thumbnail takes --frame, because a simulation that cannot be rendered without
a Wayland session cannot be checked. The growth chain in this commit — kernel
seed, Diffuse, Develop, Remesh, Visualize, inside a simnet — was verified
through it.
Co-Authored-By: Claude Opus 5 <[email protected]>
CLAUDE.md | 7 +-
nodes/develop.json | 14 ++
nodes/remesh.json | 15 ++
shapeshifter.md | 17 ++
src/detail.rs | 22 ++
src/geometry.rs | 229 +++++++++++++++++++--
src/main.rs | 244 +++++++++++++++++++++-
src/remesh.rs | 581 +++++++++++++++++++++++++++++++++++++++++++++++++++++
src/thumbnail.rs | 13 +-
9 files changed, 1115 insertions(+), 27 deletions(-)
diff --git a/CLAUDE.md b/CLAUDE.md
index 565ed4d..0b766ec 100644
--- a/CLAUDE.md
+++ b/CLAUDE.md
@@ -35,9 +35,12 @@ cross-validation test compares backends and skips silently with no platform.
### CLI modes
-- `cce-designer --thumbnail <project-dir-or-state.json> <out.png> [--size N] [--samples N]`
+- `cce-designer --thumbnail <project-dir-or-state.json> <out.png> [--size N] [--samples N] [--frame N]`
— headless path-traced thumbnail (no Wayland, no window; `src/thumbnail.rs`).
- `cce-files` shells out to this for its preview cache.
+ `cce-files` shells out to this for its preview cache. Without `--frame` there
+ is no timeline and simnets render at their seed; with it the solve runs to
+ that frame (start frame 1, the playbar's default), which is the only way to
+ look at a simulation without a Wayland session.
- `cce-designer --detached-network` — a separate network-pane-only window. It syncs
with the main window by autosaving/polling `default_project.json` mtime (see the
main loop in `src/main.rs`) — there is no socket between the two.
diff --git a/nodes/develop.json b/nodes/develop.json
new file mode 100644
index 0000000..f5354d7
--- /dev/null
+++ b/nodes/develop.json
@@ -0,0 +1,14 @@
+{
+ "name": "Develop",
+ "type": "develop",
+ "inputs": 1,
+ "outputs": 1,
+ "params": [
+ { "name": "Input", "type": "text", "default": "" },
+ { "name": "Attribute", "type": "text", "default": "growth" },
+ { "name": "Scale", "type": "slider", "default": "0.10", "min": -2.0, "max": 2.0, "step": 0.01 },
+ { "name": "Direction", "type": "choice:Normal,Attribute", "default": "Normal" },
+ { "name": "Source", "type": "text", "default": "" },
+ { "name": "Group", "type": "text", "default": "" }
+ ]
+}
diff --git a/nodes/remesh.json b/nodes/remesh.json
new file mode 100644
index 0000000..9b62608
--- /dev/null
+++ b/nodes/remesh.json
@@ -0,0 +1,15 @@
+{
+ "name": "Remesh",
+ "type": "remesh",
+ "inputs": 1,
+ "outputs": 1,
+ "params": [
+ { "name": "Input", "type": "text", "default": "" },
+ { "name": "Target Length", "type": "slider", "default": "0.10", "min": 0.001, "max": 1.0, "step": 0.005 },
+ { "name": "Iterations", "type": "spinbox", "default": "3", "min": 1.0, "max": 20.0, "step": 1.0 },
+ { "name": "Relax", "type": "slider", "default": "0.50", "min": 0.0, "max": 1.0, "step": 0.01 },
+ { "name": "Split", "type": "choice:true,false", "default": "true" },
+ { "name": "Collapse", "type": "choice:true,false", "default": "true" },
+ { "name": "Flip", "type": "choice:true,false", "default": "true" }
+ ]
+}
diff --git a/shapeshifter.md b/shapeshifter.md
index d7e02dc..0f7aa68 100644
--- a/shapeshifter.md
+++ b/shapeshifter.md
@@ -218,6 +218,23 @@ Touches: `geometry.rs`, `app.rs`, `render.rs`, `playbar.rs`.
*Large. Needs Phases 0, 1 and 2.*
+> **Started.** `develop` displaces along the point normal by an attribute, and
+> `remesh` is in as its own module (`src/remesh.rs`): split, collapse, flip and
+> tangential relax, the Botsch–Kobbelt passes. It carries the simulation's data
+> across — a split interpolates, a collapse keeps the survivor's identity and
+> values, and a group only grows where both parents were members.
+>
+> Fixed on the way: the native generators wound BACKWARDS. Every normal on a
+> native sphere pointed into it, and every face of a native box wound against
+> the `Norm` it shipped. The template meshes were always right, which is why
+> the winding test and the overlay test both passed; a path tracer shades both
+> sides, so nothing looked wrong. Develop is the first operator whose answer
+> depends on it, and it grew the surface inward.
+>
+> Outstanding: `adapt`, `open`, and collision (`detangle`, `suture`) — which
+> want the spatial index the remesher's missing surface-projection pass also
+> needs.
+
`Develop` is easy — displace along the normal by a development attribute.
**Remesh is the hard one**, and it is load-bearing: without topology that keeps
primitives proportional to surface area, every growth sim degenerates within a
diff --git a/src/detail.rs b/src/detail.rs
index a252931..3eefe78 100644
--- a/src/detail.rs
+++ b/src/detail.rs
@@ -1162,6 +1162,28 @@ impl Detail {
.collect()
}
+ /// Replace every point's identity, and the counter new points draw from.
+ ///
+ /// For a rebuild that KNOWS which points it preserved — the remesher,
+ /// which tears a mesh apart and puts it back, and needs the survivors to
+ /// come out as themselves. Everything else must let [`Detail::add_point`]
+ /// allocate, or two points end up answering to one identity.
+ ///
+ /// A mismatched length is refused rather than padded: a partial identity
+ /// map is worse than none, because the points it does map look right.
+ pub fn set_ids(&mut self, ids: Vec<PointId>, next_id: PointId) -> Result<(), String> {
+ if ids.len() != self.pos.len() {
+ return Err(format!(
+ "{} identities for {} points",
+ ids.len(),
+ self.pos.len()
+ ));
+ }
+ self.next_id = next_id.max(ids.iter().copied().max().map(|m| m + 1).unwrap_or(0));
+ self.ids = ids;
+ Ok(())
+ }
+
/// Add a point at `pos`, assigning it a fresh identity. Returns its index.
pub fn add_point(&mut self, pos: Vec3) -> u32 {
let idx = self.pos.len() as u32;
diff --git a/src/geometry.rs b/src/geometry.rs
index b074591..e382ff6 100644
--- a/src/geometry.rs
+++ b/src/geometry.rs
@@ -309,22 +309,34 @@ pub fn sphere_detail(center: Vec3, radius: f32, lat_steps: usize, lon_steps: usi
}
let south = d.add_point(sphere_point(center, radius, std::f32::consts::PI, 0.0));
- // Winding follows the soup's exactly, so the fan in `Detail::triangulate`
- // reproduces the old triangles corner for corner — minus the degenerate
- // pole pair, which is why a sphere is now 2*lon_steps triangles lighter.
+ // Wound counter-clockwise seen from OUTSIDE, so the plain
+ // cross(B-A, C-A) points away from the surface. That is the raster
+ // culling convention, what the template meshes do, and what
+ // `point_normals` — and therefore Develop, the normal overlay and
+ // Align's surface tangent — all assume.
+ //
+ // The soup this replaced wound the other way, and had done since it was
+ // written: every normal on a native sphere pointed INTO it. Nothing
+ // caught it because the winding test covers the template meshes, the
+ // overlay test uses a template sphere, and a path tracer shades both
+ // sides of a triangle. Develop is the first operator whose answer depends
+ // on it, and it grew the surface inward.
let wrap = |lon: usize| (lon + 1) % lon_steps;
for lon in 0..lon_steps {
- d.add_prim(&[north, rings[0][lon], rings[0][wrap(lon)]]);
+ d.add_prim(&[north, rings[0][wrap(lon)], rings[0][lon]]);
}
+ // Each quad is the soup's quad reversed but ANCHORED on the same corner,
+ // so it fans into the same two triangles rather than across the other
+ // diagonal. The surface is identical; only the facing changed.
for lat in 1..lat_steps - 1 {
let (a, b) = (&rings[lat - 1], &rings[lat]);
for lon in 0..lon_steps {
- d.add_prim(&[a[lon], b[lon], b[wrap(lon)], a[wrap(lon)]]);
+ d.add_prim(&[a[lon], a[wrap(lon)], b[wrap(lon)], b[lon]]);
}
}
let last = &rings[lat_steps - 2];
for lon in 0..lon_steps {
- d.add_prim(&[last[lon], south, last[wrap(lon)]]);
+ d.add_prim(&[last[lon], last[wrap(lon)], south]);
}
let n: Vec<Vec3> = (0..d.num_points())
@@ -404,15 +416,17 @@ pub fn box_detail(start: Vec3, end: Vec3, thickness: f32) -> Detail {
d.add_point(c);
}
- // Face winding is the soup's: each `add_quad(p0, p1, p2, p3)` emitted
- // (p0, p1, p2) then (p0, p2, p3), which is exactly a fan over the quad.
+ // Wound counter-clockwise seen from outside, like the sphere and the
+ // template meshes. The soup's order was the reverse, which meant every
+ // face of a native box wound against the `Norm` attribute the same
+ // function attached to it — the geometry and its own normal disagreed.
let faces: [([u32; 4], Vec3); 6] = [
- ([0, 1, 2, 3], -dir), // start cap
- ([5, 4, 7, 6], dir), // end cap
- ([4, 0, 3, 7], -u), // left
- ([1, 5, 6, 2], u), // right
- ([3, 2, 6, 7], v), // top
- ([0, 4, 5, 1], -v), // bottom
+ ([3, 2, 1, 0], -dir), // start cap
+ ([6, 7, 4, 5], dir), // end cap
+ ([7, 3, 0, 4], -u), // left
+ ([2, 6, 5, 1], u), // right
+ ([7, 6, 2, 3], v), // top
+ ([1, 5, 4, 0], -v), // bottom
];
for (quad, _) in &faces {
d.add_prim(quad);
@@ -726,6 +740,10 @@ pub fn generate_single_node_geometry_with_errors(
resolve_neighbour_geometry_with_errors(root, target, visited, ocl_error, sim)
} else if target.node_type.eq_ignore_ascii_case("time") {
resolve_time_geometry_with_errors(root, target, visited, ocl_error, sim)
+ } else if target.node_type.eq_ignore_ascii_case("remesh") {
+ resolve_remesh_geometry_with_errors(root, target, visited, ocl_error, sim)
+ } else if target.node_type.eq_ignore_ascii_case("develop") {
+ resolve_develop_geometry_with_errors(root, target, visited, ocl_error, sim)
} else if target.node_type.eq_ignore_ascii_case("visualize") {
resolve_visualize_geometry_with_errors(root, target, visited, ocl_error, sim)
} else if target.node_type.eq_ignore_ascii_case("analysis") {
@@ -1274,6 +1292,126 @@ pub fn resolve_relax_geometry_with_errors(
Some(geom)
}
+/// The Remesh node: keep the triangulation proportional to the surface.
+///
+/// The counterweight to Develop. Growth pushes points apart and the triangles
+/// between them stretch; an attribute diffused across a stretched mesh is
+/// being averaged over distances that no longer mean what they meant, so a
+/// growth sim without remeshing degenerates within a few dozen frames however
+/// good its attribute maths is.
+///
+/// The passes live in [`crate::remesh`], with their own tests, because the
+/// algorithm is worth reading on its own and a node body is not where it
+/// belongs.
+pub fn resolve_remesh_geometry_with_errors(
+ root: &FsNode,
+ target: &FsNode,
+ visited: &mut Vec<String>,
+ ocl_error: &mut Option<String>,
+ sim: &mut EvalSim,
+) -> Option<Detail> {
+ let input_name = node_param_str(target, "Input", "");
+ if input_name.is_empty() {
+ return None;
+ }
+ let input_node = find_node_by_name(root, &input_name)?;
+ let geom = generate_single_node_geometry_with_errors(root, input_node, visited, ocl_error, sim)?;
+ Some(crate::remesh::remesh(&geom, remesh_settings(target)))
+}
+
+pub(crate) fn remesh_settings(target: &FsNode) -> crate::remesh::Settings {
+ crate::remesh::Settings {
+ target: node_param_f32(target, "Target Length", 0.1).max(1e-4),
+ iterations: node_param_f32(target, "Iterations", 3.0).clamp(1.0, 20.0) as usize,
+ relax: node_param_f32(target, "Relax", 0.5),
+ split: node_param_str(target, "Split", "true") == "true",
+ collapse: node_param_str(target, "Collapse", "true") == "true",
+ flip: node_param_str(target, "Flip", "true") == "true",
+ }
+}
+
+/// The Develop node: move the surface along its normals by an attribute.
+///
+/// The whole of surface development in one operator — everything else in the
+/// Developer set exists to decide WHAT this should read. A growth attribute
+/// built by diffusion, migration and decay is a scalar field; Develop is the
+/// step that turns a field into a shape.
+///
+/// Direction Normal displaces along the smooth point normal, which is what
+/// growth means on a surface. Direction Attribute takes a vector attribute
+/// instead, for the cases where the surface is not what decides — a
+/// gravity-fed sag, a flow along a field.
+///
+/// Note what this deliberately does NOT do: it moves points and touches
+/// nothing else. Topology is `remesh`'s business, and a node that quietly
+/// retriangulated while it displaced would make it impossible to tell which of
+/// the two turned a simulation to mush.
+pub fn resolve_develop_geometry_with_errors(
+ root: &FsNode,
+ target: &FsNode,
+ visited: &mut Vec<String>,
+ ocl_error: &mut Option<String>,
+ sim: &mut EvalSim,
+) -> Option<Detail> {
+ let input_name = node_param_str(target, "Input", "");
+ if input_name.is_empty() {
+ return None;
+ }
+ let input_node = find_node_by_name(root, &input_name)?;
+ let mut geom = generate_single_node_geometry_with_errors(root, input_node, visited, ocl_error, sim)?;
+ apply_develop(&mut geom, target, ocl_error);
+ Some(geom)
+}
+
+pub(crate) fn apply_develop(geom: &mut Detail, target: &FsNode, ocl_error: &mut Option<String>) {
+ let name = node_param_str(target, "Attribute", "").trim().to_string();
+ if name.is_empty() {
+ return;
+ }
+ if !geom.points().has(&name) {
+ if ocl_error.is_none() {
+ *ocl_error = Some(format!(
+ "Develop '{}': no point attribute named '{}'",
+ target.name, name
+ ));
+ }
+ return;
+ }
+
+ let scale = node_param_f32(target, "Scale", 0.1);
+ let group = node_param_str(target, "Group", "");
+ let group = group.trim().to_string();
+ let by_attr = node_param_str(target, "Direction", "Normal").eq_ignore_ascii_case("attribute");
+ let src = node_param_str(target, "Source", "");
+ let src = src.trim().to_string();
+
+ // Normals come off the geometry as it arrives, so every point is displaced
+ // along the surface it had BEFORE the displacement — otherwise the points
+ // computed late would be following a surface the earlier ones had already
+ // moved, and the result would depend on point order.
+ let dirs: Vec<Vec3> = if by_attr {
+ (0..geom.num_points())
+ .map(|p| {
+ geom.points()
+ .value(&src, p)
+ .map(|v| v.as_vec3())
+ .unwrap_or(Vec3::ZERO)
+ })
+ .collect()
+ } else {
+ point_normals(geom)
+ };
+
+ for p in 0..geom.num_points() {
+ if !group.is_empty() && !geom.points().in_group(&group, p) {
+ continue;
+ }
+ let amount = geom.points().value(&name, p).map(|v| v.as_f32()).unwrap_or(0.0);
+ let moved = geom.pos(p) + dirs[p] * (amount * scale);
+ geom.set_pos(p, moved);
+ }
+}
+
/// Sample one of the built-in ramps at `t`, clamped to 0..1.
///
/// Named ramps rather than an editable curve because there is no ramp widget
@@ -3544,6 +3682,8 @@ pub fn is_geometry_node_type(node_type: &str) -> bool {
|| nt == "time"
|| nt == "analysis"
|| nt == "visualize"
+ || nt == "develop"
+ || nt == "remesh"
|| nt == "attribute"
|| nt == "simnet"
}
@@ -3691,6 +3831,24 @@ pub fn network_sphere_vertices_with_errors(
out.merge(&geom);
}
}
+ } else if node.node_type.eq_ignore_ascii_case("remesh") {
+ let _idx = *count;
+ *count += 1;
+ if is_visible {
+ let mut visited = Vec::new();
+ if let Some(geom) = resolve_remesh_geometry_with_errors(root, node, &mut visited, ocl_error, sim) {
+ out.merge(&geom);
+ }
+ }
+ } else if node.node_type.eq_ignore_ascii_case("develop") {
+ let _idx = *count;
+ *count += 1;
+ if is_visible {
+ let mut visited = Vec::new();
+ if let Some(geom) = resolve_develop_geometry_with_errors(root, node, &mut visited, ocl_error, sim) {
+ out.merge(&geom);
+ }
+ }
} else if node.node_type.eq_ignore_ascii_case("visualize") {
let _idx = *count;
*count += 1;
@@ -4281,12 +4439,43 @@ mod tests {
assert_eq!(before.len(), lat * lon * 6);
assert_eq!(kept.len(), sphere_soup_len(lat, lon), "only the pole bands go");
assert_eq!(after.len(), kept.len());
- for (i, (a, b)) in after.iter().zip(kept.iter()).enumerate() {
- // Not bit-identical, and the difference is the point: the soup
- // computed its seam corner at phi = TAU and its south pole once per
- // longitude, so the surface had a ~1e-7 crack down it. The welded
- // sphere computes each of those places once.
- assert!(d(*a, *b) < 1e-5, "corner {i}: {a:?} vs {b:?}");
+
+ // The same triangles, wound the other way round. The soup wound
+ // clockwise seen from outside, so every normal on a native sphere
+ // pointed INTO it; the welded generator wound with it until Develop
+ // made the bug visible.
+ //
+ // Compared as an unordered collection of triangles, each keyed by its
+ // corners rounded and sorted. Not bit-identical, and the difference is
+ // the point: the soup computed its seam corner at phi = TAU and its
+ // south pole once per longitude, so the surface had a ~1e-7 crack down
+ // it, which is also why the key rounds before it sorts.
+ let key = |t: &[[f32; 3]]| {
+ let mut c: Vec<[i64; 3]> = t
+ .iter()
+ .map(|p| {
+ [
+ (p[0] as f64 * 1e4).round() as i64,
+ (p[1] as f64 * 1e4).round() as i64,
+ (p[2] as f64 * 1e4).round() as i64,
+ ]
+ })
+ .collect();
+ c.sort_unstable();
+ c
+ };
+ let mut want: Vec<Vec<[i64; 3]>> = kept.chunks_exact(3).map(key).collect();
+ let mut got: Vec<Vec<[i64; 3]>> = after.chunks_exact(3).map(key).collect();
+ want.sort();
+ got.sort();
+ assert_eq!(got, want, "the welded sphere is not the same set of triangles");
+
+ // And they face outward now, which is the whole reason for the change.
+ let welded = sphere_detail(center, radius, lat, lon);
+ let normals = point_normals(&welded);
+ for p in 0..welded.num_points() {
+ let radial = (welded.pos(p) - center).normalize();
+ assert!(normals[p].dot(radial) > 0.0, "point {p} still faces inward");
}
}
diff --git a/src/main.rs b/src/main.rs
index d6675b1..6484064 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -3,6 +3,7 @@ pub mod app;
pub mod application;
pub mod curve_tool;
pub mod detail;
+pub mod remesh;
// Root-level aliases some modules import via `crate::` paths.
#[allow(unused_imports)]
@@ -37,7 +38,7 @@ fn main() {
if let Some(i) = args.iter().position(|a| a == "--thumbnail") {
let _ = env_logger::try_init();
let (Some(project), Some(out)) = (args.get(i + 1), args.get(i + 2)) else {
- eprintln!("usage: cce-designer --thumbnail <project> <out.png> [--size N]");
+ eprintln!("usage: cce-designer --thumbnail <project> <out.png> [--size N] [--samples N] [--frame N]");
std::process::exit(2);
};
let size = args
@@ -50,7 +51,11 @@ fn main() {
.windows(2)
.find(|w| w[0] == "--samples")
.and_then(|w| w[1].parse::<u32>().ok());
- match thumbnail::run(std::path::Path::new(project), std::path::Path::new(out), size, samples) {
+ let frame = args
+ .windows(2)
+ .find(|w| w[0] == "--frame")
+ .and_then(|w| w[1].parse::<i32>().ok());
+ match thumbnail::run(std::path::Path::new(project), std::path::Path::new(out), size, samples, frame) {
Ok(()) => std::process::exit(0),
Err(e) => {
eprintln!("cce-designer --thumbnail: {e}");
@@ -3356,6 +3361,241 @@ mod tests {
}
}
+ // ---- Phase 3: surface development ----
+
+ use crate::geometry::sphere_detail;
+ use crate::remesh::{remesh, Settings};
+
+ /// Mean edge length, the number remeshing steers.
+ fn mean_edge(d: &Detail) -> f32 {
+ let edges = d.edges();
+ if edges.is_empty() {
+ return 0.0;
+ }
+ edges
+ .iter()
+ .map(|e| (d.pos(e[1] as usize) - d.pos(e[0] as usize)).length())
+ .sum::<f32>()
+ / edges.len() as f32
+ }
+
+ #[test]
+ fn test_remesh_pulls_edge_lengths_toward_the_target_from_both_sides() {
+ let coarse = sphere_detail(Vec3::ZERO, 1.0, 6, 8);
+ let before = mean_edge(&coarse);
+ assert!(before > 0.4, "the test sphere starts coarse: {before}");
+
+ // Too coarse: splitting dominates and the mesh gets denser.
+ let finer = remesh(&coarse, Settings { target: 0.2, iterations: 4, ..Default::default() });
+ let after = mean_edge(&finer);
+ assert!(after < before, "{after} is not shorter than {before}");
+ assert!(finer.num_points() > coarse.num_points(), "a finer mesh needs more points");
+ assert!((after - 0.2).abs() < 0.12, "landed at {after}, wanted about 0.2");
+
+ // Too fine: collapsing dominates and the mesh gets coarser. The same
+ // node, the same passes, steered from the other side.
+ let dense = sphere_detail(Vec3::ZERO, 1.0, 24, 32);
+ let dense_before = mean_edge(&dense);
+ let coarsened = remesh(&dense, Settings { target: 0.5, iterations: 4, ..Default::default() });
+ assert!(mean_edge(&coarsened) > dense_before, "collapse did not coarsen");
+ assert!(coarsened.num_points() < dense.num_points());
+ }
+
+ #[test]
+ fn test_remesh_converges_rather_than_oscillating() {
+ // The 4/3 and 4/5 thresholds exist so a split cannot produce edges the
+ // next collapse undoes. If they were wrong, running longer would keep
+ // changing the answer instead of settling.
+ let sphere = sphere_detail(Vec3::ZERO, 1.0, 8, 12);
+ let a = remesh(&sphere, Settings { target: 0.3, iterations: 6, ..Default::default() });
+ let b = remesh(&sphere, Settings { target: 0.3, iterations: 12, ..Default::default() });
+ let (ea, eb) = (mean_edge(&a), mean_edge(&b));
+ assert!((ea - eb).abs() < 0.06, "still moving at 12 iterations: {ea} -> {eb}");
+
+ // And it is deterministic: the same input twice is the same mesh, or a
+ // simulation could not be reproduced frame to frame.
+ let again = remesh(&sphere, Settings { target: 0.3, iterations: 6, ..Default::default() });
+ assert_eq!(a.num_points(), again.num_points());
+ assert_eq!(a.positions(), again.positions());
+ }
+
+ #[test]
+ fn test_remesh_keeps_the_surface_it_was_given() {
+ // Relaxation is TANGENTIAL: points slide within the surface to even out
+ // the triangles, and the shape they describe stays where it was. A
+ // sphere of radius 1 must still be a sphere of radius 1.
+ let sphere = sphere_detail(Vec3::ZERO, 1.0, 10, 14);
+ let out = remesh(&sphere, Settings { target: 0.25, iterations: 5, ..Default::default() });
+ for p in 0..out.num_points() {
+ let r = out.pos(p).length();
+ assert!((r - 1.0).abs() < 0.08, "point {p} left the sphere at radius {r}");
+ }
+ let (lo, hi) = out.bounds().unwrap();
+ assert!(lo.x > -1.1 && hi.x < 1.1, "bounds grew: {lo:?} {hi:?}");
+ }
+
+ #[test]
+ fn test_remesh_carries_the_simulations_data_across() {
+ let mut sphere = sphere_detail(Vec3::ZERO, 1.0, 8, 12);
+ // A field that varies smoothly, so interpolation is checkable.
+ sphere.points_mut().create("mass", AttribValue::Float(0.0));
+ for p in 0..sphere.num_points() {
+ let y = sphere.pos(p).y;
+ sphere.points_mut().set_value("mass", p, AttribValue::Float(y)).unwrap();
+ }
+ sphere.points_mut().create_group("top");
+ for p in 0..sphere.num_points() {
+ if sphere.pos(p).y > 0.5 {
+ sphere.points_mut().add_to_group("top", p);
+ }
+ }
+ let before_ids: std::collections::HashSet<u64> = sphere.ids().iter().copied().collect();
+
+ let out = remesh(&sphere, Settings { target: 0.25, iterations: 4, ..Default::default() });
+
+ // A split interpolates, so a new point's value is consistent with
+ // where it sits rather than zero — which is what the attribute means.
+ assert!(out.points().has("mass"));
+ for p in 0..out.num_points() {
+ let v = out.points().value("mass", p).unwrap().as_f32();
+ assert!((v - out.pos(p).y).abs() < 0.2, "point {p}: {v} vs y {}", out.pos(p).y);
+ }
+
+ // Points that survived kept their identity: a remesh should cost the
+ // simulation as little memory as it can, and the solver has been
+ // writing to these.
+ let kept = out.ids().iter().filter(|id| before_ids.contains(id)).count();
+ assert!(kept > 0, "every identity was thrown away");
+ // And no identity is used twice, however many were minted on the way.
+ let mut all = out.ids().to_vec();
+ all.sort_unstable();
+ let unique = all.len();
+ all.dedup();
+ assert_eq!(all.len(), unique, "an identity was reused");
+
+ // Groups come across, and a new point joins only where BOTH parents
+ // were members — otherwise every group grows along its own boundary
+ // each time the mesh is remeshed.
+ let members = out.points().group_members("top");
+ assert!(!members.is_empty() && members.len() < out.num_points());
+ for &p in &members {
+ assert!(out.pos(p as usize).y > 0.3, "the group leaked downward");
+ }
+ }
+
+ #[test]
+ fn test_remesh_leaves_a_mesh_it_cannot_help_alone() {
+ // A mesh that has already been remeshed to a target is settled at it,
+ // and running again changes little. Note what is NOT settled: a UV
+ // sphere at its own MEAN edge length, because a UV sphere is
+ // anisotropic — its rings are short at the poles and long at the
+ // equator — and making it isotropic has to move points. That is the
+ // job, not churn.
+ let sphere = sphere_detail(Vec3::ZERO, 1.0, 12, 16);
+ let settled = remesh(&sphere, Settings { target: 0.3, iterations: 5, ..Default::default() });
+ let again = remesh(&settled, Settings { target: 0.3, iterations: 5, ..Default::default() });
+ let ratio = again.num_points() as f32 / settled.num_points() as f32;
+ assert!((0.85..1.18).contains(&ratio), "a settled mesh was churned: {ratio}");
+
+ // Degenerate settings pass the geometry through rather than producing
+ // nothing: a zero target has no length to steer toward.
+ let zero = remesh(&sphere, Settings { target: 0.0, ..Default::default() });
+ assert_eq!(zero.num_points(), sphere.num_points());
+ // Geometry with no primitives has no edges to split or collapse.
+ let mut cloud = Detail::new();
+ cloud.add_point(Vec3::ZERO);
+ cloud.add_point(Vec3::X);
+ assert_eq!(remesh(&cloud, Settings::default()).num_points(), 2);
+ }
+
+ #[test]
+ fn test_remesh_output_is_a_usable_mesh() {
+ let sphere = sphere_detail(Vec3::ZERO, 1.0, 8, 12);
+ let out = remesh(&sphere, Settings { target: 0.3, iterations: 4, ..Default::default() });
+
+ // Every primitive is a real triangle over live points — a stale index
+ // or a degenerate face here would crash or smear the renderer.
+ assert!(out.num_prims() > 0);
+ for prim in 0..out.num_prims() {
+ let pts = out.prim_points(prim);
+ assert_eq!(pts.len(), 3, "prim {prim} is not a triangle");
+ assert!(pts.iter().all(|&p| (p as usize) < out.num_points()), "prim {prim} dangles");
+ assert!(pts[0] != pts[1] && pts[1] != pts[2] && pts[0] != pts[2], "prim {prim} is degenerate");
+ }
+ // No orphans: every point is used by something.
+ for p in 0..out.num_points() {
+ assert!(!out.point_prims(p).is_empty(), "point {p} belongs to nothing");
+ }
+ // Still closed — every edge shared by exactly two faces. A remesh that
+ // tore a hole would be invisible until something tried to fill it.
+ for e in out.edges() {
+ let shared = (0..out.num_prims())
+ .filter(|&t| {
+ let pts = out.prim_points(t);
+ pts.contains(&e[0]) && pts.contains(&e[1])
+ })
+ .count();
+ assert_eq!(shared, 2, "edge {e:?} is on {shared} faces, so the surface is torn");
+ }
+ }
+
+ #[test]
+ fn test_develop_moves_the_surface_along_its_normals() {
+ let mut sphere = sphere_detail(Vec3::ZERO, 1.0, 8, 12);
+ sphere.points_mut().create("growth", AttribValue::Float(1.0));
+ // Only the top half grows.
+ sphere.points_mut().create_group("top");
+ for p in 0..sphere.num_points() {
+ if sphere.pos(p).y <= 0.0 {
+ sphere.points_mut().set_value("growth", p, AttribValue::Float(0.0)).unwrap();
+ } else {
+ sphere.points_mut().add_to_group("top", p);
+ }
+ }
+
+ let mut out = sphere.clone();
+ let node = crate::app::FsNode {
+ id: "d".into(),
+ name: "Develop 1".into(),
+ node_type: "develop".into(),
+ children: vec![],
+ params: [("Attribute", "growth"), ("Scale", "0.50"), ("Direction", "Normal")]
+ .into_iter()
+ .map(|(name, default)| crate::app::ParamDef {
+ name: name.into(),
+ label: String::new(),
+ param_type: "text".into(),
+ default: default.into(),
+ options: vec![],
+ min: None,
+ max: None,
+ step: None,
+ })
+ .collect(),
+ geometry_visible: true,
+ position: (0.0, 0.0),
+ inputs: 1,
+ outputs: 1,
+ };
+ let mut err = None;
+ crate::geometry::apply_develop(&mut out, &node, &mut err);
+ assert!(err.is_none(), "{err:?}");
+
+ for p in 0..out.num_points() {
+ let grew = sphere.points().value("growth", p).unwrap().as_f32() > 0.0;
+ let r = out.pos(p).length();
+ if grew {
+ // Outward along the normal, which on a sphere is radial.
+ assert!((r - 1.5).abs() < 0.05, "point {p} grew to {r}, wanted 1.5");
+ } else {
+ assert!((r - 1.0).abs() < 1e-4, "point {p} moved without growth: {r}");
+ }
+ }
+ // Topology is remesh's business: Develop moves points and nothing else.
+ assert_eq!(out.num_prims(), sphere.num_prims());
+ assert_eq!(out.ids(), sphere.ids());
+ }
+
// ---- Phase 2: the solver contract ----
#[test]
diff --git a/src/remesh.rs b/src/remesh.rs
new file mode 100644
index 0000000..ae339a6
--- /dev/null
+++ b/src/remesh.rs
@@ -0,0 +1,581 @@
+//! Incremental isotropic remeshing.
+//!
+//! The load-bearing half of Phase 3. Without topology that keeps primitives
+//! proportional to surface area, every growth simulation degenerates within a
+//! few dozen frames: `develop` pushes points apart, the triangles between them
+//! stretch, and an attribute diffused across a stretched mesh is being
+//! averaged over distances that no longer mean what they meant.
+//!
+//! The algorithm is Botsch and Kobbelt's, four passes over the mesh repeated a
+//! few times:
+//!
+//! 1. **Split** every edge longer than 4/3 of the target length.
+//! 2. **Collapse** every edge shorter than 4/5 of it.
+//! 3. **Flip** edges that would bring their four points closer to valence 6.
+//! 4. **Relax** each point toward the centroid of its neighbours, with the
+//! normal component removed so the pass smooths the triangulation without
+//! moving the surface.
+//!
+//! The 4/3 and 4/5 are the paper's, and they are not arbitrary: a window
+//! narrower than that lets a split produce two edges short enough for the next
+//! collapse to undo, and the mesh oscillates instead of converging.
+//!
+//! ## What it does with the simulation's data
+//!
+//! This is the node that Phase 2's contract was built for, so it is careful
+//! about identity and attributes:
+//!
+//! - A **split** allocates a new point and interpolates every attribute from
+//! the two endpoints. A place that did not exist gets values consistent with
+//! its neighbourhood rather than zeros.
+//! - A **collapse** keeps one endpoint — its identity and its values — rather
+//! than averaging into a new point. The surviving point is one the solver
+//! has been writing to, and a remesh should cost the simulation as little
+//! memory as it can.
+//! - A **flip** and a **relax** change no attributes at all.
+//!
+//! What it does NOT do is project back onto the input surface, which the
+//! paper's fifth pass does. Tangential relaxation alone lets a surface creep
+//! slightly over many iterations; the projection needs a spatial index over the
+//! original triangles, which is the same index Detangle and Suture will want,
+//! and is better built once for all three.
+
+use crate::detail::{AttribData, AttribValue, Detail, PointId};
+use glam::Vec3;
+use std::collections::HashMap;
+
+/// How the four passes are tuned. Defaults are the paper's.
+#[derive(Clone, Copy, Debug)]
+pub struct Settings {
+ /// The edge length the mesh is steered toward.
+ pub target: f32,
+ /// How many times the four passes run.
+ pub iterations: usize,
+ /// Strength of the tangential relaxation, 0 to 1.
+ pub relax: f32,
+ pub split: bool,
+ pub collapse: bool,
+ pub flip: bool,
+}
+
+impl Default for Settings {
+ fn default() -> Self {
+ Self { target: 0.1, iterations: 3, relax: 0.5, split: true, collapse: true, flip: true }
+ }
+}
+
+/// A triangle mesh in a form that can be edited in place.
+///
+/// [`Detail`]'s CSR storage is compact and good for reading, which is what
+/// every other operator does to it. Remeshing is the one thing that rewires
+/// topology per edge, so it converts in, edits, and converts back rather than
+/// making every other operator pay for an edit-friendly layout.
+///
+/// Points and triangles are tombstoned rather than removed during a pass:
+/// compacting mid-pass would invalidate every index the pass is holding.
+struct Mesh {
+ pos: Vec<Vec3>,
+ ids: Vec<PointId>,
+ /// Per point, its attribute values as loose components, in `attr_names`
+ /// order — the form the split interpolation works in.
+ attrs: Vec<Vec<f32>>,
+ attr_names: Vec<String>,
+ attr_types: Vec<crate::detail::AttribType>,
+ groups: Vec<(String, Vec<bool>)>,
+ tris: Vec<[u32; 3]>,
+ dead_point: Vec<bool>,
+ dead_tri: Vec<bool>,
+ /// Point to the triangles that have referenced it. Maintained as
+ /// triangles are added and rewired, and read through a filter that drops
+ /// dead entries and ones the point has since been rewired out of — so a
+ /// stale entry is harmless and nothing has to be removed eagerly.
+ ///
+ /// Without this every adjacency question is a scan of the whole mesh, and
+ /// the flip pass alone asks four per edge.
+ p2t: Vec<Vec<usize>>,
+ next_id: PointId,
+}
+
+impl Mesh {
+ fn from_detail(d: &Detail) -> Mesh {
+ let attr_names: Vec<String> = d.points().names().iter().map(|s| s.to_string()).collect();
+ let attr_types: Vec<crate::detail::AttribType> = attr_names
+ .iter()
+ .filter_map(|n| d.points().get(n).map(|a| a.ty()))
+ .collect();
+ let attrs: Vec<Vec<f32>> = (0..d.num_points())
+ .map(|p| {
+ attr_names
+ .iter()
+ .flat_map(|n| match d.points().value(n, p) {
+ Some(AttribValue::Float(x)) => vec![x],
+ Some(AttribValue::Float2(x)) => x.to_vec(),
+ Some(AttribValue::Float3(x)) => x.to_vec(),
+ Some(AttribValue::Float4(x)) => x.to_vec(),
+ Some(AttribValue::Int(x)) => vec![x as f32],
+ None => vec![],
+ })
+ .collect()
+ })
+ .collect();
+ let groups: Vec<(String, Vec<bool>)> = d
+ .points()
+ .group_names()
+ .iter()
+ .map(|g| {
+ (
+ g.to_string(),
+ (0..d.num_points()).map(|p| d.points().in_group(g, p)).collect(),
+ )
+ })
+ .collect();
+
+ // Only triangles are remeshed. A polygon fans on the way in, which is
+ // what the renderer does with it anyway.
+ let mut tris = Vec::new();
+ for prim in 0..d.num_prims() {
+ let pts = d.prim_points(prim);
+ for i in 1..pts.len().saturating_sub(1) {
+ tris.push([pts[0], pts[i], pts[i + 1]]);
+ }
+ }
+
+ let n = d.num_points();
+ let max_id = d.ids().iter().copied().max().map(|m| m + 1).unwrap_or(0);
+ let mut p2t: Vec<Vec<usize>> = vec![Vec::new(); n];
+ for (t, tri) in tris.iter().enumerate() {
+ for &q in tri {
+ p2t[q as usize].push(t);
+ }
+ }
+ Mesh {
+ pos: (0..n).map(|p| d.pos(p)).collect(),
+ ids: d.ids().to_vec(),
+ attrs,
+ attr_names,
+ attr_types,
+ groups,
+ dead_tri: vec![false; tris.len()],
+ tris,
+ dead_point: vec![false; n],
+ p2t,
+ next_id: max_id,
+ }
+ }
+
+ /// Add a triangle, keeping the incidence in step.
+ fn add_tri(&mut self, tri: [u32; 3]) {
+ let t = self.tris.len();
+ self.tris.push(tri);
+ self.dead_tri.push(false);
+ for &q in &tri {
+ self.p2t[q as usize].push(t);
+ }
+ }
+
+ /// Point `from` to `to` in triangle `t`, keeping the incidence in step.
+ fn rewire(&mut self, t: usize, from: u32, to: u32) {
+ for slot in self.tris[t].iter_mut() {
+ if *slot == from {
+ *slot = to;
+ }
+ }
+ self.p2t[to as usize].push(t);
+ }
+
+ /// Live triangles using both endpoints of an edge.
+ fn tris_on_edge(&self, a: u32, b: u32) -> Vec<usize> {
+ let mut out: Vec<usize> = self
+ .p2t
+ .get(a as usize)
+ .map(|ts| {
+ ts.iter()
+ .copied()
+ .filter(|&t| {
+ !self.dead_tri[t] && self.tris[t].contains(&a) && self.tris[t].contains(&b)
+ })
+ .collect()
+ })
+ .unwrap_or_default();
+ out.sort_unstable();
+ out.dedup();
+ out
+ }
+
+ fn into_detail(mut self) -> Detail {
+ self.dead_tri.resize(self.tris.len(), false);
+ // Drop points nothing references any more, as well as the ones
+ // collapse tombstoned: a split-then-collapse can strand a point that
+ // was never itself collapsed.
+ let mut used = vec![false; self.pos.len()];
+ for (t, tri) in self.tris.iter().enumerate() {
+ if self.dead_tri[t] {
+ continue;
+ }
+ for &p in tri {
+ used[p as usize] = true;
+ }
+ }
+
+ let mut d = Detail::new();
+ let mut remap = vec![u32::MAX; self.pos.len()];
+ let mut kept: Vec<usize> = Vec::new();
+ for p in 0..self.pos.len() {
+ if self.dead_point[p] || !used[p] {
+ continue;
+ }
+ remap[p] = d.add_point(self.pos[p]);
+ kept.push(p);
+ }
+ // Identities are restored rather than re-allocated: a point that
+ // survived a remesh is the same point, and the solver has been writing
+ // to it.
+ // `kept` and the points just added are the same list, so this cannot
+ // fail. Asserted rather than discarded because the failure mode is a
+ // silently renumbered mesh, which a simulation would experience as
+ // every point forgetting itself at once.
+ d.set_ids(kept.iter().map(|&p| self.ids[p]).collect(), self.next_id)
+ .expect("one identity per surviving point");
+
+ for (t, tri) in self.tris.iter().enumerate() {
+ if self.dead_tri[t] {
+ continue;
+ }
+ let mapped = [remap[tri[0] as usize], remap[tri[1] as usize], remap[tri[2] as usize]];
+ if mapped.iter().any(|&m| m == u32::MAX) || mapped[0] == mapped[1] || mapped[1] == mapped[2] || mapped[0] == mapped[2] {
+ continue;
+ }
+ d.add_prim(&mapped);
+ }
+
+ let mut offset = 0usize;
+ for (i, name) in self.attr_names.iter().enumerate() {
+ let ty = self.attr_types[i];
+ let k = ty.components();
+ let mut data = AttribData::zeroed(ty, kept.len());
+ for (new, &old) in kept.iter().enumerate() {
+ let row = &self.attrs[old];
+ let comps: Vec<f32> = (0..k).map(|c| row.get(offset + c).copied().unwrap_or(0.0)).collect();
+ let _ = data.set(new, components(ty, &comps));
+ }
+ let _ = d.points_mut().insert(name, data);
+ offset += k;
+ }
+ for (name, members) in &self.groups {
+ d.points_mut().create_group(name);
+ for (new, &old) in kept.iter().enumerate() {
+ if members.get(old).copied().unwrap_or(false) {
+ d.points_mut().add_to_group(name, new);
+ }
+ }
+ }
+ d
+ }
+
+ /// A point halfway along an edge, with every attribute interpolated.
+ fn split_point(&mut self, a: u32, b: u32) -> u32 {
+ let (a, b) = (a as usize, b as usize);
+ let pos = (self.pos[a] + self.pos[b]) * 0.5;
+ let attrs: Vec<f32> = self.attrs[a]
+ .iter()
+ .zip(self.attrs[b].iter())
+ .map(|(x, y)| (x + y) * 0.5)
+ .collect();
+ self.pos.push(pos);
+ self.attrs.push(attrs);
+ self.ids.push(self.next_id);
+ self.next_id += 1;
+ self.dead_point.push(false);
+ self.p2t.push(Vec::new());
+ // A new point joins a group only where BOTH its parents were in it: a
+ // point that is half in a selection is not in it, and the alternative
+ // grows every group along its own boundary every time the mesh is
+ // remeshed.
+ for (_, members) in self.groups.iter_mut() {
+ let inherits = members.get(a).copied().unwrap_or(false)
+ && members.get(b).copied().unwrap_or(false);
+ members.push(inherits);
+ }
+ (self.pos.len() - 1) as u32
+ }
+
+ /// Live triangles touching a point.
+ fn tris_of(&self, p: u32) -> Vec<usize> {
+ let mut out: Vec<usize> = self
+ .p2t
+ .get(p as usize)
+ .map(|ts| {
+ ts.iter()
+ .copied()
+ .filter(|&t| !self.dead_tri[t] && self.tris[t].contains(&p))
+ .collect()
+ })
+ .unwrap_or_default();
+ out.sort_unstable();
+ out.dedup();
+ out
+ }
+
+ /// Unique live edges, each as `[low, high]`, with the triangles on them.
+ fn edges(&self) -> Vec<([u32; 2], Vec<usize>)> {
+ let mut map: HashMap<[u32; 2], Vec<usize>> = HashMap::new();
+ for (t, tri) in self.tris.iter().enumerate() {
+ if self.dead_tri[t] {
+ continue;
+ }
+ for i in 0..3 {
+ let (a, b) = (tri[i], tri[(i + 1) % 3]);
+ map.entry([a.min(b), a.max(b)]).or_default().push(t);
+ }
+ }
+ let mut out: Vec<([u32; 2], Vec<usize>)> = map.into_iter().collect();
+ // Sorted, because HashMap order would make the result depend on the
+ // hasher's seed and a remesh has to be reproducible.
+ out.sort_unstable_by_key(|(e, _)| *e);
+ out
+ }
+
+ fn len_of(&self, e: [u32; 2]) -> f32 {
+ (self.pos[e[1] as usize] - self.pos[e[0] as usize]).length()
+ }
+}
+
+fn components(ty: crate::detail::AttribType, c: &[f32]) -> AttribValue {
+ let at = |i: usize| c.get(i).copied().unwrap_or(0.0);
+ match ty {
+ crate::detail::AttribType::Float => AttribValue::Float(at(0)),
+ crate::detail::AttribType::Float2 => AttribValue::Float2([at(0), at(1)]),
+ crate::detail::AttribType::Float3 => AttribValue::Float3([at(0), at(1), at(2)]),
+ crate::detail::AttribType::Float4 => AttribValue::Float4([at(0), at(1), at(2), at(3)]),
+ crate::detail::AttribType::Int => AttribValue::Int(at(0).round() as i32),
+ }
+}
+
+/// Split every edge longer than 4/3 of the target.
+fn split_pass(m: &mut Mesh, target: f32) -> usize {
+ let long = target * 4.0 / 3.0;
+ let mut done = 0;
+ // The edge LIST is a snapshot — the pass decides up front which edges it
+ // will consider, so a split cannot cascade within one pass. The TRIANGLES
+ // are looked up at the moment of the split: an earlier split in the same
+ // pass has already replaced the faces this edge sits on, and acting on
+ // the snapshot's stale indices is what tears the surface open.
+ for (e, _) in m.edges() {
+ if m.dead_point[e[0] as usize] || m.dead_point[e[1] as usize] || m.len_of(e) <= long {
+ continue;
+ }
+ let tris = m.tris_on_edge(e[0], e[1]);
+ if tris.is_empty() {
+ continue;
+ }
+ let mid = m.split_point(e[0], e[1]);
+ for t in tris {
+ if m.dead_tri[t] {
+ continue;
+ }
+ let tri = m.tris[t];
+ // The corner opposite the split edge; the triangle becomes two,
+ // each keeping the original winding.
+ let Some(i) = (0..3).find(|&i| !e.contains(&tri[i])) else { continue };
+ let (opp, x, y) = (tri[i], tri[(i + 1) % 3], tri[(i + 2) % 3]);
+ m.dead_tri[t] = true;
+ m.add_tri([opp, x, mid]);
+ m.add_tri([opp, mid, y]);
+ }
+ done += 1;
+ }
+ done
+}
+
+/// Collapse every edge shorter than 4/5 of the target.
+///
+/// The survivor keeps its identity and values; the other endpoint is
+/// tombstoned and every triangle referencing it is rewired. Collapses that
+/// would leave a neighbour edge too long are refused, which is what stops the
+/// pass from undoing the splits that just ran.
+fn collapse_pass(m: &mut Mesh, target: f32) -> usize {
+ let short = target * 4.0 / 5.0;
+ let long = target * 4.0 / 3.0;
+ let mut done = 0;
+ for (e, _) in m.edges() {
+ let (a, b) = (e[0], e[1]);
+ if m.dead_point[a as usize] || m.dead_point[b as usize] || m.len_of(e) >= short {
+ continue;
+ }
+ // Would the survivor end up with an edge that the next split pass
+ // would just cut again? Then leave it: two passes undoing each other
+ // is how a remesh oscillates instead of converging.
+ let keep = m.pos[a as usize];
+ let too_long = m.tris_of(b).iter().any(|&t| {
+ m.tris[t]
+ .iter()
+ .any(|&q| q != b && q != a && (m.pos[q as usize] - keep).length() > long)
+ });
+ if too_long {
+ continue;
+ }
+ // Refuse a collapse that would flip a triangle over: if any triangle
+ // keeping both points would end up facing the other way, the surface
+ // would self-intersect where it used to be flat.
+ let folds = m.tris_of(b).iter().any(|&t| {
+ let tri = m.tris[t];
+ if tri.contains(&a) {
+ return false;
+ }
+ let before = face_normal(m, tri);
+ let after_tri = tri.map(|q| if q == b { a } else { q });
+ let after = face_normal(m, after_tri);
+ before.dot(after) <= 0.0
+ });
+ if folds {
+ continue;
+ }
+
+ m.dead_point[b as usize] = true;
+ for t in m.tris_of(b) {
+ if m.dead_tri[t] {
+ continue;
+ }
+ if m.tris[t].contains(&a) {
+ // The two triangles along the collapsed edge fold to nothing.
+ m.dead_tri[t] = true;
+ continue;
+ }
+ m.rewire(t, b, a);
+ }
+ done += 1;
+ }
+ done
+}
+
+fn face_normal(m: &Mesh, tri: [u32; 3]) -> Vec3 {
+ let (a, b, c) = (
+ m.pos[tri[0] as usize],
+ m.pos[tri[1] as usize],
+ m.pos[tri[2] as usize],
+ );
+ (b - a).cross(c - a)
+}
+
+/// Flip edges whose two triangles would be better shaped the other way.
+///
+/// "Better" is total deviation from valence 6, which is the valence a regular
+/// triangulation of a plane has — the measure the paper uses, and the one that
+/// drives a mesh toward equilateral triangles.
+fn flip_pass(m: &mut Mesh) -> usize {
+ let mut done = 0;
+ for (e, _) in m.edges() {
+ // Looked up now rather than taken from the snapshot, for the same
+ // reason the split pass does: an earlier flip has rewired faces.
+ let tris = m.tris_on_edge(e[0], e[1]);
+ if tris.len() != 2 {
+ continue; // a boundary edge has nothing to flip into
+ }
+ let (t0, t1) = (tris[0], tris[1]);
+ let Some(&o0) = m.tris[t0].iter().find(|q| !e.contains(q)) else { continue };
+ let Some(&o1) = m.tris[t1].iter().find(|q| !e.contains(q)) else { continue };
+ if o0 == o1 {
+ continue;
+ }
+
+ let val = |p: u32| m.tris_of(p).len() as i32;
+ let dev = |v: i32| (v - 6).abs();
+ let before = dev(val(e[0])) + dev(val(e[1])) + dev(val(o0)) + dev(val(o1));
+ // The flip moves one triangle off each endpoint and onto each opposite
+ // corner.
+ let after = dev(val(e[0]) - 1) + dev(val(e[1]) - 1) + dev(val(o0) + 1) + dev(val(o1) + 1);
+ if after >= before {
+ continue;
+ }
+ // Refuse a flip that would fold either new triangle against the
+ // surface it came from.
+ let n0 = face_normal(m, m.tris[t0]);
+ let (new0, new1) = ([o0, e[0], o1], [o1, e[1], o0]);
+ if face_normal(m, new0).dot(n0) <= 0.0 || face_normal(m, new1).dot(n0) <= 0.0 {
+ continue;
+ }
+ // Rewiring both triangles wholesale, so the incidence is rebuilt for
+ // the corners that changed.
+ m.tris[t0] = new0;
+ m.tris[t1] = new1;
+ for &q in new0.iter().chain(new1.iter()) {
+ m.p2t[q as usize].push(t0);
+ m.p2t[q as usize].push(t1);
+ }
+ done += 1;
+ }
+ done
+}
+
+/// Move each point toward the centroid of its neighbours, with the normal
+/// component removed.
+///
+/// Removing the normal component is what makes this a retriangulation rather
+/// than a smooth: the points slide within the surface to even out the
+/// triangles, and the shape they describe is left where it was.
+fn relax_pass(m: &mut Mesh, amount: f32) {
+ if amount <= 0.0 {
+ return;
+ }
+ let mut nbrs: Vec<Vec<u32>> = vec![Vec::new(); m.pos.len()];
+ for (t, tri) in m.tris.iter().enumerate() {
+ if m.dead_tri[t] {
+ continue;
+ }
+ for i in 0..3 {
+ let (a, b) = (tri[i], tri[(i + 1) % 3]);
+ if !nbrs[a as usize].contains(&b) {
+ nbrs[a as usize].push(b);
+ }
+ if !nbrs[b as usize].contains(&a) {
+ nbrs[b as usize].push(a);
+ }
+ }
+ }
+ let mut normals: Vec<Vec3> = vec![Vec3::ZERO; m.pos.len()];
+ for (t, tri) in m.tris.iter().enumerate() {
+ if m.dead_tri[t] {
+ continue;
+ }
+ let n = face_normal(m, *tri);
+ for &p in tri {
+ normals[p as usize] += n;
+ }
+ }
+
+ let before = m.pos.clone();
+ for p in 0..m.pos.len() {
+ if m.dead_point[p] || nbrs[p].is_empty() {
+ continue;
+ }
+ let centroid: Vec3 =
+ nbrs[p].iter().map(|&q| before[q as usize]).sum::<Vec3>() / nbrs[p].len() as f32;
+ let mut delta = (centroid - before[p]) * amount;
+ let n = normals[p].normalize_or_zero();
+ if n != Vec3::ZERO {
+ delta -= n * delta.dot(n);
+ }
+ m.pos[p] = before[p] + delta;
+ }
+}
+
+/// Remesh toward `settings.target` edge length.
+pub fn remesh(input: &Detail, settings: Settings) -> Detail {
+ if input.num_prims() == 0 || settings.target <= 0.0 {
+ return input.clone();
+ }
+ let mut m = Mesh::from_detail(input);
+ for _ in 0..settings.iterations.min(20) {
+ if settings.split {
+ split_pass(&mut m, settings.target);
+ }
+ if settings.collapse {
+ collapse_pass(&mut m, settings.target);
+ }
+ if settings.flip {
+ flip_pass(&mut m);
+ }
+ relax_pass(&mut m, settings.relax.clamp(0.0, 1.0));
+ }
+ m.into_detail()
+}
diff --git a/src/thumbnail.rs b/src/thumbnail.rs
index 6266fcd..a4f2fd0 100644
--- a/src/thumbnail.rs
+++ b/src/thumbnail.rs
@@ -19,7 +19,7 @@ const SAMPLES: u32 = 96;
/// Render `project` (a project directory or a `state.json` path) to a square
/// `size`×`size` PNG at `out`, with `samples` paths per pixel (None = 96).
-pub fn run(project: &Path, out: &Path, size: u32, samples: Option<u32>) -> Result<(), String> {
+pub fn run(project: &Path, out: &Path, size: u32, samples: Option<u32>, frame: Option<i32>) -> Result<(), String> {
let state_file = if project.is_dir() { project.join("state.json") } else { project.to_path_buf() };
let content = std::fs::read_to_string(&state_file)
.map_err(|e| format!("read {}: {e}", state_file.display()))?;
@@ -31,9 +31,16 @@ pub fn run(project: &Path, out: &Path, size: u32, samples: Option<u32>) -> Resul
crate::app::merge_template_defs(&mut proj.root, &templates);
let mut ocl_error = None;
- // A headless thumbnail has no timeline: simnets render at their seed.
+ // Without `--frame`, a headless thumbnail has no timeline and simnets
+ // render at their seed. WITH it, the solve runs to that frame — which is
+ // the only way to look at a simulation without a Wayland session, and so
+ // the only way to check that a growth chain does what it claims.
+ //
+ // The start frame is the playbar's default of 1, the same number the app
+ // uses, so a frame number here means what it means in the window. A simnet
+ // with its own Start Frame answers for itself either way.
let mut sim_cache = crate::geometry::SimCache::default();
- let mut sim = crate::geometry::EvalSim::new(0, 0, &mut sim_cache);
+ let mut sim = crate::geometry::EvalSim::new(frame.unwrap_or(0), 1, &mut sim_cache);
// Thumbnails always show the whole scene from the top, regardless of the
// network level the project was saved at: root as both eval and walk root.
let geom = network_sphere_vertices_with_errors(&proj.root, &proj.root, &mut ocl_error, &mut sim);