title: Discrete Sibson interpolation.
abstract: Natural-neighbor interpolation methods, such as Sibson's method, are well-known schemes for multivariate data fitting and reconstruction. Despite its many desirable properties, Sibson's method is computationally expensive and difficult to implement, especially when applied to higher-dimensional data. The main reason for both problems is the method's implementation based on a Voronoi diagram of all data points. We describe a discrete approach to evaluating Sibson's interpolant on a regular grid, based solely on finding nearest neighbors and rendering and blending d-dimensional spheres. Our approach does not require us to construct an explicit Voronoi diagram, is easily implemented using commodity three-dimensional graphics hardware, leads to a significant speed increase compared to traditional approaches, and generalizes easily to higher dimensions. For large scattered data sets, we achieve two-dimensional (2D) interpolation at interactive rates and 3D interpolation (3D) with computation times of a few seconds.
authors.affiliation: Institute for Data Analysis and Visualization, Department of Computer Science, University of California, Davis 95616, USA. sunpark@ucdavis.edu
authors.forename: Sung W
authors.initials: SW
authors.lastname: Park
authors.forename: Lars
authors.initials: L
authors.lastname: Linsen
authors.forename: Oliver
authors.initials: O
authors.lastname: Kreylos
authors.forename: John D
authors.initials: JD
authors.lastname: Owens
authors.forename: Bernd
authors.initials: B
authors.lastname: Hamann
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D012815:Signal Processing, Computer-Assisted; D014584:User-Computer Interface