TinyBVH

Header-only BVH construction and traversal library written in C++14 / "Sane C++" (or "C with classes"). C++17 is used for threading. This library has no dependencies.

TinyBVH is fast. Here is, in a nutshell, how it compares to Intel's Embree and Madmann91's BVH library. TinyBVH currently builds a SAH BVH faster than Embree and Madmann91. It also traces individual primary and 'any hit' rays faster than those libraries. Note: These results are based on the new tiny_bvh_benchmark.cpp application and are cautiously presented as 'preliminary'. Single-ray traversal is only a small part of Embree. If you suspect an imperfection in the experiment setup, please let me know. When tracing rays on the GPU, (multicore) CPU performance is dwarfed. On an RTX 5080 laptop GPU, TinyBVH traces up to 5 billion rays per second in Crytek's Sponza scene using the basic binary BVH format, regardless of graphics API and without using specialized ray tracing hardware. That is 5 rays per pixel at 4k@120Hz, enough for most purposes.

TinyOCL

TinyBVH GPU ray traversal examples are available for OpenCL, OpenGL with compute shaders, DirectX12 and Vulkan. For OpenCL support, TinyOCL is provided: a single-header OpenCL library, which helps you select and initialize a compute device. It also loads, compiles and runs kernels, with several convenient features:

• Include-file expansion for AMD devices
• Multi-argument passing
• Host/device buffer management
• Vendor and architecture detection and propagation to #defines in OpenCL code
• ..and many other things.

To use TinyOCL, just include tiny_ocl.h; this will automatically cause linking with OpenCL.lib in the 'external' folder, which in turn passes on work to vendor-specific driver code.

Note that the tiny_bvh.h library will work without tiny_ocl.h and remains dependency-free. The new tiny_ocl.h is only needed in projects that wish to trace rays on the GPU using BVHs created by tiny_bvh.h.

BVH?

A Bounding Volume Hierarchy is a data structure used to quickly find intersections in a virtual scene; most commonly between a ray and a group of triangles. You can read more about this in a series of articles on the subject: https://jacco.ompf2.com/2022/04/13/how-to-build-a-bvh-part-1-basics .

To build a BVH using TinyBVH, simply call BVH::Build on an instantiated BVH. See tiny_bvh_minimal.cpp for a (really) small example. Internally, the call is forwarded to a specialized builder. There are fast builders, builders for 'high quality' BVHs and experimental builders for research and development.

A constructed BVH can be used to intersect a ray with geometry, using BVH::Intersect or BVH::IsOccluded, for shadow (aka any hit) rays.

Apart from the default BVH layout (simply named BVH), several other layouts are available, which all serve one or more specific purposes. You can create a BVH in the desired layout by instantiating the appropriate class. The available layouts are:

• BVH : A compact format that stores the AABB for a node, along with child pointers and leaf information in a cross-platform-friendly way. The 32-byte size allows for cache-line alignment.
• BVH_Double : Double-precision version of BVH.
• BVH4_Double : Double-precision version of BVH4_CPU, with AVX2 and NEON traversal kernels.
• MBVH<M> : In this (templated) format, each node stores M child pointers, reducing the depth of the tree. This improves performance for divergent rays. Based on the 2008 paper by Ingo Wald et al.
• BVH4_CPU : AVX2/NEON-optimized wide BVH traversal ("WiVe"). This is the fastest option on CPU.
• BVH8_CPU : AVX2/NEON-optimized wide BVH traversal ("WiVe"). BVH4_CPU is now faster; this format is left in for reference.
• BVH_GPU : This format uses 64 bytes per node and stores the AABBs of the two child nodes. This is the format presented in the 2009 Aila & Laine paper. It can be traversed with a simple GPU kernel.
• BVH4_GPU : A compact 4-wide BVH format, which may be faster for GPU ray tracing.
• BVH8_CWBVH : An advanced 80-byte representation of the 8-wide BVH, for state-of-the-art GPU rendering, based on the 2017 paper by Ylitie et al. and code by AlanIWBFT.

A BVH in any format can be rebuilt at any time by calling the Build method on the changed triangle data. A BVH may also be refitted, in case the triangles moved, using BVH::Refit. Refitting is substantially faster than rebuilding and works well if the animation is subtle. Refitting does not work if polygon counts change.

Most layouts may be serialized and de-serialized via ::Save and ::Load.

TinyBVH also supports construction of a Top-Level Acceleration Structure (TLAS). The TLAS is a BVH over Bottom-Level Acceleration Structures (BLASes), where each BLAS is a BVH, with a 4x4 matrix transform. Different layouts can be combined under a single TLAS. The TLAS can be used for cheap rigid animation (by changing the transforms) as well as instancing.

A more complete overview of TinyBVH functionality can be found in the Basic Use Manual and the Advanced Topics Manual.

How To Use

The library consists of tiny_bvh.h and the tiny_bvh_*.h headers next to it; keep them together and include only tiny_bvh.h. It is designed to be easy to use. Please have a look at tiny_bvh_minimal.cpp for an example. A Visual Studio 'solution' (.sln/.vcxproj) is included, as well as a CMake file. That being said: Most examples consist of only a single source file, which can be compiled with clang or g++, e.g.:

g++ examples/tiny_bvh_minimal.cpp

The cross-platform fenster-based single-source bitmap renderer can be compiled with

g++ -mwindows -O3 examples/tiny_bvh_fenster.cpp -o tiny_bvh_fenster (on Linux and Windows)

c++ --std=c++17 -framework Cocoa -O3 examples/tiny_bvh_fenster.cpp -o tiny_bvh_fenster (on macOS)

The multi-threaded path tracing demo can be compiled with

g++ -mwindows -O3 examples/tiny_bvh_pt.cpp -o tiny_bvh_pt (on Linux and Windows)

c++ --std=c++17 -framework Cocoa -O3 examples/tiny_bvh_pt.cpp -o tiny_bvh_pt (on macOS)

The performance measurement tool can be compiled with:

g++ -mavx2 -mfma -Ofast tiny_bvh_speedtest.cpp -o tiny_bvh_speedtest (on Linux and Windows)

c++ --std=c++17 -framework OpenCL -Ofast tiny_bvh_speedtest.cpp -o tiny_bvh_speedtest (on macOS)

Note: A new, more advanced benchmark tool is now available. See build.bat and build_debug.bat for an example of a command line to compile it using gcc.

Many additional demos are provided, demonstrating features of the library in small source files.

Version 1.9.0

Basic use:

BVH bvh;
bvh.Build( (bvhvec4*)myTriData, triangleCount );
bvh.Intersect( ray );

To build a BVH for indexed vertices, use the new indexed interface:

BVH bvh;
bvh.Build( (bvhvec4*)vertices, (uint32_t*)indices, triangleCount );

New in 1.7.3: BVH build settings are now in BVHBase::settings:

struct BVHBuildSettings
{
    bool usePresplitting = false;	// pre-split triangles before building the BVH.
    bool useSpatialSplits = false;	// consider spatial splits during construction (SBVH).
    bool presplitPostPass = true;	// attempt to un-split primitives in leaves after a presplit build.
    float presplitFactor = 0.3f;	// presplit budget relative to input data size.
    bool useFullSweep = false;		// for experiments only; full-sweep SAH builder.
    bool postOptimize = false;		// optimize generated BVH using tree rotations.
    int optimizeIterations = 50;	// default optimization iterations.
    bool useSIMDifavailable = true;	// set to false to use the scalar reference builder.
};

This supersedes the calls to ::BuildHQ and ::BuildSIMD, which are now invoked from ::Build based on the hints in BVHBuildSettings. The old interface also remains available for now.

This version of the library includes the following functionality:

• Reference 'full-sweep' SAH BVH builder
• Fast cross-platform binned SAH BVH builder
• Fast binned SAH BVH builder using AVX intrinsics
• Fast binned SAH BVH builder using NEON intrinsics, by wuyakuma
• Spatial Splits (SBVH, Stich et al., 2009) builder, including "unsplitting"
• Wide BVHs (any width) using collapsing
• TLAS builder with instancing and fast TLAS/BLAS traversal, even for 'mixed trees'
• TLAS masking (similar to OptiX), by Romain Augier.
• Support for custom geometry and mixed scenes
• Double-precision binned SAH BVH builder
• Customizable SAH parameters for all builders
• "End-Point Overlap" BVH cost metric ("On Quality Metrics of Bounding Volume Hierarchies", Aila et al., 2013)
• GPU-friendly layouts, including 'Compressed Wide BVH' (CWBVH) for state-of-the-art GPU performance
• Support for custom primitives via callbacks, also in double-precision BVHs
• BVH (de)serialization for most layouts

Besides basic examples demonstrating usage of the library, these more advanced examples are provided:

• Example OpenCL code for GPU TLAS/BLAS traversal (dragon invasion demo, tiny_bvh_gpu2.cpp)
• Example OpenGL / compute shader code for GPU BLAS traversal (tiny_bvh_gl_compute)
• Example TLAS/BLAS application using OpenGL interop (Windows only)
• In the 'external' folder: dx12rt benchmark to compare TinyBVH against DXR.
• In the 'external' folder: Vulkan machine-translation of the dx12rt benchmark.

Advanced / exotic features of the library include:

• BVH optimizer: reduces SAH cost and improves ray tracing performance (Bittner et al., 2013)
• BVH pre-splitting (implementing ideas from a paper by Karras and Aila and explanation by BoyBaykiller)
• Full-Sweep SAH BVH (with support from BoyBaykiller)
• Opacity Micro Map support (as proposed by Gruen et al. in 2020)
• Sphere/BVH collision detection via BVH::IntersectSphere(..)
• Fast AVX2 and NEON ray tracing: Implements the 2017 paper by Fuetterling et al.
• Fast triangle intersection: Implements the 2016 paper by Baldwin & Weber
• 'Watertight' ray/triangle intersection, based on the paper by Woop et al.
• OpenCL traversal example code: Aila & Laine, 4-way quantized, CWBVH
• OpenCL support for macOS, by wuyakuma
• Support for WASM / Emscripten, g++, clang, Visual Studio
• Optional user-defined memory allocation, by Thierry Cantenot
• Vertex array with a custom stride, by David Peicho
• Vertex array with indexing
• 'Bring Your Own Vector Types' (BYOVT), thanks Tijmen Verhoef
• 'Bring Your Own Thread Pool', thanks Wenzel Jakob
• 'Benchmark' tool that times and validates all builders and traversal kernels
• A manual is now available.

The API of the library is stable. Changes may happen but should be limited.

Platforms

TinyBVH is a cross-platform library and should build on any platform that supports C++17 (the '17' bit is for threading). That being said, several platforms are specifically supported:

• x86-64 Windows/Linux: These platforms benefit from highly optimized SSE/AVX/AVX2 traversal kernels.
• OPENCL: Although TinyBVH does not directly use OpenCL, GPU-specific BVHs can be constructed and example code for BLAS/TLAS traversal in OpenCL is provided.
• OpenGL/compute: Example compute shader code for BLAS traversal is also provided.
• DirectX12: Benchmark code is provided to directly compare DXR against TinyBVH.
• Vulkan: Benchmark code is provided to directly compare Vulkan Ray Tracing against TinyBVH.
• ARM_NEON: Efficient BVH construction code is provided for ARM NEON. Several layouts use NEON intrinsics for fast traversal.
• ANDROID: This platform benefits from ARM NEON support as well as aligned memory allocation.
• APPLE: This platform benefits from ARM NEON support, dedicated paths in GPU example code and specialized support in TinyBVH itself.

TinyBVH in the Wild

A list of projects using TinyBVH:

• Remedy's Northlight engine uses TinyBVH in their editor and for baking per-micro-vertex displacements.
• EA SEED's Gigi: Uses TinyBVH for WebGPU ray tracing, "..as fast as when using the DXR api in DX12". Try the demo.
• SideFX Houdini uses TinyBVH.
• wave_tracer by Shlomi Steinberg uses TinyBVH to trace path segments.
• TrenchBroomBFG, by Robert Beckebans. "TinyBVH allows to load bigger glTF 2 maps almost instantly instead of minutes".
• Jon Baker's Icarus Point Cloud visualizer uses TinyBVH to represent geometry.
• The Wonderland Engine for web-based 3D uses TinyBVH for WebGL ray tracing.
• unity-tinybvh: An example implementation for TinyBVH in Unity and a foundation for building compute based raytracing solutions, by Andrew MacIntyre.

TinyBVH Rust bindings

The TinyBVH library can now also be used from Rust, with the Rust bindings provided by David Peicho.

TinyBVH Python bindings

Florent Le Moël created Python bindings for TinyBVH. You can find details in the pytinybvh repository on GitHub.

TinyBVH .NET wrapper

Anders Forsgren provides TinyBVHNet, a .NET wrapper for TinyBVH, targeting net48 and net10.0. Get it via NuGet.

Created or know about other projects? Let me know!

Contribute

TinyBVH received features and bug fixes from 34 contributors so far. Thanks! Feel free to submit PRs; please do so in the development branch for a good workflow.

Contact

Questions, remarks? Contact me at bikker.j@protonmail.com or bikker.j@gmail.com or Bluesky: @jbikker.bsky.social .

License

This library is made available under the MIT license, which starts as follows: "Permission is hereby granted, free of charge, .. , to deal in the Software without restriction". Enjoy. If you are using this work in your research, please cite TinyBVH: Details are available in BibTeX and APA format, see the 'About' section for this repo on GitHub.

Acknowledgement

The development of this library is supported by an AMD hardware grant.

AI-use Statement

The development of TinyBVH involves the use of AI tools. Specifically, AI is used to steer refactoring, where it recommends improvements which are then manually processed. AI is also occasionally used to translate between ISAs and APIs, e.g. between x86-64 and NEON and between DirectX12 and Vulkan.

Image credit: Tamara Heeffer, IGAD / Breda University

Image credit: Hesam Ghadimi, IGAD / Breda University