20个版本 (10个重大更新)

0.10.0	2024年7月6日
0.9.0	2024年3月16日
0.8.0	2024年2月17日
0.7.2	2023年3月31日
0.1.1	2016年10月4日

#20 in 游戏开发

218 每月下载量
在 4 crates 中使用

MIT 许可证

1MB
3.5K SLoC

bvh

一个导出射线、对齐的边界框和二进制边界体积层次结构的crate。

关于

此crate可以用于包含射线与原语交错的计算的应用程序。为此，如果射线穿越的场景包含大量原语，二叉树BVH（边界体积层次结构）非常有用。使用BVH可以将交差点测试复杂度从O(n)降低到O(log2(n))，但需要预先构建BVH一次。这种技术在光线/路径追踪器中特别有用。为了在着色器中使用，此模块还导出了一种展平过程，允许迭代遍历BVH。

默认使用rayon来并行化构建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);

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

显式SIMD

此crate包含一些手动编写的SIMD指令，目前仅适用于x86_64架构。虽然nalgebra为我们提供了通用的SIMD优化（并且它的大部分工作都做得很好）——一些重要的函数，如ray-aabb-intersection，已经被手动优化。

目前优化的射线-aabb交点是：类型：f32，维度：2,3,4 类型：f64，维度：2,3,4

要启用这些优化，您必须使用nightly工具链构建并启用simd标志。

优化

此crate提供BVH更新，也称为优化。使用BVH优化，您可以修改BVH构建的形状，并相应地更新树，而无需完全重建它。当场景只有少量更改时，此方法非常有用。当场景的大部分是静态的时，更新树比从头开始重建更快。

缺点

首先，如果场景中超过一半的物体不是静态的，那么优化是没有帮助的。这是因为优化的方式：给定一组所有发生变化的形状的索引集，优化过程会尝试旋转固定的星座以寻找更好的表面积启发式（SAH）值。这是通过从底部到顶部递归地进行的，同时固定BVH内部节点的AABB。这就是为什么与重建相比，当很多形状移动时，更新BVH效率低下。

更新BVH的另一个问题是，结果BVH并不是最优的。假设场景由两个主要组组成，它们之间有一个很大的空隙。当一个形状从一个组移动到另一个组时，更新过程将无法找到一个自底向上的旋转序列，将形状深入插入到另一分支。

以下基准测试使用了两组不同的数据集

一个随机生成的场景，包含单位大小的立方体，总共（1200，12000和120000个三角形）。
Sponza，一个用于图形引擎基准测试的流行场景。

所有基准测试都是在Ryzen 3900x上进行的。

除非另有说明，否则所有基准测试都是在不启用simd功能的情况下捕获的。

通过遍历三角形列表进行交集

test testbase::bench_intersect_120k_triangles_list                            ... bench:     570,717 ns/iter (+/- 21,689)
test testbase::bench_intersect_sponza_list                                    ... bench:     510,683 ns/iter (+/- 9,525)

// simd enabled
test testbase::bench_intersect_120k_triangles_list                            ... bench:     566,916 ns/iter (+/- 22,024)
test testbase::bench_intersect_sponza_list                                    ... bench:     518,821 ns/iter (+/- 12,191)

这是将场景与射线交集的最简单方法。它定义了基线。

带有AABB检查的通过遍历三角形列表进行交集

test testbase::bench_intersect_120k_triangles_list_aabb                       ... bench:     687,660 ns/iter (+/- 6,850)
test testbase::bench_intersect_sponza_list_aabb                               ... bench:     381,037 ns/iter (+/- 1,416)

// simd enabled
test testbase::bench_intersect_120k_triangles_list_aabb                       ... bench:     295,810 ns/iter (+/- 3,309)
test testbase::bench_intersect_sponza_list_aabb                               ... bench:     163,738 ns/iter (+/- 1,822)

AABB检查相对便宜，与三角形交集算法相比。因此，先进行AABB检查可以通过快速过滤掉负结果来提高交集速度。

从头开始构建BVH

test flat_bvh::bench::bench_build_1200_triangles_flat_bvh                     ... bench:     242,357 ns/iter (+/- 1,882)
test flat_bvh::bench::bench_build_12k_triangles_flat_bvh                      ... bench:   3,681,965 ns/iter (+/- 223,716)
test flat_bvh::bench::bench_build_120k_triangles_flat_bvh                     ... bench:  46,415,590 ns/iter (+/- 3,226,404)
test bvh::bvh_impl::bench::bench_build_1200_triangles_bvh                     ... bench:     239,473 ns/iter (+/- 2,456)
test bvh::bvh_impl::bench::bench_build_1200_triangles_bvh_rayon               ... bench:     123,387 ns/iter (+/- 9,427)
test bvh::bvh_impl::bench::bench_build_12k_triangles_bvh                      ... bench:   2,903,150 ns/iter (+/- 54,318)
test bvh::bvh_impl::bench::bench_build_12k_triangles_bvh_rayon                ... bench:   1,073,300 ns/iter (+/- 89,530)
test bvh::bvh_impl::bench::bench_build_120k_triangles_bvh                     ... bench:  37,390,480 ns/iter (+/- 2,789,280)
test bvh::bvh_impl::bench::bench_build_120k_triangles_bvh_rayon               ... bench:   8,935,320 ns/iter (+/- 1,780,231)
test bvh::bvh_impl::bench::bench_build_sponza_bvh                             ... bench:  23,828,070 ns/iter (+/- 1,307,461)
test bvh::bvh_impl::bench::bench_build_sponza_bvh_rayon                       ... bench:   4,764,530 ns/iter (+/- 950,640)

压平BVH

test flat_bvh::bench::bench_flatten_120k_triangles_bvh                        ... bench:   9,806,060 ns/iter (+/- 1,771,861)

如您所见，构建BVH需要很长时间。只有当场景上执行的重叠次数超过构建时间时，构建BVH才有用。这在如光线追踪和路径追踪之类的应用中是这种情况，其中对于高清图像，最小重叠次数为1280 * 720。

通过BVH遍历进行交集 test flat_bvh::bench::bench_intersect_1200_triangles_flat_bvh ... bench: 144 ns/iter (+/- 1) test flat_bvh::bench::bench_intersect_12k_triangles_flat_bvh ... bench: 370 ns/iter (+/- 4) test flat_bvh::bench::bench_intersect_120k_triangles_flat_bvh ... bench: 866 ns/iter (+/- 16) test bvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh ... bench: 146 ns/iter (+/- 2) test bvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh ... bench: 367 ns/iter (+/- 5) test bvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh ... bench: 853 ns/iter (+/- 12) test bvh::bvh_impl::bench::bench_intersect_sponza_bvh ... bench: 1,381 ns/iter (+/- 20) test ray::ray_impl::bench::bench_intersects_aabb ... bench: 4,404 ns/iter (+/- 17) // simd enabled test bvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh ... bench: 121 ns/iter (+/- 2) test bvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh ... bench: 309 ns/iter (+/- 3) test bvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh ... bench: 749 ns/iter (+/- 15) test bvh::bvh_impl::bench::bench_intersect_sponza_bvh ... bench: 1,216 ns/iter (+/- 16) test ray::ray_impl::bench::bench_intersects_aabb ... bench: 2,447 ns/iter (+/- 18) 这些性能测量表明，遍历BVH比遍历列表要快得多。优化对更新场景所需时间的基准测试还包括一个随机化过程，它需要一些时间。 test bvh::optimization::bench::bench_update_shapes_bvh_120k_00p ... bench: 1,057,965 ns/iter (+/- 76,098) test bvh::optimization::bench::bench_update_shapes_bvh_120k_01p ... bench: 2,535,682 ns/iter (+/- 80,231) test bvh::optimization::bench::bench_update_shapes_bvh_120k_10p ... bench: 18,840,970 ns/iter (+/- 3,432,867) test bvh::optimization::bench::bench_update_shapes_bvh_120k_50p ... bench: 76,025,200 ns/iter (+/- 3,899,770) test bvh::optimization::bench::bench_randomize_120k_50p ... bench: 5,361,645 ns/iter (+/- 436,340) 这是您必须区分从头开始重建树或尝试优化旧树的地方。这些测试显示了移动特定百分比的形状（10p => 10%）的影响。重要的是要注意，这里的随机化过程会随意移动三角形。这也会导致BVH需要完全重构的情况。优化后的交集这些交集测试按数据集和BVH生成方法分组。 _after_optimize使用通过调用optimize保持最新的BVH，而 _with_rebuild使用与_after_optimize相同的三角形数据，但从头开始构建BVH。 120K 三角形 test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_00p ... bench: 855 ns/iter (+/- 15) test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_01p ... bench: 921 ns/iter (+/- 13) test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_10p ... bench: 2,677 ns/iter (+/- 191) test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_50p ... bench: 2,992 ns/iter (+/- 103) test bvh::optimization::bench::bench_intersect_120k_with_rebuild_00p ... bench: 852 ns/iter (+/- 13) test bvh::optimization::bench::bench_intersect_120k_with_rebuild_01p ... bench: 918 ns/iter (+/- 13) test bvh::optimization::bench::bench_intersect_120k_with_rebuild_10p ... bench: 1,920 ns/iter (+/- 266) test bvh::optimization::bench::bench_intersect_120k_with_rebuild_50p ... bench: 2,075 ns/iter (+/- 318) Sponza test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_00p ... bench: 2,023 ns/iter (+/- 52) test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_01p ... bench: 3,444 ns/iter (+/- 120) test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_10p ... bench: 16,873 ns/iter (+/- 2,123) test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_50p ... bench: 9,075 ns/iter (+/- 486) test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_00p ... bench: 1,388 ns/iter (+/- 46) test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_01p ... bench: 1,529 ns/iter (+/- 102) test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_10p ... bench: 1,920 ns/iter (+/- 120) test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_50p ... bench: 2,505 ns/iter (+/- 88) 这组测试显示了随机移动三角形并产生退化树的影响。该120K 三角形数据集已被随机更新。使用具有形状最大偏移距离的方法更新了Sponza场景。这模拟了一个更真实的场景。我们还可以看到，仅就场景而言，它包含一些可以被紧密包裹在BVH中的结构。通过移动这些结构，我们破坏了三角形组的局部性，导致BVH中需要检查的分支更多，从而使得交点持续时间更长。运行基准测试套件基准测试套件使用来自测试库的功能，因此无法在稳定版Rust上运行。使用nightly工具链，运行cargo bench --features bench。

依赖关系 ~5.5MB ~112K SLoC approx log nalgebra 0.33+default+serde-serialize num 0.4 rand default rayon optional serde+derive dev doc-comment dev float_eq dev obj-rs dev proptest 其他特性 bench simd