2015/07/23 by Morad Behandish, Horea T. Ilieş, Horea T. Ilies · 15 citations
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Algorithm #Artificial intelligence #Computation #Computational Geometry and Mesh Generation #Computer science #Convolution (computer science) #Discretization #Fast Fourier transform #Geometry #Grid #Mathematical analysis #Mathematical optimization #Mathematics #Octree #Robotic Path Planning Algorithms #cs.CG #cs.GR
paper · pdf · doi:10.1016/j.cad.2015.06.016
published in Computer-Aided Design 70, 100-115 (Elsevier BV) · Special Issue on SIAM/ACM symposium on Solid and Physical Modeling (SPM'2015) (Best Paper Award, 2nd Place)
openalex publication_date 2015/07/23 · arxiv created 2017/11/14 · arxiv updated 2017/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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.