🚀 go-pugleaf

$@!!0JA0!"#3<!85$N%5%s%W%kE@$N4V$NJd4V$NOC$7$,$3$3$G$G$F$^$7$?$,!"4XO"Ej9F(J
$@$,$"$j$^$7$?$N$G!"E>:\$7$F$*$-$^$9!#(J

					$@B@ED!!>;9'(J
					mohta@cc.titech.ac.jp

Path: titccy.cc.titech!cs.titech!wnoc-tyo-news!sh.wide!sun-barr!olivea!uunet!munnari.oz.au!uniwa!watson
>From: watson@maths.uwa.oz.au (David Watson)
Newsgroups: comp.graphics,sci.math
Subject: Re: Delaunay Interpolation
Keywords: surface interpolation, Delaunay triangulation, CAGD
Message-ID: <1992Aug19.002855.8728@uniwa.uwa.edu.au>
Date: 19 Aug 92 00:28:55 GMT
References: <1992Aug18.174121.18067@blaze.cs.jhu.edu>
Sender: news@uniwa.uwa.edu.au (USENET News System)
Organization: University of Western Australia
Lines: 41
Xref: titccy.cc.titech comp.graphics:26107 sci.math:17187
Nntp-Posting-Host: madvax.maths.uwa.oz.au


pjt@newton.cs.jhu.edu (Paul Tanenbaum) writes:

>     Suppose I have a bunch of sample points from the boundary of a closed
>volume in $R^3$.  Suppose in particular that I have been given the Delaunay
>triangulation of these boundary points.  I'd like to interpolate a $C^3$
>surface through these vertices.  The related surface-interpolation algorithms
>I've found seem not to be applicable:  they either assume that the
>triangulation is regular (usually of degree six) or that the surface is
>monotonic with respect to some plane.
>     Does there exist an algorithm to solve this problem?  References to
>the literature would be greatly appreciated.

There are many ways to interpolate from a Delaunay tesselation.  The quickest
is with barycentric coordinates but is only $C^0$.  If you require higher
smoothness then it is a question of data set size - for 100 data or so just
fit a radial basis spline.  If you must deal with subsets, splines will
give discontinuities at subset boundaries.  Sibson's natural neighbour
interpolation -
Sibson, R., 1981, A brief description of natural neighbour interpolation, _in_ 
Barnett, V., ed., Interpreting multivariate data: John Wiley, p.21--36.
Alfield, P., 1989, Scattered data interpolation in three or more 
variables, _in_ Mathematical methods in computer aided geometric 
design, Lyche, T., and Schumaker, L.L., ed., Academic Press, San Diego,
p. 12-13.
Watson, D.F., and Philip, G.M., 1987, Neighborhood-based interpolation: Geobyte, 2(2),
p. 12--16.
will provide continuous slopes everywhere but at the data points themselves.
Incorporating estimated gradients will give total continuity.

For a summary of interpolation techniques that can be extended to higher
dimensions, see
	ftp marlin.nosc.mil /pub/contour.file
for an ASCII, TeX, or PostScript, file.

Email questions are welcome.
--
Dave Watson                          Internet: watson@maths.uwa.edu.au
Department of Mathematics            
The University of Western Australia               Tel: (61 9) 380 3359
Nedlands, WA 6009  Australia.                     FAX: (61 9) 380 1028