svenstaro/bvh
svenstaro/bvh hiện có 271 sao trên GitHub, viết chủ yếu bằng Rust. A fast BVH using SAH in rust
Tóm tắt dựng từ metadata GitHub của chính dự án — chưa có bài review TopGit. Trang sẽ tự động cập nhật khi bài review đầy đủ được xuất bản.
TopGit viết bài đầy đủ cho repo có nhiều sao nhất và được yêu cầu nhiều nhất. Trang này là snapshot trong thời gian chờ — xem README gốc ở tab READ ME.
Snapshot
Cộng tác viên hàng đầu
Xem cộng tác viên hàng đầu
bvh
A crate which exports rays, axis-aligned bounding boxes, and binary bounding volume hierarchies.
About
This crate can be used for applications which contain intersection computations of rays with primitives. For this purpose a binary tree BVH (Bounding Volume Hierarchy) is of great use if the scene which the ray traverses contains a huge number of primitives. With a BVH the intersection test complexity is reduced from O(n) to O(log2(n)) at the cost of building the BVH once in advance. This technique is especially useful in ray/path tracers. For use in a shader this module also exports a flattening procedure, which allows for iterative traversal of the BVH.
It uses rayon to parallelize building the BVH and wide for explicit SIMD.
Both of these are enabled by default.
Make sure to use RUSTFLAGS='-C target-cpu=native' for the best possible speedup.
It can also be used in no_std contexts by disabling default features.
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);
struct Sphere {
position: Point3<f32>,
radius: f32,
node_index: usize,
}
impl Bounded<f32, 3> for Sphere {
fn aabb(&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)
}
}
impl BHShape<f32, 3> for Sphere {
fn set_bh_node_index(&mut self, index: usize) {
self.node_index = index;
}
fn bh_node_index(&self) -> usize {
self.node_index
}
}
let mut spheres = Vec::new();
for i in 0..1000u32 {
let position = Point3::new(i as f32, i as f32, i as f32);
let radius = (i % 10) as f32 + 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 SIMD operations. See wide documentation for supported architectures.
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:
- f32, dimensions 2, 3, 4
- f64, dimensions 2, 3, 4
These optimizations are enabled by default via the simd feature.
Optimization
This crate provides BVH updating, which is also called optimization. With BVH optimization you 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 constellations in search for a better surface area heuristic (SAH) value. This is done recursively from bottom to top while fixing the AABBs in the inner nodes of the BVH. Which is why it is inefficient to update the BVH in comparison to rebuilding, when a lot of shapes have moved.
Another problem with updated BVHs is, that the resulting BVH is not optimal. Assume that the scene is composed of two major groups separated by a large gap. When one shape moves from one group to another, the updating procedure will not be able to find 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 captured with divan via cargo bench on an AMD Ryzen 9 9950X3D, built with RUSTFLAGS="-C target-cpu=native". Numbers are machine-specific snapshots; see "Running the benchmark suite" below to reproduce them.
Build
Benchmarks for building a BVH from scratch and flattening it.
build fastest │ slowest │ median │ mean │ samples │ iters
├─ build_sponza 11.42 ms │ 15.54 ms │ 11.53 ms │ 11.84 ms │ 85 │ 85
├─ build_sponza_par 1.555 ms │ 2.879 ms │ 1.644 ms │ 1.677 ms │ 100 │ 100
├─ flatten_120k 955.5 µs │ 2.388 ms │ 1 ms │ 1.02 ms │ 100 │ 100
├─ build_triangles │ │ │ │ │
│ ├─ Bvh<f32, 3> │ │ │ │ │
│ │ ├─ 100 124.5 µs │ 155.9 µs │ 125.7 µs │ 127.4 µs │ 100 │ 100
│ │ ├─ 1000 1.514 ms │ 1.664 ms │ 1.531 ms │ 1.532 ms │ 100 │ 100
│ │ ╰─ 10000 18.61 ms │ 19.73 ms │ 18.72 ms │ 18.76 ms │ 54 │ 54
│ ╰─ Vec<bvh::flat_bvh::FlatNode<f32, 3>> │ │ │ │ │
│ ├─ 100 132.7 µs │ 145.5 µs │ 134.3 µs │ 134.8 µs │ 100 │ 100
│ ├─ 1000 1.602 ms │ 1.662 ms │ 1.614 ms │ 1.617 ms │ 100 │ 100
│ ╰─ 10000 21.28 ms │ 22.22 ms │ 21.5 ms │ 21.52 ms │ 46 │ 46
╰─ build_triangles_par │ │ │ │ │
├─ Bvh<f32, 3> │ │ │ │ │
│ ├─ 100 42.35 µs │ 208.8 µs │ 68.38 µs │ 78.83 µs │ 100 │ 100
│ ├─ 1000 304.7 µs │ 729.9 µs │ 343.5 µs │ 350.7 µs │ 100 │ 100
│ ╰─ 10000 2.73 ms │ 3.821 ms │ 2.916 ms │ 2.97 ms │ 100 │ 100
╰─ Vec<bvh::flat_bvh::FlatNode<f32, 3>> │ │ │ │ │
├─ 100 79.82 µs │ 198.9 µs │ 123.4 µs │ 127.9 µs │ 100 │ 100
├─ 1000 446.3 µs │ 845.2 µs │ 478.2 µs │ 523.6 µs │ 100 │ 100
╰─ 10000 4.995 ms │ 6.602 ms │ 5.457 ms │ 5.512 ms │ 100 │ 100
As you can see, building a BVH takes a long time. Building a BVH is only useful if the number of intersections performed on the scene exceeds the build duration. This is the case in applications such as ray tracing and path tracing.
Traverse
The *_list entries intersect a scene by traversing the raw list of triangles. This is
the most naive approach and defines the baseline. The *_list_aabb entries precede the
triangle test with AABB checks, which are cheap compared to the triangle-intersection
algorithms and so they filter negative results a lot faster.
The nearest_to* benchmarks find the closest shape to a point.
traverse fastest │ slowest │ median │ mean │ samples │ iters
├─ intersect_120k_list 204.9 µs │ 397.4 µs │ 309 µs │ 307 µs │ 100 │ 100
├─ intersect_120k_list_aabb 171.5 µs │ 206.3 µs │ 174.8 µs │ 175.5 µs │ 100 │ 100
├─ intersect_sponza_bvh 139.8 ns │ 2.789 µs │ 844.8 ns │ 931.6 ns │ 100 │ 100
├─ intersect_sponza_iter 92.91 µs │ 129 µs │ 106.4 µs │ 107.8 µs │ 100 │ 100
├─ intersect_sponza_list 251.7 µs │ 331 µs │ 305 µs │ 301.2 µs │ 100 │ 100
├─ intersect_sponza_list_aabb 94.59 µs │ 104.5 µs │ 96.48 µs │ 96.95 µs │ 100 │ 100
├─ intersect_sponza_vec 94.74 µs │ 133.5 µs │ 107.7 µs │ 108.6 µs │ 100 │ 100
├─ nearest_to_120k_list 493.1 µs │ 612.9 µs │ 545.9 µs │ 547.2 µs │ 100 │ 100
├─ nearest_to_120k_list_aabb 170.4 µs │ 215.7 µs │ 176.6 µs │ 177.3 µs │ 100 │ 100
├─ nearest_to_sponza_bvh 309.8 ns │ 9.609 µs │ 1.549 µs │ 2.037 µs │ 100 │ 100
├─ nearest_to_sponza_list 479.2 µs │ 591.6 µs │ 516.6 µs │ 518.8 µs │ 100 │ 100
├─ nearest_to_sponza_list_aabb 94.39 µs │ 110 µs │ 99.25 µs │ 99.32 µs │ 100 │ 100
├─ intersect_triangles │ │ │ │ │
│ ├─ Bvh<f32, 3> │ │ │ │ │
│ │ ├─ 100 74.81 ns │ 267.3 ns │ 111 ns │ 122.4 ns │ 100 │ 400
│ │ ├─ 1000 197.3 ns │ 514.8 ns │ 346 ns │ 345.1 ns │ 100 │ 400
│ │ ╰─ 10000 229.8 ns │ 2.269 µs │ 734.8 ns │ 827.2 ns │ 100 │ 100
│ ╰─ Vec<bvh::flat_bvh::FlatNode<f32, 3>> │ │ │ │ │
│ ├─ 100 72.31 ns │ 292.3 ns │ 109.8 ns │ 123.4 ns │ 100 │ 400
│ ├─ 1000 242.3 ns │ 1.344 µs │ 363.5 ns │ 378.2 ns │ 100 │ 400
│ ╰─ 10000 339.8 ns │ 6.069 µs │ 1.059 µs │ 1.454 µs │ 100 │ 100
╰─ nearest_to_triangles │ │ │ │ │
├─ Bvh<f32, 3> │ │ │ │ │
│ ├─ 100 169.8 ns │ 382.3 ns │ 249.8 ns │ 253.7 ns │ 100 │ 400
│ ├─ 1000 272.3 ns │ 712.3 ns │ 388.5 ns │ 416.2 ns │ 100 │ 400
│ ╰─ 10000 309.8 ns │ 1.489 µs │ 449.8 ns │ 544.3 ns │ 100 │ 100
╰─ Vec<bvh::flat_bvh::FlatNode<f32, 3>> │ │ │ │ │
├─ 100 79.81 ns │ 1.789 µs │ 734.8 ns │ 737.7 ns │ 100 │ 100
├─ 1000 139.8 ns │ 9.559 µs │ 2.559 µs │ 2.545 µs │ 100 │ 100
╰─ 10000 509.8 ns │ 50.9 µs │ 13.54 µs │ 14.44 µs │ 100 │ 100
These performance measurements show that traversing a BVH is much faster than traversing a list.
Ray
The single ray–AABB intersection test that traversal performs at every node, measured in
isolation across 2/3/4 dimensions and f32/f64. Traversal runs this test many times
per query.
ray fastest │ slowest │ median │ mean │ samples │ iters
├─ intersects_aabb 1.549 µs │ 1.649 µs │ 1.584 µs │ 1.586 µs │ 100 │ 100
╰─ intersects_aabb_f64 │ │ │ │ │
├─ 2 1.209 µs │ 1.309 µs │ 1.219 µs │ 1.224 µs │ 100 │ 100
├─ 3 2.089 µs │ 2.279 µs │ 2.099 µs │ 2.107 µs │ 100 │ 100
╰─ 4 1.779 µs │ 9.139 µs │ 1.839 µs │ 1.911 µs │ 100 │ 100
Optimize
These benchmarks show how long it takes to update the scene after moving a percentage of
the shapes (10p means 10%).
This is where you have to differentiate between rebuilding the tree from
scratch or trying to optimize the old one (see Optimization
above).
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.
The *_after_update_shapes entries traverse a BVH kept up to date with calls to
update_shapes while *_with_rebuild uses the same triangle data but constructs a BVH
from scratch. This set of tests shows the impact of randomly moving triangles around and
producing degenerated trees.
optimize fastest │ slowest │ median │ mean │ samples │ iters
├─ intersect_120k_after_update_shapes │ │ │ │ │
│ ├─ 0 229.8 ns │ 4.739 µs │ 599.8 ns │ 749.1 ns │ 100 │ 100
│ ├─ 0.01 299.8 ns │ 1.949 µs │ 759.8 ns │ 771.4 ns │ 100 │ 100
│ ├─ 0.1 269.8 ns │ 5.239 µs │ 1.369 µs │ 1.574 µs │ 100 │ 100
│ ╰─ 0.5 189.8 ns │ 5.619 µs │ 1.564 µs │ 1.67 µs │ 100 │ 100
├─ intersect_120k_with_rebuild │ │ │ │ │
│ ├─ 0 219.8 ns │ 2.109 µs │ 754.8 ns │ 872.6 ns │ 100 │ 100
│ ├─ 0.01 279.8 ns │ 4.879 µs │ 1.559 µs │ 1.751 µs │ 100 │ 100
│ ├─ 0.1 259.8 ns │ 10.85 µs │ 2.859 µs │ 3.517 µs │ 100 │ 100
│ ╰─ 0.5 169.8 ns │ 11.14 µs │ 2.649 µs │ 3.48 µs │ 100 │ 100
├─ intersect_sponza_after_update_shapes │ │ │ │ │
│ ├─ 0 129.8 ns │ 4.989 µs │ 924.8 ns │ 1.2 µs │ 100 │ 100
│ ├─ 0.01 209.8 ns │ 4.749 µs │ 1.484 µs │ 1.613 µs │ 100 │ 100
│ ├─ 0.1 119.8 ns │ 26.09 µs │ 4.849 µs │ 6.345 µs │ 100 │ 100
│ ╰─ 0.5 69.81 ns │ 20.73 µs │ 3.714 µs │ 4.456 µs │ 100 │ 100
├─ intersect_sponza_with_rebuild │ │ │ │ │
│ ├─ 0 129.8 ns │ 2.389 µs │ 764.8 ns │ 826.5 ns │ 100 │ 100
│ ├─ 0.01 189.8 ns │ 3.039 µs │ 804.8 ns │ 943 ns │ 100 │ 100
│ ├─ 0.1 129.8 ns │ 3.969 µs │ 939.8 ns │ 1.12 µs │ 100 │ 100
│ ╰─ 0.5 59.81 ns │ 5.289 µs │ 1.254 µs │ 1.477 µs │ 100 │ 100
├─ randomize_120k_50p 1.317 ms │ 1.442 ms │ 1.326 ms │ 1.33 ms │ 100 │ 100
╰─ update_shapes_bvh_120k │ │ │ │ │
├─ 0 235.5 µs │ 262.5 µs │ 238.3 µs │ 239.2 µs │ 100 │ 100
├─ 0.01 677 µs │ 810 µs │ 734.5 µs │ 728.8 µs │ 100 │ 100
├─ 0.1 4.349 ms │ 6.84 ms │ 5.61 ms │ 5.639 ms │ 100 │ 100
╰─ 0.5 24.8 ms │ 34.03 ms │ 28.79 ms │ 28.87 ms │ 35 │ 35
Running the benchmark suite
The benchmarks use divan and run on stable Rust:
cargo bench # default features (includes SIMD)
cargo bench --no-default-features --features std,rayon # without SIMD
Testing
Unit tests
This project aspires to be fully tested, and that starts with a unit test suite. Use
cargo test to run all the tests. The tests automatically run in CI, too. Contributors
are expected to add tests for all new functionality.
Proptest
This project uses proptest as a second
line of defense against bugs, allowing random instances of certain tests to be tested.
These tests run alongside unit-tests.
Fuzzer
This project uses cargo fuzz as
a third line of defense against bugs, meaning that the fuzz/ directory was generated
using cargo fuzz init. At the moment, there is a single fuzz target, and running
cargo fuzz run fuzz will fuzz until an assertion is violated. The fuzzer automatically
runs in CI, too.
Contributing
We recommend you install the just command runner, to
run commands including:
just lint- checks style, syntax, etc.just bench- runs the benchmarksjust test- runs the unit tests and prop testsjust fuzz- runs the fuzzer
Repo liên quan
Master programming by recreating your favorite technologies from scratch.
A curated meta-list of curated lists organized by technology domain. The repository acts as a directory pointing to hundreds of specialized awesome lists covering programming languages, platforms, frameworks, and tooling. All content is community-contributed under the CC0 public domain dedication.
Public APIs is a community-curated GitHub repository listing free, publicly accessible APIs across a wide range of categories, with auth type, HTTPS, and CORS noted for each entry. It's a browsable reference, not a library to install.
freeCodeCamp is a free, self-paced curriculum for learning to code, published as open source at freeCodeCamp/freeCodeCamp. It's a 501(c)(3) nonprofit funded by donor support, structured around six certifications in its Full-Stack Developer Curriculum, each gated by required projects instead of open-book quizzes. The repository also carries beta language certifications for developers, interview-prep resources, and the code that runs the live freecodecamp.org platform.
Trả lời nhanh
Đọc thêm về svenstaro/bvh ở đâu?
Trang TopGit này là một snapshot — tab "Readme" hiển thị nguyên văn README của repo (đã bỏ link, giữ ảnh). Repo GitHub ở github.com/svenstaro/bvh là nguồn chính thức.
svenstaro/bvh có bao nhiêu sao?
svenstaro/bvh có 271 sao GitHub — tải lại trang để xem số mới nhất, hoặc xem trực tiếp github.com/svenstaro/bvh. TopGit phản chiếu số sao của GitHub nhưng không cam kết đến từng phút.
svenstaro/bvh có phải mã nguồn mở không?
Có — svenstaro/bvh phát hành theo license MIT, nghĩa là mã nguồn mở để đọc, fork và (tùy license) tái sử dụng. Mã: github.com/svenstaro/bvh.
svenstaro/bvh có trang demo không?
Dự án có trang chủ ở https://docs.rs/bvh. Tab "Readme" ở trang này thường có ảnh chụp và hướng dẫn bắt đầu nhanh.
svenstaro/bvh là gì?
svenstaro/bvh (svenstaro/bvh) là dự án Rust trên GitHub. Theo mô tả gốc: A fast BVH using SAH in rust
Đọc đầy đủ README ở tab phía trên.
Chưa chắc bvh có hợp với bạn?
Để ChatGPT, Claude hoặc Perplexity tìm hiểu giúp — bấm bên dưới và xem AI nói gì về bvh.