Access or reproduce the leaf permutation?

[weymouth]

Thanks for sharing this package. It looks nice and the speeds you report are impressive.

I am working on a boundary element method and would love to use this package to accelerate evaluations given large STL geometries, similar to a Barnes-Hut method used for N-body simulations. This would involve aggregating properties from the STL faces up to the nodes created in the ImplicitTree. However, the leaves in the BVH are sorted, meaning they won't line up with my original panel vector.

Is there a way to map these back to their original ordering, or to reproduce the permutation you apply to the leaves to my panel vector?

Thanks,
Gabe

[weymouth]

I guess I could define a wrapper for a BV

struct IndexedBV{T}
  bv::T
  idx::Int
end
BBox{T}(x::IndexedBV) where {T} = BBox{T}(x.bv)

and then use BVH.leaves.idx to figure out where everything has moved.

[anicusan]

Hi @weymouth , thank you - we're also using it for particulate simulations with STL meshes for contact resolution acceleration.

In previous versions, we weren't sorting the bounding volumes inline; we were storing an explicit "order" as returned by sortperm. Now we wrap the bounding volumes in the BoundingVolume struct which has the index field - this is user-defined, and you can use it to store the element ID in your simulation to map it back; traverse also returns IndexPairs of that index field. Even though the BVH.leaves field is sorted, you can loop over it and access the .index to process your simulated elements.

Sorting inline has multiple benefits: reduced memory use, sort is faster than sortperm, and, if your elements move during the simulation and you have to rebuild the BVH starting from a previous one, sort can naturally become faster for almost-sorted elements - a way to exploit frame coherence.

[weymouth]

Sorry! I didn't realize from the examples that was the input index. I confirmed with:

using ImplicitBVH
using ImplicitBVH: BBox, BSphere

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

# Build BVH
bvh = BVH(bounding_spheres)
bvh.leaves

# output
5-element Vector{ImplicitBVH.BoundingVolume{BSphere{Float32}, Int32, UInt32}}:
 ImplicitBVH.BoundingVolume{BSphere{Float32}, Int32, UInt32}(BSphere{Float32}((0.0f0, 0.0f0, 0.0f0), 0.5f0), 3, 0x06186186)
 ImplicitBVH.BoundingVolume{BSphere{Float32}, Int32, UInt32}(BSphere{Float32}((0.0f0, 0.0f0, 1.0f0), 0.6f0), 5, 0x063cf3cf)
 ImplicitBVH.BoundingVolume{BSphere{Float32}, Int32, UInt32}(BSphere{Float32}((0.0f0, 0.0f0, 2.0f0), 0.5f0), 1, 0x073cf3cf)
 ImplicitBVH.BoundingVolume{BSphere{Float32}, Int32, UInt32}(BSphere{Float32}((0.0f0, 0.0f0, 3.0f0), 0.4f0), 4, 0x0e3cf3cf)
 ImplicitBVH.BoundingVolume{BSphere{Float32}, Int32, UInt32}(BSphere{Float32}((0.0f0, 0.0f0, 4.0f0), 0.6f0), 2, 0x0f3cf3cf)

which shows it's working great!
Thanks for anticipating what I needed already ;-)