dimforge / dimforge/parry

Feature request: all-hits ray casting for TriMesh

Open
#411 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.