Feature request: all-hits ray casting for TriMesh
- Dominant language
- Rust
- Stars
- 867
- Forks
- 157
- Avg merge
- 7d 13h
- Merged PRs (30d)
- 2
Description
## Problem
`cast_local_ray()` and `cast_local_ray_and_get_normal()` return only the nearest intersection. This is correct for collision detection (parry's primary use case), but several common geometry processing tasks need **all** intersections along a ray:
- **Inside/outside testing** via parity (odd number of hits = inside)
- **Wall thickness measurement** (distance between entry/exit pairs)
- **Hollow shape detection** (4+ hits = walled structure)
- **X-ray style visualization**
Currently, users wanting all hits must either iterate all triangles manually (O(n), losing BVH acceleration) or use `bvh().traverse()` with a custom closure. A first-class `cast_local_ray_all` method would be cleaner and benefit the ecosystem.
## Proposed API
### TriMesh (primary user-facing API)
```rust
impl TriMesh {
/// Returns all ray-mesh intersections, BVH-accelerated.
pub fn cast_local_ray_all(
&self,
ray: &Ray,
max_time_of_impact: Real,
sort: bool,
) -> Vec;
/// World-space variant with explicit mesh transform.
pub fn cast_ray_all(
&self,
m: &Pose,
ray: &Ray,
max_time_of_impact: Real,
sort: bool,
) -> Vec;
}
```
### Bvh (reusable building block)
```rust
impl Bvh {
/// Like cast_ray but collects all leaf hits instead of pruning by best cost.
pub fn cast_ray_all(
&self,
ray: &Ray,
max_time_of_impact: Real,
primitive_check: impl Fn(u32) -> Option,
) -> Vec<(u32, L)>;
}
```
### CompositeShapeRef (intermediate layer)
```rust
impl CompositeShapeRef<'_, S> {
pub fn cast_local_ray_and_get_normal_all(
&self,
ray: &Ray,
max_time_of_impact: Real,
sort: bool,
) -> Vec<(u32, RayIntersection)>;
}
```
## Implementation approach
The core change is a BVH traversal that prunes by AABB miss but does NOT prune by best cost. This reuses the existing `Bvh::leaves()` iterator with a ray-AABB predicate:
```
nearest-hit: prune by AABB miss AND by best_cost -> O(log n)
all-hits: prune by AABB miss only -> O(log n + k)
```
Where k is the number of intersected triangles (typically small: 2-6 for solid/hollow shapes).
The SIMD-accelerated AABB test path (`SimdInvRay`) is used on `f32/dim3/simd-is-enabled` builds, matching the existing `cast_ray` behavior.
## Design decisions
- **`solid` is hardcoded to `false`**: all-hits wants boundary intersections, not an immediate zero-distance "you're inside" result.
- **`max_time_of_impact` boundary is exclusive**: matching `cast_local_ray`'s convention.
- **`sort` parameter**: some use cases (parity testing) don't need sorted results, so sorting is optional.
- **Parity caveat**: rays through shared edges/vertices may produce duplicate hits. This is documented but not deduplicated, as the correct deduplication strategy is application-dependent.
## I have an implementation ready
I have a tested implementation with 18 unit tests and doc-test examples covering:
- Solid box, hollow box (combined mesh), single triangle
- Normal vector and feature ID assertions
- Edge cases: zero-direction ray, ray from inside, diagonal ray, non-unit direction
- Boundary cases: max_toi=0, max_toi=MAX, exact boundary exclusion
- World-space transform with rotation
- Consistency check against existing single-hit results
Happy to open a PR if you're interested.
Contributor guide
Assessment
This issue has not been assessed yet.