Namespace for space-filling curves (SFCs) used to linearly order 3D grid cells.
More...
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;
uint64_t Code
Alias for SFC code.
Definition EBGeometry_SFC.hpp:50
Fixed-size array with host- and device-callable members.
Definition EBGeometry_Array.hpp:33
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.
template<class T >
| std::vector< Index > EBGeometry::SFC::computeBins |
( |
const std::vector< Vec3T< T > > & |
a_points | ) |
|
|
inline |
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). The grid cells are cubes, sized so that the longest extent of the points spans the whole grid; a flat cloud therefore occupies only a thin slab of bins along its short axis, and the curve keeps following distance. If the points coincide, or their extent is too small for a cell size that is a normal floating-point number, every point gets bin 0 on every axis.
- Template Parameters
-
| T | Floating-point precision. |
- Parameters
-
| [in] | a_points | Points to bin (e.g. bounding-volume centroids, or a raw point cloud). Every coordinate must be finite; this is checked in every build. |
- Returns
- One SFC::Index per input point, in the same order.
template<class Curve = Morton, class T >
| std::vector< uint32_t > EBGeometry::SFC::order |
( |
const std::vector< Vec3T< T > > & |
a_points | ) |
|
|
inline |
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
-
- Parameters
-
| [in] | a_points | Points to order. |
- Returns
- Indices into a_points, sorted by ascending SFC code.
