d84914ef1e5a
subdivide.rs
//! The dense copy of the mesh that viewport displacement moves in the vertex shader (wgpu has no
//! tessellation stage): every triangle split into a regular grid of `4^level` triangles, the
//! attributes interpolated linearly (flat subdivision: the surface stays where it was until the
//! height channel moves it).
use bytemuck::{Pod, Zeroable};
/// The mesh vertex as the viewport draws it.
#[repr(C)]
#[derive(Clone, Copy, Debug, Default, PartialEq, Pod, Zeroable)]
pub(crate) struct Vertex {
pub pos: [f32; 3],
pub nrm: [f32; 3],
pub tan: [f32; 4],
pub uv: [f32; 2],
}
/// An index range to draw: first index, count, material.
pub(crate) type Draw = (u32, u32, usize);
/// Most triangles of a dense mesh: the level is the highest that stays within it.
pub(crate) const DENSE_TRIANGLES: usize = 1 << 19;
/// Finest split: 64 × 64 segments per edge (for very coarse meshes such as a cube).
const MAX_LEVEL: u32 = 6;
/// The vertices of `mesh` as the viewport draws them (missing attributes get defaults).
pub(crate) fn vertices(mesh: &texturecraft_geom::Mesh) -> Vec<Vertex> {
mesh.positions
.iter()
.enumerate()
.map(|(i, p)| Vertex {
pos: p.to_array(),
nrm: mesh.normals.get(i).map(|n| n.to_array()).unwrap_or([0.0, 1.0, 0.0]),
tan: mesh.tangents.get(i).map(|t| t.to_array()).unwrap_or([1.0, 0.0, 0.0, 1.0]),
uv: mesh.uvs.get(i).map(|u| u.to_array()).unwrap_or([0.0, 0.0]),
})
.collect()
}
/// Subdivision level for a mesh of `triangles` (0: dense enough as it is).
pub(crate) fn level_for(triangles: usize) -> u32 {
(0..=MAX_LEVEL).rev().find(|l| triangles.saturating_mul(1 << (2 * l)) <= DENSE_TRIANGLES).unwrap_or(0)
}
/// `w` of `a`, `b`, `c` per component.
fn mix<const N: usize>(a: [f32; N], b: [f32; N], c: [f32; N], w: [f32; 3]) -> [f32; N] {
std::array::from_fn(|k| a[k] * w[0] + b[k] * w[1] + c[k] * w[2])
}
/// The point `k / n` of the way from vertex `p` to vertex `q`, with the same bits whichever way
/// round the edge is given (by position: vertices split at UV seams agree too).
fn on_edge(verts: &[Vertex], (p, q): (u32, u32), k: u32, n: u32) -> Option<Vertex> {
let (p, q) = (*verts.get(p as usize)?, *verts.get(q as usize)?);
let key = |v: &Vertex| v.pos.map(f32::to_bits);
let (a, b, k) = if key(&p) <= key(&q) { (p, q, k) } else { (q, p, n - k) };
if k == 0 || k == n {
return Some(if k == 0 { a } else { b });
}
let t = k as f32 / n as f32;
fn lerp<const N: usize>(x: [f32; N], y: [f32; N], t: f32) -> [f32; N] {
std::array::from_fn(|i| x[i] + (y[i] - x[i]) * t)
}
Some(Vertex { pos: lerp(a.pos, b.pos, t), nrm: lerp(a.nrm, b.nrm, t), tan: lerp(a.tan, b.tan, t), uv: lerp(a.uv, b.uv, t) })
}
/// Split the triangles of `indices` (index ranges `draws`: first, count, material) `level`
/// times. Returns the vertices, indices and the draws over them.
pub(crate) fn subdivide(vertices: &[Vertex], indices: &[u32], draws: &[Draw], level: u32) -> (Vec<Vertex>, Vec<u32>, Vec<Draw>) {
let segments = 1u32 << level.min(MAX_LEVEL);
let (mut output_vertices, mut output_indices, mut output_draws) = (Vec::new(), Vec::new(), Vec::new());
for &(start, count, material) in draws {
let first = output_indices.len() as u32;
let triangles = indices.get(start as usize..(start as usize).saturating_add(count as usize)).unwrap_or_default();
for t in triangles.as_chunks::<3>().0 {
let (Some(a), Some(b), Some(c)) = (vertices.get(t[0] as usize), vertices.get(t[1] as usize), vertices.get(t[2] as usize)) else { continue };
let base = output_vertices.len() as u32;
// Row j holds segments + 1 - j points inside the triangle
// Shared edges use identical interpolation in both triangles to prevent cracks
for j in 0..=segments {
for i in 0..=segments - j {
let edge = match (i, j) {
(_, 0) => Some(((t[0], t[1]), i)),
(0, _) => Some(((t[0], t[2]), j)),
_ if i + j == segments => Some(((t[1], t[2]), j)),
_ => None,
};
let p = match edge.and_then(|(ends, k)| on_edge(vertices, ends, k, segments)) {
Some(p) => p,
None => {
let w = [1.0 - (i + j) as f32 / segments as f32, i as f32 / segments as f32, j as f32 / segments as f32];
Vertex {
pos: mix(a.pos, b.pos, c.pos, w),
nrm: mix(a.nrm, b.nrm, c.nrm, w),
tan: mix(a.tan, b.tan, c.tan, w),
uv: mix(a.uv, b.uv, c.uv, w),
}
}
};
output_vertices.push(Vertex { tan: [p.tan[0], p.tan[1], p.tan[2], a.tan[3]], ..p });
}
}
let at = |i: u32, j: u32| base + j * (segments + 1) - j * j.saturating_sub(1) / 2 + i;
for j in 0..segments {
for i in 0..segments - j {
output_indices.extend_from_slice(&[at(i, j), at(i + 1, j), at(i, j + 1)]);
if i + j + 1 < segments {
output_indices.extend_from_slice(&[at(i + 1, j), at(i + 1, j + 1), at(i, j + 1)]);
}
}
}
}
output_draws.push((first, output_indices.len() as u32 - first, material));
}
(output_vertices, output_indices, output_draws)
}
/// World length per unit of UV over the whole mesh (the square root of their area ratio): how
/// far a height change moves the surface for the slope height-to-normal shows.
pub(crate) fn world_per_uv(vertices: &[Vertex], indices: &[u32]) -> Option<f32> {
let (mut world_area, mut uv_area) = (0.0f64, 0.0f64);
for t in indices.as_chunks::<3>().0 {
let (Some(a), Some(b), Some(c)) = (vertices.get(t[0] as usize), vertices.get(t[1] as usize), vertices.get(t[2] as usize)) else { continue };
let d = |p: [f32; 3], q: [f32; 3]| [f64::from(q[0] - p[0]), f64::from(q[1] - p[1]), f64::from(q[2] - p[2])];
let (e1, e2) = (d(a.pos, b.pos), d(a.pos, c.pos));
let cross = [e1[1] * e2[2] - e1[2] * e2[1], e1[2] * e2[0] - e1[0] * e2[2], e1[0] * e2[1] - e1[1] * e2[0]];
world_area += (cross[0] * cross[0] + cross[1] * cross[1] + cross[2] * cross[2]).sqrt() * 0.5;
let (u1, u2) = ([b.uv[0] - a.uv[0], b.uv[1] - a.uv[1]], [c.uv[0] - a.uv[0], c.uv[1] - a.uv[1]]);
uv_area += f64::from(u1[0] * u2[1] - u1[1] * u2[0]).abs() * 0.5;
}
let scale = (world_area / uv_area).sqrt() as f32;
(uv_area > 1e-12 && scale.is_finite() && scale > 0.0).then_some(scale)
}
#[cfg(test)]
mod tests {
use super::*;
fn v(pos: [f32; 3], uv: [f32; 2]) -> Vertex {
Vertex { pos, nrm: [0.0, 0.0, 1.0], tan: [1.0, 0.0, 0.0, -1.0], uv }
}
#[test]
fn grids_cover_each_triangle_with_four_per_level() {
let verts = [v([0.0, 0.0, 0.0], [0.0, 0.0]), v([2.0, 0.0, 0.0], [1.0, 0.0]), v([0.0, 2.0, 0.0], [0.0, 1.0]), v([2.0, 2.0, 0.0], [1.0, 1.0])];
let indices = [0, 1, 2, 1, 3, 2];
for level in 0..=3 {
let (vs, is, draws) = subdivide(&verts, &indices, &[(0, 3, 0), (3, 3, 1)], level);
let per = 1usize << (2 * level);
assert_eq!(draws, vec![(0, 3 * per as u32, 0), (3 * per as u32, 3 * per as u32, 1)]);
assert_eq!(is.len(), 6 * per);
assert!(is.iter().all(|i| (*i as usize) < vs.len()));
// Same area, same winding (all +z), attributes interpolated.
let area: f32 = is
.chunks(3)
.map(|t| {
let (a, b, c) = (vs[t[0] as usize].pos, vs[t[1] as usize].pos, vs[t[2] as usize].pos);
((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])) * 0.5
})
.inspect(|a| assert!(*a > 0.0))
.sum();
assert!((area - 4.0).abs() < 1e-4, "level {level}: area {area}");
assert!(vs.iter().all(|x| (x.uv[0] * 2.0 - x.pos[0]).abs() < 1e-5 && x.tan[3] == -1.0));
// The shared edge (vertices 1-2, given the other way round by the second triangle)
// has the same points, to the bit, on both sides.
let n = 1usize << level;
let bits = |v: &Vertex| v.pos.map(f32::to_bits);
let (first, second) = vs.split_at(vs.len() / 2);
let shared = first.iter().filter(|p| second.iter().any(|q| bits(q) == bits(p))).count();
assert_eq!(shared, n + 1, "level {level}");
}
let flipped = [0, 1, 2, 2, 1, 3];
let (vs, _, _) = subdivide(&verts, &flipped, &[(0, 3, 0), (3, 3, 1)], 3);
let bits = |v: &Vertex| v.pos.map(f32::to_bits);
let (first, second) = vs.split_at(vs.len() / 2);
assert_eq!(first.iter().filter(|p| second.iter().any(|q| bits(q) == bits(p))).count(), 9);
assert_eq!(level_for(12), 6);
assert_eq!(level_for(DENSE_TRIANGLES), 0);
assert_eq!(level_for(DENSE_TRIANGLES / 4), 1);
assert_eq!(world_per_uv(&verts, &indices), Some(2.0));
assert_eq!(world_per_uv(&verts, &[]), None);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.