Files
texturecraft/crates/geom/src/unwrap.rs
bflatastic ec859420d5 TextureCraft: clean-room 3D texture painting in pure Rust
An open-source, clean-room implementation of a Substance 3D Painter-style texturing
workflow, written in pure Rust with egui and wgpu.

- Layer stack with 32 blend modes, masks, generators, content effects and anchor points
- Painting, projection, smudge, clone, path, lasso fill, particle brush and quick mask
- 43 procedural materials, 17 smart materials and 10 smart masks
- Mesh map baking with high-poly, cage and match-by-name support
- PBR viewport with HDR environments, TAA and a path-traced Rendering mode
- glTF, FBX, COLLADA, OBJ, PLY and STL import; texture export presets; OBJ and GLB export
- Dockable Painter-style UI, shortcut editor, web build, MCP server and CLI

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-15 01:33:13 +07:00

385 lines
15 KiB
Rust
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
//! 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());
}
}