# Mesh Alignment

> NumKong for C++

### Many-to-Many Shape Distances

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.

```c
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:

```cpp
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());
```

`#include <numkong/shapes.hpp>`

## shapes_packed

Owning, move-only set of packed clouds, the operand every many-to-many kernel takes.

```cpp
template <shapes_dtype value_type_,
          typename allocator_type_ = aligned_allocator<char>>
class shapes_packed
```

One 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_type

The allocator of the packs' one block, which uses-allocator construction looks up.

```cpp
using allocator_type = allocator_type_;
```

## pack_size_kernel_t

One backend's `nk_shapes_pack_size_*` kernel.

```cpp
using pack_size_kernel_t = nk_status_t(*)(nk_size_t, nk_size_t *);
```

## pack_kernel_t

One backend's plain or normalized `nk_shapes_pack` kernel.

```cpp
using pack_kernel_t = nk_status_t(*)(typename value_type_::raw_t const *, nk_size_t, void *, nk_stream_t);
```

## shapes_packed

```cpp
shapes_packed() noexcept=default;
```

```cpp
shapes_packed(allocator_type_ const & alloc) noexcept;
```

```cpp
shapes_packed(shapes_packed && o) noexcept;
```

```cpp
shapes_packed(shapes_packed const &)=delete;
```

## ~shapes_packed

```cpp
~shapes_packed() noexcept;
```

## operator=

```cpp
shapes_packed & operator=(shapes_packed && o) noexcept;
```

```cpp
shapes_packed & operator=(shapes_packed const &)=delete;
```

## data

The table of pack pointers the kernels take.

```cpp
void const *const * data() const noexcept;
```

## operator[]

The pack of cloud `index`.

```cpp
void const * operator[](std::size_t index) const noexcept;
```

## size

The number of packed clouds.

```cpp
std::size_t size() const noexcept;
```

## points

The points in cloud `index`.

```cpp
std::size_t points(std::size_t index) const noexcept;
```

## max_points

The largest cloud, which sizes the transport workspaces.

```cpp
std::size_t max_points() const noexcept;
```

## get_allocator

The allocator the packs came from, so a replacement can be packed from the same one.

```cpp
allocator_type get_allocator() const noexcept;
```

## make

Packs every cloud of `clouds`, each ____[points,3] interleaved.

```cpp
expected<shapes_packed> make(
    std::span<std::span<value_type_ const> const> clouds,
    allocator_type_ alloc = {},
    nk_capability_t capabilities = default_capabilities()) noexcept;
```

```cpp
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`](https://www.unum.cloud/docs/numkong/cpp/runtime-dispatch.md#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`](#make_normalized).

Statuses: - [`unexpected_dimensions_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#unexpected_dimensions_k) A cloud's length is not a multiple of 3.
- [`missing_kernel_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#missing_kernel_k)
- The packing kernel's failure.

## make_normalized

Packs every cloud like [`make`](https://www.unum.cloud/docs/numkong/cpp/runtime-dispatch.md#make), each divided by its RMS distance from the centroid.

```cpp
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_size

Returns the bytes a pack of [`points`](#points) takes.

```cpp
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_pack

Packs one cloud: centers it, rotates it onto its principal axes, and keeps its constants.

```cpp
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`](https://www.unum.cloud/docs/numkong/cpp/runtime-dispatch.md#count) × 3 interleaved values.
- `count` (in): Number of points in the cloud.
- `packed` (out): At least [`shapes_pack_size`](#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_normalized

Packs one cloud like [`shapes_pack`](#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.

```cpp
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_shape

Reads a pack's points and constants, skipping every null output.

```cpp
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_unpack

Restores a pack's cloud as x = scale × 𝑄ᵀ × x′ + centroid, rounded once into `in_type_`.

```cpp
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_packed

Superposed RMSDs between every row pack and every column pack of equally many points.

```cpp
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.

Statuses: - [`misaligned_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#misaligned_k)
- [`unexpected_dimensions_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#unexpected_dimensions_k) The packs differ in points.
- [`missing_kernel_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#missing_kernel_k)

## hausdorffs_packed

Hausdorff distances between every row and every column pack, the best of 8 axis flips.

```cpp
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_packed

Chamfer distances between every row pack and every column pack, the best of 8 axis flips.

```cpp
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`](#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_size

Returns the workspace bytes of [`chamfers_packed`](#chamfers_packed) between clouds of up to `row_points` and `column_points` points.

```cpp
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_size

Returns the workspace bytes of [`wassersteinprocrustes_packed`](#wassersteinprocrustes_packed) between clouds of up to `row_points` and `column_points` points.

```cpp
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_packed

Wasserstein-Procrustes distances between every row pack and every column pack.

```cpp
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`](#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`](#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.

Statuses: - [`misaligned_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#misaligned_k)
- [`unexpected_dimensions_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#unexpected_dimensions_k) A short workspace.
- [`missing_kernel_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#missing_kernel_k)

## gromovwassersteins_workspace_size

The workspace bytes of [`gromovwassersteins_packed`](#gromovwassersteins_packed), queried like the Procrustes workspace.

```cpp
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_packed

Gromov-Wasserstein distances between every row and column pack, with the parameters of [`wassersteinprocrustes_packed`](#wassersteinprocrustes_packed) and the workspace of [`gromovwassersteins_workspace_size`](#gromovwassersteins_workspace_size).

```cpp
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_k

The stopping tolerance of the network simplex in every math type, relative to its cost scale.

```cpp
double shapes_transport_epsilon_k;
```