ImplicitBVH.jl Documentation

struct BVH{VN<:(AbstractVector), VL<:(AbstractVector), VO<:(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 unsigned integer type used for the Morton encoding can be chosen between Union{UInt16, UInt32, UInt64}.

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

function BVH(
    bounding_volumes::AbstractVector{L},
    node_type::Type{N}=L,
    morton_type::Type{U}=UInt,
    built_level::Integer=1;
    num_threads=Threads.nthreads(),
) where {L, N, U <: MortonUnsigned}

Fields

• tree::ImplicitTree{Int}
• nodes::VN <: AbstractVector
• leaves::VL <: AbstractVector
• order::VO <: AbstractVector
• built_level::Int

Examples

Simple usage with bounding spheres and default 64-bit types:

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 = [(1, 2), (2, 3), (4, 5)]

Using Float32 bounding spheres for leaves, Float32 bounding boxes for nodes above, and UInt32 Morton codes:

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}, UInt32)

# 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}, UInt32, 2)
traversal = traverse(bvh, 3, traversal)

traverse(
    bvh::BVH,
    start_level::Int=default_start_level(bvh),
    cache::Union{Nothing, BVHTraversal}=nothing;
    num_threads=Threads.nthreads(),
)::BVHTraversal

Traverse bvh downwards from start_level, returning all contacting bounding volume leaves. The returned BVHTraversal also contains two contact buffers that can be reused on future traversals.

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}, UInt32)

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

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

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

traverse(
    bvh1::BVH,
    bvh2::BVH,
    start_level1::Int=default_start_level(bvh1),
    start_level2::Int=default_start_level(bvh2),
    cache::Union{Nothing, BVHTraversal}=nothing;
    num_threads=Threads.nthreads(),
)::BVHTraversal

Return all the bvh1 bounding volume leaves that are in contact with any in bvh2. The returned BVHTraversal also contains two contact buffers that can be reused on future traversals.

Examples

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}, UInt32)
bvh2 = BVH(bounding_spheres2, BBox{Float32}, UInt32)

# Traverse BVH for contact detection
traversal = traverse(bvh1, bvh2, default_start_level(bvh1), default_start_level(bvh2))

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

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

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 total number of contact checks done.
• num_contacts::Int: the number of contacts found.
• contacts::view(cache1, 1:num_contacts): the contacting pairs found, as a view into cache1.
• cache1::C1{IndexPair} <: AbstractVector: first BVH traversal buffer.
• cache2::C2{IndexPair} <: AbstractVector: second BVH traversal buffer.

default_start_level(bvh::BVH)::Int
default_start_level(num_leaves::Integer)::Int

Compute the default start level when traversing a single BVH tree.

struct Tuple{Int64, Int64}

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