C · Mesh Alignment

Mesh Alignment

#include <numkong/capabilities.h>#include <numkong/shapes.h> 8.0.0-rc.1 · b1f866ab

§ 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.

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

API

Types

nk_shapes_workspace_size_punned_tWorkspace sizes are host arithmetic, like pack sizes, so they take no stream.
capabilities.h:1033 ↗
typedef nk_status_t(*) nk_shapes_workspace_size_punned_t(nk_size_t row_points, nk_size_t column_points, nk_size_t *bytes);

Functions

nk_shapes_pack_size_*_best× 3Returns the bytes a pack of points takes.
shapes.h:144 ↗
nk_status_t nk_shapes_pack_size_f64_best(
    nk_size_t points,
    nk_capability_t capabilities,
    nk_size_t *bytes);
SymbolBackends
nk_shapes_pack_size_f64_best1
nk_shapes_pack_size_f32_best1
nk_shapes_pack_size_f16_best1

Backends

  • nk_shapes_pack_size_f64serial
  • nk_shapes_pack_size_f32serial
  • nk_shapes_pack_size_f16serial

Parameters

pointsinThe number of 3D points.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
bytesoutThe size of the pack.

Statuses

nk_shapes_pack_*_best× 3Packs one cloud: centers it, rotates it onto its principal axes, and keeps its constants.
shapes.h:162 ↗
nk_status_t nk_shapes_pack_f64_best(
    nk_f64_t const *points,
    nk_size_t count,
    void *packed,
    nk_capability_t capabilities,
    nk_stream_t stream);
SymbolpointsBackends
nk_shapes_pack_f64_bestnk_f64_t1
nk_shapes_pack_f32_bestnk_f32_t6
nk_shapes_pack_f16_bestnk_f16_t6

Backends

  • nk_shapes_pack_f64serial
  • nk_shapes_pack_f32serialhaswellskylakev128relaxedneonrvv
  • nk_shapes_pack_f16serialhaswellskylakev128relaxedneonrvv

Parameters

pointsinThe cloud, count × 3 interleaved [x0,y0,z0, x1,y1,z1, ...].
countinThe number of 3D points.
packedoutThe pack, as many bytes as nk_shapes_pack_size_f64_best reports, starting on an nk_default_alignment_k boundary.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_shapes_pack_normalized_*_best× 3Packs one cloud like nk_shapes_pack_f64_best, also dividing it by its RMS distance from the centroid, kept as the pack's scale, or by 1 when the cloud has no spread.
shapes.h:178 ↗
nk_status_t nk_shapes_pack_normalized_f64_best(
    nk_f64_t const *points,
    nk_size_t count,
    void *packed,
    nk_capability_t capabilities,
    nk_stream_t stream);
SymbolpointsBackends
nk_shapes_pack_normalized_f64_bestnk_f64_t1
nk_shapes_pack_normalized_f32_bestnk_f32_t6
nk_shapes_pack_normalized_f16_bestnk_f16_t6

Backends

  • nk_shapes_pack_normalized_f64serial
  • nk_shapes_pack_normalized_f32serialhaswellskylakev128relaxedneonrvv
  • nk_shapes_pack_normalized_f16serialhaswellskylakev128relaxedneonrvv

Every kind then compares shapes regardless of size, and a rotation between two normalized packs takes the column cloud onto the row cloud as aᵢ ≈ (scale_a / scale_b) × R × (bⱼ − b̄) + ā.

nk_shapes_packed_shape_*_best× 3Reads a pack's points and constants, skipping every null output.
shapes.h:204 ↗
nk_status_t nk_shapes_packed_shape_f64_best(
    void const *packed,
    nk_size_t *points,
    nk_f64_t *centroid,
    nk_f64_t *frame,
    nk_f64_t *scale,
    nk_f64_t *spreads,
    nk_f64_t *max_radius,
    nk_capability_t capabilities,
    nk_stream_t stream);
Symbolcentroid, frame, scale, spreads, max_radiusBackends
nk_shapes_packed_shape_f64_bestnk_f64_t1
nk_shapes_packed_shape_f32_bestnk_f64_t1
nk_shapes_packed_shape_f16_bestnk_f32_t1

Backends

  • nk_shapes_packed_shape_f64serial
  • nk_shapes_packed_shape_f32serial
  • nk_shapes_packed_shape_f16serial

Parameters

packedinA pack of f64 points, plain or normalized.
pointsoutNull, or the number of 3D points.
centroidoutNull, or the 3 coordinates of the mean input point.
frameoutNull, or the unit quaternion (x, y, z, w) of 𝑄, rotating centered inputs onto the principal axes.
scaleoutNull, or what the rotated inputs were divided by: their RMS distance from the centroid, or 1.
spreadsoutNull, or the 3 descending eigenvalues of the packed points' second moments.
max_radiusoutNull, or the largest packed point norm.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_shapes_unpack_*_best× 3Restores a pack's cloud as x = scale × 𝑄ᵀ × x′ + centroid, computed in the math type and rounded once into the input type.
shapes.h:234 ↗
nk_status_t nk_shapes_unpack_f64_best(
    void const *packed,
    nk_f64_t *points,
    nk_capability_t capabilities,
    nk_stream_t stream);
SymbolpointsBackends
nk_shapes_unpack_f64_bestnk_f64_t1
nk_shapes_unpack_f32_bestnk_f32_t1
nk_shapes_unpack_f16_bestnk_f16_t1

Backends

  • nk_shapes_unpack_f64serial
  • nk_shapes_unpack_f32serial
  • nk_shapes_unpack_f16serial

Unpacking an absolute pack returns its inputs within one storage rounding, and a normalized pack its cloud at the original scale.

Parameters

packedinA pack of f64 points, plain or normalized.
pointsoutThe cloud, its points × 3 interleaved [x0,y0,z0, x1,y1,z1, ...].
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_rmsds_packed_*_best× 3Superposed RMSD between every row and every column frame, matched point by point.
shapes.h:265 ↗
nk_status_t nk_rmsds_packed_f64_best(
    void const *const *a_packed,
    nk_size_t rows,
    void const *const *b_packed,
    nk_size_t columns,
    nk_f64_t *results,
    nk_size_t results_stride,
    nk_capability_t capabilities,
    nk_stream_t stream);
SymbolresultsBackends
nk_rmsds_packed_f64_bestnk_f64_t8
nk_rmsds_packed_f32_bestnk_f64_t8
nk_rmsds_packed_f16_bestnk_f32_t12

Backends

  • nk_rmsds_packed_f64serialhaswellskylakev128relaxedneonrvvcudarocm
  • nk_rmsds_packed_f32serialhaswellskylakev128relaxedneonrvvcudarocm
  • nk_rmsds_packed_f16serialhaswellskylakev128relaxedneonneonfhmrvvblackwellmetalapple10cudarocm

Each is √(min_R Σ‖aᵢ − R × bᵢ‖² / n) over proper rotations R, and zero between empty frames.

Parameters

a_packedinThe row shape packs, plain or normalized, rows pointers.
rowsinThe number of row frames.
b_packedinThe column packs, columns pointers.
columnsinThe number of column frames.
resultsoutThe [rows,columns] distances.
results_strideinThe bytes between consecutive rows of results.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_hausdorffs_packed_*_best× 3Hausdorff distances between every row and every column cloud, the best of 8 axis flips.
shapes.h:304 ↗
nk_status_t nk_hausdorffs_packed_f64_best(
    void const *const *a_packed,
    nk_size_t rows,
    void const *const *b_packed,
    nk_size_t columns,
    nk_f64_t *results,
    nk_size_t results_stride,
    nk_f32_t *rotations,
    nk_f64_t const *limit,
    nk_capability_t capabilities,
    nk_stream_t stream);
Symbolresults, limitBackends
nk_hausdorffs_packed_f64_bestnk_f64_t2
nk_hausdorffs_packed_f32_bestnk_f64_t8
nk_hausdorffs_packed_f16_bestnk_f32_t12

Backends

  • nk_hausdorffs_packed_f64serialskylake
  • nk_hausdorffs_packed_f32serialhaswellskylakev128relaxedneonrvvcudarocm
  • nk_hausdorffs_packed_f16serialhaswellskylakev128relaxedneonneonfhmrvvblackwellmetalapple10cudarocm

Each is max(maxᵢ minⱼ ‖aᵢ − S × bⱼ‖, maxⱼ minᵢ ‖aᵢ − S × bⱼ‖), zero between two empty clouds and infinite between an empty and a non-empty one.

Parameters

a_packedinThe row packs, rows pointers.
rowsinThe number of row clouds.
b_packedinThe column packs, columns pointers.
columnsinThe number of column clouds.
resultsoutThe [rows,columns] distances.
results_strideinThe bytes between consecutive rows of results.
rotationsoutNull, or the [rows,columns,3,3] rotations taking each column cloud onto each row cloud.
limitinDistances 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.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_chamfers_packed_*_best× 3Chamfer distances between every row and every column cloud, the best of 8 axis flips.
shapes.h:351 ↗
nk_status_t nk_chamfers_packed_f64_best(
    void const *const *a_packed,
    nk_size_t rows,
    void const *const *b_packed,
    nk_size_t columns,
    nk_f64_t *results,
    nk_size_t results_stride,
    nk_f32_t *rotations,
    nk_f64_t const *limit,
    void *workspace,
    nk_size_t workspace_bytes,
    nk_capability_t capabilities,
    nk_stream_t stream);
Symbolresults, limitBackends
nk_chamfers_packed_f64_bestnk_f64_t2
nk_chamfers_packed_f32_bestnk_f64_t8
nk_chamfers_packed_f16_bestnk_f32_t12

Backends

  • nk_chamfers_packed_f64serialskylake
  • nk_chamfers_packed_f32serialhaswellskylakev128relaxedneonrvvcudarocm
  • nk_chamfers_packed_f16serialhaswellskylakev128relaxedneonneonfhmrvvblackwellmetalapple10cudarocm

Each is ½ × (meanᵢ minⱼ ‖aᵢ − S × bⱼ‖ + meanⱼ minᵢ ‖aᵢ − S × bⱼ‖), with the same empty-cloud convention as nk_hausdorffs_packed_f64_best.

Parameters

a_packedinThe row packs, rows pointers.
rowsinThe number of row clouds.
b_packedinThe column packs, columns pointers.
columnsinThe number of column clouds.
resultsoutThe [rows,columns] distances.
results_strideinThe bytes between consecutive rows of results.
rotationsoutNull, or the [rows,columns,3,3] rotations taking each column cloud onto each row cloud.
limitinDistances 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.
workspaceinoutScratch of workspace_bytes on an nk_default_alignment_k boundary, as nk_chamfers_workspace_size_f64_best reports for the largest clouds.
workspace_bytesinThe bytes of workspace.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_chamfers_workspace_size_*_best× 3Reports the workspace bytes nk_chamfers_packed_f64_best needs between clouds of up to row_points and column_points points.
shapes.h:377 ↗
nk_status_t nk_chamfers_workspace_size_f64_best(
    nk_size_t row_points,
    nk_size_t column_points,
    nk_capability_t capabilities,
    nk_size_t *bytes);
SymbolBackends
nk_chamfers_workspace_size_f64_best1
nk_chamfers_workspace_size_f32_best3
nk_chamfers_workspace_size_f16_best6

Backends

  • nk_chamfers_workspace_size_f64serial
  • nk_chamfers_workspace_size_f32serialcudarocm
  • nk_chamfers_workspace_size_f16serialblackwellmetalapple10cudarocm

Parameters

row_pointsinThe most points in any row cloud.
column_pointsinThe most points in any column cloud.
capabilitiesinOne device's capabilities.
bytesoutThe workspace bytes.
nk_wassersteinprocrustes_workspace_size_*_best× 3Returns the workspace bytes the transport kinds need between clouds of up to row_points and column_points points.
shapes.h:397 ↗
nk_status_t nk_wassersteinprocrustes_workspace_size_f64_best(
    nk_size_t row_points,
    nk_size_t column_points,
    nk_capability_t capabilities,
    nk_size_t *bytes);
SymbolBackends
nk_wassersteinprocrustes_workspace_size_f64_best1
nk_wassersteinprocrustes_workspace_size_f32_best3
nk_wassersteinprocrustes_workspace_size_f16_best4

Backends

  • nk_wassersteinprocrustes_workspace_size_f64serial
  • nk_wassersteinprocrustes_workspace_size_f32serialcudarocm
  • nk_wassersteinprocrustes_workspace_size_f16serialmetalcudarocm

Parameters

row_pointsinThe largest row cloud.
column_pointsinThe largest column cloud.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
bytesoutThe size of the workspace.

Statuses

nk_wassersteinprocrustes_packed_*_best× 3Wasserstein-Procrustes distances between every row cloud and every column cloud.
shapes.h:438 ↗
nk_status_t nk_wassersteinprocrustes_packed_f64_best(
    void const *const *a_packed,
    nk_size_t rows,
    void const *const *b_packed,
    nk_size_t columns,
    nk_f64_t *results,
    nk_size_t results_stride,
    nk_f32_t *rotations,
    void *workspace,
    nk_size_t workspace_bytes,
    nk_capability_t capabilities,
    nk_stream_t stream);
SymbolresultsBackends
nk_wassersteinprocrustes_packed_f64_bestnk_f64_t2
nk_wassersteinprocrustes_packed_f32_bestnk_f64_t8
nk_wassersteinprocrustes_packed_f16_bestnk_f32_t9

Backends

  • nk_wassersteinprocrustes_packed_f64serialskylake
  • nk_wassersteinprocrustes_packed_f32serialhaswellskylakev128relaxedneonrvvcudarocm
  • nk_wassersteinprocrustes_packed_f16serialhaswellskylakev128relaxedneonrvvmetalcudarocm

Each is the root mean squared distance of an exact optimal transport plan between uniform weights under a rotation or reflection, the best of the local optima that alternating the two reaches from the 8 axis flips, zero between two empty clouds and infinite between an empty and a non-empty one. Other parameters match the Chamfer kernel's.

Parameters

a_packedinThe row packs, rows pointers.
rowsinThe number of row clouds.
b_packedinThe column packs, columns pointers.
columnsinThe number of column clouds.
resultsoutThe [rows,columns] distances.
results_strideinThe bytes between consecutive rows of results.
rotationsoutNull, or the [rows,columns,3,3] rotations taking each column cloud onto each row cloud.
workspaceinThe scratch memory, aligned to nk_default_alignment_k.
workspace_bytesinAt least the bytes the matching workspace-size query reports for the largest clouds on each side.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
streaminNull on the CPU, or the GPU stream of that device to queue on.

Statuses

nk_gromovwassersteins_workspace_size_*_best× 3Returns the workspace bytes the transport kinds need between clouds of up to row_points and column_points points.
shapes.h:460 ↗
nk_status_t nk_gromovwassersteins_workspace_size_f64_best(
    nk_size_t row_points,
    nk_size_t column_points,
    nk_capability_t capabilities,
    nk_size_t *bytes);
SymbolBackends
nk_gromovwassersteins_workspace_size_f64_best1
nk_gromovwassersteins_workspace_size_f32_best3
nk_gromovwassersteins_workspace_size_f16_best4

Backends

  • nk_gromovwassersteins_workspace_size_f64serial
  • nk_gromovwassersteins_workspace_size_f32serialcudarocm
  • nk_gromovwassersteins_workspace_size_f16serialmetalcudarocm

Parameters

row_pointsinThe largest row cloud.
column_pointsinThe largest column cloud.
capabilitiesinOne device's capabilities, like nk_cpu_capabilities_enabled reports.
bytesoutThe size of the workspace.

Statuses

nk_gromovwassersteins_packed_*_best× 3Gromov-Wasserstein distances between every row cloud and every column cloud.
shapes.h:477 ↗
nk_status_t nk_gromovwassersteins_packed_f64_best(
    void const *const *a_packed,
    nk_size_t rows,
    void const *const *b_packed,
    nk_size_t columns,
    nk_f64_t *results,
    nk_size_t results_stride,
    nk_f32_t *rotations,
    void *workspace,
    nk_size_t workspace_bytes,
    nk_capability_t capabilities,
    nk_stream_t stream);
SymbolresultsBackends
nk_gromovwassersteins_packed_f64_bestnk_f64_t2
nk_gromovwassersteins_packed_f32_bestnk_f64_t8
nk_gromovwassersteins_packed_f16_bestnk_f32_t9

Backends

  • nk_gromovwassersteins_packed_f64serialskylake
  • nk_gromovwassersteins_packed_f32serialhaswellskylakev128relaxedneonrvvcudarocm
  • nk_gromovwassersteins_packed_f16serialhaswellskylakev128relaxedneonrvvmetalcudarocm

Each compares the two clouds' plain distance matrices under the best transport plan reached from the Wasserstein-Procrustes plans and the product plan. The rotation is the orthogonal Procrustes fit of that plan. Parameters and returns match the Wasserstein-Procrustes kernel's, with the workspace sized by nk_gromovwassersteins_workspace_size_f64_best.

nk_shapes_output_dtypeReturns the distance dtype of the many-to-many shape kernels, as the C++ shapes_distance_t alias in types.hpp names it.
shapes.h:1318 ↗
nk_dtype_t nk_shapes_output_dtype(nk_dtype_t dtype);
nk_rmsds_output_dtypeReturns the distance dtype of the superposed RMSD kernels.
shapes.h:1328 ↗
nk_dtype_t nk_rmsds_output_dtype(nk_dtype_t dtype);
nk_shapes_find_kernelFinds the shape kernel of kind for dtype, from the best of capabilities.
shapes.h:1349 ↗
nk_status_t nk_shapes_find_kernel(
    nk_kernel_kind_t kind,
    nk_dtype_t dtype,
    nk_capability_t capabilities,
    nk_kernel_punned_t *kernel,
    nk_capability_t *capability);

Parameters

kindinThe verb whose kernel to find.
dtypeinThe input type the kernel reads.
capabilitiesinThe mask to pick the best capability from.
kerneloutThe kernel, or null when no capability in capabilities has it.
capabilityoutThe capability the kernel belongs to, or zero.

Statuses