Scaling Global Interpolation for High Resolution Geometry

25 concepts23 papers1 proposal

In computer graphics, 3D vision, and physical simulation, we constantly crave higher resolution. Dense polygonal meshes with hundreds of thousands or millions of vertices allow us to represent intricate organic details, high-fidelity textures, and complex physical boundaries. However, as geometric resolution scales up, the mathematical frameworks we use to manipulate, deform, and optimize these shapes frequently hit a computational wall.

The root of this issue lies in the tension between global coherence and computational complexity. When we perform operations like surface interpolation, registration, or smooth deformation, we want changes in one region of a shape to propagate naturally across the entire surface. Achieving this typically requires solving global equations or optimizing dense matrices. As vertex counts scale, these global operations become prohibitively expensive.

To make high-resolution geometry practical, researchers have developed a variety of strategies to bypass these scaling bottlenecks. Understanding why these methods work requires looking closely at how they break down global complexity into scalable components.

The Polynomial Cost of Global Coherence

Why do standard geometric algorithms struggle with dense meshes? The core bottleneck is often the polynomial complexity of global linear solvers and matrix inversions.

When we deform a mesh smoothly using radial basis functions (RBFs) or solve partial differential equations (PDEs) across a surface, every vertex potentially influences every other vertex. As noted by Roberto Cavoretto et al. in Partition of unity interpolation using stable kernel-based techniques, global interpolation methods for scattered data often exhibit cubic computational complexity ($O(N^3)$) relative to the number of data points. Similarly, Adrien Poulenard et al. point out in Continuous and orientation-preserving correspondences via functional maps that high-resolution geometric processing faces severe scalability challenges due to the cubic complexity of linear solvers. Even when matrix inversion can be optimized, Vidhi Zala et al. in Curvilinear Mesh Adaptation using Radial Basis Function Interpolation and Smoothing observe that global interpolation for mesh deformation incurs at least quadratic scaling costs ($O(N^2)$), making the approach impractical for large-scale simulations containing millions of elements.

This scaling crisis is not limited to classical deformation; it propagates through modern reconstruction and optimization pipelines:

To overcome these limits, researchers rely on three primary insights: localization, low-dimensional proxies, and linearized optimization.

Localization: Dividing the Global Domain

The most direct way to eliminate $O(N^3)$ or $O(N^2)$ global complexity is to transform a single massive global problem into many smaller, localized problems.

A powerful mathematical tool for this is the Partition of Unity (PU) framework. Instead of constructing a massive interpolation matrix for an entire dataset, the authors of Partition of unity interpolation using stable kernel-based techniques divide the global domain into overlapping local subdomains. They solve stable, localized interpolation bases within each subdomain and then blend them together using weight functions that sum to one. Because the computational cost is confined to small, local matrices, the overall complexity scales linearly with the number of subdomains rather than cubically with the total number of points.

A similar intuition applies to surface modeling. By representing complex organic geometries as collections of discrete surface patches, solvers can operate locally. As shown by Lingyun You in Fast generation of 3D deformable moving surfaces, combining localized trial functions with exact boundary constraints allows physics-based animations to solve partial differential equations at speeds orders of magnitude faster than traditional global numerical methods.

Global Interpolation (Cubic Complexity)
[  Dense Matrix (N x N)  ] -> Inversion scales at O(N³)

Partition of Unity Localization (Linear Complexity)
[Local Patch 1] + [Local Patch 2] + [Local Patch 3] -> Blended smoothly via PU weights

Decoupling via Proxies and Spatial Fields

Another core strategy is decoupling—separating the high-resolution geometry from the underlying optimization or deformation logic. Directly manipulating or optimizing every vertex in a dense mesh to resolve physical inconsistencies or stylistic edits is often too slow for interactive applications (Ziwei Yu et al. in UV-Based 3D Hand-Object Reconstruction with Grasp Optimization; Hsueh-Ti Derek Liu et al. in Cubic Stylization).

Instead of optimizing the mesh directly, algorithms can embed the high-resolution geometry inside a lower-dimensional proxy:

  • Deformation Cages: By mathematically coupling a low-resolution control cage to a high-resolution mesh, animations can be computed entirely on the cage's sparse vertices and then propagated smoothly to the dense geometry (Fabrizio Corda et al. in Real-time Deformation with Coupled Cages and Skeletons).
  • Spatial Force Fields: Rather than tracking vertex connections, the deformation logic can be embedded in an abstract spatial field. As demonstrated by Xiaosong Yang et al. in Defoxel: A New Tool for Virtual Aesthetic Shaping, treating deformation as a spatial force field grounded in solid mechanics allows complex shapes to be modified independently of their underlying mesh topology.

Linearizing Constraints and Proxies

When an algorithm must optimize the full high-resolution mesh globally, the key to scalability is avoiding expensive second-order optimizations (like Newton-Raphson methods) that require recomputing and inverting massive Hessian matrices at every iteration.

The authors of Large-scale bounded distortion mappings solve this by introducing a hyperplane proxy framework. When computing mappings for meshes with millions of elements, traditional bounded-distortion methods suffer from highly non-linear, expensive constraints. By replacing these complex non-linear constraints with a clever linear "hyperplane proxy," Shahar Z. Kovalsky et al. enable simple, first-order alternating optimization algorithms to achieve convergence speeds comparable to second-order methods. This allows volumetric deformations of massive meshes to be solved in minutes rather than hours.

Coarse-to-Fine and Parallel Acceleration

Finally, when dense calculations cannot be avoided structurally, pipelines rely on multi-scale evaluation and hardware acceleration to maintain performance:

Summary

Scaling global interpolation and optimization to high-resolution geometry is not about finding a single mathematical silver bullet; it is about choosing the right abstraction to break polynomial complexity. Whether by localizing global domains via Partition of Unity, decoupling vertices using low-dimensional cages and spatial fields, or linearizing complex constraints with hyperplane proxies, the goal remains the same: preserving the visual beauty of high-resolution shapes without paying the catastrophic computational price of global density.

Key Foundational Work

A fast multigrid algorithm for mesh deformation (2006) — contributed 3 concept elements to this direction.
Fast generation of 3D deformable moving surfaces (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_scaling_of_global_interpol_5971b32b,
  title = {computational scaling of global interpolation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scaling-of-global-interpolation/rdr_5971b32b6b9842be891393a40bb74c90},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_scaling_of_global_interpol_5971b32b_v1,
  title = {computational scaling of global interpolation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scaling-of-global-interpolation/rdr_5971b32b6b9842be891393a40bb74c90/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake