Morton Encoding

abstract type MortonAlgorithm

Morton encoding algorithms; a new alg needs to implement:

morton_encode!(bounding_volumes, alg, options)
eltype(alg) -> Type

At the moment, only the canonical DefaultMortonAlgorithm is exported; we are prototyping extended Morton encoding algorithms as well to ideally improve BVH quality and reduce the number of contact checks during traversal.

struct DefaultMortonAlgorithm{M<:Union{UInt16, UInt32, UInt64}, T} <: ImplicitBVH.MortonAlgorithm

Canonical Morton encoding algorithm using bit interleaving.

The Morton code type is specified by the exemplar parameter; supported types are UInt16, UInt32 and UInt64.

If compute_extrema=false and mins / maxs are defined, they will not be computed from the distribution of bounding volumes; useful if you have a fixed simulation box, for example. You must ensure that no bounding volume centers will touch or be outside these bounds, otherwise logically incorrect results will be silently produced.

Examples

Use 32-bit Morton encoding:

using ImplicitBVH
options = BVHOptions(morton=DefaultMortonAlgorithm(UInt32))

morton_encode!(
    bounding_volumes::AbstractVector{<:BoundingVolume},
    options=BVHOptions(),
)

Encode each each bounding volume (given as BoundingVolume) into Morton codes following the algorithm set in options.alg; the Morton codes are updated inline in the morton field of each bounding volume.

morton_encode_single(centre, mins, maxs, U::MortonUnsignedType=UInt32)

Return Morton code for a single 3D position centre scaled uniformly between mins and maxs. Works transparently for SVector, Vector, etc. with eltype UInt16, UInt32 or UInt64.

morton_scaling(::Type{UInt16}) = 2^5
morton_scaling(::Type{UInt32}) = 2^10
morton_scaling(::Type{UInt64}) = 2^21

Exclusive maximum number possible to use for 3D Morton encoding for each type.

morton_split3(v::UInt16)
morton_split3(v::UInt32)
morton_split3(v::UInt64)

Shift a number's individual bits such that they have two zeros between them.

bounding_volumes_extrema(bounding_volumes)

Compute exclusive lower and upper bounds in iterable of bounding volumes, e.g. Vector{BBox}.

relative_precision(::Type{Float16}) = 1e-2
relative_precision(::Type{Float32}) = 1e-5
relative_precision(::Type{Float64}) = 1e-14

Relative precision value for floating-point types.