EBGeometry::SFC Namespace Reference

Namespace for space-filling curves (SFCs) used to linearly order 3D grid cells. More...

Classes
struct	Hilbert
	Implementation of the 3D Hilbert space-filling curve. More...
struct	Morton
	Implementation of the Morton SFC. More...
struct	Nested
	Implementation of a nested index SFC. More...

Typedefs
using	Code = uint64_t
	Alias for SFC code.
using	Index = std::array< unsigned int, 3 >
	Alias for 3D cell index.

Functions
template<class T >
std::vector< Index >	computeBins (const std::vector< Vec3T< T > > &a_points) noexcept
	Bin a set of points into the space-filling curve's integer grid, normalizing by their own bounding range.
template<class Curve = Morton, class T >
std::vector< uint32_t >	order (const std::vector< Vec3T< T > > &a_points) noexcept
	Return the index permutation that orders a_points along a space-filling curve.

Detailed Description

Namespace for space-filling curves (SFCs) used to linearly order 3D grid cells.

A space-filling curve maps a 3D grid index (Index, three unsigned integers each in [0, ValidSpan]) to a single 64-bit code (Code) and back, such that cells that are close together in space tend to also be close together in code order. This is used to build spatially coherent orderings of primitives (e.g. TreeBVH::bottomUpSortAndPartition<S>(), which sorts primitives by S::encode(...) of their binned cell index before partitioning into a tree).

Every SFC in this namespace (e.g. Morton, Nested, Hilbert) implements exactly two static member functions:

[[nodiscard]] static Code  encode(const Index& a_point) noexcept;
[[nodiscard]] static Index decode(const Code& a_code) noexcept;

decode(encode(p)) must reproduce p for every p with components in [0, ValidSpan]; encode() need not be injective outside that range (out-of-range components are a precondition violation, not a defined-but-lossy encoding). Any new SFC struct added to this namespace, or supplied by a caller as the template argument to code that is templated on an SFC (such as TreeBVH::bottomUpSortAndPartition<S>()), must implement both functions with these exact signatures to be usable as a drop-in replacement.

Function Documentation

computeBins()

template<class T >

std::vector< Index > EBGeometry::SFC::computeBins ( const std::vector< Vec3T< T > > &  a_points )

inlinenoexcept

Bin a set of points into the space-filling curve's integer grid, normalizing by their own bounding range.

Converts real-valued points into SFC::Index values suitable for SFC::Morton::encode() or SFC::Nested::encode(). The binning itself is curve-independent – every curve grids the same way; only the subsequent encode() differs – so this takes no curve type (see order() for the curve-parameterized ordering built on top of it). If every point coincides on some axis (a planar cloud or duplicate points), that axis's normalization divisor would be zero; it is clamped to 1 (the numerator is also exactly zero there for every point, so any nonzero divisor yields the same, correct bin index of 0), avoiding a divide-by-zero.

Template Parameters

T	Floating-point precision.

Parameters

[in]

a_points

Points to bin (e.g. bounding-volume centroids, or a raw point cloud).

Returns

One SFC::Index per input point, in the same order.

order()

template<class Curve = Morton, class T >

std::vector< uint32_t > EBGeometry::SFC::order ( const std::vector< Vec3T< T > > &  a_points )

inlinenoexcept

Return the index permutation that orders a_points along a space-filling curve.

Bins the points (computeBins), encodes each cell with Curve::encode(), and returns the indices sorted by ascending code – so a_points[result[0]], a_points[result[1]], ... walk the curve. This is the one-call form of the "bin, encode, sort" pattern; the points themselves are not moved or copied. Curve is a pure template parameter (encode() is static, so no instance is needed) and comes first so it can be named while T is still deduced from a_points – e.g. order<SFC::Nested>(points), or just order(points) for the Morton default.

Template Parameters

Curve	Space-filling curve type (SFC::Morton, SFC::Nested, ...). Defaults to SFC::Morton.
T	Floating-point precision (deduced from a_points).

Parameters

[in]

a_points

Points to order.

Returns

Indices into a_points, sorted by ascending SFC code.