Progressive-iterative approximation method

Generally, progressive-iterative approximation (PIA) 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,{{Cite journal |last=Lin |first=Hongwei |date=2010 |title=Local progressive-iterative approximation format for blending curves and patches |journal=Computer Aided Geometric Design |volume=27 |issue=4 |pages=322–339 |doi=10.1016/j.cagd.2010.01.003 |issn=0167-8396}} implicit-PIA, fairing-PIA,{{Cite journal |last1=Jiang |first1=Yini |last2=Lin |first2=Hongwei |last3=Huang |first3=Weixian |date=2023-05-16 |title=Fairing-PIA: progressive-iterative approximation for fairing curve and surface generation |journal=The Visual Computer |volume=40 |issue=3 |pages=1467–1484 |arxiv=2211.11416 |doi=10.1007/s00371-023-02861-7 |issn=0178-2789}} and isogeometric least-squares progressive-iterative approximation (IG-LSPIA)—that are specialized for solving the isogeometric analysis problem.{{Cite journal |last1=Hughes |first1=T. J. R. |last2=Cottrell |first2=J. A. |last3=Bazilevs |first3=Y. |date=2005-10-01 |title=Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement |url=https://www.sciencedirect.com/science/article/pii/S0045782504005171 |journal=Computer Methods in Applied Mechanics and Engineering |volume=194 |issue=39 |pages=4135–4195 |doi=10.1016/j.cma.2004.10.008 |bibcode=2005CMAME.194.4135H |issn=0045-7825}}

[[File:截屏2024-08-10 09.23.08.png|thumb|439x439px|Interpolation scheme of PIA
Top left: The data points and the initial control polygon (Here, the initial control points are taken as the data points). Top right: The initial curve and the difference vectors. Bottom left: New control polygon is generated by adding the difference vectors to the old control points. Bottom right: The new control polygon and new curve (in purple).

]]

In interpolation algorithms of PIA,{{Cite journal |last1=Chen |first1=Jie |last2=Wang |first2=Guo-Jin |date=2011 |title=Progressive iterative approximation for triangular Bézier surfaces |journal=Computer-Aided Design |volume=43 |issue=8 |pages=889–895 |doi=10.1016/j.cad.2011.03.012 |issn=0010-4485}} every data point is used as a control point. To facilitate the description of the PIA iteration format for different forms of curves and surfaces, the following formula is uniformly used:

$$\backslash mathbf\{P\}(\backslash mathbf\{t\})=\backslash sum\_\{i=1\}^n\backslash mathbf\{P\}\_iB\_i(\backslash mathbf\{t\}).$$

For example:

• If $\backslash mathbf\{P\}(\backslash mathbf\{t\})$ is a B-spline curve, then $\backslash mathbf\{t\}$ is a scalar, $B\_i(t)$ is a B-spline basis function, and $\backslash mathbf\{P\}\_i$ denotes the control point;
• If $\backslash mathbf\{P\}(\backslash mathbf\{t\})$ is a B-spline patch with $n\_u\backslash times\; n\_v$ control points, then $\backslash mathbf\{t\}=(u,v)$ and $B\_i(\backslash mathbf\{t\})=N\_i(u)N\_i(v)$, where $N\_i(u)$ and $N\_i(v)$ are B-spline basis functions;
• If $\backslash mathbf\{P\}(\backslash mathbf\{t\})$ is a trivariate B-spline solid with $n\_u\; \backslash times\; n\_v\; \backslash times\; n\_w$ control points, then $\backslash mathbf\{t\}=(u,v,w)$ and $B\_i(\backslash mathbf\{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.{{Cite journal |last1=Lin |first1=Hongwei |last2=Jin |first2=Sinan |last3=Hu |first3=Qianqian |last4=Liu |first4=Zhenbao |date=2015 |title=Constructing B-spline solids from tetrahedral meshes for isogeometric analysis |url=http://dx.doi.org/10.1016/j.cagd.2015.03.013 |journal=Computer Aided Geometric Design |volume=35-36 |pages=109–120 |doi=10.1016/j.cagd.2015.03.013 |issn=0167-8396|url-access=subscription }}

Additionally, this can be applied to NURBS curves and surfaces, T-spline surfaces, and triangular Bernstein–Bézier surfaces.

Given an ordered data set $\backslash mathbf\{Q\}\_i$ with parameters $t\_i$ satisfying

$$\backslash mathbf\{P\}^\{(0)\}(t)=\backslash sum\_\{i=1\}^n\backslash mathbf\{P\}\_i^\{(0)\}B\_i(t)$$

where the initial control points of the initial fitting curve $\backslash mathbf\{P\}\_i^\{(0)\}$ can be randomly selected. Suppose that after the $k$th iteration, the $k$th fitting curve $\backslash mathbf\{P\}^\{(k)\}(t)$ is generated by

{{NumBlk|:|$\backslash mathbf\{P\}^\{(k)\}(t)=\backslash sum\_\{i=1\}^n\backslash mathbf\{P\}\_i^\{(k)\}B\_i(t).$|{{EquationRef|1}}}}

To construct the $(k+1)$st curve, we first calculate the difference vectors,

$$\backslash mathbf\{\backslash Delta\}^\{(k)\}\_i=\backslash mathbf\{Q\}\_i-\backslash mathbf\{P\}^\{(k)\}(t\_i),\; \backslash quad$$

i=1,2,\cdots,n

and use them to update the control points by

$$\backslash mathbf\{P\}\_i^\{(k+1)\}=\backslash mathbf\{P\}\_i^\{(k)\}+\backslash mathbf\{\backslash Delta\}\_i^\{(k)\}$$

which leads to the $(k+1)$st fitting curve:

\mathbf{P}^{(k+1)}(t)=\sum_{i=1}^n\mathbf{P}_i^{(k+1)}B_i(t).

In this way, we obtain a sequence of curves $$

\mathbf{P}^{(\alpha)}(t),\alpha=0,1,2,\cdots

, which converges to a limit curve that interpolates the give data points, i.e.,

\lim \limits_{\alpha\rightarrow\infty}\mathbf{P}^{(\alpha)}(t_i)=\mathbf{Q}_i, \quad

i=1,2,\cdots,n.

[[File:截屏2024-08-13 09.51.05.png|thumb|641x641px|Approximation scheme: LSPIA
Top left: Data points $\backslash mathbf\{Q\}\_i$ (blue circles), initial control polygon (green lines) constructed from a subset of $\backslash mathbf\{Q\}$, and initial fitting curve $\backslash mathbf\{P\}^\{(0)\}\; (t)$. Top right: Difference vectors $\backslash boldsymbol\{\backslash delta\}^\{(k)\}\_i$ for data points and difference vectors $\backslash mathbf\{\backslash Delta\}^\{(k)\}\_j$ for control points. Bottom: A new control polygon (purple lines) is generated by adding $\backslash mathbf\{\backslash Delta\}^\{(k)\}\_j$ to the old control points; it then creates the next fitting curve $\backslash mathbf\{P\}^\{(1)\}\; (t)$ (purple curve).

]]

For the B-spline curve and surface fitting problem, Deng and Lin proposed a least-squares progressive–iterative approximation (LSPIA),{{Cite journal |last1=Deng |first1=Chongyang |last2=Lin |first2=Hongwei |date=2014 |title=Progressive and iterative approximation for least squares B-spline curve and surface fitting |journal=Computer-Aided Design |volume=47 |pages=32–44 |doi=10.1016/j.cad.2013.08.012 |issn=0010-4485}} which allows the number of control points to be less than the number of the data points and is more suitable for large-scale data fitting problems.

Assume there exists $m$ data points and $n$ control points, where $n\backslash le\; m$. Start with equation ({{EquationNote|1}}), which gives the $k$th fitting curve as

\mathbf{P}^{(k)}(t)=\sum_{j=1}^n\mathbf{P}_j^{(k)}B_j(t).

To generate the $(k+1)$th fitting curve, first compute the difference vectors for the data points

\boldsymbol{\delta}^{(k)}_i=\mathbf{Q}_i-\mathbf{P}^{(k)}(t_i), \quad

i=1,2,\cdots,m

and then the difference vectors for the control points

$$\backslash mathbf\{\backslash Delta\}^\{(k)\}\_j=\backslash frac\{$$

\sum_{i \in I_j}{c_i B_j(t_i) \boldsymbol{\delta}_i^{(k)}}}{\sum_{i \in I_j}c_i B_j(t_i)}, \quad

j = 1,2,\cdots,n

where $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)\backslash ne0$. The $c\_i$ are weights that guarantee the convergence of the algorithm, usually taken as $c\_i\; =\; 1,\; i\; \backslash in\; I\_j$.

Finally, the control points of the $(k+1)$th curve are updated by $\backslash mathbf\{P\}\_j^\{(k+1)\}=\backslash mathbf\{P\}\_j^\{(k)\}+\backslash mathbf\{\backslash Delta\}\_j^\{(k)\},$ leading to the $(k+1)$th fitting curve $\backslash mathbf\{P\}^\{(k+1)\}(t)$. In this way, we obtain a sequence of curve, and the limit curve converges to the least-squares fitting result to the given data points.

File:截屏2024-08-13 13.45.43.png

In the local-PIA method, the control points are divided into active and fixed control points, whose subscripts are denoted as $I=\backslash left\backslash \{i\_1,i\_2,\backslash cdots,i\_I\backslash right\backslash \}$ and $J=\backslash left\backslash \{j\_1,j\_2,\backslash cdots,j\_J\backslash right\backslash \}$, respectively. Assume that, the $k$th fitting curve is $\backslash mathbf\{P\}^\{(k)\}(t)=\backslash sum\_\{j=1\}^n\backslash mathbf\{P\}\_j^\{(k)\}B\_j(t)$, where the fixed control points satisfy

\mathbf{P}_j^{(k)}=\mathbf{P}_j^{(0)},\quad j\in J,\quad k=0,1,2,\cdots.

Then, on the one hand, the iterative formula of the difference vector $\backslash mathbf\{\backslash Delta\}\_h^\{(k+1)\}$ corresponding to the fixed control points is

$$\backslash begin\{aligned\}$$

\mathbf{\Delta}_h^{(k+1)}&=\mathbf{Q}_h-\sum_{j=1}^n\mathbf{P}_j^{(k+1)}B_j(t_h)\\

&=\mathbf{Q}_h-\sum_{j\in J}\mathbf{P}_j^{(k+1)}B_j(t_h)-\sum_{i\in I}\left(\mathbf{P}_i^{(k)}+\mathbf{\Delta}_i^{(k)}\right)B_i(t_h)\\

&=\mathbf{Q}_h-\sum_{j=1}^n\mathbf{P}_j^{(k)}B_j(t_h)-\sum_{i\in I}\mathbf{\Delta}_i^{(k)}B_i(t_h)\\

&=\mathbf{\Delta}_h^{(k)}-\sum_{i\in I}\mathbf{\Delta}_i^{(k)}B_i(t_h), \quad h\in J.

\end{aligned}

On the other hand, the iterative formula of the difference vector $\backslash mathbf\{D\}\_l^\{(k+1)\}$ corresponding to the active control points is

\begin{aligned}

\mathbf{\Delta}_l^{(k+1)}&=\mathbf{Q}_l-\sum_{j=1}^n\mathbf{P}_j^{(k+1)}B_j(t_l)\\

&=\mathbf{Q}_l-\sum_{j=1}^n\mathbf{P}_j^{(k)}B_j(t_l)-\sum_{i\in I}\mathbf{\Delta}_i^{(k)}B_i(t_l)\\

&=\mathbf{\Delta}_l^{(k)}-\sum_{i\in I}\mathbf{\Delta}_i^{(k)}B_i(t_l)\\

&=-\mathbf{\Delta}_{i_1}^{(k)}B_{i_1}(t_l)-\mathbf{\Delta}_{i_2}^{(k)}B_{i_2}(t_l)-\cdots+\left(1-B_l(t_l)\right)\mathbf{\Delta}_l ^{(k)}-\cdots-\mathbf{\Delta}_{i_I}^{(k)}B_{i_I}(t_l),\quad l\in I.

\end{aligned}

Arranging the above difference vectors into a one-dimensional sequence,

\mathbf{D}^{(k+1)}=\left[\mathbf{\Delta}_{j_1}^{(k+1)} ,\mathbf{\Delta}_{j_2}^{(k+1)},\cdots,\mathbf{\Delta}_{j_J}^{(k+1)},\mathbf{\Delta}_{i_1}^{(k+1)},\mathbf{\Delta}_{i_2}^{(k+1)},\cdots,\mathbf{\Delta}_{i_I}^{(k+1)}\right]^T,\quad k=0,1,2,\cdots,

the local iteration format in matrix form is,

\mathbf{D}^{(k+1)}=\mathbf{T}\mathbf{D}^{(k)},\quad k=0,1,2,\cdots,

where $\backslash mathbf\{T\}$ is the iteration matrix:

\mathbf{T}=

\begin{bmatrix}

\mathbf{E}_J & -\mathbf{B}_1\\

0 & \mathbf{E}_I-\mathbf{B}_2

\end{bmatrix},

where $\backslash mathbf\{E\}\_J$ and $\backslash mathbf\{E\}\_I$ are the identity matrices and

\mathbf{B}_1=

\begin{bmatrix}

B_{i_1}\left(t_{j_1} \right) & B_{i_2}\left(t_{j_1} \right) & \cdots &B_{i_I}\left(t_{j_1} \right) \\

B_{i_1}\left(t_{j_2} \right) & B_{i_2}\left(t_{j_2} \right) & \cdots &B_{i_I}\left(t_{j_2} \right) \\

\vdots & \vdots &\vdots & \vdots \\

B_{i_1}\left(t_{j_J} \right) & B_{i_2}\left(t_{j_J} \right) & \cdots &B_{i_I}\left(t_{j_J} \right) \\

\end{bmatrix},

\mathbf{B}_2=

\begin{bmatrix}

B_{i_1}\left(t_{i_1} \right) & B_{i_2}\left(t_{i_1} \right) & \cdots &B_{i_I}\left(t_{i_1} \right) \\

B_{i_1}\left(t_{i_2} \right) & B_{i_2}\left(t_{i_2} \right) & \cdots &B_{i_I}\left(t_{i_2} \right) \\

\vdots & \vdots &\vdots & \vdots \\

B_{i_1}\left(t_{i_I} \right) & B_{i_2}\left(t_{i_I} \right) & \cdots &B_{i_I}\left(t_{i_I} \right) \\

\end{bmatrix}.

The above local iteration format converges and can be extended to blending surfaces and subdivision surfaces.{{Cite journal |last1=Zhao |first1=Yu |last2=Lin |first2=Hongwei |last3=Bao |first3=Hujun |date=2012 |title=Local progressive interpolation for subdivision surface fitting |journal=Journal of Computer Research and Development |volume=49 |issue=8 |pages=1699–1707}}

The PIA format for implicit curve and surface reconstruction is presented in the following. Given an ordered point cloud $\backslash left\backslash \{\backslash mathbf\{Q\}\_i\backslash right\backslash \}\_\{i=1\}^n$ and a unit normal vector $\backslash left\backslash \{\backslash mathbf\{n\}\_i\backslash right\backslash \}\_\{i=1\}^n$ on the data points, we want to reconstruct an implicit curve from the given point cloud. To avoid a trivial solution, some offset points $\backslash left\backslash \{\backslash mathbf\{Q\}\_l\backslash right\backslash \}\_\{l=n+1\}^\{2n\}$ are added to the point cloud. They are offset by a distance $\backslash sigma$ along the unit normal vector of each point

\mathbf{Q}_l=\mathbf{Q}_i+\sigma\mathbf{n}_i,\quad l=n+i,\quad i=1,2,\cdots,n.

Assume that $\backslash epsilon$ is the value of the implicit function at the offset point

f\left(\mathbf{Q}_l\right)=\epsilon,\quad l=n+1,n+2,\cdots,2n.

Let the implicit curve after the $\backslash alpha$th iteration be

f^{(\alpha)}(x,y)=\sum_{i=1}^{N_u}\sum_{j=1}^{N_v}C_{ij}^{(\alpha)}B_i(x)B_j(y),

where $C\_\{ij\}^\{(\backslash alpha)\}$ is the control point.

Define the difference vector of data points as

\begin{aligned}

\boldsymbol{\delta}_k^{(\alpha)}&=0-f^{(\alpha)}(x_k,y_k),\quad k=1,2,\cdots,n,\\

\boldsymbol{\delta}_l^{(\alpha)}&=\epsilon-f^{(\alpha)}(x_l,y_l),\quad l=n+1,n+2,\cdots, 2n.

\end{aligned}

Next, calculate the difference vector of control coefficients

\boldsymbol{\Delta}_{ij}^{(\alpha)}=\mu\sum_{k=1}^{2n} B_i(x_k)B_j(y_k) \boldsymbol{\delta}_k^{(\alpha)},\quad i=1,2,\cdots,N_u,\quad j=1,2,\cdots,N_v,

where $\backslash mu$ is the convergence coefficient. As a result, the new control coefficients are

C_{ij}^{(\alpha+1)}=C_{ij}^{(\alpha)}+\boldsymbol{\Delta}_{ij}^{(\alpha)},

leading to the new algebraic B-spline curve

f^{(\alpha+1)}(x,y)=\sum_{i=1}^{N_u}\sum_{j=1}^{N_v}C_{ij}^{(\alpha+1)}B_i(x)B_j(y).

The above procedure is carried out iteratively to generate a sequence of algebraic B-spline functions $\backslash left\backslash \{f^\{(\backslash alpha)\}(x,y),\; \backslash quad\; \backslash alpha=0,1,2,\backslash cdots\backslash right\backslash \}$. The sequence converges to a minimization problem with constraints when the initial control coefficients $C\_\{ij\}^\{(0)\}=0$.

Assume that the implicit surface generated after the $\backslash alpha$th iteration is

f^{(\alpha)}(x,y,z)=\sum_{i=1}^{N_u}\sum_{j=1}^{N_v}\sum_{k=1}^{N_w}C_{ijk}^{(\alpha)}B_i(x)B_j(y)B_k(z),

the iteration format is similar to that of the curve case.{{Cite journal |last1=Liu |first1=Shengjun |last2=Liu |first2=Tao |last3=Hu |first3=Ling |last4=Shang |first4=Yuanyuan |last5=Liu |first5=Xinru |date=2021-09-01 |title=Variational progressive-iterative approximation for RBF-based surface reconstruction |url=https://doi.org/10.1007/s00371-021-02213-3 |journal=The Visual Computer |language=en |volume=37 |issue=9 |pages=2485–2497 |doi=10.1007/s00371-021-02213-3 |issn=1432-2315|url-access=subscription }}

To develop fairing-PIA, we first define the functionals as follows:

\mathcal{F}_{r,j}(f) = \int_{t_1}^{t_m}B_{r,j}(t)fdt,\quad j=1,2,\cdots,n,\quad r=1,2,3,

where $B\_\{r,j\}(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 be

\mathbf{P}^{[k]}(t)=\sum_{j=1}^nB_j(t)\mathbf{P}_j^{[k]},\quad t\in[t_1,t_m].

To construct the new curve $\backslash mathbf\{P\}^\{[k+1]\}(t)$, we first calculate the $(k\; +\; 1)$st difference vectors for data points,

\mathbf{d}_i^{[k]} = \mathbf{Q}_i - \mathbf{P}^{[k]}(t_i),\quad i=1,2,\cdots,m.

Then, the fitting difference vectors and the fairing vectors for control points are calculated by

\begin{align}

\boldsymbol{\delta}_j^{[k]} &= \sum_{h\in I_j}B_j(t_h)\mathbf{d}_h^{[k]},\quad j=1,2,\cdots,n \\

\boldsymbol{\eta}_{j}^{[k]} &= \sum_{l=1}^n \mathcal{F}_{r,l}\left(B_{r,j}(t)\right)\mathbf{P}_l^{[k]},\quad j=1,2,\cdots,n \\

\end{align}

Finally, the control points of the $(k+1)$st curve are produced by

\mathbf{P}_j^{[k+1]} = \mathbf{P}_j^{[k]} + \mu_j

\left[

\left(1-\omega_j\right)\boldsymbol{\delta}_j^{[k]} - \omega_j\boldsymbol{\eta}_{j}^{[k]}

\right],\quad j=1,2,\cdots,n,

where $\backslash mu\_j$ is a normalization weight, and $\backslash 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

\mathbf{P}^{[k+1]}(t)=\sum_{j=1}^nB_j(t)\mathbf{P}_j^{[k+1]},\quad t\in[t_1,t_m].

In this way, we obtain a sequence of curves $\backslash left\backslash \{\backslash mathbf\{P\}^\{[k]\}(t),\backslash ;k=1,2,3,\backslash cdots\backslash right\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.

Isogeometric least-squares progressive-iterative approximation (IG-LSPIA).{{Cite journal |last1=Jiang |first1=Yini |last2=Lin |first2=Hongwei |date=2023-02-10 |title=IG-LSPIA: Least Squares Progressive Iterative Approximation for Isogeometric Collocation Method |journal=Mathematics |volume=11 |issue=4 |pages=898 |doi=10.3390/math11040898 |issn=2227-7390 |doi-access=free }} Given a boundary value problem

\left\{

\begin{aligned}

\mathcal{L}u=f,&\quad \text{in}\;\Omega,\\

\mathcal{G}u=g,&\quad \text{on}\;\partial\Omega,

\end{aligned}

\right.

where $u:\backslash Omega\backslash to\backslash mathbb\{R\}$ is the unknown solution, $\backslash mathcal\{L\}$ is the differential operator, $\backslash mathcal\{G\}$ is the boundary operator, and $f$ and $g$ are the continuous functions. In the isogeometric analysis method, NURBS basis functions are used as shape functions to solve the numerical solution of this boundary value problem. The same basis functions are applied to represent the numerical solution $u\_h$ and the geometric mapping $G$:

\begin{aligned}

u_h\left(\hat{\tau}\right) &= \sum_{j=1}^nR_{j}(\hat\tau )u_j,\\

G({\hat \tau }) &= \sum_{j=1}^nR_{j}(\hat\tau )P_j,

\end{aligned}

where $R\_j(\backslash hat\{\backslash tau\})$ denotes the NURBS basis function, $u\_j$ is the control coefficient. After substituting the collocation points{{Cite journal |last1=Lin |first1=Hongwei |last2=Hu |first2=Qianqian |last3=Xiong |first3=Yunyang |date=2013-12-01 |title=Consistency and convergence properties of the isogeometric collocation method |url=https://www.sciencedirect.com/science/article/pii/S0045782513002521 |journal=Computer Methods in Applied Mechanics and Engineering |volume=267 |pages=471–486 |doi=10.1016/j.cma.2013.09.025 |bibcode=2013CMAME.267..471L |issn=0045-7825|url-access=subscription }} $\backslash hat\backslash tau\_\{i\}\; ,i\; =\; 1,2,...,\{m\}$ into the strong form of PDE, we obtain a discretized problem

\left\{

\begin{aligned}

\mathcal{L}u_{h}(\hat\tau_{i})=f(G(\hat\tau_{i})),&\quad i\in\mathcal{I_L},\\

\mathcal{G}u_{h}(\hat\tau_{j})=g(G(\hat\tau_{j})),&\quad j\in\mathcal{I_G},

\end{aligned}

\right.

where $\backslash mathcal\{I\_L\}$ and $\backslash mathcal\{I\_G\}$ denote the subscripts of internal and boundary collocation points, respectively.

Arranging the control coefficients $u\_j$ of the numerical solution $u\_h(\backslash hat\backslash tau)$ into an $1$-dimensional column vector $\backslash mathbf\{U\}=[u\_1,u\_2,...,u\_n]^T$, the discretized problem can be reformulated in matrix form as

\mathbf{AU}=\mathbf{b}

where $\backslash mathbf\{A\}$ is the collocation matrix and $\backslash mathbf\{b\}$ is the load vector.

Assume that the discretized load values are data points $\backslash left\backslash \{b\_i\backslash right\backslash \}\_\{i=1\}^m$ to be fitted. Given the initial guess of the control coefficients

U^{(0)}(\hat\tau) = \sum_{j=1}^nA_j(\hat\tau)u_j^{(0)},\quad\hat\tau\in[\hat\tau_1,\hat\tau_m],

where $A\_j(\backslash hat\backslash tau)$, $j=1,2,\backslash cdots,n$, represents the combination of different order derivatives of the NURBS basis functions determined using the operators $\backslash mathcal\{L\}$ and $\backslash mathcal\{G\}$

A_j(\hat\tau) = \left\{

\begin{aligned}

\mathcal{L}R_j(\hat\tau), &\quad \hat{\tau}\ \text{in}\ \Omega_p^{in},\\

\mathcal{G}R_j(\hat\tau), &\quad \hat{\tau}\ \text{in}\ \Omega_p^{bd}, \quad j=1,2,\cdots,n,

\end{aligned}

\right.

where $\backslash Omega\_p^\{in\}$ and $\backslash Omega\_p^\{bd\}$ indicate the interior and boundary of the parameter domain, respectively. Each $A\_j(\backslash hat\backslash tau)$ corresponds to the $j$th control coefficient. Assume that $J\_\{in\}$ and $J\_\{bd\}$ are the index sets of the internal and boundary control coefficients, respectively. Without loss of generality, we further assume that the boundary control coefficients have been obtained using strong or weak imposition and are fixed, i.e.,

u_{j}^{(k)}=u_{j}^{*},\quad j\in J_{bd},\quad k=0,1,2,\cdots.

The $k$th blending function, generated after the $k$th iteration of IG-LSPIA, is assumed to be as follows:

U^{(k)}(\hat\tau) = \sum_{j=1}^nA_j(\hat\tau)u_j^{(k)},\quad\hat\tau\in[\hat\tau_1,\hat\tau_m].

Then, the difference vectors for collocation points (DCP) in the $(k\; +\; 1)$st iteration are obtained using

\begin{align}

\boldsymbol{\delta}_i^{(k)}

&= b_i-\sum_{j=1}^{n}A_j(\hat\tau_i)u_j^{(k)}\\

&= b_i-\sum_{j\in J_{bd}}A_j(\hat\tau_i)u_j^{(k)}

-\sum_{j\in J_{in}}A_j(\hat\tau_i)u_j^{(k)}

,\quad i=1,2,...,m.

\end{align}

Moreover, group all load values whose parameters fall in the local support of the $j$th derivatives function, i.e., $A\_j(\backslash hat\backslash tau\_i)\backslash ne\; 0$, into the $j$th group corresponding to the $j$th control coefficient, and denote the index set of the $j$th group of load values as $I\_j$. Lastly, the differences for control coefficients (DCC) can be constructed as follows:

d_j^{(k)}=\mu\sum_{h\in I_j}A_j(\hat\tau_h)\boldsymbol{\delta}_h^{(k)},\quad j=1,2,...,n,

where $\backslash mu$ is a normalization weight to guarantee the convergence of the algorithm.

Thus, the new control coefficients are updated via the following formula,

u_j^{(k+1)}=u_j^{(k)}+d_j^{(k)},\quad j=1,2,...,n,

Consequently, the $(k\; +\; 1)$st blending function is generated as follows:

U^{(k+1)}(\hat\tau) = \sum_{j=1}^nA_j(\hat\tau)u_j^{(k+1)}.

The above iteration process is performed until the desired fitting precision is reached and a sequence of blending functions is obtained

\left \{ U^{(k)}(\hat\tau),k=0,1,\dots \right \}.

The IG-LSPIA converges to the solution of a constrained least-squares collocation problem.

Let {{Mvar|n}} be the number of control points and {{Mvar|m}} be the number of data points.

If $n=m$, the PIA iterative format in matrix form is

\begin{align}

\mathbf{P^{(\alpha+1)}} &=\mathbf{P^{(\alpha)}}+\mathbf{\Delta}^{(\alpha)} \\

&=\mathbf{P}^{(\alpha)}+\mathbf{Q}-\mathbf{B}\mathbf{P}^{(\alpha)} \\

&=\left(\mathbf{I}-\mathbf{B}\right)\mathbf{P}^{(\alpha)}+\mathbf{Q}

\end{align}

where

\begin{align}

\mathbf{Q} &= \left[\mathbf{Q}_1,\mathbf{Q}_2,\cdots,\mathbf{Q}_m\right]^T \\

\mathbf{P^{(\alpha)}} &= \left[\mathbf{P}_1^{(\alpha)},\mathbf{P}_2^{(\alpha)},\cdots,\mathbf{P}_n^{(\alpha)}\right]^T \\

\mathbf{\Delta}^{(\alpha)} &= \left[\mathbf{\Delta}_1^{(\alpha)},\mathbf{\Delta}^{(\alpha)}_2,\cdots,\mathbf{\Delta}^{(\alpha)}_n\right]^T \\

\mathbf{B} &= \begin{bmatrix}

B_1(t_1) & B_2(t_1) &\cdots &B_n(t_1)\\

B_1(t_2) & B_2(t_2) &\cdots &B_n(t_2)\\

\vdots & \vdots &\ddots & \vdots \\

B_1(t_m) & B_2(t_m) &\cdots &B_n(t_m)\\

\end{bmatrix}.

\end{align}

The convergence of the PIA is related to the properties of the collocation matrix. If the spectral radius of the iteration matrix $\backslash mathbf\{I\}-\backslash mathbf\{B\}$ is less than $1$, then the PIA is convergent. It has been shown that the PIA methods are convergent for Bézier curves and surfaces, B-spline curves and surfaces, NURBS curves and surfaces, triangular Bernstein–Bézier surfaces, and subdivision surfaces (Loop, Catmull-Clark, Doo-Sabin).

If

\begin{align}

\mathbf{P^{(\alpha+1)}}&=\mathbf{P^{(\alpha)}}+\mu\mathbf{B}^T\mathbf{\Delta}^{(\alpha)} \\

&=\mathbf{P}^{(\alpha)}+\mu\mathbf{B}^T\left(\mathbf{Q}-\mathbf{B}\mathbf{P}^{(\alpha)}\right) \\

&=\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)\mathbf{P}^{(\alpha)}+\mu\mathbf{B}^T\mathbf{Q}.

\end{align}

When the matrix $\backslash mathbf\{B\}^T\backslash mathbf\{B\}$ is nonsingular, the following results can be obtained:{{Cite book |last1=Horn |first1=Roger A. |url=http://dx.doi.org/10.1017/cbo9781139020411 |title=Matrix Analysis |last2=Johnson |first2=Charles R. |date=2012-10-22 |publisher=Cambridge University Press |doi=10.1017/cbo9781139020411 |isbn=978-0-521-83940-2}}

{{Math theorem |If , where $\backslash lambda\_0$ is the largest eigenvalue of the matrix $\backslash mathbf\{B\}^T\backslash mathbf\{B\}$, then the eigenvalues of $\backslash mu\backslash mathbf\{B\}^T\backslash mathbf\{B\}$ are real numbers and satisfy . |name=Lemma}}

Proof Since $\backslash mathbf\{B\}^T\backslash mathbf\{B\}$ is nonsingular, and $\backslash mu>0$, then $\backslash lambda(\backslash mu\backslash mathbf\{B\}^T\backslash mathbf\{B\})>0$. Moreover,

\lambda(\mu\mathbf{B}^T\mathbf{B}) =\mu\lambda(\mathbf{B}^T\mathbf{B})<2\frac{\lambda(\mathbf{B}^T\mathbf{B})}{\lambda_0}<2.

In summary, .

{{Math theorem |If , LSPIA is convergent, and converges to the least-squares fitting result to the given data points. |name=Theorem}}

Proof From the matrix form of iterative format, we obtain the following:

\begin{align}

\mathbf{P^{(\alpha+1)}}&=\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)\mathbf{P}^{(\alpha)}+\mu\mathbf{B}^T\mathbf{Q},\\

&=\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)\left[\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)\mathbf{P}^{(\alpha-1)}+\mu\mathbf{B}^T\mathbf{Q}\right]+\mu\mathbf{B}^T\mathbf{Q},\\

&=\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)^2\mathbf{P}^{(\alpha-1)}+\sum_{i=0}^1\left( \mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)\mu\mathbf{B}^T\mathbf{Q},\\

&=\cdots\\

&=\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)^{\alpha+1}\mathbf{P}^{(0)}+\sum_{i=0}^{\alpha}\left( \mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)^{\alpha}\mu\mathbf{B}^T\mathbf{Q}.\\

\end{align}

According to above Lemma, the spectral radius of the matrix $\backslash mu\backslash mathbf\{B\}^T\backslash mathbf\{B\}$ satisfies

0<\rho\left({\mu\mathbf{B}^T\mathbf{B}}\right)<2

and thus the spectral radius of the iteration matrix satisfies

0<\rho\left({\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}}\right)<1.

When $\backslash alpha\backslash rightarrow\; \backslash infty$

\left(\mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)^{\infty}=0,\ \sum_{i=0}^{\infty}\left( \mathbf{I}-\mu\mathbf{B}^T\mathbf{B}\right)^{\alpha}=\frac{1}{\mu}\left(\mathbf{B}^T\mathbf{B}\right)^{-1}.

As a result,

$$\backslash mathbf\{P\}^\{(\backslash infty)\}=\backslash left(\backslash mathbf\{B\}^T\backslash mathbf\{B\}\backslash right)^\{-1\}\backslash mathbf\{B\}^T\backslash mathbf\{Q\},$$

i.e., $\backslash mathbf\{B\}^T\backslash mathbf\{B\}\backslash mathbf\{P\}^\{(\backslash infty)\}=\backslash mathbf\{B\}^T\backslash mathbf\{Q\}$, which is equivalent to the normal equation of the fitting problem. Hence, the LSPIA algorithm converges to the least squares result for a given sequence of points.

Lin et al. showed that LSPIA converges even when the iteration matrix is singular.{{Cite journal |last1=Lin |first1=Hongwei |last2=Cao |first2=Qi |last3=Zhang |first3=Xiaoting |title=The Convergence of Least-Squares Progressive Iterative Approximation for Singular Least-Squares Fitting System |journal=Journal of Systems Science and Complexity |date=2018 |volume=31 |issue=6 |pages=1618–1632 |doi=10.1007/s11424-018-7443-y |s2cid=255157830 |issn=1009-6124}}

• Precondition: Liu et al. proposed a preconditioned PIA for Bézier surfaces via the diagonally compensated reduction method, effectively improving the accuracy and efficiency of the classical algorithm.{{Cite journal |last1=Liu |first1=Chengzhi |last2=Han |first2=Xuli |last3=Li |first3=Juncheng |date=2020 |title=Preconditioned progressive iterative approximation for triangular Bézier patches and its application |journal=Journal of Computational and Applied Mathematics |volume=366 |pages=112389 |doi=10.1016/j.cam.2019.112389 |issn=0377-0427 |s2cid=202942809|doi-access=free }}
• Iteration matrix inverse approximation: Sajavičius improved the LSPIA based on the matrix approximate inverse method. In each iteration step, the approximate inverse of the coefficient matrix of the least-squares fitting problem is first computed and then used as the weight to adjust the control points.{{Cite journal |last=Sajavičius |first=Svajūnas |date=2023 |title=Hyperpower least squares progressive iterative approximation |journal=Journal of Computational and Applied Mathematics |volume=422 |pages=114888 |doi=10.1016/j.cam.2022.114888 |issn=0377-0427 |s2cid=252965212}}
• Optimal weight: Lu initially presented a weighted progressive-iterative approximation (WPIA) that introduces the optimal weight of difference vectors for control points to accelerate the convergence.{{Cite journal |last=Lu |first=Lizheng |title=Weighted progressive iteration approximation and convergence analysis |journal=Computer Aided Geometric Design |date=2010 |volume=27 |issue=2 |pages=129–137 |doi=10.1016/j.cagd.2009.11.001 |issn=0167-8396}} Moreover, Zhang et al. proposed a weighted local PIA format for tensor Bézier surfaces.{{Cite journal |last=Zhang |first=Li |date=2014-05-01 |title=Weighted Local Progressive Iterative Approximation for Tensor-product B\'{e}zier Surfaces |journal=Journal of Information and Computational Science |volume=11 |issue=7 |pages=2117–2124 |doi=10.12733/jics20103359 |issn=1548-7741}} Li et al. assigned initial weights to each data point, and the weights of the interpolated points are determined adaptively during the iterative process.{{Cite journal |last1=Li |first1=Shasha |last2=Xu |first2=Huixia |last3=Deng |first3=Chongyang |year=2019 |title=Data-weighted least square progressive and iterative approximation and related B-Spline curve fitting |journal=Journal of Computer-Aided Design & Computer Graphics |volume=31 |issue=9 |pages=1574–1580}}
• Acceleration with memory: In 2020, Huang et al. proposed a PIA method with memory for least square fitting (MLSPIA), which has a similar format to the momentum method. MLSPIA generates a series of fitting curves with three weights by iteratively adjusting the control points. With appropriate parameter selection, these curves converge to the least squares fit results for a given data point and are more efficient than LSPIA.{{Cite journal |last1=Huang |first1=Zheng-Da |last2=Wang |first2=Hui-Di |date=2020 |title=On a progressive and iterative approximation method with memory for least square fitting |journal=Computer Aided Geometric Design |volume=82 |pages=101931 |arxiv=1908.06417 |doi=10.1016/j.cagd.2020.101931 |issn=0167-8396 |s2cid=201070122}}
• Stochastic descent strategy: Rios and Jüttle explored the relationship between LSPIA and gradient descent method and proposed a stochastic LSPIA algorithm with parameter correction.{{Cite journal |last1=Rios |first1=Dany |last2=Jüttler |first2=Bert |date=2022 |title=LSPIA, (stochastic) gradient descent, and parameter correction |journal=Journal of Computational and Applied Mathematics |volume=406 |pages=113921 |doi=10.1016/j.cam.2021.113921 |issn=0377-0427 |s2cid=244018717}}

Since PIA has obvious geometric meaning, constraints can be easily integrated in the iterations. Currently, PIA has been widely applied in many fields, such as data fitting, reverse engineering, geometric design, mesh generation, data compression, fairing curve and surface generation, and isogeometric analysis.

• Adaptive data fitting: The control points are divided into active control points and fixed control points. In each round of iteration, if the fitting error of a data point reaches a given precision, its corresponding control point is fixed and not updated. This iterative process is repeated until all control points are fixed. The algorithm performs well on large-scale data fitting by adaptively reducing the number of active control points.{{Cite journal |last=Lin |first=Hongwei |date=2012 |title=Adaptive data fitting by the progressive-iterative approximation |journal=Computer Aided Geometric Design |volume=29 |issue=7 |pages=463–473 |doi=10.1016/j.cagd.2012.03.005 |issn=0167-8396}}
• Large-scale data fitting: By combining T-spline with PIA, an incremental fitting algorithm suitable for fitting large-scale data sets is proposed. During the incremental iteration, each new round of iterations reuses information from the last round of iterations to save computation. While the convergence speed of the traditional point-by-point iterative algorithm decreases as the number of control points increases, in PIA the computation of each iteration step is unrelated to the number of control points; this gives PIA a powerful capability for data fitting.
• Local fitting: Based on the local property of PIA, a series of local PIA formats have been proposed.{{Cite journal |last1=Zhao |first1=Yu |last2=Lin |first2=Hongwei |last3=Bao |first3=Hujun |year=2012 |title=Local progressive interpolation for subdivision surface fitting |journal=Computer Research and Development |volume=49 |issue=8 |pages=1699–1707}}

For implicit curve and surface reconstruction, PIA avoids the additional zero level set and regularization term, which greatly improves the speed of the reconstruction algorithm.

Firstly, the data points are sampled on the original curve. Then, the initial polynomial approximation curve or rational approximation curve of the offset curve is generated from these sampled points. Finally, the offset curve is approximated iteratively using the PIA method.{{Cite journal |last1=Zhang |first1=Li |last2=Wang |first2=Huan |last3=Li |first3=Yuanyuan |last4=Tan |first4=Jieqing |year=2014 |title=A progressive iterative approximation method in offset approximation |journal=Journal of Computer Aided Design and Computer Graphics |volume=26 |issue=10 |pages=1646–1653}}

Given a triangular mesh model as input, the algorithm first constructs the initial hexahedral mesh, then extracts the quadrilateral mesh of the surface as the initial boundary mesh. During the iterations, the movement of each mesh vertex is constrained to ensure the validity of the mesh. Finally, the hexahedral model is fitted to the given input model. The algorithm can guarantee the validity of the generated hexahedral mesh, i.e., the Jacobi value at each mesh vertex is greater than zero.{{Cite journal |last1=Lin |first1=Hongwei |last2=Jin |first2=Sinan |last3=Liao |first3=Hongwei |last4=Jian |first4=Qun |year=2015 |title=Quality guaranteed all-hex mesh generation by a constrained volume iterative fitting algorithm |journal=Computer-Aided Design |volume=67-68 |pages=107–117 |doi=10.1016/j.cad.2015.05.004 |issn=0010-4485}}

First, the image data are converted into a one-dimensional sequence by Hilbert scan. Then, these data points are fitted by LSPIA to generate a Hilbert curve. Finally, the Hilbert curve is sampled, and the compressed image can be reconstructed. This method can well preserve the neighborhood information of pixels.{{Cite journal |last1=Hu |first1=Lijuan |last2=Yi |first2=Yeqing |last3=Liu |first3=Chengzhi |last4=Li |first4=Juncheng |year=2020 |title=Iterative method for image compression by using LSPIA |journal=IAENG International Journal of Computer Science |volume=47 |issue=4 |pages=1–7}}

Given a data point set, we first define the fairing functional, and calculate the fitting difference vector and the fairing vector of the control point; then, adjust the control points with fairing weights. According to the above steps, the fairing curve and surface can be generated iteratively. Due to the sufficient fairing parameters, the method can achieve global or local fairing. It is also flexible to adjust knot vectors, fairing weights, or data parameterization after each round of iteration. The traditional energy-minimization method is a special case of this method, i.e., when the smooth weights are all the same.

The discretized load values are regarded as the set of data points, and the combination of the basis functions and their derivative functions is used as the blending function for fitting. The method automatically adjusts the degrees of freedom of the numerical solution of the partial differential equation according to the fitting result of the blending function to the load values. In addition, the average iteration time per step is only related to the number of data points (i.e., collocation points) and unrelated to the number of control coefficients.

• {{Creative Commons text attribution notice|cc=by4|url=https://www.mdpi.com/2227-7390/11/4/898 |author(s)=zju_cagd}}

{{reflist}}

{{Improve categories|date=August 2024}}

Category:Computer-aided design

Category:Computer graphics

Category:Computational geometry

Category:Geometric algorithms

Category:Curve fitting