ImplicitBVH.jl Documentation

struct BVH{I<:Integer, VN<:(AbstractVector), VL<:(AbstractVector), VM<:(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---

Note: in order to not mutate the leaves (you may store them somewhere else, and this avoids making a copy), we save the sorted order of the BVH leaves inside the order field.

Methods

# Normal constructor which builds BVH
BVH(
    bounding_volumes::AbstractVector{L},
    node_type::Type{N}=L,
    morton_type::Type{U}=UInt32,
    built_level=1,
    cache::Union{Nothing, BVH}=nothing;
    options=BVHOptions(),
) where {L, N, U <: MortonUnsigned}

Fields

• tree::ImplicitTree{I <: Integer}
• nodes::VN <: AbstractVector
• leaves::VL <: AbstractVector
• mortons::VM <: 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 = Tuple{Int32, Int32}[(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 = Tuple{Int32, Int32}[(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)

Reuse previous BVH memory for a new BVH (specifically, the nodes, mortons, and order vectors, but not the leaves):

bvh = BVH(bounding_spheres, BBox{Float32}, UInt32, 1, bvh)

traverse(
    bvh::BVH,
    start_level::Int=default_start_level(bvh),
    cache::Union{Nothing, BVHTraversal}=nothing;
    options=BVHOptions(),
)::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 = Tuple{Int32, Int32}[(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;
    options=BVHOptions(),
)::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 = Tuple{Int32, Int32}[(1, 1), (2, 3)]

traverse_rays(
    bvh::BVH,
    points::AbstractArray,
    directions::AbstractArray,
    start_level::Int=1,
    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.

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

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

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

# 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, 2, 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 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.

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

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