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.
276#[inline]
277pub fn analyze_overdraw_generic<I: crate::Index>(
278    indices: &[I],
279    positions: Positions<'_>,
280    workspace: &mut Workspace,
281) -> Result<OverdrawStatistics, Error> {
282    I::with_input(indices, workspace, |indices, workspace| {
283        analyze_overdraw_u32(indices, positions, workspace)
284    })
285}
286
287fn analyze_overdraw_u32(
288    indices: &[u32],
289    positions: Positions<'_>,
290    workspace: &mut Workspace,
291) -> Result<OverdrawStatistics, Error> {
292    Ok(analyze(indices, positions, workspace, false)?.0)
293}
294
295/// Analyze projected coverage on three axes with the upstream rasterizer.
296///
297/// # Errors
298/// `InvalidTopology` for incomplete triangles or `IndexOutOfBounds` for invalid vertex references.
299/// `NumericalFailure` for non-finite geometry or calculations.
300/// `SizeOverflow` for size overflow, `LimitExceeded` for exhausted limits, or `AllocationFailed` for failed reservation.
301#[inline]
302pub fn analyze_coverage_generic<I: crate::Index>(
303    indices: &[I],
304    positions: Positions<'_>,
305    workspace: &mut Workspace,
306) -> Result<CoverageStatistics, Error> {
307    I::with_input(indices, workspace, |indices, workspace| {
308        analyze_coverage_u32(indices, positions, workspace)
309    })
310}
311
312fn analyze_coverage_u32(
313    indices: &[u32],
314    positions: Positions<'_>,
315    workspace: &mut Workspace,
316) -> Result<CoverageStatistics, Error> {
317    Ok(analyze(indices, positions, workspace, true)?.1)
318}
319
320/// The source-compatible u32 entry point; see [`analyze_overdraw_generic`] for selectable index widths.
321#[inline]
322pub fn analyze_overdraw(
323    indices: &[u32],
324    positions: Positions<'_>,
325    workspace: &mut Workspace,
326) -> Result<OverdrawStatistics, Error> {
327    analyze_overdraw_generic::<u32>(indices, positions, workspace)
328}
329
330/// The source-compatible u32 entry point; see [`analyze_coverage_generic`] for selectable index widths.
331#[inline]
332pub fn analyze_coverage(
333    indices: &[u32],
334    positions: Positions<'_>,
335    workspace: &mut Workspace,
336) -> Result<CoverageStatistics, Error> {
337    analyze_coverage_generic::<u32>(indices, positions, workspace)
338}
339
340#[cfg(test)]
341mod tests {
342    use super::*;
343    use crate::Limits;
344
345    #[test]
346    fn empty_views_keep_triangle_and_scan_work() {
347        // Unreferenced finite geometry fixes the scale at 1. All projected
348        // triangle boxes are subpixel in at least one dimension in every view.
349        let storage = [
350            [1.01, 1.01, 1.01],
351            [1.03, 1.01, 1.02],
352            [1.01, 1.03, 1.03],
353            [0.0, 0.0, 0.0],
354            [256.0, 256.0, 256.0],
355        ];
356        let positions = Positions::from_packed(&storage);
357        let indices = [0, 1, 2, 0, 1, 2];
358        let total = 6 + 5 + 6 + 3 * (2 + VIEWPORT * VIEWPORT);
359        for fuel in [
360            0,
361            5,
362            6,
363            10,
364            11,
365            16,
366            17,
367            18,
368            19,
369            65555,
370            65556,
371            65557,
372            total - 1,
373            total,
374        ] {
375            for coverage in [false, true] {
376                let mut workspace = Workspace::new(Limits {
377                    max_bytes: 2 << 20,
378                    max_work: fuel as u64,
379                });
380                let result = analyze(&indices, positions, &mut workspace, coverage);
381                assert_eq!(workspace.usage().work, fuel as u64);
382                if fuel == total {
383                    assert_eq!(
384                        result,
385                        Ok((
386                            OverdrawStatistics::default(),
387                            CoverageStatistics {
388                                coverage: [0.0; 3],
389                                extent: 256.0,
390                            }
391                        ))
392                    );
393                } else {
394                    assert_eq!(result, Err(Error::LimitExceeded));
395                }
396            }
397        }
398    }
399
400    #[test]
401    fn packed_transform_keeps_logical_mapped_positions() {
402        let storage = [
403            [0.0, 0.0, 0.0],
404            [1.0, 0.0, 0.0],
405            [0.0, 1.0, 0.0],
406            [f32::NAN; 3],
407        ];
408        let mapping = [2, 0, 1];
409        let ordered = mapping.map(|i| storage[i as usize]);
410        let mapped = Positions::from_packed(&storage).mapped(&mapping);
411        let reference = Positions::from_packed(&ordered);
412        let mut actual_ws = Workspace::default();
413        let mut reference_ws = Workspace::default();
414        assert_eq!(
415            analyze_overdraw(&[0, 1, 2], mapped, &mut actual_ws),
416            analyze_overdraw(&[0, 1, 2], reference, &mut reference_ws)
417        );
418        assert_eq!(actual_ws.usage(), reference_ws.usage());
419        assert_eq!(
420            analyze_coverage(&[0, 1, 2], mapped, &mut actual_ws),
421            analyze_coverage(&[0, 1, 2], reference, &mut reference_ws)
422        );
423        assert_eq!(actual_ws.usage(), reference_ws.usage());
424    }
425
426    #[test]
427    fn pixel_scan_keeps_tight_fuel_and_statistics_prefixes() {
428        let buffer = [[0, 0], [3, 0], [0, 5], [7, 11]].map(|overdraw| Pixel {
429            overdraw,
430            ..Pixel::default()
431        });
432        for limit in 0..=5 {
433            for coverage in [false, true] {
434                let mut workspace = Workspace::new(Limits {
435                    max_bytes: 1024,
436                    max_work: limit,
437                });
438                let mut work = workspace.begin();
439                let mut stats = OverdrawStatistics::default();
440                let result = if work.covers(buffer.len()).unwrap() {
441                    work.add(buffer.len()).unwrap();
442                    if coverage {
443                        scan_pixels::<true, false>(&buffer, &mut stats, &mut work)
444                    } else {
445                        scan_pixels::<false, false>(&buffer, &mut stats, &mut work)
446                    }
447                } else if coverage {
448                    scan_pixels::<true, true>(&buffer, &mut stats, &mut work)
449                } else {
450                    scan_pixels::<false, true>(&buffer, &mut stats, &mut work)
451                };
452                workspace.finish(&work);
453                assert_eq!(workspace.usage().work, limit.min(4));
454                assert_eq!(result.is_ok(), limit >= 4);
455                if coverage {
456                    assert_eq!(
457                        result,
458                        if limit >= 4 {
459                            Ok(3)
460                        } else {
461                            Err(Error::LimitExceeded)
462                        }
463                    );
464                    assert_eq!((stats.pixels_covered, stats.pixels_shaded), (0, 0));
465                } else {
466                    let expected = [(0, 0), (0, 0), (1, 3), (2, 8), (4, 26), (4, 26)];
467                    assert_eq!(
468                        (stats.pixels_covered, stats.pixels_shaded),
469                        expected[limit as usize]
470                    );
471                    assert_eq!(
472                        result,
473                        if limit >= 4 {
474                            Ok(0)
475                        } else {
476                            Err(Error::LimitExceeded)
477                        }
478                    );
479                }
480            }
481        }
482    }
483}