d84914ef1e5a
unwrap.rs
//! Automatic UV unwrapping for meshes imported without texture coordinates.
//!
//! Triangles are grouped into charts by flood fill across shared (welded) edges while each face
//! normal stays within 60° of the chart's seed face, so every chart is a height field over its
//! seed plane and projects onto it without flipping. Charts are rotated to their principal axes
//! and shelf-packed per material into 0..1 with one uniform scale, so texel density is the same
//! everywhere within a material.
use std::collections::{HashMap, VecDeque};
use glam::{Vec2, Vec3};
use crate::{GeomError, Mesh, Result};
/// Faces of a chart stay within this angle of the seed face normal (cos 60°).
const CHART_COS: f32 = 0.5;
/// Packing never goes beyond this virtual resolution (texels per side).
const MAX_PACK_RES: f32 = 65_536.0;
/// Welded vertex id per vertex: vertices at the same position (snapped to a grid of 1e-6 of
/// the bounding diagonal) share an id. Ids are dense, in order of first appearance.
pub fn weld_ids(positions: &[Vec3]) -> Vec<u32> {
let (lo, hi) = positions.iter().fold((Vec3::splat(f32::MAX), Vec3::splat(f32::MIN)), |(lo, hi), p| (lo.min(*p), hi.max(*p)));
let cell = ((hi - lo).length() * 1e-6).max(1e-12);
let mut map: HashMap<[i64; 3], u32> = HashMap::with_capacity(positions.len());
positions
.iter()
.map(|p| {
let q = ((*p - lo) / cell).round();
let next = map.len() as u32;
*map.entry([q.x as i64, q.y as i64, q.z as i64]).or_insert(next)
})
.collect()
}
/// True when the mesh has triangles and every one of them has two corners at the same position.
/// MikkTSpace (and so [`Mesh::compute_tangents`]) crashes on such meshes, so callers reject them.
pub fn all_triangles_degenerate(mesh: &Mesh) -> bool {
let p = |i: &u32| mesh.positions.get(*i as usize);
!mesh.indices.is_empty()
&& mesh.indices.chunks(3).all(|t| match t {
[a, b, c] => p(a) == p(b) || p(a) == p(c) || p(b) == p(c),
_ => true,
})
}
struct Chart {
material: usize,
/// Projection basis (right-handed with the seed normal).
t: Vec3,
b: Vec3,
/// Rotation to the chart's principal axes (cos, sin).
rot: Vec2,
lo: Vec2,
hi: Vec2,
/// Texel offset of the chart's packed rectangle and the material's scale and resolution.
offset: Vec2,
}
impl Chart {
fn local(&self, p: Vec3) -> Vec2 {
let q = Vec2::new(p.dot(self.t), p.dot(self.b));
Vec2::new(q.x * self.rot.x - q.y * self.rot.y, q.x * self.rot.y + q.y * self.rot.x)
}
fn size(&self) -> Vec2 {
(self.hi - self.lo).max(Vec2::ZERO)
}
}
/// Replace the UVs of `mesh` with an automatic non-overlapping layout: each material gets its
/// own 0..1 space with charts at least `padding_texels` (minimum 1) away from each other and
/// the borders at `resolution`. Vertices are split at chart borders; tangents are recomputed.
/// Returns the number of charts.
pub fn auto_unwrap(mesh: &mut Mesh, padding_texels: f32, resolution: u32) -> Result<usize> {
mesh.validate_indices()?;
if all_triangles_degenerate(mesh) {
return Err(GeomError::Invalid("every triangle of the mesh is degenerate".into()));
}
if mesh.normals.len() != mesh.positions.len() {
mesh.compute_normals();
}
let n = mesh.triangle_count();
let weld = weld_ids(&mesh.positions);
let pos = |v: usize| mesh.positions.get(v).copied().unwrap_or_default();
let wid = |v: usize| weld.get(v).copied().unwrap_or(u32::MAX);
// Face normals (None for degenerate faces) and materials.
let mut normal: Vec<Option<Vec3>> = Vec::with_capacity(n);
let mut area = Vec::with_capacity(n);
for t in 0..n {
let [a, b, c] = mesh.tri(t).unwrap_or([0; 3]);
let cr = (pos(b) - pos(a)).cross(pos(c) - pos(a));
area.push(cr.length() * 0.5);
normal.push(cr.try_normalize());
}
let mut material = vec![0usize; n];
for s in &mesh.submeshes {
for t in (s.start / 3) as usize..((s.start as usize + s.count as usize) / 3) {
if let Some(m) = material.get_mut(t) {
*m = s.material;
}
}
}
// Manifold edge adjacency over welded vertices: edge → (face, face, count).
let mut edges: HashMap<(u32, u32), (u32, u32, u8)> = HashMap::with_capacity(n * 2);
let tri_edges = |t: usize| -> [(u32, u32); 3] {
let [a, b, c] = mesh.tri(t).unwrap_or([0; 3]);
let key = |x: usize, y: usize| {
let (p, q) = (wid(x), wid(y));
(p.min(q), p.max(q))
};
[key(a, b), key(b, c), key(c, a)]
};
for t in 0..n {
for e in tri_edges(t) {
if e.0 == e.1 {
continue;
}
let slot = edges.entry(e).or_insert((t as u32, u32::MAX, 0));
if slot.2 == 1 {
slot.1 = t as u32;
}
slot.2 = slot.2.saturating_add(1);
}
}
// Grow charts from the largest unassigned faces.
let mut order: Vec<usize> = (0..n).collect();
order.sort_by(|a, b| area[*b].total_cmp(&area[*a]));
let mut chart_of = vec![u32::MAX; n];
let mut charts: Vec<Chart> = Vec::new();
let mut queue = VecDeque::new();
for &seed in &order {
if chart_of[seed] != u32::MAX {
continue;
}
let id = charts.len() as u32;
let sn = normal[seed].unwrap_or(Vec3::Z);
let t = sn.any_orthonormal_vector();
charts.push(Chart { material: material[seed], t, b: sn.cross(t), rot: Vec2::X, lo: Vec2::ZERO, hi: Vec2::ZERO, offset: Vec2::ZERO });
chart_of[seed] = id;
queue.push_back(seed);
while let Some(f) = queue.pop_front() {
for e in tri_edges(f) {
let Some(&(f0, f1, 2)) = edges.get(&e) else { continue };
let g = if f0 as usize == f { f1 } else { f0 } as usize;
let ok = normal.get(g).is_some_and(|nn| nn.is_none_or(|nn| nn.dot(sn) >= CHART_COS));
if ok && chart_of.get(g) == Some(&u32::MAX) && material.get(g) == Some(&material[seed]) {
chart_of[g] = id;
queue.push_back(g);
}
}
}
}
// Principal axes and bounds of every chart.
let mut cov = vec![(Vec2::ZERO, [0.0f64; 3], 0usize); charts.len()];
for (t, &c) in chart_of.iter().enumerate() {
let c = c as usize;
for v in mesh.tri(t).unwrap_or([0; 3]) {
if let (Some(ch), Some(acc)) = (charts.get(c), cov.get_mut(c)) {
let q = ch.local(pos(v));
acc.0 += q;
acc.1[0] += (q.x * q.x) as f64;
acc.1[1] += (q.y * q.y) as f64;
acc.1[2] += (q.x * q.y) as f64;
acc.2 += 1;
}
}
}
for (ch, (sum, m, k)) in charts.iter_mut().zip(&cov) {
let k = (*k).max(1) as f64;
let (mx, my) = (sum.x as f64 / k, sum.y as f64 / k);
let (cxx, cyy, cxy) = (m[0] / k - mx * mx, m[1] / k - my * my, m[2] / k - mx * my);
let angle = 0.5 * (2.0 * cxy).atan2(cxx - cyy);
// Rotate so the principal axis lies along x.
ch.rot = Vec2::new((-angle).cos() as f32, (-angle).sin() as f32);
ch.lo = Vec2::splat(f32::MAX);
ch.hi = Vec2::splat(f32::MIN);
}
for (t, &c) in chart_of.iter().enumerate() {
let c = c as usize;
for v in mesh.tri(t).unwrap_or([0; 3]) {
if let Some(ch) = charts.get_mut(c) {
let q = ch.local(pos(v));
ch.lo = ch.lo.min(q);
ch.hi = ch.hi.max(q);
}
}
}
for ch in &mut charts {
if ch.size().y > ch.size().x {
// Quarter turn (x, y) → (y, −x) so shelves stay low.
ch.rot = Vec2::new(ch.rot.y, -ch.rot.x);
let (lo, hi) = (ch.lo, ch.hi);
ch.lo = Vec2::new(lo.y, -hi.x);
ch.hi = Vec2::new(hi.y, -lo.x);
}
}
// Pack each material's charts into its own 0..1 square.
let pad = padding_texels.max(1.0);
let mut scale = HashMap::new();
let mats: std::collections::BTreeSet<usize> = charts.iter().map(|c| c.material).collect();
for m in mats {
let ids: Vec<usize> = (0..charts.len()).filter(|i| charts[*i].material == m).collect();
let sizes: Vec<Vec2> = ids.iter().map(|i| charts[*i].size()).collect();
let (s, res, offsets) = pack(&sizes, resolution.max(16) as f32, pad)?;
for (i, o) in ids.iter().zip(offsets) {
charts[*i].offset = o;
}
scale.insert(m, (s, res));
}
// Rebuild vertices: one per (vertex, chart).
let mut remap: HashMap<(u32, u32), u32> = HashMap::with_capacity(mesh.positions.len() * 2);
let (mut positions, mut normals, mut uvs, mut colors) = (Vec::new(), Vec::new(), Vec::new(), Vec::new());
let mut indices = Vec::with_capacity(mesh.indices.len());
for (t, &c) in chart_of.iter().enumerate() {
let Some(ch) = charts.get(c as usize) else { continue };
let (s, res) = scale.get(&ch.material).copied().unwrap_or((0.0, 1.0));
for v in mesh.tri(t).unwrap_or([0; 3]) {
let idx = *remap.entry((v as u32, c)).or_insert_with(|| {
let q = ch.local(pos(v));
// Chart y points up; UV v points down the image.
let texel = ch.offset + Vec2::splat(pad) + Vec2::new(q.x - ch.lo.x, ch.hi.y - q.y) * s;
positions.push(pos(v));
normals.push(mesh.normals.get(v).copied().unwrap_or(Vec3::Y));
if let Some(c) = mesh.colors.get(v) {
colors.push(*c);
}
uvs.push((texel / res).clamp(Vec2::ZERO, Vec2::ONE));
(positions.len() - 1) as u32
});
indices.push(idx);
}
}
mesh.positions = positions;
mesh.normals = normals;
mesh.uvs = uvs;
mesh.colors = colors;
mesh.indices = indices;
mesh.compute_tangents();
mesh.validate()?;
Ok(charts.len())
}
/// Shelf-pack rectangles of world `sizes` (each grown by `pad` texels per side) into a square of
/// `res` texels with the largest uniform scale that fits. Returns (texels per world unit,
/// resolution used, texel offset per rectangle). The resolution doubles when the padding alone
/// cannot fit (very many charts), so the result always fits in 0..1.
fn pack(sizes: &[Vec2], mut res: f32, pad: f32) -> Result<(f32, f32, Vec<Vec2>)> {
let mut order: Vec<usize> = (0..sizes.len()).collect();
order.sort_by(|a, b| sizes[*b].y.total_cmp(&sizes[*a].y));
let place = |s: f32, res: f32| -> Option<Vec<Vec2>> {
let mut out = vec![Vec2::ZERO; sizes.len()];
let (mut x, mut y, mut shelf) = (0.0f32, 0.0f32, 0.0f32);
for &i in &order {
let r = sizes[i] * s + Vec2::splat(2.0 * pad);
if r.x > res {
return None;
}
if x + r.x > res {
y += shelf;
x = 0.0;
shelf = 0.0;
}
if y + r.y > res {
return None;
}
out[i] = Vec2::new(x, y);
x += r.x;
shelf = shelf.max(r.y);
}
Some(out)
};
while place(0.0, res).is_none() {
res *= 2.0;
if res > MAX_PACK_RES {
return Err(GeomError::Invalid("too many UV charts to pack".into()));
}
}
let largest = sizes.iter().map(|s| s.max_element()).fold(0.0f32, f32::max);
if largest <= 0.0 {
return Ok((0.0, res, place(0.0, res).unwrap_or_default()));
}
let (mut lo, mut hi) = (0.0f32, (res - 2.0 * pad).max(0.0) / largest);
if place(hi, res).is_some() {
lo = hi;
}
for _ in 0..40 {
if hi - lo <= lo * 1e-4 {
break;
}
let mid = 0.5 * (lo + hi);
if place(mid, res).is_some() { lo = mid } else { hi = mid }
}
Ok((lo, res, place(lo, res).unwrap_or_default()))
}
impl Mesh {
/// Index-range checks only (attribute arrays may be incomplete before unwrapping).
fn validate_indices(&self) -> Result<()> {
let n = self.positions.len();
if !self.indices.len().is_multiple_of(3) || self.indices.iter().any(|i| *i as usize >= n) {
return Err(GeomError::Invalid("mesh indices are out of range".into()));
}
if self.triangle_count() > crate::MAX_TRIANGLES {
return Err(GeomError::Invalid(format!("mesh has more than {} triangles", crate::MAX_TRIANGLES)));
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{UvGBuffer, primitives};
fn check(mut m: Mesh, min_coverage: f32) {
m.uvs.clear();
let charts = auto_unwrap(&mut m, 4.0, 512).unwrap();
assert!(charts >= 1);
m.validate().unwrap();
assert!(m.uvs.iter().all(|uv| (0.0..=1.0).contains(&uv.x) && (0.0..=1.0).contains(&uv.y)));
let g = UvGBuffer::new(&m, 0, 512, 512);
let covered = g.covered_count() as f32;
let coverage = covered / (512.0 * 512.0);
assert!(coverage > min_coverage, "coverage {coverage} with {charts} charts");
assert!((g.overlaps as f32) < covered * 0.005, "overlaps {} of {covered}", g.overlaps);
}
#[test]
fn sphere_unwraps_without_overlaps() {
check(primitives::sphere(1.0, 48, 24), 0.3);
}
#[test]
fn cube_unwraps_without_overlaps() {
check(primitives::cube(2.0), 0.3);
}
#[test]
fn torus_and_material_ball_unwrap() {
check(primitives::torus(1.0, 0.3, 48, 24), 0.2);
let mut ball = primitives::material_ball();
ball.uvs.clear();
auto_unwrap(&mut ball, 2.0, 1024).unwrap();
for m in 0..ball.materials.len() {
let g = UvGBuffer::new(&ball, m, 512, 512);
assert!((g.overlaps as f32) < g.covered_count() as f32 * 0.005 + 1.0, "material {m}: {} overlaps", g.overlaps);
}
}
#[test]
fn many_tiny_charts_still_fit() {
// 2000 disconnected triangles: the packer grows its virtual resolution.
let mut p = Vec::new();
let mut idx = Vec::new();
for i in 0..2000u32 {
let o = Vec3::new(i as f32 * 3.0, 0.0, 0.0);
p.extend([o, o + Vec3::X, o + Vec3::Y]);
idx.extend([i * 3, i * 3 + 1, i * 3 + 2]);
}
let mut m = Mesh::from_parts(p, None, Vec::new(), idx, "m").unwrap();
auto_unwrap(&mut m, 4.0, 128).unwrap();
assert!(m.uvs.iter().all(|uv| (0.0..=1.0).contains(&uv.x) && (0.0..=1.0).contains(&uv.y)));
}
#[test]
fn degenerate_and_empty_meshes_do_not_fail() {
let mut empty = Mesh::default();
assert_eq!(auto_unwrap(&mut empty, 4.0, 256).unwrap(), 0);
// A sliver (zero-area) triangle next to a real one.
let p = vec![Vec3::ZERO, Vec3::X, Vec3::Y, Vec3::X * 2.0];
let mut m = Mesh::from_parts(p, None, Vec::new(), vec![0, 1, 2, 0, 1, 3], "m").unwrap();
auto_unwrap(&mut m, 4.0, 256).unwrap();
m.validate().unwrap();
let mut point = Mesh { positions: vec![Vec3::ONE; 3], indices: vec![0, 1, 2], ..Mesh::default() };
assert!(all_triangles_degenerate(&point));
assert!(auto_unwrap(&mut point, 4.0, 256).is_err());
}
}
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.