template struct mola::index3d_hash

Overview

Hash functor and comparator for index3d_t, usable with both std::unordered_map / tsl::robin_map (hash) and std::map (comparator).

The hash function is the optimized spatial hash from: Teschner et al., “Optimized spatial hashing for collision detection of

deformable objects”, VMV 2003, which mixes the three integer coordinates with large prime multipliers, followed by a splitmix64 finalizer.

The finalizer is not cosmetic. tsl::robin_map, the container these keys are used with, indexes its buckets with the low bits of the hash, and the low bits of a sum of odd-prime multiples depend on very few input bits, so grid-aligned keys cluster. Mixing costs two multiplies and pays for itself: on a 4 M-key voxel set, the longest bucket chain drops from 14 to 8 and lookups get about 30% faster.

The operator()(k1,k2) overload provides a strict weak ordering on index3d_t (X-primary, Y-secondary, Z-tertiary) for std::map.

#include <index3d_t.h>

template <typename cell_coord_t = int32_t>
struct index3d_hash
{
    // methods

    std::size_t operator () (const index3d_t<cell_coord_t>& k) const;
    bool operator () (const index3d_t<cell_coord_t>& k1, const index3d_t<cell_coord_t>& k2) const;
};

Methods

std::size_t operator () (const index3d_t<cell_coord_t>& k) const

Hash operator for unordered maps:

bool operator () (const index3d_t<cell_coord_t>& k1, const index3d_t<cell_coord_t>& k2) const

k1 < k2? for std::map containers