BVH Construction and Traversal Library

Note: This is the 2nd version of this library. Check the v1 branch for the older, first version of this library.

This library is a small, standalone library for BVH construction and traversal. It is licensed under the MIT license.

(Scene by Blend Swap user MaTTeSr, available here, distributed under CC-BY 3.0)

Performance

Here is a comparison of this library with other alternatives (Embree, Fast-BVH, and nanort):

Features

Here is a list of features supported by this library (changes from v1 are indicated with [NEW]):

• [NEW] C++20 interface using std::span instead of raw pointers,
• Low-level API with direct access to various builders,
• [NEW] High-level DefaultBuilder API which selects the best builder depending on the desired BVH quality level.
• High-quality, single-threaded sweeping SAH builder,
• Fast, medium-quality, single-threaded binned SAH builder inspired by "On Fast Construction of SAH-based Bounding Volume Hierarchies", by I. Wald,
• Fast, high-quality, multithreaded mini-tree BVH builder inspired by "Rapid Bounding Volume Hierarchy Generation using Mini Trees", by P. Ganestam et al.,
• Reinsertion optimizer based on "Parallel Reinsertion for Bounding Volume Hierarchy Optimization", by D. Meister and J. Bittner,
• Fast and robust traversal algorithm using "Robust BVH Ray Traversal", by T. Ize.
• Fast ray-triangle intersection algorithm based on "Fast, Minimum Storage Ray/Triangle Intersection", by T. Möller and B. Trumbore,
• [NEW] Surface area traversal order heuristic for shadow rays based on "SATO: Surface Area Traversal Order for Shadow Ray Tracing", by J. Nah and D. Manocha,
• Fast ray-sphere intersection routine,
• [NEW] Serialization/deserialization interface,
• [NEW] Variable amount of dimensions (e.g. 2D, 3D, 4D BVHs are supported) and different scalar types (e.g. float or double),
• [NEW] Only depends on the standard library (parallelization uses a custom thread pool based on std::thread),
• [NEW] C API for the high-level parts of the library is available.

Building

This library is header-only, and can be added as a CMake subproject by cloning or adding as this repository as submodule, for instance in <your-project>/contrib/bvh, and then adding this to <your-project>/CMakeLists.txt:

add_subdirectory(contrib/bvh)
target_link_library(my_project PUBLIC bvh)

If you want to build the examples, use:

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=<Debug|Release> -DENABLE_TESTING=ON
cmake --build .

C API

The library can be used via a small set of high-level C bindings. These bindings are not enabled by default, but can be built by configuring CMake with -DBVH_BUILD_C_API=ON. Additionally, if the intent is to use the library in a pure C environment which does not have the C++ standard library as a dependency, it might be a good idea to statically the C++ standard library. That can be done by adding the flag -DBVH_STATIC_LINK_STDLIB_C_API=ON to the CMake command line.

Usage

The library contains several examples that are kept up-to-date with the API:

• A basic example that traces one ray on a scene made of a couple of triangles,
• A benchmarking utility that showcases what the library can do.
• A serialization test that shows how to save and load a BVH from a file.
• A C API example that shows how to use the C bindings to this library.