Analytic methods for geometric modeling via spherical decomposition. (January 2016)

• Record Type: Journal Article
• Authors: Behandish, Morad; Ilieş, Horea T.
• Is Part Of: Computer aided design. Volume 70(2016)
• Page Start: 100
• Page End: 115
• Publication Date: 2016-01
• Subjects: Analytic methods -- Shape correlation -- Spherical sampling -- Fourier transform -- Collision detection; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.06.016
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: 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. Highlights: 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.