We consider the problem of scattered data interpolation in R3 using curve networks extended to smooth interpolation surfaces. Nielson (1983) proposed a solution that constructs smooth interpolation curve network with minimal L2-norm of the second derivative. The obtained minimum norm network (MNN) is cubic. Vlachkova (2020) generalized Nielson's result to smooth interpolation curve networks with minimal Lp-norm of the second derivative for 1<p<∞. Vlachkova and Radev (2020) proposed an algorithm that degree elevates the MNN to quartic curve network and then extends it to a smooth surface consisting of quartic triangular Bézier surfaces. Here we apply this algorithm to the following two curve networks: (i) the MNN which is degree elevated to quartic; (ii) the minimum Lp-norm network for p=3/2 which is slightly modified to quartic. We evaluate and compare the quality and the shape of the obtained surfaces with respect to different criteria. We performed a large number of experiments using data of increasing complexity. Here we present and comment the results of our experiments.
Interpolation of data points in ℝ3 by smooth surface is a fundamental problem in applied mathematics which nfids applications in a variety of efilds such as medi cine, architecture, archeology, computer graphics and animation, bioinformatics, scienticfi visualization, and more. In general the problem can be formulated as follows: Given a set of points (xi, yi, zi) ∈ ℝ3, i = 1, ..., n, nfid a bivariate function F(x, y) denfied in a certain domain D containing points Vi = (xi, yi), such that F possesses continuous partial derivatives up to a given order, and F(xi, yi) = zi.
Various methods and approaches for solving this problem were proposed and discussed, see, e.g., the surveys [1, 2, 3], and also [4, 5]. A standard approach to solve the problem consists of two steps, see [1]: 1. Construct a triangulation T = T(V1, ..., VN); 2. For every triangle in construct a surface which interpolates the data in the three vertices.
The interpolation surface constructed in Step 2 is usually polynomial or piecewise polynomial. Typically, the patches are computed with a priori prescribed normal vectors at the data points G1 or G2 smoothness of the resulting surface is achieved either by increasing the degree of the patches, or by the so called splitting [6] in which for each triangle in T a macro-patch consisting of a ifxed number of Bézier sub-patches is constructed. Splitting allows to keep the degree of the Bézier patches low by increasing the degrees of freedom. In practice using patches of least degree and splitting is preferable since it is computationally simple and eficient.
Shirman and Séquin [7, 8] construct a G1 smooth surface consisting of quartic
triangular Bézier surfaces. Their method assumes that the normal vectors at the
data points are given as part of the input. Shirman and Séquin construct a smooth
cubic curve network defined on the edges of T, first, and then degree elevate it
to quartic. Next, they apply splitting where for each triangle in T a macro-patch
consisting of three quartic Bézier sub-patches is constructed. To compute the
inner Bézier control points closest to the boundary of the macro-patch, Shirman and
Séquin use a method proposed by Chiyokura and Kimura [
Nielson [
Step 1. Triangulation. Construct a triangulation T of Vi, i = 1, ..., n. The domain D is the union of all triangles in T.
Step 2. Minimum norm network. The interpolant F and its first order partial derivatives are defined on the edges of T to satisfy an extremal property. The resulting MNN is a cubic curve network, i. e. on every edge of T it is a cubic polynomial.
Step 3. Interpolation surface. The MNN obtained is extended to F by an appropriate blending method based on convex combination schemes. Nielson’s interpolant F is a rational function on every triangle in T.
Andersson et al. [
Vlachkova and Radev [
Vlachkova [
In this paper, we consider the following two curve networks: (i) Nielson’s MNN which is degree elevated to quartic; (ii) the minimum Lp-norm network for p = 3/2 which is slightly modified to quartic.
Using the algorithm proposed in [
Our work and contributions presented here are in the field of experimental
algorithmics. We share and comment on the observations from the experiments
performed, which will help to further optimize the quality and the shape of the
interpolation surfaces generated with the algorithm proposed in [
Let n ≥ 3 be an integer and Pi: = (xi, yi, zi), i = 1, ..., n be diferent points in ℝ3. We call this set of points data. We assume that the projections Vi = (xi, yi) of the data Oxy into the plane are diferent and non-collinear. Stressing the fact that Vi are in a general position, although not necessarily irregularly placed, we call such data scattered.
Definition 1. A collection of non-overlapping, non-degenerate triangles in is a triangulation of the points Vi, i = 1, ..., n, if the set of the vertices of the triangles coincides with the set of the points Vi, i = 1, ..., n.
Hereafter we assume that a triangulation T of the points Vi, i = 1, ..., n, is given and fixed. Furthermore, for the sake of simplicity, we assume that the do main D formed by the union of the triangles in T is connected. In general D is a collection of polygons with holes. The set of the edges of the triangles in T is denoted by E. If there is an edge between Vi and Vj in E, it will be referred to by eij or simply by e if no ambiguity arises.
Definition 2. A curve network is a collection of real-valued univariate functions {fe}e∈E defined on the edges in E.
With any real-valued bivariate function defined on we naturally associate the curve network defined as the restriction of on the edges in , i. e. for , (1) where 0 ≤ t ≤ || e || and || e || =
Furthermore, according to the context F will denote either a real-valued bivariate function or a curve network defined by (1). For p, such that 1 < p < ∞, we introduce the following class of smooth interpolants
where is the class of bivariate continuous functions defined in D, AC is the class of univariate absolutely continuous functions defined in [0, || e ||], and Lp is the class of univariate functions defined in [0, || e ||] whose p-th power of the absolute value is Lebesgue integrable. The restrictions on E of the functions in Fp form the corresponding class of so-called smooth interpolation curve networks
The smoothness of the interpolation curve network F ∈ Cp(E) geometrically means that at each point Pi there is a tangent plane to F, where a plane is tangent to the curve network at a point Pi if it contains the tangent vectors at Pi of the curves incident to Pi.
Inner product and Lp-norm are defined in Cp(E) by (2) where F ∈ Cp(E) and G: = {ge}e∈E ∈ Cp(E). We denote the networks of the second derivative of F by F″: = {fe″}e∈E and consider the following extremal problem:
For i = 1, ..., n let mi denote the degree of the vertex Vi, i. e. the number of
the edges in E incident to Vi. In [
Let q be the conjugate of p, i.e. 1/p + 1/q = 1. In [
Now we briefly discuss the constrained interpolation problem of finding a
minimum norm network which is convex along the edges of T. We recall that this
problem was set and solved in [
For a given triangulation, there is a unique continuous function L : D → ℝ1 that is linear inside each of the triangles of T and interpolates the data.
Definition 3. Scattered data D in are convex if there exists a triangulation T of Vi, i = 1, ..., n, such that the corresponding function L is convex. The data are strictly convex if they are convex and the gradient of L has a jump discontinuity across each edge inside D.
We introduce the class of smooth interpolation edge convex curve networks
and consider the following constrained extremal interpolation problem
In [
where (x)+ : = max(x, 0), and αis ∈ ℝ. The coeficients αis are obtained as the unique solution to a nonlinear system of equations. The solution F̂ * on each edge in T is either a convex cubic polynomial, or a convex cubic spline with one knot consisting of a linear function and a convex cubic polynomial.
In this paper we consider the unconstrained problem (Pp) for p = 3/2 and also the constrained problem (P̂ ). The solution of (Pp) for p = 3/2 (hence q =3) on each edge in T is a quartic spline with at most one knot. For both problems, we slightly modify their solutions to obtain a polynomial curve networks (quartic for (Pp) for p = 3/2, and cubic for (P̂ )) while preserving the same tangent planes at the data points.
Here we present and comment on two examples from the experiments
performed and we share our observations and conclusions. We use BezierView [
Example 1. We consider data obtained from a symmetric triangular pyramid. We have n = 4, V4 = (0,0), and zi = 0, i = 1,2,3, z4 = –1/2. The triangulation and the corresponding MNN are shown in Figure 1. The highlight lines on the interpolation surface are visualized in Figure 2 (left). The Gaussian curvature is visualized in Figure 2 (right) where the color scale goes from blue (low) to red (large). The minimum value of the Gaussian curvature is -11.8318, the maximum value is 34.3368. The surface that interpolates the edge convex MNN is shown in Figure 3. The highlight lines of this surface are visualized in Figure 3 (left) and its Gaussian curvature is visualized in Figure 3 (right). The minimum value of the Gaussian curvature is -0.6046, and the maximum value is 36.1598.
Example 2. We consider the convex function f = exp((x – 0.5)2 + (y – 0.5)2) which is sampled at 25 points shown in Table 1. The triangulation, which is shown in Figure 4 (left), is the Delaunay triangulation. The corresponding edge convex MNN is shown in Figure 4 (right). The highlight lines on the surface are visualized in Figure 6.
For Example 1, see Figure 2, we can see that our interpolant for the unconstrained case is visually pleasant: the highlight lines are smooth with a small number of inflection points (if any), and the Gaussian curvature is evenly dis tributed. The highlight lines of the surface interpolating the edge convex MNN in Figure 3 (left) also look nicely as in the unconstrained case but the Gaussian curvature in Figure 3 (right) is not evenly distributed.
For Example 2 where the data are sampled from the convex exponential
function, it is clearly seen that the interpolation surface generated from our algorithm
presented in [
The above observations shows that the algorithm presented in [
Given the importance of surface modeling and simulation techniques in
practice, it is important to better understand and create interpolation surfaces with
good approximation properties based on diferent criteria. In the future we intend
to enlarge our work by analyzing in-depth more data sets, which will support
further optimization of our algorithm [
This work was supported in part by Sofia University Science Fund Grant No. 80-10-109/2022, and European Regional Development Fund and the Operational Program “Science and Education for Smart Growth” under contract № BG05M2OP001-1.001-0004 (2018-2023). 6. References