Cubic mean value coordinates

Xian-Ying Li, Tao Ju, Shi-Min HuACM Trans. Graphics 2013 · DOI

TL;DR

This paper introduces "cubic mean value coordinates" (CMV coordinates), a new mathematical tool for smoothly interpolating both values and gradients across a 2D polygonal domain. This advancement enables more natural and controllable shape deformations and image representations, particularly for complex, non-convex shapes.

What Problem Does This Paper Address?

Creating smooth and controllable deformations in computer graphics often requires interpolating not just points but also their rates of change (gradients) across a surface. Traditional methods like mean value coordinates excel at interpolating values but struggle with gradients, leading to visible "seams" or discontinuities when combining multiple deformation elements. Existing methods that do handle gradients, like biharmonic or moving least squares coordinates, either have limitations in their closed-form solutions, computational efficiency, or can produce unnatural "ripples" in non-convex shapes. This paper aims to bridge this gap by providing a method that is mathematically sound, computationally efficient, and produces visually pleasing results for both values and gradients, even in complex scenarios.

Methods

The core of this work is the development of "cubic mean value coordinates" (CMV coordinates). The authors build upon existing "transfinite interpolants" and re-derive them using the mean value property of biharmonic functions, extending the concept from harmonic functions used in standard mean value coordinates. This theoretical foundation allows them to define a function that interpolates both boundary values and their normal derivatives.

Key methodological contributions include:

  • Biharmonic Extension: Adapting the mean value property from harmonic functions to biharmonic functions to handle gradient interpolation.
  • Closed-Form Solution: Deriving explicit, computationally efficient formulas for the CMV coordinates, which are crucial for practical applications. This involves complex integral calculations and algebraic manipulation, detailed in the appendices.
  • Piecewise Polynomial Representation: Defining boundary constraints using cubic polynomials for values and linear polynomials for normal derivatives along each edge of a polygon. This provides a flexible way to control the interpolation.

Datasets

Not discussed in the paper. The paper focuses on the mathematical development and algorithmic applications, demonstrating its capabilities with generated examples and visual results rather than relying on specific datasets.

Key Insights and Ideas

  • The Power of Biharmonics for Gradients: The paper elegantly shows how extending the mean value property from harmonic to biharmonic functions naturally leads to a method that interpolates gradients, not just values. This is a significant theoretical leap for this class of interpolation methods.
  • CMV Coordinates: The Best of Both Worlds: CMV coordinates achieve a desirable balance: they offer a closed-form solution for efficient computation (unlike some biharmonic methods), handle both values and gradients smoothly (unlike standard mean value coordinates), and avoid the unnatural distortions seen in other gradient-interpolating methods like MLS in non-convex domains.
  • Cubic Control for Smoothness: Using cubic polynomials for boundary values and linear for gradients provides a sweet spot for flexibility and smoothness. This allows for natural-looking interpolations that are C¹ continuous (smooth value and gradient) across boundaries, crucial for applications like cage-based deformation.
  • Curved Cages Enable Natural Deformations: The ability to define deformations using curved cage edges, directly supported by CMV coordinates, allows for much more intuitive and precise shape manipulation, conforming to complex user-defined shapes.

Key Results

  • Visual Quality: The paper demonstrates visually compelling results in two main applications:
  • Shape Deformation: CMV coordinates produce smooth, seam-free deformations using curved cage networks, outperforming standard mean value coordinates and avoiding the "wiggles" of MLS in non-convex cases.
  • Adaptive Gradient Meshes: CMV coordinates enable the creation of adaptive gradient meshes that can represent images with varying levels of detail, aligning patch boundaries with image features for efficient and visually pleasing vector graphics.
  • Computational Efficiency: The CMV coordinates have a time complexity of O(n) for a polygon with n edges, making them computationally efficient for real-time applications. This is comparable to mean value coordinates and significantly faster than some other Hermite interpolants.
  • Theoretical Guarantees: The paper provides proofs for the CMV interpolant's properties, including its well-definedness over the entire plane, its interpolation of values, and its reproduction of cubic functions. It also offers a proof that CMV coordinates match boundary gradients for polygonal domains.

Limitations and Future Work

  • Non-Convex Domain Impact: The authors acknowledge that, like other methods relying on Euclidean distances, CMV coordinates can still exhibit some negative impact from distant boundary constraints in non-convex polygons, though visually less pronounced than some alternatives. They note that biharmonic coordinates might offer a more "shape-aware" propagation of constraints.
  • Higher Dimensions and Orders: The paper suggests that the techniques could be extended to higher dimensions and for matching higher-order derivatives. While the transfinite interpolant has a general form, deriving the specific closed-form coordinates for these extensions remains an open research question.
  • Comparison with Shape-Aware Methods: While CMV coordinates are visually pleasing, the paper notes that methods like biharmonic coordinates might be more "shape-aware" in how constraints propagate. Future work could explore combining the strengths of both approaches.
  • Extension to 3D: Extending the CMV coordinates to 3D domains is a significant future direction.

Summary updated

BibTeX
@article{li2013cubic,
  author = {Xian-Ying Li and Tao Ju and Shi-Min Hu},
  title = {{Cubic mean value coordinates}},
  journal = {ACM Trans. Graphics},
  year = {2013},
  doi = {10.1145/2461912.2461917},
}
Figure