Skip to main content

meshoptimizer_rs/
hidden.rs

1//! Conservative opaque-surface visibility. An extension, not in C++ meshoptimizer.
2use crate::budget::Budget;
3use crate::sanitize::sort_work;
4use crate::workspace::Work;
5use crate::{Error, Positions, Workspace};
6use alloc::vec::Vec;
7
8type Point = [f64; 3];
9
10/// Views for hidden-surface removal. Not in C++ meshoptimizer.
11/// Surfaces occlude from both sides; winding does not affect visibility.
12#[derive(Clone, Copy, Debug)]
13#[non_exhaustive]
14pub enum HiddenViews<'a> {
15    /// 26 orthographic directions: every nonzero vector in {-1,0,1}³,
16    /// normalized, in lexicographic order. Views extend to infinity.
17    Outside,
18    /// Perspective views at each supplied finite point. An empty list is invalid.
19    Points(&'a [[f32; 3]]),
20    /// Perspective views at the eight corners and center of this finite box.
21    /// Each minimum component must be at most the corresponding maximum.
22    Bounds {
23        /// Inclusive minimum corner.
24        min: [f32; 3],
25        /// Inclusive maximum corner.
26        max: [f32; 3],
27    },
28}
29
30/// Sampling controls. Not in C++ meshoptimizer. Always available, including no_std.
31#[derive(Clone, Copy, Debug)]
32#[non_exhaustive]
33pub struct HiddenOptions<'a> {
34    /// Requested views; defaults to [`HiddenViews::Outside`].
35    pub views: HiddenViews<'a>,
36    /// Barycentric denominator for finite views and the outside compatibility
37    /// guard, 1..=64 (default 2). Raster coverage is independent of this value. All lattice
38    /// points, including vertices and edges, and the centroid are tested.
39    /// There are (s+1)(s+2)/2 + 1 samples, including a repeated centroid
40    /// when s is divisible by three.
41    pub subdivisions: u32,
42    /// World-space depth tolerance (outside), or distance ignored next to
43    /// each sample and viewpoint (finite views).
44    /// Must be finite and nonnegative; default zero. A numerical guard of
45    /// 64*f64::EPSILON times the largest absolute referenced coordinate
46    /// (at least one) is added. Outside views add a relative depth guard of
47    /// 1e-12 times the longest mesh side. Larger values only retain more faces.
48    pub tolerance: f64,
49    /// Outside-view pixel width in world units. Zero (default) selects
50    /// longest referenced bounding-box side / 128. Positive values select
51    /// ceil(2*side / pixel_size) pixels, at least one and at most 2048;
52    /// requests above 2048 are invalid. Actual pixel width is 2*side / resolution.
53    /// Coarser pixels may retain more uncertain geometry. Ignored for finite views.
54    pub pixel_size: f64,
55}
56impl Default for HiddenOptions<'_> {
57    fn default() -> Self {
58        Self {
59            views: HiddenViews::Outside,
60            subdivisions: 2,
61            tolerance: 0.0,
62            pixel_size: 0.0,
63        }
64    }
65}
66
67/// Counts by disjoint removal reason. Not in C++ meshoptimizer.
68#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
69#[non_exhaustive]
70pub struct HiddenReport {
71    /// Number of input triangles.
72    pub input_triangles: usize,
73    /// Number of retained triangles.
74    pub output_triangles: usize,
75    /// Later exact position duplicates with the same cyclic winding.
76    pub duplicate: usize,
77    /// Occluded representatives with an exact opposite-wound counterpart.
78    /// Both orientations are tested; exposed back-to-back walls are retained.
79    pub enclosed_back_to_back: usize,
80    /// Other triangles with every requested sample occluded in every view.
81    pub occluded: usize,
82}
83impl HiddenReport {
84    /// Total triangles removed.
85    pub const fn removed(&self) -> usize {
86        self.duplicate + self.enclosed_back_to_back + self.occluded
87    }
88    /// Written index count.
89    pub const fn index_count(&self) -> usize {
90        self.output_triangles * 3
91    }
92}
93
94/// Filtered mesh in original triangle order. Not in C++ meshoptimizer.
95#[derive(Clone, Debug, Default, PartialEq, Eq)]
96#[non_exhaustive]
97pub struct VisibleMeshGeneric<I: crate::Index = u32> {
98    /// Original indices of retained triangles; positions are unchanged.
99    pub indices: Vec<I>,
100    /// Disjoint removal counts.
101    pub report: HiddenReport,
102}
103
104/// Remove hidden triangles using deterministic software item buffers (outside
105/// views) or BVH ray casts (finite viewpoints). Not in C++ meshoptimizer.
106///
107/// Outside views use 26 orthographic directions and an 8x8 tiled depth/item
108/// buffer. Fixed-point edges certify only fully covered pixels; bounded unions
109/// sharing original edges may jointly cover a pixel. Depth bounds cover each cell.
110/// Outward triangle rectangles query those bounds. An uncertain pixel retains
111/// the triangle, including subpixel and edge-on geometry. At the requested
112/// pixel size, every triangle visible over at least one pixel-area in any tested
113/// direction is kept; in fact any visible projected portion is retained under
114/// these coverage bounds. The existing lattice-sample guarantee also holds.
115/// Raster-hidden candidates additionally run the original BVH sample checks:
116/// floating-point shared-edge misses can restore faces, never remove more.
117/// Exact same-winding duplicates retain only their earliest copy, independently
118/// of visibility. Signed zeros match. Degenerate triangles otherwise stay.
119///
120/// Finite views retain a triangle if any barycentric lattice sample or centroid
121/// has an unobstructed segment to any camera. Near contacts (within tolerance
122/// plus numerical guard), coplanar contacts and viewpoint endpoints do not
123/// occlude. Occluders are always the original opaque two-sided mesh.
124///
125/// Views between tested directions, transparency, motion, topology and newly
126/// exposed geometry after filtering are outside this contract. Predicates use
127/// ordinary f64 on finite f32 input, not adaptive exact arithmetic. Resting
128/// surfaces may remain visible from below: restrict finite viewpoints to the
129/// accessible region when appropriate.
130///
131/// Raster work is O(n log n + views * (n + rasterized rectangle area)), with
132/// resolution bounded by 2048. Compatibility and finite-view BVH queries are
133/// data-dependent and worst-case quadratic. Storage and work are fallibly charged to Workspace.
134/// The implementation is serial even with `parallel`, giving identical results
135/// in every thread pool; no extra feature is needed to use this API.
136///
137/// ```
138/// use meshoptimizer_rs::{remove_hidden_triangles, HiddenOptions, Positions, Workspace};
139/// let p = [[0.,0.,0.], [1.,0.,0.], [0.,1.,0.]];
140/// let mesh = remove_hidden_triangles(&[0,1,2, 1,2,0], Positions::from_packed(&p),
141///     HiddenOptions::default(), &mut Workspace::default())?;
142/// assert_eq!(mesh.indices, [0,1,2]);
143/// assert_eq!(mesh.report.duplicate, 1);
144/// # Ok::<(), meshoptimizer_rs::Error>(())
145/// ```
146///
147/// # Errors
148/// `InvalidTopology` for an incomplete triangle, `IndexOutOfBounds` for an
149/// invalid index, `NumericalFailure` for a non-finite referenced position,
150/// `InvalidParameter` for invalid options/views, and the usual `SizeOverflow`,
151/// `LimitExceeded` or `AllocationFailed`. No partial result is returned.
152#[inline]
153pub fn remove_hidden_triangles_generic<I: crate::Index>(
154    indices: &[I],
155    positions: Positions<'_>,
156    options: HiddenOptions<'_>,
157    workspace: &mut Workspace,
158) -> Result<VisibleMeshGeneric<I>, Error> {
159    I::with_input(indices, workspace, |indices, workspace| {
160        remove_hidden_triangles_u32(indices, positions, options, workspace)
161            .and_then(|value| crate::index::Convert::<I>::convert(value, workspace))
162    })
163}
164
165fn remove_hidden_triangles_u32(
166    indices: &[u32],
167    positions: Positions<'_>,
168    options: HiddenOptions<'_>,
169    workspace: &mut Workspace,
170) -> Result<VisibleMeshGeneric, Error> {
171    let mut work = workspace.begin();
172    let result = (|| {
173        let mut budget = Budget::new(workspace);
174        let (keep, report) = plan(indices, positions, options, &mut budget, &mut work)?;
175        work.add(indices.len())?;
176        let mut out = budget.reserved(report.index_count())?;
177        for (t, &k) in indices.as_chunks::<3>().0.iter().zip(&keep) {
178            if k {
179                out.extend_from_slice(t);
180            }
181        }
182        Ok(VisibleMeshGeneric {
183            indices: out,
184            report,
185        })
186    })();
187    workspace.finish(&work);
188    result
189}
190
191/// [`remove_hidden_triangles`] into caller storage. Not in C++ meshoptimizer.
192/// At most `indices.len()` entries are written. Every error leaves the entire
193/// destination unchanged; success writes [`HiddenReport::index_count`] entries
194/// and preserves the tail. Options, sampling and errors are identical to the
195/// owned form, with `BufferTooSmall` when the retained indices do not fit.
196#[inline]
197pub fn remove_hidden_triangles_into_generic<I: crate::Index>(
198    destination: &mut [I],
199    indices: &[I],
200    positions: Positions<'_>,
201    options: HiddenOptions<'_>,
202    workspace: &mut Workspace,
203) -> Result<HiddenReport, Error> {
204    I::with_input(indices, workspace, |indices, workspace| {
205        I::with_mut(destination, workspace, |destination, workspace| {
206            remove_hidden_triangles_into_u32(destination, indices, positions, options, workspace)
207        })
208    })
209}
210
211fn remove_hidden_triangles_into_u32(
212    destination: &mut [u32],
213    indices: &[u32],
214    positions: Positions<'_>,
215    options: HiddenOptions<'_>,
216    workspace: &mut Workspace,
217) -> Result<HiddenReport, Error> {
218    let mut work = workspace.begin();
219    let result = (|| {
220        let mut budget = Budget::new(workspace);
221        let (keep, report) = plan(indices, positions, options, &mut budget, &mut work)?;
222        if destination.len() < report.index_count() {
223            return Err(Error::BufferTooSmall);
224        }
225        work.add(indices.len())?;
226        let mut cursor = 0;
227        for (t, &k) in indices.as_chunks::<3>().0.iter().zip(&keep) {
228            if k {
229                destination[cursor..cursor + 3].copy_from_slice(t);
230                cursor += 3;
231            }
232        }
233        Ok(report)
234    })();
235    workspace.finish(&work);
236    result
237}
238
239fn sub(a: Point, b: Point) -> Point {
240    core::array::from_fn(|k| a[k] - b[k])
241}
242fn dot(a: Point, b: Point) -> f64 {
243    (a[0] * b[0] + a[1] * b[1]) + a[2] * b[2]
244}
245fn cross(a: Point, b: Point) -> Point {
246    [
247        a[1] * b[2] - a[2] * b[1],
248        a[2] * b[0] - a[0] * b[2],
249        a[0] * b[1] - a[1] * b[0],
250    ]
251}
252fn point(p: [f32; 3]) -> Point {
253    p.map(f64::from)
254}
255fn finite(p: [f32; 3]) -> bool {
256    p.iter().all(|x| x.is_finite())
257}
258
259#[derive(Clone, Copy)]
260struct Triangle {
261    p: [Point; 3],
262    id: usize,
263}
264#[derive(Clone, Copy)]
265struct Face {
266    key: [[u32; 3]; 3],
267    reverse: bool,
268    id: usize,
269}
270#[derive(Clone, Copy)]
271struct Node {
272    min: Point,
273    max: Point,
274    start: usize,
275    count: usize,
276    end: usize,
277}
278
279fn views(options: HiddenOptions<'_>, work: &mut Work) -> Result<usize, Error> {
280    if !(1..=64).contains(&options.subdivisions)
281        || !options.tolerance.is_finite()
282        || options.tolerance < 0.0
283        || !options.pixel_size.is_finite()
284        || options.pixel_size < 0.0
285    {
286        return Err(Error::InvalidParameter);
287    }
288    match options.views {
289        HiddenViews::Outside => Ok(26),
290        HiddenViews::Points(p) => {
291            if p.is_empty() {
292                return Err(Error::InvalidParameter);
293            }
294            work.add(p.len())?;
295            if !p.iter().copied().all(finite) {
296                return Err(Error::InvalidParameter);
297            }
298            Ok(p.len())
299        }
300        HiddenViews::Bounds { min, max } => {
301            if !finite(min) || !finite(max) || (0..3).any(|k| min[k] > max[k]) {
302                return Err(Error::InvalidParameter);
303            }
304            Ok(9)
305        }
306    }
307}
308fn direction(views: HiddenViews<'_>, view: usize, sample: Point) -> (Point, f64) {
309    let (d, outside) = match views {
310        HiddenViews::Outside => {
311            let code = if view < 13 { view } else { view + 1 };
312            let component = |v: usize| [-1.0, 0.0, 1.0][v % 3];
313            (
314                [component(code / 9), component(code / 3), component(code)],
315                true,
316            )
317        }
318        HiddenViews::Points(p) => (sub(point(p[view]), sample), false),
319        HiddenViews::Bounds { min, max } => {
320            let p = core::array::from_fn(|k| {
321                if view == 8 {
322                    (f64::from(min[k]) + f64::from(max[k])) * 0.5
323                } else if view & (1 << k) == 0 {
324                    f64::from(min[k])
325                } else {
326                    f64::from(max[k])
327                }
328            });
329            (sub(p, sample), false)
330        }
331    };
332    let length = libm::sqrt(dot(d, d));
333    if length == 0.0 {
334        return ([0.; 3], 0.0);
335    }
336    (
337        d.map(|x| x / length),
338        if outside { f64::INFINITY } else { length },
339    )
340}
341
342fn plan(
343    indices: &[u32],
344    positions: Positions<'_>,
345    options: HiddenOptions<'_>,
346    budget: &mut Budget<'_>,
347    work: &mut Work,
348) -> Result<(Vec<bool>, HiddenReport), Error> {
349    if !indices.len().is_multiple_of(3) {
350        return Err(Error::InvalidTopology);
351    }
352    let view_count = views(options, work)?;
353    let n = indices.len() / 3;
354    work.add(n)?;
355    let mut triangles = budget.reserved::<Triangle>(n)?;
356    let mut scale = 1.0_f64;
357    for (id, t) in indices.as_chunks::<3>().0.iter().enumerate() {
358        let mut p = [[0.; 3]; 3];
359        for k in 0..3 {
360            let vertex = usize::try_from(t[k]).map_err(|_| Error::SizeOverflow)?;
361            let v = positions.get(vertex).ok_or(Error::IndexOutOfBounds)?;
362            if !finite(v) {
363                return Err(Error::NumericalFailure);
364            }
365            p[k] = point(v);
366            for x in p[k] {
367                scale = scale.max(x.abs());
368            }
369        }
370        triangles.push(Triangle { p, id });
371    }
372    work.add(n.checked_mul(3).ok_or(Error::SizeOverflow)?)?;
373    work.add(sort_work(n)?)?;
374    let mut keep = budget.filled(n, true)?;
375    let mut paired = budget.filled(n, false)?;
376    let mut faces = budget.reserved::<Face>(n)?;
377    for t in &triangles {
378        // Coordinates originated as finite f32; this narrowing is exact.
379        let p =
380            t.p.map(|v| v.map(|x| if x == 0.0 { 0 } else { (x as f32).to_bits() }));
381        let rotate = |p: [[u32; 3]; 3]| p.min([p[1], p[2], p[0]]).min([p[2], p[0], p[1]]);
382        let a = rotate(p);
383        let b = rotate([p[0], p[2], p[1]]);
384        faces.push(Face {
385            key: a.min(b),
386            reverse: b < a,
387            id: t.id,
388        });
389    }
390    faces.sort_unstable_by_key(|f| (f.key, f.reverse, f.id));
391    let mut report = HiddenReport {
392        input_triangles: n,
393        ..HiddenReport::default()
394    };
395    work.add(n)?;
396    let mut first: Option<Face> = None;
397    // Two orientation representatives per position class, found in one scan.
398    let mut opposite: Option<Face> = None;
399    for f in &faces {
400        if let Some(a) = first.filter(|a| a.key == f.key) {
401            if a.reverse == f.reverse {
402                keep[f.id] = false;
403                report.duplicate += 1;
404            } else if let Some(b) = opposite {
405                keep[f.id] = false;
406                report.duplicate += 1;
407                paired[b.id] = true;
408            } else {
409                paired[a.id] = true;
410                paired[f.id] = true;
411                opposite = Some(*f);
412            }
413        } else {
414            first = Some(*f);
415            opposite = None;
416        }
417    }
418    budget.release(faces);
419    let epsilon = options.tolerance + 64.0 * f64::EPSILON * scale;
420    if matches!(options.views, HiddenViews::Outside) {
421        outside_visibility(
422            &mut triangles,
423            &mut keep,
424            &paired,
425            options,
426            epsilon,
427            budget,
428            work,
429        )?;
430        work.add(n.checked_mul(2).ok_or(Error::SizeOverflow)?)?;
431        for t in &triangles {
432            if keep[t.id] {
433                continue;
434            }
435            // Duplicates were counted before visibility; classify only representatives.
436            if paired[t.id] {
437                report.enclosed_back_to_back += 1;
438            }
439        }
440        report.occluded =
441            keep.iter().filter(|&&k| !k).count() - report.duplicate - report.enclosed_back_to_back;
442    } else {
443        finite_visibility(
444            &mut triangles,
445            &mut keep,
446            &paired,
447            &mut report,
448            options,
449            view_count,
450            epsilon,
451            budget,
452            work,
453        )?;
454    }
455    report.output_triangles = n - report.removed();
456    budget.release(paired);
457    budget.release(triangles);
458    Ok((keep, report))
459}
460
461fn build(
462    triangles: &mut [Triangle],
463    start: usize,
464    nodes: &mut Vec<Node>,
465    work: &mut Work,
466) -> Result<(), Error> {
467    work.add(triangles.len())?;
468    let mut min = [f64::INFINITY; 3];
469    let mut max = [f64::NEG_INFINITY; 3];
470    for t in triangles.iter() {
471        for p in t.p {
472            for k in 0..3 {
473                min[k] = min[k].min(p[k]);
474                max[k] = max[k].max(p[k]);
475            }
476        }
477    }
478    let at = nodes.len();
479    nodes.push(Node {
480        min,
481        max,
482        start,
483        count: triangles.len(),
484        end: 0,
485    });
486    if triangles.len() > 4 {
487        let mut axis = 0;
488        for k in 1..3 {
489            if max[k] - min[k] > max[axis] - min[axis] {
490                axis = k;
491            }
492        }
493        work.add(sort_work(triangles.len())?)?;
494        let middle = triangles.len() / 2;
495        triangles.select_nth_unstable_by(middle, |a, b| {
496            let centroid = |t: &Triangle| (t.p[0][axis] + t.p[1][axis]) + t.p[2][axis];
497            centroid(a).total_cmp(&centroid(b)).then(a.id.cmp(&b.id))
498        });
499        let (a, b) = triangles.split_at_mut(middle);
500        build(a, start, nodes, work)?;
501        build(b, start + middle, nodes, work)?;
502        nodes[at].count = 0;
503    }
504    nodes[at].end = nodes.len();
505    Ok(())
506}
507fn box_hit(node: &Node, origin: Point, d: Point, max_t: f64, epsilon: f64) -> bool {
508    let mut lo = epsilon;
509    let mut hi = max_t - epsilon;
510    for k in 0..3 {
511        if d[k] == 0.0 {
512            if origin[k] < node.min[k] - epsilon || origin[k] > node.max[k] + epsilon {
513                return false;
514            }
515        } else {
516            let a = (node.min[k] - epsilon - origin[k]) / d[k];
517            let b = (node.max[k] + epsilon - origin[k]) / d[k];
518            lo = lo.max(a.min(b));
519            hi = hi.min(a.max(b));
520            if lo > hi {
521                return false;
522            }
523        }
524    }
525    true
526}
527// Inclusive barycentrics are essential at shared edges. Parallel rays and
528// hits outside the triangle are rejected. Predicates use ordinary f64.
529fn hit(t: &Triangle, o: Point, d: Point, max: f64, epsilon: f64) -> bool {
530    let e1 = sub(t.p[1], t.p[0]);
531    let e2 = sub(t.p[2], t.p[0]);
532    let h = cross(d, e2);
533    let determinant = dot(e1, h);
534    if determinant == 0.0 {
535        return false;
536    }
537    let q = sub(o, t.p[0]);
538    let u = dot(q, h) / determinant;
539    let r = cross(q, e1);
540    let v = dot(d, r) / determinant;
541    let distance = dot(e2, r) / determinant;
542    u >= 0.0 && v >= 0.0 && u + v <= 1.0 && distance > epsilon && distance < max - epsilon
543}
544#[derive(Clone, Copy)]
545struct Ray {
546    origin: Point,
547    direction: Point,
548    distance: f64,
549    epsilon: f64,
550}
551fn blocked(
552    ray: Ray,
553    id: usize,
554    triangles: &[Triangle],
555    nodes: &[Node],
556    witness: &mut [Option<(usize, usize)>; 4],
557    work: &mut Work,
558) -> Result<bool, Error> {
559    let Ray {
560        origin: o,
561        direction: d,
562        distance: max,
563        epsilon,
564    } = ray;
565    for slot in 0..witness.len() {
566        let Some((triangle, leaf)) = witness[slot] else {
567            continue;
568        };
569        work.add(2)?;
570        let t = &triangles[triangle];
571        // The same hit and box predicates as the traversal below. Every
572        // ancestor encloses this leaf: monotone floating-point subtraction
573        // and division make its slab interval a superset of the leaf's.
574        // Thus a successful leaf witness proves the original traversal would
575        // return true too, including shared-edge rounding behavior.
576        if t.id != id && hit(t, o, d, max, epsilon) && box_hit(&nodes[leaf], o, d, max, epsilon) {
577            witness.swap(0, slot);
578            return Ok(true);
579        }
580    }
581    let mut at = 0;
582    while at < nodes.len() {
583        work.add(1)?;
584        let node = &nodes[at];
585        if !box_hit(node, o, d, max, epsilon) {
586            at = node.end;
587            continue;
588        }
589        for (offset, t) in triangles[node.start..node.start + node.count]
590            .iter()
591            .enumerate()
592        {
593            work.add(1)?;
594            if t.id != id && hit(t, o, d, max, epsilon) {
595                witness.rotate_right(1);
596                witness[0] = Some((node.start + offset, at));
597                return Ok(true);
598            }
599        }
600        at += 1;
601    }
602    Ok(false)
603}
604
605#[allow(clippy::too_many_arguments)]
606fn finite_visibility(
607    triangles: &mut [Triangle],
608    keep: &mut [bool],
609    paired: &[bool],
610    report: &mut HiddenReport,
611    options: HiddenOptions<'_>,
612    view_count: usize,
613    epsilon: f64,
614    budget: &mut Budget<'_>,
615    work: &mut Work,
616) -> Result<(), Error> {
617    let n = triangles.len();
618    let cap = n.checked_mul(2).ok_or(Error::SizeOverflow)?;
619    work.add(cap)?;
620    let mut nodes = budget.reserved::<Node>(cap)?;
621    if n != 0 {
622        build(triangles, 0, &mut nodes, work)?;
623    }
624    let s = options.subdivisions;
625    // Four nearby blockers avoid alternating BVH searches around wall seams.
626    let mut witnesses = budget.filled(view_count, [None; 4])?;
627    work.add(26)?;
628    // Outside directions do not depend on the sample. Preserve the original
629    // normalization and reuse it rather than repeating sqrt at every sample.
630    let outside =
631        core::array::from_fn::<_, 26, _>(|view| direction(HiddenViews::Outside, view, [0.; 3]));
632    for t in triangles.iter() {
633        if !keep[t.id] {
634            continue;
635        }
636        let normal = cross(sub(t.p[1], t.p[0]), sub(t.p[2], t.p[0]));
637        if dot(normal, normal) == 0.0 {
638            continue;
639        }
640        let mut visible = false;
641        'samples: for row in 0..=s + 1 {
642            let width = if row == s + 1 { 0 } else { s - row };
643            for col in 0..=width {
644                work.add(1)?;
645                let (u, v) = if row == s + 1 {
646                    (1.0 / 3.0, 1.0 / 3.0)
647                } else {
648                    (f64::from(row) / f64::from(s), f64::from(col) / f64::from(s))
649                };
650                let sample = core::array::from_fn(|k| {
651                    t.p[0][k] * (1.0 - u - v) + t.p[1][k] * u + t.p[2][k] * v
652                });
653                for (view, witness) in witnesses.iter_mut().enumerate() {
654                    work.add(1)?;
655                    let (d, distance) = if matches!(options.views, HiddenViews::Outside) {
656                        outside[view]
657                    } else {
658                        direction(options.views, view, sample)
659                    };
660                    if !blocked(
661                        Ray {
662                            origin: sample,
663                            direction: d,
664                            distance,
665                            epsilon,
666                        },
667                        t.id,
668                        triangles,
669                        &nodes,
670                        witness,
671                        work,
672                    )? {
673                        visible = true;
674                        break 'samples;
675                    }
676                }
677            }
678        }
679        if !visible {
680            keep[t.id] = false;
681            if paired[t.id] {
682                report.enclosed_back_to_back += 1;
683            } else {
684                report.occluded += 1;
685            }
686        }
687    }
688    budget.release(witnesses);
689    budget.release(nodes);
690    Ok(())
691}
692
693// Fixed-point coverage is deliberately inward for occluders. A pixel can
694// certify occlusion only when a triangle (or a bounded adjacent union) covers its
695// entire square. Queries use outward bounding rectangles and maximum depth.
696// Thus quantization, subpixel slivers and incomplete cells can only retain.
697const SUBPIXEL: i64 = 256;
698const TILE: usize = 8;
699
700#[derive(Clone, Copy)]
701struct RasterGrid {
702    size: usize,
703    cells: usize,
704    margin: i64,
705}
706impl RasterGrid {
707    fn new(size: usize) -> Result<Self, Error> {
708        if !(1..=2048).contains(&size) {
709            return Err(Error::InvalidParameter);
710        }
711        let margin = i64::try_from(size)
712            .ok()
713            .and_then(|n| n.checked_mul(SUBPIXEL))
714            .and_then(|n| n.checked_mul(8))
715            .and_then(|n| n.checked_add(16))
716            .ok_or(Error::SizeOverflow)?;
717        let cells = size
718            .div_ceil(TILE)
719            .checked_mul(size.div_ceil(TILE))
720            .and_then(|n| n.checked_mul(TILE * TILE))
721            .ok_or(Error::SizeOverflow)?;
722        Ok(Self {
723            size,
724            cells,
725            margin,
726        })
727    }
728    fn subpixel(self, cell: usize) -> i64 {
729        // Only raster loop coordinates call this: cell < size <= 2048.
730        // The cast and product are exact, with result below 2^19.
731        cell as i64 * SUBPIXEL
732    }
733}
734#[derive(Clone, Copy)]
735struct Projection {
736    center: Point,
737    u: Point,
738    v: Point,
739    d: Point,
740    scale: f64,
741    grid: RasterGrid,
742}
743#[derive(Clone, Copy)]
744struct Projected {
745    xy: [[i64; 2]; 3],
746    lo: f64,
747    hi: f64,
748    plane: [f64; 3],
749    depths: [f64; 3],
750}
751// Projected vertices and cell corners lie in [0, 2048*256]. Each
752// difference is at most 2^19 and each determinant at most 2^39, so all
753// subtraction, multiplication, sign adjustment and abs operations fit i64.
754fn edge(a: [i64; 2], b: [i64; 2], p: [i64; 2]) -> i64 {
755    (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])
756}
757impl Projected {
758    fn depth_bounds(&self, x: usize, y: usize) -> (f64, f64) {
759        let [a, b, c] = self.plane;
760        if !c.is_finite() {
761            return self.clipped_depth(x, y);
762        }
763        let center = a * (x as f64 * 256.0 + 128.0) + b * (y as f64 * 256.0 + 128.0) + c;
764        // 128 subpixels to the cell corner + 2 for vertex quantization.
765        // At any true projected triangle point the affine quantized plane
766        // differs from the true depth by <= |a|+|b| (barycentric argument).
767        let radius = (a.abs() + b.abs()) * 130.0;
768        (self.lo.max(center - radius), self.hi.min(center + radius))
769    }
770    fn clipped_depth(&self, x: usize, y: usize) -> (f64, f64) {
771        // Edge-on triangles have no screen-space depth plane. Clip their
772        // original depth-carrying polygon to an outward-expanded pixel;
773        // global triangle depth would falsely expose enclosed edge-on faces.
774        let mut polygon = [[0.; 3]; 12];
775        for (k, p) in polygon[..3].iter_mut().enumerate() {
776            *p = [self.xy[k][0] as f64, self.xy[k][1] as f64, self.depths[k]];
777        }
778        let mut count = 3;
779        for (axis, bound, sign) in [
780            (0, x as f64 * 256.0 - 2.0, 1.0),
781            (0, (x + 1) as f64 * 256.0 + 2.0, -1.0),
782            (1, y as f64 * 256.0 - 2.0, 1.0),
783            (1, (y + 1) as f64 * 256.0 + 2.0, -1.0),
784        ] {
785            if count == 0 {
786                break;
787            }
788            let mut out = [[0.; 3]; 12];
789            let mut n = 0;
790            let mut prev = polygon[count - 1];
791            for &cur in &polygon[..count] {
792                let a = (prev[axis] - bound) * sign >= 0.0;
793                let b = (cur[axis] - bound) * sign >= 0.0;
794                if a != b {
795                    let t = (bound - prev[axis]) / (cur[axis] - prev[axis]);
796                    out[n] = core::array::from_fn(|k| prev[k] + (cur[k] - prev[k]) * t);
797                    n += 1;
798                }
799                if b {
800                    out[n] = cur;
801                    n += 1;
802                }
803                prev = cur;
804            }
805            polygon = out;
806            count = n;
807        }
808        polygon[..count]
809            .iter()
810            .fold((f64::INFINITY, f64::NEG_INFINITY), |(lo, hi), p| {
811                (lo.min(p[2]), hi.max(p[2]))
812            })
813    }
814    fn overlaps(&self, x: usize, y: usize, grid: RasterGrid) -> bool {
815        let sign = edge(self.xy[0], self.xy[1], self.xy[2]).signum();
816        if sign == 0 {
817            return true;
818        }
819        let x = grid.subpixel(x);
820        let y = grid.subpixel(y);
821        let margin = grid.margin;
822        for k in 0..3 {
823            let a = self.xy[k];
824            let b = self.xy[(k + 1) % 3];
825            let ex = b[0] - a[0];
826            let ey = b[1] - a[1];
827            let corner = [
828                if -ey * sign > 0 { x + SUBPIXEL } else { x },
829                if ex * sign > 0 { y + SUBPIXEL } else { y },
830            ];
831            if edge(a, b, corner) * sign < -margin {
832                return false;
833            }
834        }
835        true
836    }
837}
838impl Projection {
839    fn project(&self, t: &Triangle) -> Projected {
840        let mut lo = f64::INFINITY;
841        let mut hi = f64::NEG_INFINITY;
842        let mut depths = [0.; 3];
843        let mut vertex = 0;
844        let xy = t.p.map(|p| {
845            let p = sub(p, self.center);
846            let z = dot(p, self.d);
847            lo = lo.min(z);
848            hi = hi.max(z);
849            depths[vertex] = z;
850            vertex += 1;
851            [self.u, self.v].map(|axis| {
852                let x = dot(p, axis) * self.scale + self.grid.size as f64 * 128.0;
853                // Finite normalized coordinates and size <=2048 cannot wrap.
854                libm::floor(x.clamp(0.0, self.grid.size as f64 * 256.0)) as i64
855            })
856        });
857        let dx1 = (xy[1][0] - xy[0][0]) as f64;
858        let dy1 = (xy[1][1] - xy[0][1]) as f64;
859        let dx2 = (xy[2][0] - xy[0][0]) as f64;
860        let dy2 = (xy[2][1] - xy[0][1]) as f64;
861        let area = dx1 * dy2 - dy1 * dx2;
862        let plane = if area == 0.0 {
863            [0., 0., f64::NAN]
864        } else {
865            let a = ((depths[1] - depths[0]) * dy2 - (depths[2] - depths[0]) * dy1) / area;
866            let b = (dx1 * (depths[2] - depths[0]) - dx2 * (depths[1] - depths[0])) / area;
867            [a, b, depths[0] - a * xy[0][0] as f64 - b * xy[0][1] as f64]
868        };
869        Projected {
870            xy,
871            lo,
872            hi,
873            plane,
874            depths,
875        }
876    }
877    fn rectangle(&self, p: &Projected) -> [usize; 4] {
878        let bounds = |axis: usize| {
879            let [a, b, c] = p.xy.map(|p| p[axis]);
880            let lo = a.min(b).min(c);
881            let hi = a.max(b).max(c);
882            // One subpixel covers floor quantization and projection roundoff.
883            // project() clamps vertices to [0, size*256], size <= 2048.
884            // Expanded nonnegative pixel coordinates are <= 2048 and fit usize.
885            let lo = ((lo - 1).max(0) / SUBPIXEL) as usize;
886            let hi = (((hi + 1) / SUBPIXEL) as usize).min(self.grid.size - 1);
887            (lo, hi)
888        };
889        let (x0, x1) = bounds(0);
890        let (y0, y1) = bounds(1);
891        [x0, y0, x1, y1]
892    }
893    fn covered(&self, p: &Projected, cell: [usize; 2], skip: usize) -> bool {
894        let sign = edge(p.xy[0], p.xy[1], p.xy[2]).signum();
895        if sign == 0 {
896            return false;
897        }
898        // Each rounded vertex differs from its real projection by <= 1
899        // subpixel. The edge determinant error at a cell corner is less
900        // than 8*grid_width + 16 (including f64 projection roundoff).
901        let margin = self.grid.margin;
902        let x = self.grid.subpixel(cell[0]);
903        let y = self.grid.subpixel(cell[1]);
904        for k in 0..3 {
905            if k == skip {
906                continue;
907            }
908            let a = p.xy[k];
909            let b = p.xy[(k + 1) % 3];
910            let ex = b[0] - a[0];
911            let ey = b[1] - a[1];
912            // Minimum affine edge value over the four square corners.
913            let corner = [
914                if -ey * sign < 0 { x + SUBPIXEL } else { x },
915                if ex * sign < 0 { y + SUBPIXEL } else { y },
916            ];
917            if edge(a, b, corner) * sign <= margin {
918                return false;
919            }
920        }
921        true
922    }
923    fn union_covers(
924        &self,
925        triangles: &[Triangle],
926        ids: &[usize],
927        projected: &[Projected],
928        cell: [usize; 2],
929    ) -> bool {
930        // At most eight triangles (24 edges): a fixed-size certificate,
931        // never a scan over mesh triangles. Normalize all edges to CCW.
932        let mut boundary = 0;
933        for (i, &id) in ids.iter().enumerate() {
934            let p = &projected[i];
935            let sign = edge(p.xy[0], p.xy[1], p.xy[2]).signum();
936            for k in 0..3 {
937                let (a, b) = if sign > 0 {
938                    (k, (k + 1) % 3)
939                } else {
940                    ((k + 1) % 3, k)
941                };
942                let mut opposite = 0;
943                let mut same = 0;
944                for (j, &other) in ids.iter().enumerate() {
945                    if i == j {
946                        continue;
947                    }
948                    let q = &projected[j];
949                    let reverse = edge(q.xy[0], q.xy[1], q.xy[2]) < 0;
950                    for e in 0..3 {
951                        let (c, d) = if reverse {
952                            ((e + 1) % 3, e)
953                        } else {
954                            (e, (e + 1) % 3)
955                        };
956                        if triangles[id].p[a] == triangles[other].p[d]
957                            && triangles[id].p[b] == triangles[other].p[c]
958                        {
959                            opposite += 1;
960                        }
961                        if triangles[id].p[a] == triangles[other].p[c]
962                            && triangles[id].p[b] == triangles[other].p[d]
963                        {
964                            same += 1;
965                        }
966                    }
967                }
968                if opposite == 1 && same == 0 {
969                    continue;
970                }
971                boundary += 1;
972                if !self.edge_covers(p.xy[a], p.xy[b], cell) {
973                    return false;
974                }
975            }
976        }
977        // A positive-oriented union whose every external edge strictly
978        // contains the square covers it. Internal original edges cancel;
979        // an internal hole or an incomplete fan fails an external edge.
980        boundary >= 3
981    }
982    fn edge_covers(&self, a: [i64; 2], b: [i64; 2], cell: [usize; 2]) -> bool {
983        let margin = self.grid.margin;
984        let x = self.grid.subpixel(cell[0]);
985        let y = self.grid.subpixel(cell[1]);
986        let corner = [
987            if b[1] > a[1] { x + SUBPIXEL } else { x },
988            if b[0] < a[0] { y + SUBPIXEL } else { y },
989        ];
990        edge(a, b, corner) > margin
991    }
992    fn address(&self, x: usize, y: usize) -> usize {
993        // 8x8 pixel tiles are contiguous, including padded boundary tiles.
994        ((y / TILE) * self.grid.size.div_ceil(TILE) + x / TILE) * TILE * TILE
995            + (y % TILE) * TILE
996            + x % TILE
997    }
998}
999fn outside_visibility(
1000    triangles: &mut [Triangle],
1001    keep: &mut [bool],
1002    paired: &[bool],
1003    options: HiddenOptions<'_>,
1004    epsilon: f64,
1005    budget: &mut Budget<'_>,
1006    work: &mut Work,
1007) -> Result<(), Error> {
1008    if triangles.is_empty() {
1009        return Ok(());
1010    }
1011    work.add(triangles.len())?;
1012    let mut min = [f64::INFINITY; 3];
1013    let mut max = [f64::NEG_INFINITY; 3];
1014    for t in triangles.iter() {
1015        for p in t.p {
1016            for k in 0..3 {
1017                min[k] = min[k].min(p[k]);
1018                max[k] = max[k].max(p[k]);
1019            }
1020        }
1021    }
1022    let side = (0..3).map(|k| max[k] - min[k]).fold(0.0, f64::max);
1023    if side == 0.0 {
1024        return Ok(());
1025    }
1026    let resolution = if options.pixel_size == 0.0 {
1027        256.0
1028    } else {
1029        libm::ceil((2.0 * side) / options.pixel_size).max(1.0)
1030    };
1031    if resolution > 2048.0 {
1032        return Err(Error::InvalidParameter);
1033    }
1034    // Resolution is checked before narrowing and all storage arithmetic.
1035    let size = resolution as usize;
1036    let grid = RasterGrid::new(size)?;
1037    let cells = grid.cells;
1038    // Select possible cell occluders before allocating the raster. Projected
1039    // area never exceeds 3D area, so excluding these tiny faces can only retain.
1040    work.add(triangles.len())?;
1041    let mut occluders = budget.reserved::<usize>(triangles.len())?;
1042    let screen_scale = size as f64 * 128.0 / side;
1043    let threshold = (size as f64 * 256.0 * 8.0 + 16.0) / (screen_scale * screen_scale);
1044    work.add(triangles.len())?;
1045    for t in triangles.iter() {
1046        if !keep[t.id] {
1047            continue;
1048        }
1049        let normal = cross(sub(t.p[1], t.p[0]), sub(t.p[2], t.p[0]));
1050        if dot(normal, normal) > threshold * threshold {
1051            occluders.push(t.id);
1052        }
1053    }
1054    if occluders.is_empty() {
1055        budget.release(occluders);
1056        return Ok(());
1057    }
1058    work.add(
1059        cells
1060            .checked_mul(3)
1061            .and_then(|n| n.checked_add(keep.len()))
1062            .ok_or(Error::SizeOverflow)?,
1063    )?;
1064    let mut depth = budget.filled(cells, f64::NEG_INFINITY)?;
1065    let mut owner = budget.filled(cells, usize::MAX)?;
1066    let mut partial = budget.filled(cells, [usize::MAX; 8])?;
1067    let mut visible = budget.filled(keep.len(), false)?;
1068    let mut remaining = 0;
1069    work.add(triangles.len())?;
1070    for t in triangles.iter() {
1071        if !keep[t.id] {
1072            continue;
1073        }
1074        let normal = cross(sub(t.p[1], t.p[0]), sub(t.p[2], t.p[0]));
1075        if dot(normal, normal) == 0.0 {
1076            visible[t.id] = true;
1077        } else {
1078            remaining += 1;
1079        }
1080    }
1081    let guard = epsilon + side * 1e-12;
1082    for view in 0..26 {
1083        if remaining == 0 {
1084            break;
1085        }
1086        work.add(cells.checked_mul(3).ok_or(Error::SizeOverflow)?)?;
1087        depth.fill(f64::NEG_INFINITY);
1088        owner.fill(usize::MAX);
1089        partial.fill([usize::MAX; 8]);
1090        let (d, _) = direction(HiddenViews::Outside, view, [0.; 3]);
1091        let axis = if d[0].abs() < 0.9 {
1092            [1., 0., 0.]
1093        } else {
1094            [0., 1., 0.]
1095        };
1096        let u = cross(d, axis);
1097        let length = libm::sqrt(dot(u, u));
1098        let u = u.map(|x| x / length);
1099        let projection = Projection {
1100            center: core::array::from_fn(|k| (min[k] + max[k]) * 0.5),
1101            u,
1102            v: cross(d, u),
1103            d,
1104            scale: (size as f64 * 128.0) / side,
1105            grid,
1106        };
1107        work.add(occluders.len())?;
1108        for &id in &occluders {
1109            let t = &triangles[id];
1110            let p = projection.project(t);
1111            let [x0, y0, x1, y1] = projection.rectangle(&p);
1112            // Charge the complete rectangle before touching any of its cells.
1113            work.add(
1114                (x1 - x0 + 1)
1115                    .checked_mul(y1 - y0 + 1)
1116                    .ok_or(Error::SizeOverflow)?,
1117            )?;
1118            for y in y0..=y1 {
1119                for x in x0..=x1 {
1120                    let at = projection.address(x, y);
1121                    if p.hi <= depth[at] {
1122                        continue;
1123                    }
1124                    let mut z = p.depth_bounds(x, y).0;
1125                    let mut covered = projection.covered(&p, [x, y], 3);
1126                    // Small triangles cannot individually cover a pixel. Keeping
1127                    // them out of bounded union certificates only retains more.
1128                    let area = edge(p.xy[0], p.xy[1], p.xy[2]).abs();
1129                    if !covered
1130                        && p.overlaps(x, y, grid)
1131                        && area > (SUBPIXEL * SUBPIXEL / 8).max(grid.margin)
1132                    {
1133                        work.add(8 * 8 * 8 * 9 + 32)?;
1134                        let ids = &mut partial[at];
1135                        let mut ps = [p; 8];
1136                        let mut count = 0;
1137                        for &id in ids.iter() {
1138                            if id == usize::MAX {
1139                                break;
1140                            }
1141                            ps[count] = projection.project(&triangles[id]);
1142                            count += 1;
1143                        }
1144                        let upper = p.depth_bounds(x, y).1;
1145                        let mut insert = count;
1146                        for (j, q) in ps[..count].iter().enumerate() {
1147                            if upper > q.depth_bounds(x, y).1 {
1148                                insert = j;
1149                                break;
1150                            }
1151                        }
1152                        if insert < 8 {
1153                            count = (count + 1).min(8);
1154                            for j in (insert + 1..count).rev() {
1155                                ids[j] = ids[j - 1];
1156                                ps[j] = ps[j - 1];
1157                            }
1158                            ids[insert] = t.id;
1159                            ps[insert] = p;
1160                        }
1161                        z = f64::INFINITY;
1162                        for end in 1..=count {
1163                            z = z.min(ps[end - 1].depth_bounds(x, y).0);
1164                            if z <= depth[at] {
1165                                break;
1166                            }
1167                            if projection.union_covers(triangles, &ids[..end], &ps[..end], [x, y]) {
1168                                covered = true;
1169                                break;
1170                            }
1171                        }
1172                    }
1173                    if covered && z > depth[at] {
1174                        depth[at] = z;
1175                        owner[at] = t.id;
1176                    }
1177                }
1178            }
1179        }
1180        work.add(triangles.len())?;
1181        for t in triangles.iter() {
1182            if !keep[t.id] || visible[t.id] {
1183                continue;
1184            }
1185            let p = projection.project(t);
1186            let [x0, y0, x1, y1] = projection.rectangle(&p);
1187            work.add(
1188                (x1 - x0 + 1)
1189                    .checked_mul(y1 - y0 + 1)
1190                    .ok_or(Error::SizeOverflow)?,
1191            )?;
1192            'query: for y in y0..=y1 {
1193                for x in x0..=x1 {
1194                    let at = projection.address(x, y);
1195                    if p.depth_bounds(x, y).1 != f64::NEG_INFINITY
1196                        && p.overlaps(x, y, grid)
1197                        && (owner[at] == t.id || p.depth_bounds(x, y).1 + guard >= depth[at])
1198                    {
1199                        visible[t.id] = true;
1200                        remaining -= 1;
1201                        break 'query;
1202                    }
1203                }
1204            }
1205        }
1206    }
1207    budget.release(depth);
1208    budget.release(owner);
1209    budget.release(partial);
1210    budget.release(occluders);
1211    if remaining != 0 {
1212        // Preserve the original floating-point sample guarantee as well as
1213        // continuous pixel coverage: legacy rays can miss an exact shared-edge
1214        // intersection. Only raster-hidden candidates need this compatibility
1215        // check; it may restore triangles and can never remove a raster-kept one.
1216        work.add(keep.len())?;
1217        let mut legacy = budget.filled(keep.len(), false)?;
1218        for ((candidate, &k), &v) in legacy.iter_mut().zip(keep.iter()).zip(&visible) {
1219            *candidate = k && !v;
1220        }
1221        let mut ignored = HiddenReport::default();
1222        finite_visibility(
1223            triangles,
1224            &mut legacy,
1225            paired,
1226            &mut ignored,
1227            options,
1228            26,
1229            epsilon,
1230            budget,
1231            work,
1232        )?;
1233        work.add(keep.len())?;
1234        for (v, &legacy) in visible.iter_mut().zip(&legacy) {
1235            *v |= legacy;
1236        }
1237        budget.release(legacy);
1238    }
1239    work.add(keep.len())?;
1240    for (k, v) in keep.iter_mut().zip(&visible) {
1241        *k &= *v;
1242    }
1243    budget.release(visible);
1244    Ok(())
1245}
1246
1247/// The source-compatible u32 entry point; see [`remove_hidden_triangles_generic`] for selectable index widths.
1248#[inline]
1249pub fn remove_hidden_triangles(
1250    indices: &[u32],
1251    positions: Positions<'_>,
1252    options: HiddenOptions<'_>,
1253    workspace: &mut Workspace,
1254) -> Result<VisibleMesh, Error> {
1255    remove_hidden_triangles_generic::<u32>(indices, positions, options, workspace).map(Into::into)
1256}
1257
1258/// The source-compatible u32 entry point; see [`remove_hidden_triangles_into_generic`] for selectable index widths.
1259#[inline]
1260pub fn remove_hidden_triangles_into(
1261    destination: &mut [u32],
1262    indices: &[u32],
1263    positions: Positions<'_>,
1264    options: HiddenOptions<'_>,
1265    workspace: &mut Workspace,
1266) -> Result<HiddenReport, Error> {
1267    remove_hidden_triangles_into_generic::<u32>(destination, indices, positions, options, workspace)
1268}
1269
1270/// The source-compatible u32 form of [`VisibleMeshGeneric`].
1271/// Filtered mesh in original triangle order. Not in C++ meshoptimizer.
1272#[derive(Clone, Debug, Default, PartialEq, Eq)]
1273#[non_exhaustive]
1274pub struct VisibleMesh {
1275    /// Original indices of retained triangles; positions are unchanged.
1276    pub indices: Vec<u32>,
1277    /// Disjoint removal counts.
1278    pub report: HiddenReport,
1279}
1280impl From<VisibleMeshGeneric<u32>> for VisibleMesh {
1281    #[inline]
1282    fn from(value: VisibleMeshGeneric<u32>) -> Self {
1283        Self {
1284            indices: value.indices,
1285            report: value.report,
1286        }
1287    }
1288}
1289
1290impl From<VisibleMesh> for VisibleMeshGeneric<u32> {
1291    #[inline]
1292    fn from(value: VisibleMesh) -> Self {
1293        Self {
1294            indices: value.indices,
1295            report: value.report,
1296        }
1297    }
1298}
1299
1300#[cfg(test)]
1301mod tests {
1302    use super::*;
1303
1304    #[test]
1305    fn cached_witness_matches_full_traversal_and_checks_leaf() -> Result<(), Error> {
1306        let mut ws = Workspace::default();
1307        let mut work = ws.begin();
1308        let mut triangles = Vec::new();
1309        for id in 0..64 {
1310            let x = (id % 8) as f64;
1311            let y = (id / 8) as f64;
1312            triangles.push(Triangle {
1313                p: [[x, y, 1.], [x + 2., y, 1.], [x, y + 2., 1.]],
1314                id,
1315            });
1316        }
1317        let mut nodes = Vec::new();
1318        build(&mut triangles, 0, &mut nodes, &mut work)?;
1319        let mut witness = [None; 4];
1320        let mut cached_hits = 0;
1321        for step in 0..256 {
1322            let origin = [(step % 16) as f64 * 0.5, (step / 16) as f64 * 0.5, 0.];
1323            for view in 0..28 {
1324                let ray = Ray {
1325                    origin,
1326                    direction: if view < 26 {
1327                        direction(HiddenViews::Outside, view, origin).0
1328                    } else if view == 26 {
1329                        [0.1, 0.2, 1.]
1330                    } else {
1331                        [-0.2, 0.1, 1.]
1332                    },
1333                    distance: if step % 2 == 0 { f64::INFINITY } else { 2. },
1334                    epsilon: 1e-12,
1335                };
1336                for id in [usize::MAX, step % 64] {
1337                    let expected = blocked(ray, id, &triangles, &nodes, &mut [None; 4], &mut work)?;
1338                    for _ in 0..2 {
1339                        cached_hits += usize::from(witness[0].is_some() && expected);
1340                        assert_eq!(
1341                            blocked(ray, id, &triangles, &nodes, &mut witness, &mut work)?,
1342                            expected
1343                        );
1344                    }
1345                }
1346            }
1347        }
1348        assert!(cached_hits > 0);
1349        // A triangle hit alone is insufficient: the legacy box predicate must
1350        // also accept. This deliberately inconsistent fixture exercises that guard.
1351        let t = Triangle {
1352            p: [[0., 0., 1.], [2., 0., 1.], [0., 2., 1.]],
1353            id: 0,
1354        };
1355        let node = Node {
1356            min: [10.; 3],
1357            max: [11.; 3],
1358            start: 0,
1359            count: 1,
1360            end: 1,
1361        };
1362        let ray = Ray {
1363            origin: [0.5, 0.5, 0.],
1364            direction: [0., 0., 1.],
1365            distance: f64::INFINITY,
1366            epsilon: 1e-12,
1367        };
1368        assert!(hit(
1369            &t,
1370            ray.origin,
1371            ray.direction,
1372            ray.distance,
1373            ray.epsilon
1374        ));
1375        assert!(!blocked(
1376            ray,
1377            usize::MAX,
1378            &[t],
1379            &[node],
1380            &mut [Some((0, 0)); 4],
1381            &mut work
1382        )?);
1383        Ok(())
1384    }
1385
1386    #[test]
1387    fn raster_size_validation_precedes_arithmetic() {
1388        for size in [0, 2049, i64::MAX as usize, usize::MAX] {
1389            assert!(matches!(
1390                RasterGrid::new(size),
1391                Err(Error::InvalidParameter)
1392            ));
1393        }
1394        for size in [1, 8, 256, 2048] {
1395            let grid = RasterGrid::new(size).unwrap();
1396            assert_eq!(grid.margin, size as i64 * 256 * 8 + 16);
1397            assert_eq!(grid.cells, size.div_ceil(8).pow(2) * 64);
1398            assert_eq!(grid.subpixel(size - 1), (size as i64 - 1) * 256);
1399        }
1400        let bound = 2048 * SUBPIXEL;
1401        assert_eq!(edge([0, 0], [bound, 0], [0, bound]), bound * bound);
1402        assert_eq!(edge([0, 0], [0, bound], [bound, 0]), -bound * bound);
1403    }
1404}