1use 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#[derive(Clone, Copy, Debug)]
13#[non_exhaustive]
14pub enum HiddenViews<'a> {
15 Outside,
18 Points(&'a [[f32; 3]]),
20 Bounds {
23 min: [f32; 3],
25 max: [f32; 3],
27 },
28}
29
30#[derive(Clone, Copy, Debug)]
32#[non_exhaustive]
33pub struct HiddenOptions<'a> {
34 pub views: HiddenViews<'a>,
36 pub subdivisions: u32,
42 pub tolerance: f64,
49 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
69#[non_exhaustive]
70pub struct HiddenReport {
71 pub input_triangles: usize,
73 pub output_triangles: usize,
75 pub duplicate: usize,
77 pub enclosed_back_to_back: usize,
80 pub occluded: usize,
82}
83impl HiddenReport {
84 pub const fn removed(&self) -> usize {
86 self.duplicate + self.enclosed_back_to_back + self.occluded
87 }
88 pub const fn index_count(&self) -> usize {
90 self.output_triangles * 3
91 }
92}
93
94#[derive(Clone, Debug, Default, PartialEq, Eq)]
96#[non_exhaustive]
97pub struct VisibleMeshGeneric<I: crate::Index = u32> {
98 pub indices: Vec<I>,
100 pub report: HiddenReport,
102}
103
104#[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#[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 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 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 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(¢roid(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}
527fn 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 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 let mut witnesses = budget.filled(view_count, [None; 4])?;
627 work.add(26)?;
628 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
693const 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 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}
751fn 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 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 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 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 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 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 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 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 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 ((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 let size = resolution as usize;
1036 let grid = RasterGrid::new(size)?;
1037 let cells = grid.cells;
1038 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 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 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 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#[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#[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#[derive(Clone, Debug, Default, PartialEq, Eq)]
1273#[non_exhaustive]
1274pub struct VisibleMesh {
1275 pub indices: Vec<u32>,
1277 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 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}