teamcraft/mesh/
render.rs

1//! A small software renderer for thumbnails: an isometric view of a
2//! [`Mesh`] with a z-buffer, flat shading and dark outlines where the depth
3//! jumps (silhouettes, steps), written as an RGBA PNG with a transparent
4//! background, so it sits on light and dark skins alike.
5//!
6//! Pure Rust; the PNG is written with `flate2` (zlib stream and CRC-32).
7//! Cost is bounded by the triangle count (checked by [`Mesh::check`]) and
8//! the pixel count.
9
10use std::io::Write;
11
12use super::Mesh;
13
14/// Supersampling factor (anti-aliasing).
15const SS: usize = 2;
16
17/// The mesh drawn as a `size` × `size` PNG, or `None` for point clouds and
18/// meshes without area.
19pub fn png(mesh: &Mesh, size: u32) -> Option<Vec<u8>> {
20    if mesh.is_point_cloud() || size == 0 {
21        return None;
22    }
23    let rgba = draw(mesh, size as usize)?;
24    Some(encode_png(size, size, &rgba))
25}
26
27type V = [f64; 3];
28
29fn sub(a: V, b: V) -> V {
30    [a[0] - b[0], a[1] - b[1], a[2] - b[2]]
31}
32
33fn dot(a: V, b: V) -> f64 {
34    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
35}
36
37fn cross(a: V, b: V) -> V {
38    [
39        a[1] * b[2] - a[2] * b[1],
40        a[2] * b[0] - a[0] * b[2],
41        a[0] * b[1] - a[1] * b[0],
42    ]
43}
44
45fn unit(a: V) -> V {
46    let l = dot(a, a).sqrt();
47    if l > 0.0 {
48        [a[0] / l, a[1] / l, a[2] / l]
49    } else {
50        a
51    }
52}
53
54/// RGBA pixels of the view (row major), or `None` without a visible area.
55fn draw(mesh: &Mesh, size: usize) -> Option<Vec<u8>> {
56    let w = size * SS;
57    let points: Vec<V> = mesh
58        .positions
59        .chunks_exact(3)
60        .map(|p| match *p {
61            [x, y, z] => [f64::from(x), f64::from(y), f64::from(z)],
62            _ => [0.0; 3],
63        })
64        .collect();
65    let b = mesh.bounds();
66    let centre = [
67        (f64::from(b[0]) + f64::from(b[3])) / 2.0,
68        (f64::from(b[1]) + f64::from(b[4])) / 2.0,
69        (f64::from(b[2]) + f64::from(b[5])) / 2.0,
70    ];
71    // isometric camera from +x, -y, +z with z up
72    let view = unit([1.0, -1.0, 0.8]);
73    let right = unit(cross([0.0, 0.0, 1.0], view));
74    let up = cross(view, right);
75    let light = unit([
76        0.75 * view[0] + 0.45 * up[0] - 0.35 * right[0],
77        0.75 * view[1] + 0.45 * up[1] - 0.35 * right[1],
78        0.75 * view[2] + 0.45 * up[2] - 0.35 * right[2],
79    ]);
80    // screen coordinates (x, y in pixels, z towards the camera)
81    let projected: Vec<V> = points
82        .iter()
83        .map(|&p| {
84            let q = sub(p, centre);
85            [dot(q, right), dot(q, up), dot(q, view)]
86        })
87        .collect();
88    let (mut lo, mut hi) = ([f64::MAX; 3], [f64::MIN; 3]);
89    for p in &projected {
90        for ((l, h), &v) in lo.iter_mut().zip(hi.iter_mut()).zip(p) {
91            *l = l.min(v);
92            *h = h.max(v);
93        }
94    }
95    let half = ((hi[0] - lo[0]).max(hi[1] - lo[1]) / 2.0) * 1.08;
96    if !(half.is_finite() && half > 0.0) {
97        return None;
98    }
99    let mid = [(lo[0] + hi[0]) / 2.0, (lo[1] + hi[1]) / 2.0];
100    let scale = w as f64 / (2.0 * half);
101    let screen: Vec<V> = projected
102        .iter()
103        .map(|p| {
104            [
105                (p[0] - mid[0]) * scale + w as f64 / 2.0,
106                w as f64 / 2.0 - (p[1] - mid[1]) * scale,
107                p[2],
108            ]
109        })
110        .collect();
111
112    let mut depth = vec![f64::NEG_INFINITY; w * w];
113    let mut colour = vec![[0u8; 3]; w * w];
114    let has_colours = mesh.colors.len() == mesh.positions.len();
115    for t in mesh.indices.chunks_exact(3) {
116        let [ia, ib, ic] = match *t {
117            [a, b, c] => [a as usize, b as usize, c as usize],
118            _ => continue,
119        };
120        let (Some(&a), Some(&b), Some(&c)) = (screen.get(ia), screen.get(ib), screen.get(ic))
121        else {
122            continue;
123        };
124        let (Some(&pa), Some(&pb), Some(&pc)) = (points.get(ia), points.get(ib), points.get(ic))
125        else {
126            continue;
127        };
128        let normal = unit(cross(sub(pb, pa), sub(pc, pa)));
129        let shade = if dot(normal, view) >= 0.0 {
130            0.22 + 0.78 * dot(normal, light).clamp(0.0, 1.0)
131        } else {
132            0.12 // inside seen through an open mesh
133        };
134        let base = if has_colours {
135            let c = |i: usize, k: usize| f64::from(*mesh.colors.get(i * 3 + k).unwrap_or(&0));
136            [0, 1, 2].map(|k| (c(ia, k) + c(ib, k) + c(ic, k)) / 3.0)
137        } else {
138            [150.0, 170.0, 192.0]
139        };
140        let rgb = base.map(|v| (v * shade * 1.35).clamp(0.0, 255.0) as u8);
141        fill(&mut depth, &mut colour, w, [a, b, c], rgb);
142    }
143    if depth.iter().all(|d| d.is_infinite()) {
144        return None;
145    }
146    outline(&depth, &mut colour, w, hi[2] - lo[2]);
147    Some(downsample(&depth, &colour, w, size))
148}
149
150/// Rasterises one triangle into the z-buffer.
151fn fill(depth: &mut [f64], colour: &mut [[u8; 3]], w: usize, [a, b, c]: [V; 3], rgb: [u8; 3]) {
152    let area = (b[1] - c[1]) * (a[0] - c[0]) + (c[0] - b[0]) * (a[1] - c[1]);
153    if area.abs() < 1e-12 || !area.is_finite() {
154        return;
155    }
156    let max = (w - 1) as f64;
157    let x0 = a[0].min(b[0]).min(c[0]).floor().clamp(0.0, max) as usize;
158    let x1 = a[0].max(b[0]).max(c[0]).ceil().clamp(0.0, max) as usize;
159    let y0 = a[1].min(b[1]).min(c[1]).floor().clamp(0.0, max) as usize;
160    let y1 = a[1].max(b[1]).max(c[1]).ceil().clamp(0.0, max) as usize;
161    for y in y0..=y1 {
162        let py = y as f64 + 0.5;
163        for x in x0..=x1 {
164            let px = x as f64 + 0.5;
165            let w0 = ((b[1] - c[1]) * (px - c[0]) + (c[0] - b[0]) * (py - c[1])) / area;
166            let w1 = ((c[1] - a[1]) * (px - c[0]) + (a[0] - c[0]) * (py - c[1])) / area;
167            let w2 = 1.0 - w0 - w1;
168            if w0 < -1e-9 || w1 < -1e-9 || w2 < -1e-9 {
169                continue;
170            }
171            let z = w0 * a[2] + w1 * b[2] + w2 * c[2];
172            let i = y * w + x;
173            if let (Some(d), Some(col)) = (depth.get_mut(i), colour.get_mut(i)) {
174                if z > *d {
175                    *d = z;
176                    *col = rgb;
177                }
178            }
179        }
180    }
181}
182
183/// Darkens pixels where the depth jumps (silhouettes and steps).
184fn outline(depth: &[f64], colour: &mut [[u8; 3]], w: usize, range: f64) {
185    let jump = range * 0.02;
186    let far = |d: f64| if d.is_finite() { d } else { -1e30 };
187    let mut edge = vec![false; w * w];
188    for y in 0..w {
189        for x in 0..w {
190            let i = y * w + x;
191            let d = far(*depth.get(i).unwrap_or(&f64::NEG_INFINITY));
192            let right = (x + 1 < w).then(|| far(*depth.get(i + 1).unwrap_or(&f64::NEG_INFINITY)));
193            let below = (y + 1 < w).then(|| far(*depth.get(i + w).unwrap_or(&f64::NEG_INFINITY)));
194            if [right, below]
195                .into_iter()
196                .flatten()
197                .any(|n| (n - d).abs() > jump)
198            {
199                if let Some(e) = edge.get_mut(i) {
200                    *e = true;
201                }
202            }
203        }
204    }
205    for (c, e) in colour.iter_mut().zip(&edge) {
206        if *e {
207            *c = c.map(|v| (f64::from(v) * 0.35) as u8);
208        }
209    }
210}
211
212/// Averages `SS` × `SS` blocks into RGBA; empty pixels are transparent.
213fn downsample(depth: &[f64], colour: &[[u8; 3]], w: usize, size: usize) -> Vec<u8> {
214    let mut out = Vec::with_capacity(size * size * 4);
215    for y in 0..size {
216        for x in 0..size {
217            let (mut sum, mut covered) = ([0u32; 3], 0u32);
218            for dy in 0..SS {
219                for dx in 0..SS {
220                    let i = (y * SS + dy) * w + x * SS + dx;
221                    if depth.get(i).is_some_and(|d| d.is_finite()) {
222                        if let Some(c) = colour.get(i) {
223                            for (s, &v) in sum.iter_mut().zip(c) {
224                                *s += u32::from(v);
225                            }
226                            covered += 1;
227                        }
228                    }
229                }
230            }
231            if covered == 0 {
232                out.extend([0, 0, 0, 0]);
233            } else {
234                out.extend(sum.map(|s| (s / covered) as u8));
235                out.push((covered * 255 / (SS * SS) as u32) as u8);
236            }
237        }
238    }
239    out
240}
241
242/// An 8-bit RGBA PNG (no filtering, zlib-compressed).
243fn encode_png(width: u32, height: u32, rgba: &[u8]) -> Vec<u8> {
244    let mut raw = Vec::with_capacity(rgba.len() + height as usize);
245    for row in rgba.chunks(width as usize * 4) {
246        raw.push(0); // filter: none
247        raw.extend_from_slice(row);
248    }
249    let mut z = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::default());
250    // writing into a Vec cannot fail
251    let compressed: Vec<u8> = z
252        .write_all(&raw)
253        .and_then(|_| z.finish())
254        .unwrap_or_default();
255    let mut png = vec![0x89, b'P', b'N', b'G', 0x0D, 0x0A, 0x1A, 0x0A];
256    let mut ihdr = Vec::with_capacity(13);
257    ihdr.extend(width.to_be_bytes());
258    ihdr.extend(height.to_be_bytes());
259    ihdr.extend([8, 6, 0, 0, 0]); // 8 bit, RGBA, deflate, no filter set, no interlace
260    chunk(&mut png, b"IHDR", &ihdr);
261    chunk(&mut png, b"IDAT", &compressed);
262    chunk(&mut png, b"IEND", &[]);
263    png
264}
265
266fn chunk(png: &mut Vec<u8>, kind: &[u8; 4], data: &[u8]) {
267    png.extend((data.len() as u32).to_be_bytes());
268    png.extend(kind);
269    png.extend(data);
270    let mut crc = flate2::Crc::new();
271    crc.update(kind);
272    crc.update(data);
273    png.extend(crc.sum().to_be_bytes());
274}
275
276#[cfg(test)]
277mod tests {
278    use super::*;
279
280    fn cube() -> Mesh {
281        let p = [
282            [0., 0., 0.],
283            [1., 0., 0.],
284            [1., 1., 0.],
285            [0., 1., 0.],
286            [0., 0., 1.],
287            [1., 0., 1.],
288            [1., 1., 1.],
289            [0., 1., 1.],
290        ];
291        let faces = [
292            [0, 2, 1],
293            [0, 3, 2],
294            [4, 5, 6],
295            [4, 6, 7],
296            [0, 1, 5],
297            [0, 5, 4],
298            [1, 2, 6],
299            [1, 6, 5],
300            [2, 3, 7],
301            [2, 7, 6],
302            [3, 0, 4],
303            [3, 4, 7],
304        ];
305        Mesh {
306            positions: p.iter().flatten().map(|&v: &f64| v as f32).collect(),
307            indices: faces.iter().flatten().copied().collect(),
308            parts: 1,
309            ..Mesh::default()
310        }
311    }
312
313    #[test]
314    fn a_cube_becomes_a_png_with_a_transparent_background() {
315        let png = png(&cube(), 64).unwrap();
316        assert!(png.starts_with(&[0x89, b'P', b'N', b'G']));
317        // IHDR: 64 × 64, RGBA
318        assert_eq!(png.get(16..24), Some(&[0, 0, 0, 64, 0, 0, 0, 64][..]));
319        assert_eq!(png.get(25), Some(&6));
320        let rgba = draw(&cube(), 64).unwrap();
321        let alpha: Vec<u8> = rgba.chunks(4).filter_map(|p| p.get(3).copied()).collect();
322        assert_eq!(alpha.first(), Some(&0), "corner is background");
323        assert_eq!(alpha.get(32 * 64 + 32), Some(&255), "centre is the cube");
324        // three visible sides with three different shades
325        let mut shades: Vec<&[u8]> = rgba
326            .chunks(4)
327            .filter(|p| p.get(3) == Some(&255))
328            .filter_map(|p| p.get(..3))
329            .collect();
330        shades.sort();
331        shades.dedup();
332        assert!(shades.len() >= 3, "{shades:?}");
333    }
334
335    #[test]
336    fn png_chunks_carry_valid_checksums() {
337        let png = encode_png(2, 1, &[255, 0, 0, 255, 0, 0, 255, 128]);
338        let mut at = 8;
339        let mut kinds = Vec::new();
340        let be =
341            |from: usize| u32::from_be_bytes(png.get(from..from + 4).unwrap().try_into().unwrap());
342        while at < png.len() {
343            let len = be(at) as usize;
344            let kind = png.get(at + 4..at + 8).unwrap();
345            let data = png.get(at + 8..at + 8 + len).unwrap();
346            let crc = be(at + 8 + len);
347            let mut c = flate2::Crc::new();
348            c.update(kind);
349            c.update(data);
350            assert_eq!(c.sum(), crc);
351            kinds.push(String::from_utf8_lossy(kind).to_string());
352            at += 12 + len;
353        }
354        assert_eq!(kinds, ["IHDR", "IDAT", "IEND"]);
355    }
356
357    #[test]
358    fn point_clouds_and_flat_nothing_give_no_image() {
359        let mut points = cube();
360        points.indices.clear();
361        assert!(png(&points, 32).is_none());
362        let empty = Mesh {
363            positions: vec![0.0; 9],
364            indices: vec![0, 1, 2],
365            ..Mesh::default()
366        };
367        assert!(png(&empty, 32).is_none());
368    }
369}
teamcraft/mesh/render.rs

teamcraft/mesh/
render.rs
