Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up

A fast BVH using SAH in rust

License

NotificationsYou must be signed in to change notification settings

svenstaro/bvh

Repository files navigation

CIDocs StatuscodecovlicenseCrates.ioCrates.io

A crate which exports rays, axis-aligned bounding boxes, and binary boundingvolume hierarchies.

About

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.

Example

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);

Explicit SIMD

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.

Optimization

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.

Drawbacks

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.

Intersection via traversal of the list of triangles

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.

Intersection via traversal of the list of triangles with AABB checks

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.

Build of a BVH from scratch

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)

Flatten a BVH

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.

Intersection via BVH traversal

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.

Optimization

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.

Intersection after the optimization

These intersection tests are grouped by dataset and by the BVH generation method.

  • _after_optimize uses a BVH which was kept up to date with calls tooptimize, while
  • _with_rebuild uses 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.

Running the benchmark suite

The benchmark suite uses features from thetest crate and therefore cannot be run on stable rust.Using a nightly toolchain, runcargo bench --features bench.

Testing

Unit tests

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.

Proptest

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.

Fuzzer

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.

Contributing

We recommend you install thejust command runner, toruncommands including:

  • just lint - checks style, syntax, etc.
  • just bench - runs the benchmarks
  • just test - runs the unit tests and prop tests
  • just fuzz - runs the fuzzer

[8]ページ先頭

©2009-2025 Movatter.jp