- Notifications
You must be signed in to change notification settings - Fork38
A fast BVH using SAH in rust
License
svenstaro/bvh
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
A crate which exports rays, axis-aligned bounding boxes, and binary boundingvolume hierarchies.
This crate can be used for applications which contain intersection computations of rayswith primitives. For this purpose a binary tree BVH (Bounding Volume Hierarchy) is of greatuse if the scene which the ray traverses contains a huge number of primitives. With a BVH theintersection test complexity is reduced from O(n) to O(log2(n)) at the cost of buildingthe BVH once in advance. This technique is especially useful in ray/path tracers. Foruse in a shader this module also exports a flattening procedure, which allows foriterative traversal of the BVH.
It usesrayon by default to parallelize building the BVH.
use bvh::aabb::{Aabb,Bounded};use bvh::bounding_hierarchy::{BHShape,BoundingHierarchy};use bvh::bvh::Bvh;use bvh::ray::Ray;use nalgebra::{Point3,Vector3};let origin =Point3::new(0.0,0.0,0.0);let direction =Vector3::new(1.0,0.0,0.0);let ray =Ray::new(origin, direction);structSphere{position:Point3<f32>,radius:f32,node_index:usize,}implBounded<f32,3>forSphere{fnaabb(&self) ->Aabb<f32,3>{let half_size =Vector3::new(self.radius,self.radius,self.radius);let min =self.position - half_size;let max =self.position + half_size;Aabb::with_bounds(min, max)}}implBHShape<f32,3>forSphere{fnset_bh_node_index(&mutself,index:usize){self.node_index = index;}fnbh_node_index(&self) ->usize{self.node_index}}letmut spheres =Vec::new();for iin0..1000u32{let position =Point3::new(iasf32, iasf32, iasf32);let radius =(i %10)asf32 +1.0; spheres.push(Sphere{position: position,radius: radius,node_index:0,});}let bvh =Bvh::build_par(&mut spheres);let hit_sphere_aabbs = bvh.traverse(&ray,&spheres);
This crate features some manually written SIMD instructions, currently only for thex86_64 architecture.While nalgebra provides us with generic SIMD optimization (and it does a great job for the most part) -some important functions, such as ray-aabb-intersection have been optimized by hand.
The currently optimized intersections for ray-aabb are:Type: f32, Dimension: 2,3,4Type: f64, Dimension: 2,3,4
To enable these optimziations, you must build with thenightly toolchain and enable thesimd flag.
This crate provides BVH updating, which is also called optimization. With BVH optimizationyou can mutate the shapes on which the BVH is built and update the tree accordingly without rebuilding it completely.This method is very useful when there are only very few changes to a huge scene. When the major part of the scene is static,it is faster to update the tree, instead of rebuilding it from scratch.
First of all, optimizing is not helpful if more than half of the scene is not static.This is due to how optimizing takes place:Given a set of indices of all shapes which have changed, the optimize procedure tries to rotate fixed constellationsin search for a better surface area heuristic (SAH) value. This is done recursively from bottom to top while fixing the AABBsin the inner nodes of the BVH. Which is why it is inefficient to update the BVH in comparison to rebuilding, when a lotof shapes have moved.
Another problem with updated BVHs is, that the resulting BVH is not optimal. Assume that the scene is composed of two majorgroups separated by a large gap. When one shape moves from one group to another, the updating procedure will not be able tofind a sequence of bottom-up rotations which inserts the shape deeply into the other branch.
The following benchmarks are run with two different datasets:
- A randomly generated scene with unit sized cubes containing a total of (1200, 12000, and 120000 triangles).
- Sponza, a popular scene for benchmarking graphics engines.
All benchmarks were taken on a Ryzen 3900x.
All benchmarks unless otherwise noted were captured with thesimd feature off.
testtestbase::bench_intersect_120k_triangles_list ...bench:570,717ns/iter (+/-21,689)testtestbase::bench_intersect_sponza_list ...bench:510,683ns/iter (+/-9,525)// simd enabledtesttestbase::bench_intersect_120k_triangles_list ...bench:566,916ns/iter (+/-22,024)testtestbase::bench_intersect_sponza_list ...bench:518,821ns/iter (+/-12,191)
This is the most naive approach to intersecting a scene with a ray. It defines the baseline.
testtestbase::bench_intersect_120k_triangles_list_aabb ...bench:687,660ns/iter (+/-6,850)testtestbase::bench_intersect_sponza_list_aabb ...bench:381,037ns/iter (+/-1,416)// simd enabledtesttestbase::bench_intersect_120k_triangles_list_aabb ...bench:295,810ns/iter (+/-3,309)testtestbase::bench_intersect_sponza_list_aabb ...bench:163,738ns/iter (+/-1,822)
AABB checks are cheap, compared to triangle-intersection algorithms. Therefore, preceeding AABB checksincrease intersection speed by filtering negative results a lot faster.
testflat_bvh::bench::bench_build_1200_triangles_flat_bvh ...bench:242,357ns/iter (+/-1,882)testflat_bvh::bench::bench_build_12k_triangles_flat_bvh ...bench:3,681,965ns/iter (+/-223,716)testflat_bvh::bench::bench_build_120k_triangles_flat_bvh ...bench:46,415,590ns/iter (+/-3,226,404)testbvh::bvh_impl::bench::bench_build_1200_triangles_bvh ...bench:239,473ns/iter (+/-2,456)testbvh::bvh_impl::bench::bench_build_1200_triangles_bvh_rayon ...bench:123,387ns/iter (+/-9,427)testbvh::bvh_impl::bench::bench_build_12k_triangles_bvh ...bench:2,903,150ns/iter (+/-54,318)testbvh::bvh_impl::bench::bench_build_12k_triangles_bvh_rayon ...bench:1,073,300ns/iter (+/-89,530)testbvh::bvh_impl::bench::bench_build_120k_triangles_bvh ...bench:37,390,480ns/iter (+/-2,789,280)testbvh::bvh_impl::bench::bench_build_120k_triangles_bvh_rayon ...bench:8,935,320ns/iter (+/-1,780,231)testbvh::bvh_impl::bench::bench_build_sponza_bvh ...bench:23,828,070ns/iter (+/-1,307,461)testbvh::bvh_impl::bench::bench_build_sponza_bvh_rayon ...bench:4,764,530ns/iter (+/-950,640)
testflat_bvh::bench::bench_flatten_120k_triangles_bvh ...bench:9,806,060ns/iter (+/-1,771,861)
As you can see, building a BVH takes a long time. Building a BVH is only useful if the number of intersections performed on thescene exceeds the build duration. This is the case in applications such as ray and path tracing, where the minimumnumber of intersections is1280 * 720 for an HD image.
testflat_bvh::bench::bench_intersect_1200_triangles_flat_bvh ...bench:144ns/iter (+/-1)testflat_bvh::bench::bench_intersect_12k_triangles_flat_bvh ...bench:370ns/iter (+/-4)testflat_bvh::bench::bench_intersect_120k_triangles_flat_bvh ...bench:866ns/iter (+/-16)testbvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh ...bench:146ns/iter (+/-2)testbvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh ...bench:367ns/iter (+/-5)testbvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh ...bench:853ns/iter (+/-12)testbvh::bvh_impl::bench::bench_intersect_sponza_bvh ...bench:1,381ns/iter (+/-20)testray::ray_impl::bench::bench_intersects_aabb ...bench:4,404ns/iter (+/-17)// simd enabledtestbvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh ...bench:121ns/iter (+/-2)testbvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh ...bench:309ns/iter (+/-3)testbvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh ...bench:749ns/iter (+/-15)testbvh::bvh_impl::bench::bench_intersect_sponza_bvh ...bench:1,216ns/iter (+/-16)testray::ray_impl::bench::bench_intersects_aabb ...bench:2,447ns/iter (+/-18)
These performance measurements show that traversing a BVH is much faster than traversing a list.
The benchmarks for how long it takes to update the scene also contain a randomization process which takes some time.
testbvh::optimization::bench::bench_update_shapes_bvh_120k_00p ...bench:1,057,965ns/iter (+/-76,098)testbvh::optimization::bench::bench_update_shapes_bvh_120k_01p ...bench:2,535,682ns/iter (+/-80,231)testbvh::optimization::bench::bench_update_shapes_bvh_120k_10p ...bench:18,840,970ns/iter (+/-3,432,867)testbvh::optimization::bench::bench_update_shapes_bvh_120k_50p ...bench:76,025,200ns/iter (+/-3,899,770)testbvh::optimization::bench::bench_randomize_120k_50p ...bench:5,361,645ns/iter (+/-436,340)
This is the place where you have to differentiate between rebuilding the tree from scratch or trying to optimize the old one.These tests show the impact of moving around a particular percentage of shapes (10p =>10%).It is important to note that the randomization process here moves triangles around indiscriminately.This will also lead to cases where the BVH would have to be restructured completely.
These intersection tests are grouped by dataset and by the BVH generation method.
_after_optimizeuses a BVH which was kept up to date with calls tooptimize, while_with_rebuilduses the same triangle data as_after_optimize, but constructs a BVH from scratch.
120K Triangles
testbvh::optimization::bench::bench_intersect_120k_after_update_shapes_00p ...bench:855ns/iter (+/-15)testbvh::optimization::bench::bench_intersect_120k_after_update_shapes_01p ...bench:921ns/iter (+/-13)testbvh::optimization::bench::bench_intersect_120k_after_update_shapes_10p ...bench:2,677ns/iter (+/-191)testbvh::optimization::bench::bench_intersect_120k_after_update_shapes_50p ...bench:2,992ns/iter (+/-103)testbvh::optimization::bench::bench_intersect_120k_with_rebuild_00p ...bench:852ns/iter (+/-13)testbvh::optimization::bench::bench_intersect_120k_with_rebuild_01p ...bench:918ns/iter (+/-13)testbvh::optimization::bench::bench_intersect_120k_with_rebuild_10p ...bench:1,920ns/iter (+/-266)testbvh::optimization::bench::bench_intersect_120k_with_rebuild_50p ...bench:2,075ns/iter (+/-318)
Sponza
testbvh::optimization::bench::bench_intersect_sponza_after_update_shapes_00p ...bench:2,023ns/iter (+/-52)testbvh::optimization::bench::bench_intersect_sponza_after_update_shapes_01p ...bench:3,444ns/iter (+/-120)testbvh::optimization::bench::bench_intersect_sponza_after_update_shapes_10p ...bench:16,873ns/iter (+/-2,123)testbvh::optimization::bench::bench_intersect_sponza_after_update_shapes_50p ...bench:9,075ns/iter (+/-486)testbvh::optimization::bench::bench_intersect_sponza_with_rebuild_00p ...bench:1,388ns/iter (+/-46)testbvh::optimization::bench::bench_intersect_sponza_with_rebuild_01p ...bench:1,529ns/iter (+/-102)testbvh::optimization::bench::bench_intersect_sponza_with_rebuild_10p ...bench:1,920ns/iter (+/-120)testbvh::optimization::bench::bench_intersect_sponza_with_rebuild_50p ...bench:2,505ns/iter (+/-88)
This set of tests shows the impact of randomly moving triangles around and producing degenerated trees.The120K Triangles dataset has been updated randomly. TheSponza scene was updated using a methodwhich has a maximum offset distance for shapes. This simulates a more realistic scenario.
We also see that theSponza scene by itself contains some structures which can be tightly wrapped in a BVH.By mowing those structures around we destroy the locality of the triangle groups which leads to more branches in theBVH requiring a check, thus leading to a higher intersection duration.
The benchmark suite uses features from thetest crate and therefore cannot be run on stable rust.Using a nightly toolchain, runcargo bench --features bench.
This project aspires to be fully tested, and that starts with a unit test suite. Usecargo test to run all the tests. The tests automatically run in CI, too. Contributorsare expected to add tests for all new functionality.
This project usesproptest as a secondline of defense against bugs, allowing random instances of certain tests to be tested.These tests run alongside unit-tests.
This project usescargo fuzz asa third line of defense against bugs, meaning that thefuzz/ directory was generatedusingcargo fuzz init. At the moment, there is a single fuzz target, and runningcargo fuzz run fuzz will fuzz until an assertion is violated. The fuzzer automaticallyruns in CI, too.
We recommend you install thejust command runner, toruncommands including:
just lint- checks style, syntax, etc.just bench- runs the benchmarksjust test- runs the unit tests and prop testsjust fuzz- runs the fuzzer
About
A fast BVH using SAH in rust