Skip to main content

meshoptimizer_rs/
raster.rs

1//! Scalar software rasterizer used by the two upstream raster analyzers.
2use crate::input::PositionReader;
3use crate::workspace::{checked_bytes, topology, Work};
4use crate::{Error, Positions, Workspace};
5use alloc::vec::Vec;
6
7/// Result of `meshopt_analyzeOverdraw`.
8#[derive(Clone, Copy, Debug, Default, PartialEq)]
9pub struct OverdrawStatistics {
10    /// Rasterized pixels with at least one depth pass.
11    pub pixels_covered: u32,
12    /// Total depth passes.
13    pub pixels_shaded: u32,
14    /// Shaded to covered pixel ratio.
15    pub overdraw: f32,
16}
17
18/// Result of `meshopt_analyzeCoverage`.
19#[derive(Clone, Copy, Debug, Default, PartialEq)]
20pub struct CoverageStatistics {
21    /// Covered viewport fraction along X, Y and Z.
22    pub coverage: [f32; 3],
23    /// Largest axis extent in mesh coordinates.
24    pub extent: f32,
25}
26
27#[derive(Clone, Copy, Default)]
28struct Pixel {
29    depth: [f32; 2],
30    overdraw: [u32; 2],
31}
32const VIEWPORT: usize = 256;
33
34fn reserve<T: Default + Clone>(count: usize) -> Result<Vec<T>, Error> {
35    checked_bytes(count, core::mem::size_of::<T>())?;
36    let mut value = Vec::new();
37    value
38        .try_reserve_exact(count)
39        .map_err(|_| Error::AllocationFailed)?;
40    value.resize(count, T::default());
41    Ok(value)
42}
43
44fn transform(
45    indices: &[u32],
46    positions: impl PositionReader,
47    work: &mut Work,
48) -> Result<(Vec<[f32; 3]>, f32), Error> {
49    let mut minv = [f32::MAX; 3];
50    let mut maxv = [-f32::MAX; 3];
51    work.scan(0..positions.len(), |i| {
52        let value = positions.read(i);
53        for j in 0..3 {
54            if !value[j].is_finite() {
55                return Err(Error::NumericalFailure);
56            }
57            minv[j] = if minv[j] > value[j] {
58                value[j]
59            } else {
60                minv[j]
61            };
62            maxv[j] = if maxv[j] < value[j] {
63                value[j]
64            } else {
65                maxv[j]
66            };
67        }
68        Ok(())
69    })?;
70    let mut extent = 0.0f32;
71    for j in 0..3 {
72        let d = maxv[j] - minv[j];
73        extent = if d < extent { extent } else { d };
74    }
75    if !extent.is_finite() {
76        return Err(Error::NumericalFailure);
77    }
78    let scale = if extent == 0.0 {
79        0.0
80    } else {
81        VIEWPORT as f32 / extent
82    };
83    checked_bytes(indices.len(), core::mem::size_of::<[f32; 3]>())?;
84    let mut transformed = Vec::new();
85    transformed
86        .try_reserve_exact(indices.len())
87        .map_err(|_| Error::AllocationFailed)?;
88    let transform_position = |index: u32| {
89        // topology checked indices before this reader is selected.
90        let value = positions.read(index as usize);
91        [
92            (value[0] - minv[0]) * scale,
93            (value[1] - minv[1]) * scale,
94            (value[2] - minv[2]) * scale,
95        ]
96    };
97    if work.covers(indices.len())? {
98        work.add(indices.len())?;
99        // The exact iterator length fits the fallibly reserved capacity.
100        // Vec's iterator extension fills it directly without zeroing first.
101        transformed.extend(indices.iter().copied().map(transform_position));
102    } else {
103        for &index in indices {
104            work.add(1)?;
105            transformed.push(transform_position(index));
106        }
107    }
108    Ok((transformed, extent))
109}
110
111fn rasterize(buffer: &mut [Pixel], mut p: [[f32; 3]; 3], work: &mut Work) -> Result<(), Error> {
112    let det = (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) - (p[1][1] - p[0][1]) * (p[2][0] - p[0][0]);
113    let invdet = if det == 0.0 { 0.0 } else { 1.0 / det };
114    let mut dzx = ((p[1][2] - p[0][2]) * (p[2][1] - p[0][1])
115        - (p[1][1] - p[0][1]) * (p[2][2] - p[0][2]))
116        * invdet;
117    let mut dzy = ((p[1][0] - p[0][0]) * (p[2][2] - p[0][2])
118        - (p[1][2] - p[0][2]) * (p[2][0] - p[0][0]))
119        * invdet;
120    let side = usize::from(det > 0.0);
121    if side != 0 {
122        let (a, b) = p.split_at_mut(2);
123        core::mem::swap(&mut a[1][0], &mut b[0][0]);
124        core::mem::swap(&mut a[1][1], &mut b[0][1]);
125        p[0][2] = VIEWPORT as f32 - p[0][2];
126        dzx = -dzx;
127        dzy = -dzy;
128    }
129    let x = p.map(|v| (16.0 * v[0] + 0.5) as i32);
130    let y = p.map(|v| (16.0 * v[1] + 0.5) as i32);
131    let minx = ((x[0].min(x[1]).min(x[2]) + 7) >> 4).max(0);
132    let miny = ((y[0].min(y[1]).min(y[2]) + 7) >> 4).max(0);
133    let maxx = ((x[0].max(x[1]).max(x[2]) + 7) >> 4).min(VIEWPORT as i32);
134    let maxy = ((y[0].max(y[1]).max(y[2]) + 7) >> 4).min(VIEWPORT as i32);
135    let visits = (maxx - minx).max(0) as usize * (maxy - miny).max(0) as usize;
136    let bulk_pixels = work.covers(visits)?;
137    if bulk_pixels {
138        work.add(visits)?;
139    }
140    if minx >= maxx || miny >= maxy {
141        return Ok(());
142    }
143    let (dx12, dx23, dx31) = (x[0] - x[1], x[1] - x[2], x[2] - x[0]);
144    let (dy12, dy23, dy31) = (y[0] - y[1], y[1] - y[2], y[2] - y[0]);
145    let tl1 = i32::from(dy12 < 0 || (dy12 == 0 && dx12 > 0));
146    let tl2 = i32::from(dy23 < 0 || (dy23 == 0 && dx23 > 0));
147    let tl3 = i32::from(dy31 < 0 || (dy31 == 0 && dx31 > 0));
148    let (fx, fy) = ((minx << 4) + 8, (miny << 4) + 8);
149    let mut cy1 = dx12 * (fy - y[0]) - dy12 * (fx - x[0]) + tl1 - 1;
150    let mut cy2 = dx23 * (fy - y[1]) - dy23 * (fx - x[1]) + tl2 - 1;
151    let mut cy3 = dx31 * (fy - y[2]) - dy31 * (fx - x[2]) + tl3 - 1;
152    let mut zy = p[0][2] + (dzx * (fx - x[0]) as f32 + dzy * (fy - y[0]) as f32) * (1.0 / 16.0);
153    for yy in miny..maxy {
154        let (mut cx1, mut cx2, mut cx3) = (cy1, cy2, cy3);
155        let mut zx = zy;
156        let row_start = yy as usize * VIEWPORT + minx as usize;
157        let row_end = yy as usize * VIEWPORT + maxx as usize;
158        for pixel in &mut buffer[row_start..row_end] {
159            if !bulk_pixels {
160                work.add(1)?;
161            }
162            if (cx1 | cx2 | cx3) >= 0 && zx >= pixel.depth[side] {
163                pixel.depth[side] = zx;
164                pixel.overdraw[side] += 1;
165            }
166            cx1 -= dy12 << 4;
167            cx2 -= dy23 << 4;
168            cx3 -= dy31 << 4;
169            zx += dzx;
170        }
171        cy1 += dx12 << 4;
172        cy2 += dx23 << 4;
173        cy3 += dx31 << 4;
174        zy += dzy;
175    }
176    Ok(())
177}
178
179// Keep the covered integer reduction free of the tight-fuel branch so both
180// consumer profiles can vectorize it. The fallback charges before each pixel.
181fn scan_pixels<const COVERAGE: bool, const CHARGE: bool>(
182    buffer: &[Pixel],
183    overdraw: &mut OverdrawStatistics,
184    work: &mut Work,
185) -> Result<u32, Error> {
186    let mut covered = 0;
187    for pixel in buffer {
188        if CHARGE {
189            work.add(1)?;
190        }
191        if COVERAGE {
192            covered += u32::from((pixel.overdraw[0] | pixel.overdraw[1]) > 0);
193        } else {
194            for &value in &pixel.overdraw {
195                overdraw.pixels_covered += u32::from(value > 0);
196                overdraw.pixels_shaded += value;
197            }
198        }
199    }
200    Ok(covered)
201}
202
203fn analyze(
204    indices: &[u32],
205    positions: Positions<'_>,
206    workspace: &mut Workspace,
207    coverage: bool,
208) -> Result<(OverdrawStatistics, CoverageStatistics), Error> {
209    let mut work = workspace.begin();
210    let result = (|| {
211        topology(indices, positions.len(), &mut work)?;
212        let bytes = checked_bytes(indices.len(), 12)?
213            .checked_add(checked_bytes(
214                VIEWPORT * VIEWPORT,
215                core::mem::size_of::<Pixel>(),
216            )?)
217            .ok_or(Error::SizeOverflow)?;
218        workspace.account_codec(bytes)?;
219        let (triangles, extent) = if let Some(packed) = positions.packed_values() {
220            transform(indices, packed, &mut work)?
221        } else {
222            transform(indices, positions, &mut work)?
223        };
224        let mut buffer = reserve::<Pixel>(VIEWPORT * VIEWPORT)?;
225        let mut overdraw = OverdrawStatistics::default();
226        let mut result_coverage = CoverageStatistics {
227            extent,
228            ..CoverageStatistics::default()
229        };
230        for axis in 0..3 {
231            // reserve initializes positive zero; clear only between views.
232            if axis != 0 {
233                buffer.fill(Pixel::default());
234            }
235            for tri in triangles.as_chunks::<3>().0 {
236                work.add(1)?;
237                let [a, b, c] = *tri;
238                let reordered = match axis {
239                    0 => [[a[2], a[1], a[0]], [b[2], b[1], b[0]], [c[2], c[1], c[0]]],
240                    1 => [[a[0], a[2], a[1]], [b[0], b[2], b[1]], [c[0], c[2], c[1]]],
241                    _ => [[a[1], a[0], a[2]], [b[1], b[0], b[2]], [c[1], c[0], c[2]]],
242                };
243                rasterize(&mut buffer, reordered, &mut work)?;
244            }
245            let bulk_scan = work.covers(buffer.len())?;
246            if bulk_scan {
247                work.add(buffer.len())?;
248            }
249            let covered = match (coverage, bulk_scan) {
250                (true, true) => scan_pixels::<true, false>(&buffer, &mut overdraw, &mut work)?,
251                (true, false) => scan_pixels::<true, true>(&buffer, &mut overdraw, &mut work)?,
252                (false, true) => scan_pixels::<false, false>(&buffer, &mut overdraw, &mut work)?,
253                (false, false) => scan_pixels::<false, true>(&buffer, &mut overdraw, &mut work)?,
254            };
255            if coverage {
256                result_coverage.coverage[axis] = covered as f32 / (VIEWPORT * VIEWPORT) as f32;
257            }
258        }
259        overdraw.overdraw = if overdraw.pixels_covered == 0 {
260            0.0
261        } else {
262            overdraw.pixels_shaded as f32 / overdraw.pixels_covered as f32
263        };
264        Ok((overdraw, result_coverage))
265    })();
266    workspace.finish(&work);
267    result
268}
269
270/// Analyze raster overdraw with upstream's 256-pixel viewport model.
271///
272/// # Errors
273/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
274/// `NumericalFailure` for non-finite geometry or calculations.
275/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
276pub fn analyze_overdraw(
277    indices: &[u32],
278    positions: Positions<'_>,
279    workspace: &mut Workspace,
280) -> Result<OverdrawStatistics, Error> {
281    Ok(analyze(indices, positions, workspace, false)?.0)
282}
283
284/// Analyze projected coverage on three axes with the upstream rasterizer.
285///
286/// # Errors
287/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
288/// `NumericalFailure` for non-finite geometry or calculations.
289/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
290pub fn analyze_coverage(
291    indices: &[u32],
292    positions: Positions<'_>,
293    workspace: &mut Workspace,
294) -> Result<CoverageStatistics, Error> {
295    Ok(analyze(indices, positions, workspace, true)?.1)
296}
297
298#[cfg(test)]
299mod tests {
300    use super::*;
301    use crate::Limits;
302
303    #[test]
304    fn empty_views_keep_triangle_and_scan_work() {
305        // Unreferenced finite geometry fixes the scale at 1. All projected
306        // triangle boxes are subpixel in at least one dimension in every view.
307        let storage = [
308            [1.01, 1.01, 1.01],
309            [1.03, 1.01, 1.02],
310            [1.01, 1.03, 1.03],
311            [0.0, 0.0, 0.0],
312            [256.0, 256.0, 256.0],
313        ];
314        let positions = Positions::from_packed(&storage);
315        let indices = [0, 1, 2, 0, 1, 2];
316        let total = 6 + 5 + 6 + 3 * (2 + VIEWPORT * VIEWPORT);
317        for fuel in [
318            0,
319            5,
320            6,
321            10,
322            11,
323            16,
324            17,
325            18,
326            19,
327            65555,
328            65556,
329            65557,
330            total - 1,
331            total,
332        ] {
333            for coverage in [false, true] {
334                let mut workspace = Workspace::new(Limits {
335                    max_bytes: 2 << 20,
336                    max_work: fuel as u64,
337                });
338                let result = analyze(&indices, positions, &mut workspace, coverage);
339                assert_eq!(workspace.usage().work, fuel as u64);
340                if fuel == total {
341                    assert_eq!(
342                        result,
343                        Ok((
344                            OverdrawStatistics::default(),
345                            CoverageStatistics {
346                                coverage: [0.0; 3],
347                                extent: 256.0,
348                            }
349                        ))
350                    );
351                } else {
352                    assert_eq!(result, Err(Error::LimitExceeded));
353                }
354            }
355        }
356    }
357
358    #[test]
359    fn packed_transform_keeps_logical_mapped_positions() {
360        let storage = [
361            [0.0, 0.0, 0.0],
362            [1.0, 0.0, 0.0],
363            [0.0, 1.0, 0.0],
364            [f32::NAN; 3],
365        ];
366        let mapping = [2, 0, 1];
367        let ordered = mapping.map(|i| storage[i as usize]);
368        let mapped = Positions::from_packed(&storage).mapped(&mapping);
369        let reference = Positions::from_packed(&ordered);
370        let mut actual_ws = Workspace::default();
371        let mut reference_ws = Workspace::default();
372        assert_eq!(
373            analyze_overdraw(&[0, 1, 2], mapped, &mut actual_ws),
374            analyze_overdraw(&[0, 1, 2], reference, &mut reference_ws)
375        );
376        assert_eq!(actual_ws.usage(), reference_ws.usage());
377        assert_eq!(
378            analyze_coverage(&[0, 1, 2], mapped, &mut actual_ws),
379            analyze_coverage(&[0, 1, 2], reference, &mut reference_ws)
380        );
381        assert_eq!(actual_ws.usage(), reference_ws.usage());
382    }
383
384    #[test]
385    fn pixel_scan_keeps_tight_fuel_and_statistics_prefixes() {
386        let buffer = [[0, 0], [3, 0], [0, 5], [7, 11]].map(|overdraw| Pixel {
387            overdraw,
388            ..Pixel::default()
389        });
390        for limit in 0..=5 {
391            for coverage in [false, true] {
392                let mut workspace = Workspace::new(Limits {
393                    max_bytes: 1024,
394                    max_work: limit,
395                });
396                let mut work = workspace.begin();
397                let mut stats = OverdrawStatistics::default();
398                let result = if work.covers(buffer.len()).unwrap() {
399                    work.add(buffer.len()).unwrap();
400                    if coverage {
401                        scan_pixels::<true, false>(&buffer, &mut stats, &mut work)
402                    } else {
403                        scan_pixels::<false, false>(&buffer, &mut stats, &mut work)
404                    }
405                } else if coverage {
406                    scan_pixels::<true, true>(&buffer, &mut stats, &mut work)
407                } else {
408                    scan_pixels::<false, true>(&buffer, &mut stats, &mut work)
409                };
410                workspace.finish(&work);
411                assert_eq!(workspace.usage().work, limit.min(4));
412                assert_eq!(result.is_ok(), limit >= 4);
413                if coverage {
414                    assert_eq!(
415                        result,
416                        if limit >= 4 {
417                            Ok(3)
418                        } else {
419                            Err(Error::LimitExceeded)
420                        }
421                    );
422                    assert_eq!((stats.pixels_covered, stats.pixels_shaded), (0, 0));
423                } else {
424                    let expected = [(0, 0), (0, 0), (1, 3), (2, 8), (4, 26), (4, 26)];
425                    assert_eq!(
426                        (stats.pixels_covered, stats.pixels_shaded),
427                        expected[limit as usize]
428                    );
429                    assert_eq!(
430                        result,
431                        if limit >= 4 {
432                            Ok(0)
433                        } else {
434                            Err(Error::LimitExceeded)
435                        }
436                    );
437                }
438            }
439        }
440    }
441}