svenstaro / bvh

A fast BVH using SAH in rust
https://docs.rs/bvh
MIT License
225 stars 37 forks source link

Add conservative point queries for bvh #108

Open Azkellas opened 1 week ago

Azkellas commented 1 week ago

I recently implemented a distance point query with a bvh for my crate mesh_to_sdf by trait extending this crate (see https://github.com/Azkellas/mesh_to_sdf/pull/75). This PR is an attempt to upstream the changes and would solve https://github.com/svenstaro/bvh/issues/56.

This PR is different from https://github.com/svenstaro/bvh/pull/43 which only returns shapes with aabb containing the query point. On the contrary, this PR returns a conservative list of candidates, one of which for sure contains the shape that is closest to the query point. This is needed since we can't know for sure if the query point is in the aabb of its closest object.

To do so, we keep track of the best minimum/maximum distance found yet in the tree. For each node we compute the aabb min/max distance from the point (the minimum is 0 if the point is inside). Then we can prune or investigate the subtrees depending on the aabb's min/max compared to the current best min/max.

This means the search visits a subtree and not a single linear branch. It might be interesting to add an approx version following https://github.com/svenstaro/bvh/pull/43 implementation which would be faster and "close enough".

I couldn't implement the nearest_candidate method for FlatBvh. Pre-order no-stack no-recursion tree traversal requires to store the parent index in the node afaik. I didn't want to change the memory layout without talking about it first. This PR is in draft state for this reason.

Testing is a bit rudimentary (and no benchmark) as I did most of it in my crate and haven't ported it yet. Anyway for 100k triangles and 15k queries (in mesh's bounding box) it is 10x faster than brute forcing while being exact.

Waht remains to be done:

Thank you for the work, this crate is very useful.

codecov-commenter commented 3 days ago

:warning: Please install the 'codecov app svg image' to ensure uploads and comments are reliably processed by Codecov.

Codecov Report

Attention: Patch coverage is 65.07937% with 22 lines in your changes missing coverage. Please review.

Project coverage is 56.55%. Comparing base (9e886ed) to head (04957a9). Report is 3 commits behind head on master.

Files Patch % Lines
src/bvh/bvh_node.rs 54.54% 15 Missing :warning:
src/bvh/bvh_impl.rs 66.66% 5 Missing :warning:
src/aabb.rs 92.85% 1 Missing :warning:
src/bounding_hierarchy.rs 0.00% 1 Missing :warning:

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #108 +/- ## ========================================== + Coverage 56.22% 56.55% +0.32% ========================================== Files 12 12 Lines 1028 1091 +63 ========================================== + Hits 578 617 +39 - Misses 450 474 +24 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

svenstaro commented 16 hours ago

Thanks a lot! I will take an in-depth look soon. How do you think this interacts with #98? I think I would like to merge #98 first and I'm almost done with it but I don't want to negate your work. Could you take a look at let me know what you think?