search

svenstaro / bvh

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

improvements #71

Open dbenson24 opened 3 years ago

dbenson24 commented 3 years ago

Thanks for maintaining this crate, I've been integrating it into a game I'm working on in Unity and in doing so I've added/am adding a bunch of things that I needed and was wondering how much of it you might be interested me trying to separate out for a PR. The performance is amazing!

I've been implementing some new query shapes

In addition to those I've also been adding some new methods

I've also defined a C FFI so that it could be used outside of Rust code

My version is also 64bit because I needed the precision

If any of this stuff sounds like something you might be interested in a PR for let me know.

svenstaro commented 3 years ago

I'd certainly appreciate contributions! However, please try to split it up to one PR per shape if you can as that makes reviewing easier.

StarArawn commented 3 years ago

I would be interested in the Add/Remove/Rebuild. Do you have a fork up somewhere I can take a look at?

dbenson24 commented 3 years ago

I will try and get it uploaded in the next day or two. I've pretty heavily edited a few things, a merge back shouldn't be too hard but I haven't prioritized the time for that yet

dbenson24 commented 3 years ago

also I haven't implemented rebuild yet, I know how I want to but my priority is has been on add and remove. Do note that heavy use of add and remove will cause a hefty toll on the locality of the bvh over time. Regardless I'm super happy with the performance of this BVH, currently I'm able to do ~100k raycasts against a bvh with a 100k items in it < 1ms or so

dbenson24 commented 3 years ago

https://github.com/dbenson24/bvh @StarArawn warning that I have done literally nothing to prep it for viewing other than migrating my changes back into a fork of the repo

dbenson24 commented 2 years ago

@svenstaro

So I've continued working on/improving my branch of your BVH as I'm using it for a unity game I'm working on. I've attached a bench run of the 32bit version below. At this point the code has diverged quite a lot from your current version. If you are interested I'm willing to work with you to upstream changes, otherwise I'm considering publishing a fork with the 32/64bit versions + the C FFI bindings. General summary of changes is something like this: Optimize the build function to reduce allocations Merge the centroid calculation with the bucket building process Parallelize build using Rayon Use a SmallVec to back the iterator so that a panic during traversal is impossible New shapes to query the BVH with as listed above Refactored crate structure so that the code is compiled using 32bit and 64bit floats/vectors Ability to add and remove shapes from the BVH dynamically Replaced the optimization strategy with one that adds and removes nodes

I've attached a benchmark below (build is using parallel, it's about 5.5x faster to build the 120k triangle BVH in parallel on my processor (Ryzen 3900x) than it is to build serial. 


test bvh::bvh_impl::bench::bench_build_120k_triangles_bvh                 ... bench:   9,901,670 ns/iter (+/- 1,155,255)
test bvh::bvh_impl::bench::bench_build_12k_triangles_bvh                  ... bench:   1,228,996 ns/iter (+/- 229,373)
test bvh::bvh_impl::bench::bench_build_sponza_bvh                         ... bench:   5,876,435 ns/iter (+/- 945,584)
test bvh::bvh_impl::bench::bench_intersect_12000_triangles_bvh_add        ... bench:       1,423 ns/iter (+/- 36)
test bvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh             ... bench:         169 ns/iter (+/- 6)
test bvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh_add         ... bench:         552 ns/iter (+/- 23)
test bvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh             ... bench:         936 ns/iter (+/- 56)
test bvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh              ... bench:         407 ns/iter (+/- 12)
test bvh::bvh_impl::bench::bench_intersect_sponza_bvh                     ... bench:       1,694 ns/iter (+/- 71)
test bvh::bvh_impl::bench::build_1200_triangles_add                       ... bench:   5,227,095 ns/iter (+/- 604,196)
test bvh::bvh_impl::bench::build_12k_triangles_add                        ... bench:  70,848,200 ns/iter (+/- 5,039,338)
test bvh::iter::bench::bench_intersect_128rays_sponza_iter                ... bench:     212,734 ns/iter (+/- 7,567)
test bvh::iter::bench::bench_intersect_128rays_sponza_vec                 ... bench:     212,620 ns/iter (+/- 5,039)
test bvh::optimization::bench::bench_intersect_120k_after_optimize_00p    ... bench:         906 ns/iter (+/- 11)
test bvh::optimization::bench::bench_intersect_120k_after_optimize_01p    ... bench:         946 ns/iter (+/- 22)
test bvh::optimization::bench::bench_intersect_120k_after_optimize_100p   ... bench:       3,083 ns/iter (+/- 99)
test bvh::optimization::bench::bench_intersect_120k_after_optimize_10p    ... bench:       1,260 ns/iter (+/- 22)
test bvh::optimization::bench::bench_intersect_120k_after_optimize_50p    ... bench:       2,080 ns/iter (+/- 105)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_00p      ... bench:         909 ns/iter (+/- 18)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_01p      ... bench:         946 ns/iter (+/- 13)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_100p     ... bench:       2,069 ns/iter (+/- 135)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_10p      ... bench:       1,194 ns/iter (+/- 25)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_50p      ... bench:       1,723 ns/iter (+/- 151)
test bvh::optimization::bench::bench_intersect_sponza_after_optimize_00p  ... bench:       1,665 ns/iter (+/- 68)
test bvh::optimization::bench::bench_intersect_sponza_after_optimize_01p  ... bench:       1,955 ns/iter (+/- 60)
test bvh::optimization::bench::bench_intersect_sponza_after_optimize_100p ... bench:       6,534 ns/iter (+/- 302)
test bvh::optimization::bench::bench_intersect_sponza_after_optimize_10p  ... bench:       2,697 ns/iter (+/- 133)
test bvh::optimization::bench::bench_intersect_sponza_after_optimize_50p  ... bench:       4,652 ns/iter (+/- 344)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_00p    ... bench:       1,666 ns/iter (+/- 67)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_01p    ... bench:       1,772 ns/iter (+/- 56)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_100p   ... bench:       2,928 ns/iter (+/- 116)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_10p    ... bench:       2,085 ns/iter (+/- 53)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_50p    ... bench:       2,823 ns/iter (+/- 329)
test bvh::optimization::bench::bench_optimize_bvh_120k_00p                ... bench:   1,233,925 ns/iter (+/- 89,743)
test bvh::optimization::bench::bench_optimize_bvh_120k_01p                ... bench:   2,119,880 ns/iter (+/- 144,518)
test bvh::optimization::bench::bench_optimize_bvh_120k_100p               ... bench: 128,740,180 ns/iter (+/- 7,110,781)
test bvh::optimization::bench::bench_optimize_bvh_120k_10p                ... bench:  10,694,650 ns/iter (+/- 647,706)
test bvh::optimization::bench::bench_optimize_bvh_120k_50p                ... bench:  66,261,060 ns/iter (+/- 4,659,825)
test bvh::optimization::bench::bench_randomize_120k_50p                   ... bench:   4,566,690 ns/iter (+/- 1,256,935)
test flat_bvh::bench::bench_build_1200_triangles_flat_bvh                 ... bench:     175,750 ns/iter (+/- 8,817)
test flat_bvh::bench::bench_build_120k_triangles_flat_bvh                 ... bench:  20,378,960 ns/iter (+/- 4,375,637)
test flat_bvh::bench::bench_build_12k_triangles_flat_bvh                  ... bench:   2,041,862 ns/iter (+/- 344,578)
test flat_bvh::bench::bench_flatten_120k_triangles_bvh                    ... bench:  10,427,850 ns/iter (+/- 2,533,459)
test flat_bvh::bench::bench_intersect_1200_triangles_flat_bvh             ... bench:         166 ns/iter (+/- 2)
test flat_bvh::bench::bench_intersect_120k_triangles_flat_bvh             ... bench:         990 ns/iter (+/- 32)
test flat_bvh::bench::bench_intersect_12k_triangles_flat_bvh              ... bench:         411 ns/iter (+/- 5)
test ray::bench::bench_intersects_aabb                                    ... bench:      30,592 ns/iter (+/- 1,403)
test ray::bench::bench_intersects_aabb_branchless                         ... bench:      30,540 ns/iter (+/- 541)
test ray::bench::bench_intersects_aabb_naive                              ... bench:      30,469 ns/iter (+/- 286)
test testbase::bench_intersect_120k_triangles_list                        ... bench:     980,500 ns/iter (+/- 33,570)
test testbase::bench_intersect_120k_triangles_list_aabb                   ... bench:     273,730 ns/iter (+/- 6,580)
test testbase::bench_intersect_sponza_list                                ... bench:     732,835 ns/iter (+/- 17,795)
test testbase::bench_intersect_sponza_list_aabb                           ... bench:     135,343 ns/iter (+/- 3,310)```
svenstaro commented 2 years ago

Holy cow. Yeah it would be absolutely great if you could upstream your work! :)

marstaik commented 1 year ago

I've been implementing some new query shapes

* Sphere

* Capsule

* AABB

* OBB (almost)

* Segment (tbd)

I think it might be a good idea to coordinate on coming up with a new Intersect trait that returns a generic Intersection (so that specific intersection cases can also return whatever extra data they have that is useful) and so that we can make BVH traversal/intersection easy and generic. (I have no idea if you already did this)

Segment seems like Ray with minimum and maximum t-values - which was requested here https://github.com/svenstaro/bvh/issues/66