Renka I¶
The Renka I algorithm is part of the Estimate Scattered Data option in the Non-Parametric menu. It is also offered in the Interpolate Uniform Grid option.
Author
Robert Renka
Dept. of Computer Sciences
University of North Texas
Denton, TX 76203-6886
E-mail: renka@cs.unt.edu
Web page: http://www.cs.unt.edu/home/renka/
References
"Algorithm 751: TRIPACK: A Constrained Two-Dimensional Delaunay Triangulation Package", ACM Transactions on Mathematical Software, Vol. 22, no. 1, March 1996, p1-8.
"Algorithm 752: SRFPACK: Software for Scattered Data Fitting with a Constrained Surface under Tension", ACM Transactions on Mathematical Software, Vol. 22, no. 1, March 1996, p9-17.
Description
Robert Renka’s triangulation procedures have become a standard within non-parametric technology. His triangulation routines are used in the Akima II and Preusser options. The Renka I option consists of the primary capabilities offered by the TRIPACK and SRFPACK packages. This algorithm is one of the fastest of the various scattered data procedures and is thus also used for graphical rendering of the surfaces for raw data and residuals within TableCurve 3D. The Renka I C1 (once continuously differentiable) interpolant is applied successively to nodal gradients, enabling the overall algorithm to exhibit C3 properties. This procedure thus offers accurate and smooth first and second order partial derivatives. Both interpolations and extrapolations have this higher order of smoothness. A global procedure for gradient estimation enables overall trends within the data to be preserved. A tensioned interpolant may be useful for surfaces with rapidly changing features. A constrained estimation may be useful for improving extrapolations when appreciable noise is present in the data.
Revisions to Algorithm
Higher convergence criteria were implemented so that gradient estimations will be identical to the Preusser algorithm, which requires greater derivative accuracy for subsequent higher order derivative computations. The data are also intrinsically scaled to a unit square. Estimated partial derivatives are computed using a successive gradient procedure enabling smooth and continuous first and second order partial derivatives.
Interpolation
The Renka I interpolant is the Clough-Tocher finite element. It is cubic in each of the three subtriangles of equal area obtained by joining the vertices to the barycenter, but has quadratic precision. Along each triangle side, the interpolant is the Hermite cubic of the endpoint values and tangential gradient components, and the normal gradient component of the interpolant varies linearly between the interpolated endpoint normal components. Since values and first partials on a triangle side depend only on the endpoint data, the method results in a C1 interpolant over a triangulation. Second derivatives of the interpolant are discontinuous across subtriangle as well as main triangle boundaries. By computing successive gradients and using the C1 interpolant with nodal partial derivatives, the first partials are both smooth and continuous (a C2 property) and the second order partials are likewise smooth and continuous (a C3 property).
Extrapolation
The extrapolation is accomplished via passing a linear function of one variable through the target point and directional derivative from the closest boundary point in the interpolated surface to this target point. The C1 property is maintained throughout the extrapolation and at the data boundaries. Since the Preusser algorithm shares the Renka I extrapolant and gradient estimation procedure, its basic function extrapolations will exactly match those of this algorithm. The successive gradient procedure applies equally to extrapolants, and as such the first order partial derivative extrapolations will exhibit this C2 property and the second order partials will have this C3 property. The transition between interpolated and extrapolated regions will be completely smooth.
Estimated Partial Derivatives
Estimated partial derivatives are done using interpolation based upon successive gradients computed using the global gradient algorithm. This approach tends to produce a very favorable accuracy for both first and second order partial derivatives. The estimated derivatives are used for graphing the partial derivative surfaces and for partial derivatives computed in the Evaluation procedure. The five partial derivatives offered by TableCurve 3D will be completely smooth for interpolation, extrapolation, and across the transition. This is the recommended algorithm for accurate higher order partial derivatives.
Estimated Volumes
The primary method is to interpolate a uniform grid of 10,000 points and to evaluate the double integral using a bicubic B-spline integration procedure. The error reported in the Evaluation procedure will be the fractional difference with a similar 2,500 node integration. A repeat evaluation with the same limits will use an actual double integration procedure using the actual interpolant. A very fast double Gaussian quadrature procedure is first attempted to 1E-5 precision. If this is unsuccessful, a double adaptive quadrature procedure is then used.
Considerations
This algorithm is fast, robust, accurate, and offers smooth partial derivatives. The Renka I procedure fared very well in accuracy tests as its global gradient procedure was shown to be particularly favorable with more difficult surfaces. While this algorithm is still subject to thin triangle drawbacks and the non-unique nature of Delaunay triangulations, the global gradient computations aid in preserving overall shape properties. Due to identical first order gradient computation procedures, as well as a common extrapolant, the differences between the Renka I algorithm and the Preusser algorithms will be subtle. In effect, the Renka I and Preusser procedures can be regarded as a single algorithm with a variable order interpolant. An optional tensioned interpolant may possibly benefit surfaces with rapidly changing features. Extrapolations with noisy data sets can be improved by optional constraints globally computed just beyond the data bounds.
Algorithm Adjustments
This algorithm contains a tension and a constraint option.