Analytic methods for geometric modeling via spherical decomposition

• We propose a grid-free discretization scheme for analytic geometric modeling.
• Solids are approximated with countable unions of 3D balls cut from 4D cones.
• The unions turn into 3D slices of 4D Minkowski sums of knots and a template cone.
• The Minkowski formulation embeds well into cross-correlations between solids.
• The analytic formulation follows using convolution algebra and Fourier Transform.

Analytic methods are emerging in solid and configuration modeling, while providing new insights into a variety of shape and motion related problems by exploiting tools from group morphology, convolution algebras, and harmonic analysis. However, most convolution-based methods have used uniform grid-based sampling to take advantage of the fast Fourier transform (FFT) algorithm. We propose a new paradigm for more efficient computation of analytic correlations that relies on a grid-free discretization of arbitrary shapes as countable unions of balls, in turn described as sublevel sets of summations of smooth radial kernels at adaptively sampled ‘knots’. Using a simple geometric lifting trick, we interpret this combination as a convolution of an impulsive skeletal density and primitive kernels with conical support, which faithfully embeds into the convolution formulation of interactions across different objects. Our approach enables fusion of search-efficient combinatorial data structures prevalent in time-critical collision and proximity queries with analytic methods popular in path planning and protein docking, and outperforms uniform grid-based FFT methods by leveraging nonequispaced FFTs. We provide example applications in formulating holonomic collision constraints, shape complementarity metrics, and morphological operations, unified within a single analytic framework.