# A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching

arXiv: https://arxiv.org/abs/2204.12805 · HTML: https://mlsanity.com/paper/2204.12805/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 71 references that are in the map.
- First posted on arXiv 27 Apr 2022.

## Builds on (most cited first, 29 of 29)

- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [3D Menagerie: Modeling the 3D shape and pose of animals](https://mlsanity.com/paper/1611.07700/) (2016)
- [Deep Functional Maps: Structured Prediction for Dense Shape Correspondence](https://mlsanity.com/paper/1704.08686/) (2017)
- [Deep Geometric Functional Maps: Robust Feature Learning for Shape Correspondence](https://mlsanity.com/paper/2003.14286/) (2020)
- [Unsupervised Deep Learning for Structured Shape Matching](https://mlsanity.com/paper/1812.03794/) (2018)
- [NeuroMorph: Unsupervised Shape Interpolation and Correspondence in One Go](https://mlsanity.com/paper/2106.09431/) (2021)
- [Continuous and Orientation-preserving Correspondences via Functional Maps](https://mlsanity.com/paper/1806.04455/) (2018)
- [Deep Shells: Unsupervised Shape Correspondence with Optimal Transport](https://mlsanity.com/paper/2010.15261/) (2020)
- [Smooth Shells: Multi-Scale Shape Registration with Functional Maps](https://mlsanity.com/paper/1905.12512/) (2019)
- [DPFM: Deep Partial Functional Maps](https://mlsanity.com/paper/2110.09994/) (2021)
- [CorrNet3D: Unsupervised End-to-end Learning of Dense Correspondence for 3D Point Clouds](https://mlsanity.com/paper/2012.15638/) (2020)
- [Isometric Multi-Shape Matching](https://mlsanity.com/paper/2012.02689/) (2020)
- [ZoomOut: Spectral Upsampling for Efficient Shape Correspondence](https://mlsanity.com/paper/1904.07865/) (2019)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [Structured Regularization of Functional Map Computations](https://mlsanity.com/paper/2009.14624/) (2020)
- [Efficient Deformable Shape Correspondence via Kernel Matching](https://mlsanity.com/paper/1707.08991/) (2017)
- [Higher-order Projected Power Iterations for Scalable Multi-Matching](https://mlsanity.com/paper/1811.10541/) (2018)
- [Unsupervised cycle-consistent deformation for shape matching](https://mlsanity.com/paper/1907.03165/) (2019)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment](https://mlsanity.com/paper/2002.12623/) (2020)
- [Non-Rigid Puzzles](https://mlsanity.com/paper/2011.13076/) (2020)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [Alternating Direction Graph Matching](https://mlsanity.com/paper/1611.07583/) (2016)
- [Sinkhorn Algorithm for Lifted Assignment Problems](https://mlsanity.com/paper/1707.07285/) (2017)
- [Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams](https://mlsanity.com/paper/2009.00481/) (2020)
- [Linearly Converging Quasi Branch and Bound Algorithms for Global Rigid Registration](https://mlsanity.com/paper/1904.02204/) (2019)
- [A Dual Iterative Refinement Method for Non-rigid Shape Matching](https://mlsanity.com/paper/2007.13049/) (2020)
- [DS++: A flexible, scalable and provably tight relaxation for matching problems](https://mlsanity.com/paper/1705.06148/) (2017)

## Built on by (most cited first, 19 of 19)

- [Unsupervised Learning of Robust Spectral Shape Matching](https://mlsanity.com/paper/2304.14419/) (2023)
- [Spectral Meets Spatial: Harmonising 3D Shape Matching and Interpolation](https://mlsanity.com/paper/2402.18920/) (2024)
- [Self-Supervised Learning for Multimodal Non-Rigid 3D Shape Matching](https://mlsanity.com/paper/2303.10971/) (2023)
- [Partial-to-Partial Shape Matching with Geometric Consistency](https://mlsanity.com/paper/2404.12209/) (2024)
- [Geometrically Consistent Partial Shape Matching](https://mlsanity.com/paper/2309.05013/) (2023)
- [Beyond Complete Shapes: A Benchmark for Quantitative Evaluation of 3D Shape Surface Matching Algorithms](https://mlsanity.com/paper/2411.03511/) (2024)
- [Revisiting Map Relations for Unsupervised Non-Rigid Shape Matching](https://mlsanity.com/paper/2310.11420/) (2023)
- [DiscoMatch: Fast Discrete Optimisation for Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2310.08230/) (2023)
- [Synchronous Diffusion for Unsupervised Smooth Non-Rigid 3D Shape Matching](https://mlsanity.com/paper/2407.08244/) (2024)
- [Stable-SCore: A Stable Registration-based Framework for 3D Shape Correspondence](https://mlsanity.com/paper/2503.21766/) (2025)
- [Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matching](https://mlsanity.com/paper/2211.11589/) (2022)
- [SIGMA: Scale-Invariant Global Sparse Shape Matching](https://mlsanity.com/paper/2308.08393/) (2023)
- [Fast Globally Optimal and Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2504.06385/) (2025)
- [Symmetry Understanding of 3D Shapes via Chirality Disentanglement](https://mlsanity.com/paper/2508.05505/) (2025)
- [SemMorph3D: Unsupervised Semantic-Aware 3D Morphing via Mesh-Guided Gaussians](https://mlsanity.com/paper/2510.02034/) (2025)
- [An Integer Linear Programming Approach to Geometrically Consistent Partial-Partial Shape Matching](https://mlsanity.com/paper/2602.06590/) (2026)
- [Hyper-Network Neural Functional Maps for Unsupervised Robust 3D Shape Matching](https://mlsanity.com/paper/2606.30131/) (2026)
- [Ordered Diffusion for 3D Human Registration](https://mlsanity.com/paper/2608.05804/) (2026)
- [TokenMatch: 3D Mesh Correspondence Transformer with Curvature-Guided Tokenisation](https://mlsanity.com/paper/2609.04202/) (2026)

## Abstract (arXiv)

We present a scalable combinatorial algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We use the mathematically elegant formalism proposed by Windheuser et al. (ICCV 2011) where 3D shape matching was formulated as an integer linear program over the space of orientation-preserving diffeomorphisms. Until now, the resulting formulation had limited practical applicability due to its complicated constraint structure and its large size. We propose a novel primal heuristic coupled with a Lagrange dual problem that is several orders of magnitudes faster compared to previous solvers. This allows us to handle shapes with substantially more triangles than previously solvable. We demonstrate compelling results on diverse datasets, and, even showcase that we can address the challenging setting of matching two partial shapes without availability of complete shapes. Our code is publicly available at http://github.com/paul0noah/sm-comb .