Progressive-iterative approximation method explained

Progressive-iterative approximation method is an iterative method of data fitting with geometric meanings.^[1] Given the data points to be fitted, the method obtains a series of fitting curves (surfaces) by iteratively updating the control points, and the limit curve (surface) can interpolate or approximate the given data points. It avoids solving a linear system of equations directly and allows flexibility in adding constraints during the iterative process. Therefore, it has been widely used in geometric design and related fields.

The study of the iterative method with geometric meaning can be traced back to the work of scholars such as Prof. Dongxu Qi and Prof. Carl de Boor in the 1970s. In 1975, Qi et al. developed and proved the "profit and loss" algorithm for uniform cubic B-spline curves,^[2] and in 1979, de Boor independently proposed this algorithm.^[3] In 2004, Hongwei Lin and coauthors proved that non-uniform cubic B-spline curves and surfaces have the "profit and loss" property.^[4] Later, in 2005, Lin et al. proved that the curves and surfaces with normalized and totally positive basis all have this property and named it progressive iterative approximation (PIA). In 2007, Maekawa et al. changed the algebraic distance in PIA to geometric distance and named it geometric interpolation (GI).^[5] In 2008, Cheng et al. extended it to subdivision surfaces and named the method progressive interpolation (PI).^[6] Since the iteration steps of the PIA, GI, and PI algorithms are similar and all have geometric meanings, we collectively referred to them as geometric iterative methods (GIM).^[7]

PIA is now extended to several common curves and surfaces in the geometric design field,^[8] including NURBS curves and surfaces,^[9] T-spline surfaces,^[10] implicit curves and surfaces,^[11] etc.

Iteration Methods

Generally, progressive-iterative approximation can be divided into interpolation and approximation schemes. In interpolation algorithms, the number of control points is equal to that of the data points; in approximation algorithms, the number of control points can be less than that of the data points. Specifically, there are some representative iteration methods, such as local-PIA, implicit-PIA, fairing-PIA, and isogeometric least-squares progressive-iterative approximation (IG-LSPIA), which is specialized for solving the isogeometric analysis problem.^[12]

Interpolation scheme: PIA^[13]

To facilitate the description of the PIA iteration format for different forms of curves and surfaces, we write B-spline curves and surfaces, NURBS curves and surfaces, B-spline solids, T-spline surfaces, and triangular Bernstein–Bézier (B–B) surfaces uniformly in the following form:

For example:

• If

P ( t ) is a B-spline curve，then t is a scalar, B _{i(t)} is a B-spline basis function，and P _{i} denotes the control point;

• If

P ( t ) is a B-spline patch with n _{u x} n _{v} control points，then t = (u,v) ，B _{i(t)=N} _{i(u)N} _{i(v)} ，where N _{i(u)} and N _{i(v)} are B-spline basis functions;

• If

P ( t ) is a trivariate B-spline solid with n _{u} x n _{v} x n _{w} control points, then t = (u,v,w) ,B _{i(t)=N} _{i(u)N} _{i(v)N} _{i(w)} , where N _{i(u)} , N _{i(v)} and N _{i(w)} are B-spline basis functions.^[14]

Given an ordered data set

{ Q _{i,i=1,2, … ,n}} ，with parameters t _{i,i=1,2, … ,n} satisfying t _{1<t} _{2< …} , the initial fitting curve (surface) is

where the initial control points of the initial fitting curve (surface)

P ^{( 0 )} _{i} can be randomly selected. Suppose that after the k th iteration, the k th fitting curve (surface）P ^{(k)} (t) is generated by

To construct the

(k +1 ) st curve (surface)，we first calculate the difference vectors，and then update the control points byleading to the (k +1 ) st fitting curve (surface)：In this way, we obtain a sequence of curves (surfaces)It has been proved that this sequence of curves (surfaces) converges to a limit curve (surface) that interpolates the give data points, i.e.,

Approximation scheme: LSPIA^[15]

For the B-spline curve and surface fitting problem, Deng and Lin proposed a least-squares progressive–iterative approximation（LSPIA), which allows the number of control points to be less than that of the data points and is more suitable for large-scale data fitting problems.

Assume that the number of data points is

m ，and the number of control points is n(n\le m) . Following the notations in the Section above, the k th fitting curve (surface) generated after the k th iteration is P ^{(k)} (t) , i.e.,To generate the (k +1 ) st fitting curve (surface)，we compute the following difference vectors in turn:

Difference vectors for data points： and,

Difference vectors for control pointswhere

I _{j} is the index set of the data points in the j th group，whose parameters fall in the local support of the j th basis function, i.e., B _{j(t} _{i)\ne0} . c _{i,} i \in I _{j} are weights that guarantee the convergence of the algorithm, usually taken as c _{i} = 1 , i \in I _{j} .

Finally, the control points of the

(k +1 ) st curve (surface) are updated by P ^{(k +1 )} _{j} = P ^{(k)} _{j} + \Delta ^{(k)} _{j} , leading to the (k +1 ) st fitting curve (surface) P ^{(k+1)} (t) . In this way，we obtain a sequence of curve (surface)，and the limit curve (surface) converges to the least-squares fitting result to the given data points.

Local-PIA^[16]

In the local-PIA, the control points are divided into active and fixed control points, whose subscripts are denoted as $I=\backslash left\backslash$ and $J=\backslash left\backslash$, respectively. Assume that, the $k$th fitting curve (surface) is $\backslash mathbf^(t)=\backslash sum\_^n\backslash mathbf\_j^B\_j(t)$，where the fixed control point satisfyThen，on the one hand, the iterative formula of the difference vector $\backslash mathbf\_h^$ corresponding to the fixed control points isOn the other hand, the iterative formula of the difference vector $\backslash mathbf\_l^$ corresponding to the active control points isArranging the above difference vectors into a one-dimensional sequence,the local iteration format in matrix form is,where, $\backslash mathbf$ is the iteration matrix,$\backslash mathbf\_J$ and $\backslash mathbf\_I$ are the identity matrices andThe above local iteration format converges and can be extended to blending surfaces and subdivision surfaces.^[17]

Implicit-PIA

The progressive iterative approximation format for implicit curve and surface reconstruction is presented in the following. Given an ordered point cloud $\backslash left\backslash \_^n$ and a unit normal vector $\backslash left\backslash \_^n$ on the data points, we want to reconstruct an implicit curve (surface) from the given point cloud. To avoid trivial solution, some offset points $\backslash left\backslash \_^$ are added to the point cloud. They are offset by a distance $\backslash sigma$ along the unit normal vector of each pointAssume that $\backslash epsilon$ is the value of the implicit function at the offset point

Let the implicit curve after the $\backslash alpha$th iteration bewhere $C\_^$ is the control point.

Define the difference vector of data points asNext, calculate the difference vector of control coefficientswhere $\backslash mu$ is the convergence coefficient. As a result, the new control coefficients areleading to the new algebraic B-spline curveThe above procedure is carried out iteratively to generate a sequence of algebraic B-spline functions $\backslash left\backslash$. The sequence converges to a minimization problem with constraints when the initial control coefficients $C\_^=0$.

Assume that the implicit surface generated after the $\backslash alpha$th iteration isthe iteration format is similar to that of the curve case.^[18]

Fairing-PIA^[19]

To develop fairing-PIA, we first define the functionals as follows:where $B\_(t)$ represents the $r$th derivative of the basis function $B\_j(t)$, (e.g. B-spline basis function).

Let the curve after the $k$th iteration beTo construct the new curve $\backslash mathbf^(t)$，we first calculate the $(k\; +\; 1)$st difference vectors for data points,Then, the fitting difference vectors and the fairing vectors for control points are calculated by

Finally, the control points of the

(k +1 ) st curve are produced bywhere \mu _{j} is a normalization weight, and \omega _{j} is a smoothing weight corresponding to the j th control point. The smoothing weights can be employed to adjust the smoothness individually, thus bringing great flexibility for smoothness. The larger the smoothing weight is, the smoother the generated curve is. The new curve is obtained as follows

In this way, we obtain a sequence of curves $\backslash left\backslash$. The sequence converges to the solution of the conventional fairing method based on energy minimization when all smoothing weights are equal ($\backslash omega\_j=\backslash omega$). Similarly, the fairing-PIA can be extended to the surface case.

IG-LSPIA^[20]

Given a boundary value problem

Notes and References

1. Lin . Hong-Wei . Bao . Hu-Jun . Wang . Guo-Jin . Totally positive bases and progressive iteration approximation . Computers & Mathematics with Applications . 2005 . 50 . 3–4 . 575–586 . 10.1016/j.camwa.2005.01.023 . 0898-1221.
2. Qi . Dongxu . Tian . Zixian . Zhang . Auxin . Feng . Jiabin . 1975 . The method of numeric polish in curve fitting . Acta Math Sinica . 18 . 3 . 173–184.
3. Carl . de Boor . 1979 . How does Agee's smoothing method work? . Proceedings of the 1979 Army Numerical Analysis and Computers Conference, ARO Report..
4. Lin . Hongwei . Wang . Guojin . Dong . Chenshi . 2004 . Constructing iterative non-uniform B-spline curve and surface to fit data points . Science in China Series F . 47 . 3 . 315 . 10.1360/02yf0529 . 966980 . 1009-2757.
5. Maekawa . Takashi . Yasunori . Matsumoto . Ken . Namiki . 2007 . Interpolation by geometric algorithm . Computer-Aided Design . 39 . 4 . 313–323. 10.1016/j.cad.2006.12.008 .
6. Book: Cheng . Fuhua . Fan . Fengtao . Lai . Shuhua . Huang . Conglin . Wang . Jiaxi . Yong . Junhai . Advances in Geometric Modeling and Processing . Progressive Interpolation Using Loop Subdivision Surfaces . Lecture Notes in Computer Science . 2008 . 4975 . 526–533. 10.1007/978-3-540-79246-8_43 . 978-3-540-79245-1 .
7. Lin . Hongwei . Maekawa . Takashi . Deng . Chongyang . Survey on geometric iterative methods and their applications . Computer-Aided Design . 2018 . 95 . 40–51 . 10.1016/j.cad.2017.10.002 . 0010-4485.
8. Book: Hoschek, Josef . Fundamentals of computer aided geometric design . February 1993 . A. K. Peters, Ltd. . 978-1-56881-007-2 . USA.
9. Shi . Limin . Wang . Renhong . 2006 . An iterative algorithm of NURBS interpolation and approximation . Journal of Mathematical Research with Applications . 26 . 4 . 735–743.
10. Lin . Hongwei . Zhang . Zhiyu . An Efficient Method for Fitting Large Data Sets Using T-Splines . SIAM Journal on Scientific Computing . 2013 . 35 . 6 . A3052–A3068 . 10.1137/120888569 . 2013SJSC...35A3052L . 1064-8275.
11. Hamza . Yusuf Fatihu . Lin . Hongwei . Li . Zhao . 2020 . Implicit progressive-iterative approximation for curve and surface reconstruction . Computer Aided Geometric Design . 77 . 101817. 10.1016/j.cagd.2020.101817 . 1909.00551 . 202540812 .
12. Hughes . T. J. R. . Cottrell . J. A. . Bazilevs . Y. . 2005-10-01 . Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement . Computer Methods in Applied Mechanics and Engineering . 194 . 39 . 4135–4195 . 10.1016/j.cma.2004.10.008 . 2005CMAME.194.4135H . 0045-7825.
13. Chen . Jie . Wang . Guo-Jin . Progressive iterative approximation for triangular Bézier surfaces . Computer-Aided Design . 2011 . 43 . 8 . 889–895 . 10.1016/j.cad.2011.03.012 . 0010-4485.
14. Lin . Hongwei . Jin . Sinan . Hu . Qianqian . Liu . Zhenbao . 2015 . Constructing B-spline solids from tetrahedral meshes for isogeometric analysis . Computer Aided Geometric Design . 35-36 . 109–120 . 10.1016/j.cagd.2015.03.013 . 0167-8396.
15. Deng . Chongyang . Lin . Hongwei . Progressive and iterative approximation for least squares B-spline curve and surface fitting . Computer-Aided Design . 2014 . 47 . 32–44 . 10.1016/j.cad.2013.08.012 . 0010-4485.
16. Lin . Hongwei . Local progressive-iterative approximation format for blending curves and patches . Computer Aided Geometric Design . 2010 . 27 . 4 . 322–339 . 10.1016/j.cagd.2010.01.003 . 0167-8396.
17. Zhao . Yu . Lin . Hongwei . Bao . Hujun . 2012 . Local progressive interpolation for subdivision surface fitting . Journal of Computer Research and Development . 49 . 8 . 1699–1707.
18. Liu . Shengjun . Liu . Tao . Hu . Ling . Shang . Yuanyuan . Liu . Xinru . 2021-09-01 . Variational progressive-iterative approximation for RBF-based surface reconstruction . The Visual Computer . en . 37 . 9 . 2485–2497 . 10.1007/s00371-021-02213-3 . 1432-2315.
19. Jiang . Yini . Lin . Hongwei . Huang . Weixian . 2023-05-16 . Fairing-PIA: progressive-iterative approximation for fairing curve and surface generation . The Visual Computer . 40 . 3 . 1467–1484 . 10.1007/s00371-023-02861-7 . 2211.11416 . 0178-2789.
20. Jiang . Yini . Lin . Hongwei . 2023-02-10 . IG-LSPIA: Least Squares Progressive Iterative Approximation for Isogeometric Collocation Method . Mathematics . 11 . 4 . 898 . 10.3390/math11040898 . 2227-7390 . free .