Morton Encoding

ImplicitBVH.MortonAlgorithm — Type

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.

source

ImplicitBVH.DefaultMortonAlgorithm — Type

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))

source

ImplicitBVH.morton_encode! — Function

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.

source

ImplicitBVH.morton_encode_single — Function

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.

source

ImplicitBVH.morton_scaling — Function

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.

source

ImplicitBVH.morton_split3 — Function

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.

source

ImplicitBVH.bounding_volumes_extrema — Function

bounding_volumes_extrema(bounding_volumes)

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

source

ImplicitBVH.relative_precision — Function

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.

source