Shape kernels compare 3D point clouds of any size, with no correspondence between points: Chamfer, Hausdorff, Wasserstein-Procrustes, and Gromov-Wasserstein. Each cloud is packed once, centered and rotated onto its principal axes, and every kernel scores a list of row packs against a list of column packs. Packs are built one cloud at a time, so a caller passes whatever packs it holds as an array of pointers.
nk_f32_t const query[] = {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}; // 4 points
nk_f32_t const candidate[] = {0, 0, 0, 0, 2, 0, 0, 0, 2, 2, 0, 0, 1, 1, 1}; // 5 points
nk_size_t const alignment = nk_default_alignment_k; // `aligned_alloc` sizes are whole multiples of it
nk_size_t query_bytes = 0, candidate_bytes = 0;
nk_shapes_pack_size_f32_best(4, capabilities, &query_bytes);
nk_shapes_pack_size_f32_best(5, capabilities, &candidate_bytes);
void *query_packed = aligned_alloc(alignment, (query_bytes + alignment - 1) / alignment * alignment);
void *candidate_packed = aligned_alloc(alignment, (candidate_bytes + alignment - 1) / alignment * alignment);
nk_shapes_pack_f32_best(query, 4, query_packed, capabilities, NULL);
nk_shapes_pack_f32_best(candidate, 5, candidate_packed, capabilities, NULL);
void const *rows[] = {query_packed}, *columns[] = {candidate_packed};
nk_f64_t chamfer = 0, procrustes = 0;
nk_f32_t rotation[9]; // takes the candidate onto the query, through the centroids in the headers
nk_size_t chamfer_bytes = 0;
nk_chamfers_workspace_size_f32_best(4, 5, capabilities, &chamfer_bytes);
void *chamfer_workspace = aligned_alloc(alignment, (chamfer_bytes + alignment - 1) / alignment * alignment);
nk_chamfers_packed_f32_best(rows, 1, columns, 1, &chamfer, sizeof(nk_f64_t), rotation, INFINITY, chamfer_workspace,
chamfer_bytes, capabilities, NULL);
nk_size_t workspace_bytes = 0;
nk_wassersteinprocrustes_workspace_size_f32_best(4, 5, capabilities, &workspace_bytes);
void *workspace = aligned_alloc(alignment, (workspace_bytes + alignment - 1) / alignment * alignment);
nk_wassersteinprocrustes_packed_f32_best(rows, 1, columns, 1, &procrustes, sizeof(nk_f64_t), NULL, workspace,
workspace_bytes, capabilities, NULL);
nk_f64_t query_radius = 0, candidate_radius = 0; // |query_radius - candidate_radius| bounds Hausdorff from below
nk_shapes_packed_shape_f32_best(query_packed, NULL, NULL, NULL, NULL, NULL, &query_radius, capabilities, NULL);
nk_shapes_packed_shape_f32_best(candidate_packed, NULL, NULL, NULL, NULL, NULL, &candidate_radius, capabilities, NULL);
nk_f32_t restored[15]; // the candidate again, within one rounding into `f32`
nk_shapes_unpack_f32_best(candidate_packed, restored, capabilities, NULL);A pack is opaque: nk_shapes_packed_shape_* reads its points, centroid, principal frame as a quaternion, scale, descending spreads, and largest radius, and nk_shapes_unpack_* restores its cloud.
The spreads and radius bound Wasserstein-Procrustes and Hausdorff from below for free, the way vector norms bound dot products.
Gromov-Wasserstein and Wasserstein-Procrustes take a caller’s workspace, since a transport plan depends on both clouds and fits in neither pack.
nk_shapes_pack_normalized_* takes the same arguments and also divides each cloud by its RMS distance from the centroid, which it keeps as the scale, so every kind ignores size as well as pose.
Each kind compares the packed coordinates, so mixing absolute and normalized packs in one call is the caller’s choice.
Between normalized packs, a rotation takes column cloud b onto row cloud a as aᵢ ≈ (scale_a / scale_b) × R × (bⱼ − b̄) + ā.
In C++, nk::shapes_packed owns many packs in one allocation and exposes the pointer array, and make_normalized packs them normalized:
nk::f32_t const query[] = {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1};
nk::f32_t const candidate[] = {0, 0, 0, 0, 2, 0, 0, 0, 2, 2, 0, 0, 1, 1, 1};
std::span<nk::f32_t const> clouds[] = {query, candidate};
auto [packs, status] = nk::shapes_packed<nk::f32_t>::make(clouds);
nk::f64_t distances[4];
status = nk::hausdorffs_packed<nk::f32_t>(packs.data(), 2, packs.data(), 2, distances, 2 * sizeof(nk::f64_t), nullptr,
nk::f64_t::positive_infinity());shapes_packedOwning, move-only set of packed clouds, the operand every many-to-many kernel takes.14template <shapes_dtype value_type_,
typename allocator_type_ = aligned_allocator<char>>
class shapes_packedOne allocation holds the table of pack pointers, then the packs back to back, each on an nk_default_alignment_k boundary, so data() passes straight to every shape kernel.
allocator_typeThe allocator of the packs' one block, which uses-allocator construction looks up.using allocator_type = allocator_type_;pack_size_kernel_tOne backend's nk_shapes_pack_size_* kernel.using pack_size_kernel_t = nk_status_t(*)(nk_size_t, nk_size_t *);pack_kernel_tOne backend's plain or normalized nk_shapes_pack kernel.using pack_kernel_t = nk_status_t(*)(typename value_type_::raw_t const *, nk_size_t, void *, nk_stream_t);shapes_packedshapes_packed() noexcept=default;shapes_packed(allocator_type_ const & alloc) noexcept;shapes_packed(shapes_packed && o) noexcept;shapes_packed(shapes_packed const &)=delete;~shapes_packed~shapes_packed() noexcept;operator=shapes_packed & operator=(shapes_packed && o) noexcept;shapes_packed & operator=(shapes_packed const &)=delete;dataThe table of pack pointers the kernels take.void const *const * data() const noexcept;operator[]The pack of cloud index.void const * operator[](std::size_t index) const noexcept;sizeThe number of packed clouds.std::size_t size() const noexcept;pointsThe points in cloud index.std::size_t points(std::size_t index) const noexcept;max_pointsThe largest cloud, which sizes the transport workspaces.std::size_t max_points() const noexcept;get_allocatorThe allocator the packs came from, so a replacement can be packed from the same one.allocator_type get_allocator() const noexcept;makePacks every cloud of clouds, each [points,3] interleaved.expected<shapes_packed> make(
std::span<std::span<value_type_ const> const> clouds,
allocator_type_ alloc = {},
nk_capability_t capabilities = default_capabilities()) noexcept;expected<shapes_packed> make(
std::span<std::span<value_type_ const> const> clouds,
allocator_type_ alloc,
pack_size_kernel_t pack_size,
pack_kernel_t pack) noexcept;Packs every cloud like make, through one backend's kernels instead of a capability mask, such as nk_shapes_pack_size_f32_serial and nk_shapes_pack_f32_serial.
clouds | in | The point clouds to pack, one pack per cloud. |
|---|---|---|
alloc | in | Source of the packs' blocks. |
capabilities | in | Capabilities to pack with; measure with the same ones. |
pack_size | in | Measures one pack; pair it with pack. |
pack | in | Packs one cloud on the CPU, with a null stream; a normalized one packs like make_normalized. |
The packs.
unexpected_dimensions_k A cloud's length is not a multiple of 3.missing_kernel_kmake_normalizedPacks every cloud like make, each divided by its RMS distance from the centroid.expected<shapes_packed> make_normalized(
std::span<std::span<value_type_ const> const> clouds,
allocator_type_ alloc = {},
nk_capability_t capabilities = default_capabilities()) noexcept;shapes_pack_sizeReturns the bytes a pack of points takes.template <shapes_dtype in_type_>
expected<std::size_t> shapes_pack_size(
std::size_t points,
nk_capability_t capabilities = default_capabilities()) noexcept;points | in | Number of points in the cloud. |
|---|---|---|
capabilities | in | Capabilities to pick from, or zero for the layout of shapes/serial.h. |
shapes_packPacks one cloud: centers it, rotates it onto its principal axes, and keeps its constants.template <shapes_dtype in_type_, typename math_type_ = typename in_type_::shapes_distance_t>
status_t shapes_pack(
typename in_type_::raw_t const *points,
std::size_t count,
void *packed,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;points | in | The cloud, count × 3 interleaved values. |
|---|---|---|
count | in | Number of points in the cloud. |
packed | out | At least shapes_pack_size bytes, aligned to nk_default_alignment_k. |
capabilities | in | Capabilities to pick from, or zero for the template in math_type_. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
shapes_pack_normalizedPacks one cloud like shapes_pack, also dividing it by its RMS distance from the centroid, which the pack keeps as its scale, or by 1 when the cloud has no spread.template <shapes_dtype in_type_, typename math_type_ = typename in_type_::shapes_distance_t>
status_t shapes_pack_normalized(
typename in_type_::raw_t const *points,
std::size_t count,
void *packed,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;shapes_packed_shapeReads a pack's points and constants, skipping every null output.template <shapes_dtype in_type_>
status_t shapes_packed_shape(
void const *packed,
std::size_t *points,
typename in_type_::shapes_distance_t *centroid,
typename in_type_::shapes_distance_t *frame,
typename in_type_::shapes_distance_t *scale,
typename in_type_::shapes_distance_t *spreads,
typename in_type_::shapes_distance_t *max_radius,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;packed | in | The pack to read. |
|---|---|---|
points | out | Null, or the number of 3D points. |
centroid | out | Null, or the 3 coordinates of the mean input point. |
frame | out | Null, or the unit quaternion (x, y, z, w) of 𝑄. |
scale | out | Null, or what the rotated inputs were divided by: their RMS distance from the centroid, or 1. |
spreads | out | Null, or the 3 descending eigenvalues of the packed points' second moments. |
max_radius | out | Null, or the largest packed point norm. |
capabilities | in | Capabilities to pick from, or zero for the layout of shapes/serial.h. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
shapes_unpackRestores a pack's cloud as x = scale × 𝑄ᵀ × x′ + centroid, rounded once into in_type_.template <shapes_dtype in_type_, typename math_type_ = typename in_type_::shapes_distance_t>
status_t shapes_unpack(
void const *packed,
typename in_type_::raw_t *points,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;packed | in | The pack to restore the cloud from. |
|---|---|---|
points | out | The cloud, as many × 3 interleaved values as the pack holds points. |
capabilities | in | Capabilities to pick from, or zero for the template in math_type_. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
rmsds_packedSuperposed RMSDs between every row pack and every column pack of equally many points.template <shapes_dtype in_type_>
status_t rmsds_packed(
void const *const *a_packed,
std::size_t rows,
void const *const *b_packed,
std::size_t columns,
typename in_type_::shapes_distance_t *results,
std::size_t results_stride,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;a_packed | in | The row packs, one per row cloud. |
|---|---|---|
rows | in | Number of row packs. |
b_packed | in | The column packs, one per column cloud. |
columns | in | Number of column packs. |
results | out | The [rows,columns] distances, results_stride bytes apart. |
results_stride | in | Bytes between the rows of results. |
capabilities | in | Capabilities to pick from. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
misaligned_kunexpected_dimensions_k The packs differ in points.missing_kernel_khausdorffs_packedHausdorff distances between every row and every column pack, the best of 8 axis flips.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t, typename rotation_type_ = f32_t>
status_t hausdorffs_packed(
void const *const *a_packed,
std::size_t rows,
void const *const *b_packed,
std::size_t columns,
distance_type_ *results,
std::size_t results_stride,
std::type_identity_t<rotation_type_> *rotations,
std::type_identity_t<distance_type_> limit,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;a_packed | in | The row packs, one per row cloud. |
|---|---|---|
rows | in | Number of row packs. |
b_packed | in | The column packs, one per column cloud. |
columns | in | Number of column packs. |
results | out | The [rows,columns] distances, results_stride bytes apart. |
results_stride | in | Bytes between the rows of results. |
rotations | out | Null, or the [rows,columns,3,3] rotations taking each column cloud onto each row cloud through the centroids. |
limit | in | Distances up to it are exact; past it, a pair may stop early and report a lower bound that also lies past it, with that bound's flip in rotations. Infinity scores all. |
capabilities | in | Capabilities to pick from, or 0 for the template in distance_type_. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
chamfers_packedChamfer distances between every row pack and every column pack, the best of 8 axis flips.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t, typename rotation_type_ = f32_t>
status_t chamfers_packed(
void const *const *a_packed,
std::size_t rows,
void const *const *b_packed,
std::size_t columns,
distance_type_ *results,
std::size_t results_stride,
std::type_identity_t<rotation_type_> *rotations,
std::type_identity_t<distance_type_> limit,
void *workspace,
std::size_t workspace_bytes,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;a_packed | in | The row packs, one per row cloud. |
|---|---|---|
rows | in | Number of row packs. |
b_packed | in | The column packs, one per column cloud. |
columns | in | Number of column packs. |
results | out | The [rows,columns] distances, results_stride bytes apart. |
results_stride | in | Bytes between the rows of results. |
rotations | out | Null, or the [rows,columns,3,3] rotations taking each column cloud onto each row cloud through the centroids. |
limit | in | Distances up to it are exact; past it, a pair may stop early and report a lower bound that also lies past it, with that bound's flip in rotations. Infinity scores all. |
workspace | inout | Scratch of workspace_bytes, as chamfers_workspace_size reports. |
workspace_bytes | in | The bytes of workspace. |
capabilities | in | Capabilities to pick from, or 0 for the template in distance_type_. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
chamfers_workspace_sizeReturns the workspace bytes of chamfers_packed between clouds of up to row_points and column_points points.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t>
expected<std::size_t> chamfers_workspace_size(
std::size_t row_points,
std::size_t column_points,
nk_capability_t capabilities = default_capabilities()) noexcept;row_points | in | Most points in any row cloud. |
|---|---|---|
column_points | in | Most points in any column cloud. |
capabilities | in | Capabilities to pick from, or 0 for the template in distance_type_. |
wassersteinprocrustes_workspace_sizeReturns the workspace bytes of wassersteinprocrustes_packed between clouds of up to row_points and column_points points.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t>
expected<std::size_t> wassersteinprocrustes_workspace_size(
std::size_t row_points,
std::size_t column_points,
nk_capability_t capabilities = default_capabilities()) noexcept;row_points | in | Most points in any row cloud. |
|---|---|---|
column_points | in | Most points in any column cloud. |
capabilities | in | Capabilities to pick from, or 0 for the template in distance_type_. |
wassersteinprocrustes_packedWasserstein-Procrustes distances between every row pack and every column pack.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t, typename rotation_type_ = f32_t>
status_t wassersteinprocrustes_packed(
void const *const *a_packed,
std::size_t rows,
void const *const *b_packed,
std::size_t columns,
distance_type_ *results,
std::size_t results_stride,
std::type_identity_t<rotation_type_> *rotations,
std::span<std::byte> workspace,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;The other parameters match chamfers_packed.
a_packed | in | The row packs, one per row cloud. |
|---|---|---|
rows | in | Number of row packs. |
b_packed | in | The column packs, one per column cloud. |
columns | in | Number of column packs. |
results | out | The [rows,columns] distances, results_stride bytes apart. |
results_stride | in | Bytes between the rows of results. |
rotations | out | Null, or the [rows,columns,3,3] rotations taking each column cloud onto each row cloud through the centroids. |
workspace | in | Scratch aligned to nk_default_alignment_k, of what wassersteinprocrustes_workspace_size reports for the largest clouds, with the same capabilities and distance_type_, or more. |
capabilities | in | Capabilities to pick from, or 0 for the template in distance_type_. |
stream | in | Null on the CPU, or the stream of the device capabilities describes. |
misaligned_kunexpected_dimensions_k A short workspace.missing_kernel_kgromovwassersteins_workspace_sizeThe workspace bytes of gromovwassersteins_packed, queried like the Procrustes workspace.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t>
expected<std::size_t> gromovwassersteins_workspace_size(
std::size_t row_points,
std::size_t column_points,
nk_capability_t capabilities = default_capabilities()) noexcept;gromovwassersteins_packedGromov-Wasserstein distances between every row and column pack, with the parameters of wassersteinprocrustes_packed and the workspace of gromovwassersteins_workspace_size.template <shapes_dtype in_type_, typename distance_type_ = typename in_type_::shapes_distance_t, typename rotation_type_ = f32_t>
status_t gromovwassersteins_packed(
void const *const *a_packed,
std::size_t rows,
void const *const *b_packed,
std::size_t columns,
distance_type_ *results,
std::size_t results_stride,
std::type_identity_t<rotation_type_> *rotations,
std::span<std::byte> workspace,
nk_capability_t capabilities = default_capabilities(),
nk_stream_t stream = nullptr) noexcept;shapes_transport_epsilon_kThe stopping tolerance of the network simplex in every math type, relative to its cost scale.double shapes_transport_epsilon_k;