Newsgroups: comp.graphics,sci.math From: firstname.lastname@example.org (Paul Tanenbaum) Subject: Delaunay Interpolation Organization: Johns Hopkins Computer Science Department, Baltimore, MD Date: Tue, 18 Aug 1992 17:41:21 GMT
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. Thanks, +++paul
Newsgroups: comp.graphics,sci.math From: email@example.com (David Watson) Subject: Re: Delaunay Interpolation Organization: University of Western Australia Date: Wed, 19 Aug 1992 00:28:55 GMT
firstname.lastname@example.org (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: email@example.com Department of Mathematics The University of Western Australia Tel: (61 9) 380 3359 Nedlands, WA 6009 Australia. FAX: (61 9) 380 1028
Newsgroups: comp.graphics.algorithms From: firstname.lastname@example.org (A Bowyer) Subject: Re: Contours - How to draw ? Organization: School of Mechanical Engineering, University of Bath, UK Date: Tue, 31 Aug 1993 19:10:12 GMT
In the referenced article, email@example.com (Martin Ameskamp) writes: >In <firstname.lastname@example.org.OZ.AU> email@example.com.OZ.AU (Simon Bullen) writes: > >>firstname.lastname@example.org (Adam Buckley) writes: >> A nice general way to make contour maps from a set of _ANY_ points >>(ie you don't need a regular grid) is to calculate the Delaunay triangulation >>from your set of points, and then doing the contour map is pretty easy. > >> The Delaunay triangulation will turn your set of points into a >>surface composed entirely of triangles; then you merely need to solve the >>contour map problem for each triangle in the graph, which is fairly straight >>forward. You could then pass it through a bezier curve routine to smooth out >>the straight lines, if you liked. > >Right, triangulation is almost always a good idea. I'm not so sure about >the Bezier bit, though. After all, you expect certain things from contours, >e.g. you wouldn't really like them to intersect, and I don't see how you could >guarantee that by applying Bezier routines to a given set of (correct) >piecewise linear contours. > >Martin >-- >Martin Ameskamp, Inst. f. Informatik I (Computing Dept.) >Kiel University, Olshausenstr. 40, 24118 Kiel, Germany >Fax: ++49 431 8804054, Voice: ++49 431 8804474, >email: email@example.com The trouble with countouring methods based on Delaunay triangulations is that they can `click' (i.e. produce contours with spurious kinks) on near-degenerate data. It's better to use natural-neighbour interpolation (invented by Robin Sibson) on the Voronoi dual of the Delaunay triangulation. Start with Sibson, R, and Thompson, G.D. `A seamed Quadratic Element for Contouring' and follow the reference tree. Adrian Bowyer
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.
Last update: .