ImplicitBVH.jl Documentation

struct BVH{I<:Integer, VS<:(AbstractVector), VN<:(AbstractVector), VL<:(AbstractVector)}

Implicit bounding volume hierarchy constructed from an iterable of some geometric primitives' (e.g. triangles in a mesh) bounding volumes forming the ImplicitTree leaves. The leaves and merged nodes above them can have different types - e.g. BSphere{Float64} for leaves merged into larger BBox{Float64}.

The initial geometric primitives are sorted according to their Morton-encoded coordinates; the encoding algorithm is specified within the BVHOptions.

Finally, the tree can be incompletely-built up to a given built_level and later start contact detection downwards from this level, e.g.:

Implicit tree from 5 bounding volumes - i.e. the real leaves

Tree Level          Nodes & Leaves               Build Up    Traverse Down
    1                     1                         Ʌ              |
    2             2               3                 |              |
    3         4       5       6        7v           |              |
    4       8   9   10 11   12 13v  14v  15v        |              V
            -------Real------- ---Virtual---

Methods

# Normal constructor which builds BVH
BVH(
    bounding_volumes::AbstractVector{L},
    node_type::Type{N}=BBox{Float32};
    built_level::Union{Integer, AbstractFloat}=1,
    cache::Union{Nothing, BVH}=nothing,
    options=BVHOptions(),
) where {L, N}

Fields

• built_level::Int - level up to which the BVH tree has been built
• tree::ImplicitTree{I <: Integer}
• skips::VS <: AbstractVector - vector of skips (number of indices to jump in memory, per level)
• nodes::VN <: AbstractVector - vector of bounding volumes for the internal nodes above the leaves
• leaves::VL <: AbstractVector - vector of sorted BoundingVolume for the leaves

Examples

Simple usage with bounding spheres as leaves (defaults include BBox{Float32} nodes, UInt32 Morton codes, and Int32 indices):

using ImplicitBVH
using ImplicitBVH: BSphere

# Generate some simple bounding spheres
bounding_spheres = [
    BSphere([0., 0., 0.], 0.5),
    BSphere([0., 0., 1.], 0.6),
    BSphere([0., 0., 2.], 0.5),
    BSphere([0., 0., 3.], 0.4),
    BSphere([0., 0., 4.], 0.6),
]

# Build BVH
bvh = BVH(bounding_spheres)

# Traverse BVH for contact detection
traversal = traverse(bvh)
@show traversal.contacts;
;

# output
traversal.contacts = Tuple{Int32, Int32}[(1, 2), (2, 3), (4, 5)]

Using Float32 bounding spheres for leaves, Float32 bounding boxes for nodes above, UInt64 Morton codes and Int64 indices:

using ImplicitBVH
using ImplicitBVH: BBox, BSphere

# Generate some simple bounding spheres
bounding_spheres = [
    BSphere{Float32}([0., 0., 0.], 0.5),
    BSphere{Float32}([0., 0., 1.], 0.6),
    BSphere{Float32}([0., 0., 2.], 0.5),
    BSphere{Float32}([0., 0., 3.], 0.4),
    BSphere{Float32}([0., 0., 4.], 0.6),
]

# Build BVH
options = BVHOptions(index=Int64, morton=DefaultMortonAlgorithm(UInt64))
bvh = BVH(bounding_spheres, BBox{Float32}, options=options)

# Traverse BVH for contact detection
traversal = traverse(bvh)
@show traversal.contacts;
;

# output
traversal.contacts = [(1, 2), (2, 3), (4, 5)]

Build BVH up to level 2 and start traversing down from level 3, reusing the previous traversal cache:

bvh = BVH(bounding_spheres, BBox{Float32}, built_level=2)
traversal = traverse(bvh, start_level=3, cache=traversal)

Reuse previous BVH memory for a new BVH (i.e. the nodes, but not the leaves, which are modified in-place):

bvh = BVH(bounding_spheres, BBox{Float32}, cache=bvh)

Move previous BVH leaves / bounding volumes to new locations then rebuild BVH in-place:

for ibv in eachindex(bvh.leaves)
    bvh.leaves[ibv] = BoundingVolume(
        bvh.leaves[ibv].volume,             # Update if needed
        bvh.leaves[ibv].index,              # Your simulation indices, reported in contacts
        bvh.leaves[ibv].morton,             # Will be recomputed when rebuilding
    )
end
bvh = BVH(bvh.leaves, BBox{Float32}, cache=bvh)

Manually wrap bounding volumes into BoundingVolume structs before building BVH:

using ImplicitBVH
using ImplicitBVH: BoundingVolume, BSphere, BBox

# Generate some simple bounding spheres with explicit simulation indices (will be reported in
# contacts; allows different indexing strategies) and dummy morton codes (will be computed when
# building the BVH)
bounding_spheres = [
    BoundingVolume(BSphere{Float32}([0., 0., 1.], 0.6), Int32(1), UInt32(0)),
    BoundingVolume(BSphere{Float32}([0., 0., 2.], 0.5), Int32(2), UInt32(0)),
    BoundingVolume(BSphere{Float32}([0., 0., 0.], 0.5), Int32(3), UInt32(0)),
    BoundingVolume(BSphere{Float32}([0., 0., 3.], 0.4), Int32(4), UInt32(0)),
    BoundingVolume(BSphere{Float32}([0., 0., 4.], 0.6), Int32(5), UInt32(0)),
]

# Build BVH
bvh = BVH(bounding_spheres, BBox{Float32})

# The bounding_spheres was modified in-place, without extra allocations
@show bounding_spheres[1];
;

# output
bounding_spheres[1] = ImplicitBVH.BoundingVolume{ImplicitBVH.BSphere{Float32}, Int32, UInt32}(ImplicitBVH.BSphere{Float32}((0.0f0, 0.0f0, 0.0f0), 0.5f0), 3, 0x06186186)

traverse(
    bvh::BVH, alg::TraversalAlgorithm=LVTTraversal();
    start_level::Int=default_start_level(bvh, alg),
    narrow=(bv1, bv2) -> true,
    cache::Union{Nothing, BVHTraversal}=nothing,
    options=BVHOptions(),
)::BVHTraversal

traverse(
    bvh1::BVH, bvh2::BVH, alg::TraversalAlgorithm=LVTTraversal();
    start_level1::Int=default_start_level(bvh1, alg),
    start_level2::Int=default_start_level(bvh2, alg),
    narrow=(bv1, bv2) -> true,
    cache::Union{Nothing, BVHTraversal}=nothing,
    options=BVHOptions(),
)::BVHTraversal

Traverse bvh downwards from start_level, returning all contacting bounding volume leaves, using the traversal algorithm alg (TraversalAlgorithm). The returned BVHTraversal also contains two buffers that can be reused on future traversals as cache to avoid reallocations.

The optional narrow function can be used to perform a custom narrow-phase test between two bounding volumes bv1 and bv2 before registering a contact. By default, all bounding volume pairs reaching the narrow-phase are considered contacting.

Examples

using ImplicitBVH
using ImplicitBVH: BBox, BSphere

# Generate some simple bounding spheres
bounding_spheres = [
    BSphere{Float32}([0., 0., 0.], 0.5),
    BSphere{Float32}([0., 0., 1.], 0.6),
    BSphere{Float32}([0., 0., 2.], 0.5),
    BSphere{Float32}([0., 0., 3.], 0.4),
    BSphere{Float32}([0., 0., 4.], 0.6),
]

# Build BVH
bvh = BVH(bounding_spheres, BBox{Float32})

# Traverse BVH for contact detection
traversal = traverse(bvh)

# Reuse traversal buffers for future contact detection - possibly with different BVHs
traversal = traverse(bvh, cache=traversal)
@show traversal.contacts;
;

# output
traversal.contacts = Tuple{Int32, Int32}[(1, 2), (2, 3), (4, 5)]

Traverse bvh1 and bvh2 downwards from start_level1 and start_level2, returning all contacting bounding volume leaves:

using ImplicitBVH
using ImplicitBVH: BBox, BSphere

# Generate some simple bounding spheres
bounding_spheres1 = [
    BSphere{Float32}([0., 0., 0.], 0.5),
    BSphere{Float32}([0., 0., 3.], 0.4),
]

bounding_spheres2 = [
    BSphere{Float32}([0., 0., 1.], 0.6),
    BSphere{Float32}([0., 0., 2.], 0.5),
    BSphere{Float32}([0., 0., 4.], 0.6),
]

# Build BVHs
bvh1 = BVH(bounding_spheres1, BBox{Float32})
bvh2 = BVH(bounding_spheres2, BBox{Float32})

# Traverse BVH for contact detection
traversal = traverse(bvh1, bvh2, start_level1=2, start_level2=3)

# Reuse traversal buffers for future contact detection - possibly with different BVHs
traversal = traverse(bvh1, bvh2, cache=traversal)
@show traversal.contacts;
;

# output
traversal.contacts = Tuple{Int32, Int32}[(1, 1), (2, 3)]

traverse_rays(
    bvh::BVH,
    points::AbstractMatrix, directions::AbstractMatrix,
    alg::TraversalAlgorithm=LVTTraversal();
    start_level::Int=1,
    narrow=(bv, p, d) -> true,
    cache::Union{Nothing, BVHTraversal}=nothing,
    options=BVHOptions(),
)::BVHTraversal

Compute the intersections between a set of N rays defined by points (shape (3, N)) and directions (shape, (3, N)), and some bounding volumes inside a bvh. Traverse bvh downwards from start_level, returning all contacting bounding volume leaves, using the traversal algorithm alg (TraversalAlgorithm). The returned BVHTraversal also contains two buffers that can be reused on future traversals as cache to avoid reallocations.

Only forward rays are counted - i.e. the direction matters.

The returned BVHTraversal .contacts field will contain the index pairs (iboundingvolume, iray) following the indices in bvh.leaves and axes(points, 2).

The optional narrow function can be used to perform a custom narrow-phase test between a bounding volume bv, a ray point p and direction d before registering a contact. By default, all bounding volume and ray pairs reaching the narrow-phase are considered contacting.

Examples

using ImplicitBVH
using ImplicitBVH: BBox, BSphere

# Generate some simple bounding spheres
bounding_spheres = [
    BSphere{Float32}([0., 0., 0.], 0.5),
    BSphere{Float32}([0., 0., 1.], 0.6),
    BSphere{Float32}([0., 0., 2.], 0.5),
    BSphere{Float32}([0., 0., 3.], 0.4),
    BSphere{Float32}([0., 0., 4.], 0.6),
]

# Generate two rays, each defined by a point source and direction
points = [
    0.  0 
    0.  0
    -1 -1
]

# One ray passes through all bounding volumes, the other goes downwards and does not
directions = [
    0.  0
    0.  0
    1.  -1
]

# Build BVH
bvh = BVH(bounding_spheres)

# Traverse BVH for contact detection
traversal = traverse_rays(bvh, points, directions)

# Reuse traversal buffers for future contact detection - possibly with different BVHs
traversal = traverse_rays(bvh, points, directions, cache=traversal)
@show traversal.contacts;
;

# output
traversal.contacts = Tuple{Int32, Int32}[(1, 1), (2, 1), (3, 1), (4, 1), (5, 1)]

struct BVHTraversal{C1<:(AbstractVector), C2<:(AbstractVector)}

Collected BVH traversal contacts vector, some stats, plus the two buffers cache1 and cache2 which can be reused for future traversals to minimise memory allocations.

Fields

• start_level1::Int: the level at which the single/pair-tree traversal started for the first BVH.
• start_level2::Int: the level at which the pair-tree traversal started for the second BVH.
• num_checks::Int: the number of contact checks performed during traversal, not always computed.
• num_contacts::Int: the number of contacts found.
• contacts::view(cache_contacts, 1:num_contacts): the contacting pairs found, as a view into cache1.
• cache1::C1{IndexPair} <: AbstractVector: cache of all contacts found (may have greater size; use num_contacts).
• cache2::C2{IndexPair} <: AbstractVector: second cache used, depending on the traversal algorithm.

abstract type TraversalAlgorithm end
struct BFSTraversal <: TraversalAlgorithm end
struct LVTTraversal <: TraversalAlgorithm end

The algorithm used to traverse one / two BVHs for contact detection and ray-tracing.

In general, use LVTTraversal (the default) unless you use few CPU threads and memory usage is not a bottleneck.

BFSTraversal

Simultaneous breadth-first search traversal - nodes are paired level-by-level:

• Theoretical minimum number of contact checks.
• Much higher memory usage (spiking at around 10-20x the final number of contacts found).
• Faster on CPUs with few threads, but slightly worse scalability.
• More kernel launches (thread launches or enqueues - one per level).

LVTTraversal

Leaf-vs-tree traversal - independent traversal of leaves in one BVH against the entire other BVH:

• More contact checks (around 10x more than BFSTraversal).
• Much lower memory usage (only the final number of contacts found, plus 4/8 bytes per CPU/GPU thread).
• Excellent cache locality - can yield ~17 processor cycles per contact check.
• Much faster on GPUs (about 4x faster than BFSTraversal), with better scalability due to improved memory and work divergence.
• Fewer kernel launches (thread launches or enqueues = 2 passes + accumulate).
• About 2-3x slower on CPUs when single-threaded, but ideal scalability with threads.

default_start_level(bvh::BVH, alg::TraversalAlgorithm)::Int

Compute the default start level for BVH traversal given the BVH and the traversal algorithm.

const IndexPair{I} = Tuple{I, I}

Alias for a tuple of two indices representing e.g. a contacting pair.