Progressive-iterative approximation method - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-23T23:36:10Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 23:36, 23 May 2025
Line 21:		Line 21:
	* If <math>\mathbf{P}(\mathbf{t})</math> is a B-spline curve, then <math>\mathbf{t}</math> is a scalar, <math>B_i(t)</math> is a B-spline basis function, and <math>\mathbf{P}_i</math> denotes the control point;<ref name=":13" />		* If <math>\mathbf{P}(\mathbf{t})</math> is a B-spline curve, then <math>\mathbf{t}</math> is a scalar, <math>B_i(t)</math> is a B-spline basis function, and <math>\mathbf{P}_i</math> denotes the control point;<ref name=":13" />
	* If <math>\mathbf{P}(\mathbf{t})</math> is a B-spline patch with <math>n_u\times n_v</math> control points, then <math>\mathbf{t}=(u,v)</math> and <math>B_i(\mathbf{t})=N_i(u)N_i(v)</math>, where <math>N_i(u)</math> and <math>N_i(v)</math> are B-spline basis functions;<ref name=":13" />		* If <math>\mathbf{P}(\mathbf{t})</math> is a B-spline patch with <math>n_u\times n_v</math> control points, then <math>\mathbf{t}=(u,v)</math> and <math>B_i(\mathbf{t})=N_i(u)N_i(v)</math>, where <math>N_i(u)</math> and <math>N_i(v)</math> are B-spline basis functions;<ref name=":13" />
	* If <math>\mathbf{P}(\mathbf{t})</math> is a trivariate B-spline solid with <math>n_u \times n_v \times n_w</math> control points, then <math>\mathbf{t}=(u,v,w)</math> and <math>B_i(\mathbf{t})=N_i(u)N_i(v)N_i(w)</math>, where <math>N_i(u)</math>, <math>N_i(v)</math>, and <math>N_i(w)</math> are B-spline basis functions.<ref>{{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}}</ref>		* If <math>\mathbf{P}(\mathbf{t})</math> is a trivariate B-spline solid with <math>n_u \times n_v \times n_w</math> control points, then <math>\mathbf{t}=(u,v,w)</math> and <math>B_i(\mathbf{t})=N_i(u)N_i(v)N_i(w)</math>, where <math>N_i(u)</math>, <math>N_i(v)</math>, and <math>N_i(w)</math> are B-spline basis functions.<ref>{{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 }}</ref>

	Additionally, this can be applied to NURBS curves and surfaces, T-spline surfaces, and triangular Bernstein–Bézier surfaces.<ref name=":12" />		Additionally, this can be applied to NURBS curves and surfaces, T-spline surfaces, and triangular Bernstein–Bézier surfaces.<ref name=":12" />
Line 169:		Line 169:
	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),		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),
	</math>		</math>
	the iteration format is similar to that of the curve case.<ref name=":5" /><ref>{{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}}</ref>		the iteration format is similar to that of the curve case.<ref name=":5" /><ref>{{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 }}</ref>

	=== Fairing-PIA ===		=== Fairing-PIA ===
Line 225:		Line 225:
	\end{aligned}		\end{aligned}
	</math>		</math>
	where <math display="inline">R_j(\hat{\tau})</math> denotes the NURBS basis function, <math display="inline">u_j</math> is the control coefficient. After substituting the collocation points<ref name=":15">{{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}}</ref> <math display="inline">\hat\tau_{i} ,i = 1,2,...,{m}</math> into the strong form of [[Partial differential equation\|PDE]], we obtain a discretized problem<ref name=":15" />		where <math display="inline">R_j(\hat{\tau})</math> denotes the NURBS basis function, <math display="inline">u_j</math> is the control coefficient. After substituting the collocation points<ref name=":15">{{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 }}</ref> <math display="inline">\hat\tau_{i} ,i = 1,2,...,{m}</math> into the strong form of [[Partial differential equation\|PDE]], we obtain a discretized problem<ref name=":15" />
	<math display="block">		<math display="block">
	\left\{		\left\{

Jayowyn: /* Proof of convergence */ Use templates for lemma and theorem

2025-01-10T23:42:05Z

Proof of convergence: Use templates for lemma and theorem

← Previous revision		Revision as of 23:42, 10 January 2025
Line 332:		Line 332:
	When the matrix <math display="inline">\mathbf{B}^T\mathbf{B}</math> is [[Invertible matrix\|nonsingular]], the following results can be obtained:<ref>{{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}}</ref>		When the matrix <math display="inline">\mathbf{B}^T\mathbf{B}</math> is [[Invertible matrix\|nonsingular]], the following results can be obtained:<ref>{{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}}</ref>

	~~'''Lemma'''~~ If <math display="inline">0<\mu<\frac{2}{\lambda_0}</math> , where <math display="inline">\lambda_0</math> is the largest [[Eigenvalues and eigenvectors\|eigenvalue]] of the matrix <math display="inline">\mathbf{B}^T\mathbf{B}</math>, then the eigenvalues of <math display="inline">\mu\mathbf{B}^T\mathbf{B}</math> are real numbers and satisfy <math display="inline">0<\lambda(\mu\mathbf{B}^T\mathbf{B})<2</math>.		{{Math theorem \|If <math display="inline">0<\mu<\frac{2}{\lambda_0}</math> , where <math display="inline">\lambda_0</math> is the largest [[Eigenvalues and eigenvectors\|eigenvalue]] of the matrix <math display="inline">\mathbf{B}^T\mathbf{B}</math>, then the eigenvalues of <math display="inline">\mu\mathbf{B}^T\mathbf{B}</math> are real numbers and satisfy <math display="inline">0<\lambda(\mu\mathbf{B}^T\mathbf{B})<2</math>. \|name=Lemma}}

	'''Proof''' Since <math display="inline">\mathbf{B}^T\mathbf{B}</math> is nonsingular, and <math display="inline">\mu>0</math>, then <math display="inline">\lambda(\mu\mathbf{B}^T\mathbf{B})>0</math>. Moreover,		'''Proof''' Since <math display="inline">\mathbf{B}^T\mathbf{B}</math> is nonsingular, and <math display="inline">\mu>0</math>, then <math display="inline">\lambda(\mu\mathbf{B}^T\mathbf{B})>0</math>. Moreover,
Line 340:		Line 340:
	In summary, <math display="inline">0<\lambda(\mu\mathbf{B}^T\mathbf{B})<2</math>.		In summary, <math display="inline">0<\lambda(\mu\mathbf{B}^T\mathbf{B})<2</math>.

	~~'''Theorem'''~~ If <math display="inline">0<\mu<\frac{2}{\lambda_0}</math> , LSPIA is convergent, and converges to the least-squares fitting result to the given data points.<ref name=":3" /><ref name=":4" />		{{Math theorem \|If <math display="inline">0<\mu<\frac{2}{\lambda_0}</math> , LSPIA is convergent, and converges to the least-squares fitting result to the given data points.<ref name=":3" /><ref name=":4" /> \|name=Theorem}}

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

Jayowyn: Pulled citations out of section headers

2025-01-10T23:39:35Z

Pulled citations out of section headers

← Previous revision		Revision as of 23:39, 10 January 2025
Line 10:		Line 10:

	== Iteration methods ==		== Iteration methods ==
	Generally, progressive-iterative approximation (PIA) can be divided into interpolation and approximation schemes.<ref name=":9" /> 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,<ref name=":6">{{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}}</ref> implicit-PIA,<ref name=":5" /> fairing-PIA,<ref name=":7" /> and isogeometric least-squares progressive-iterative approximation (IG-LSPIA)<ref name=":8" />—that are specialized for solving the [[isogeometric analysis]] problem.<ref name=":14">{{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}}</ref>		Generally, progressive-iterative approximation (PIA) can be divided into interpolation and approximation schemes.<ref name=":9" /> 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,<ref name=":6">{{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}}</ref> implicit-PIA,<ref name=":5" /> fairing-PIA,<ref name=":7">{{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}}</ref> and isogeometric least-squares progressive-iterative approximation (IG-LSPIA)<ref name=":8" />—that are specialized for solving the [[isogeometric analysis]] problem.<ref name=":14">{{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}}</ref>

	=== Interpolation scheme: PIA ===		=== Interpolation scheme: PIA ===
Line 128:		Line 128:
	The above local iteration format converges and can be extended to blending surfaces<ref name=":6" /> and subdivision surfaces.<ref>{{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}}</ref>		The above local iteration format converges and can be extended to blending surfaces<ref name=":6" /> and subdivision surfaces.<ref>{{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}}</ref>

	=== Implicit-PIA~~<ref name=":5" />~~ ===		=== Implicit-PIA ===

	The ~~progressive iterative approximation~~ format for implicit curve and surface reconstruction is presented in the following. Given an ordered point cloud <math display="inline">\left\{\mathbf{Q}_i\right\}_{i=1}^n</math> and a unit normal vector <math display="inline">\left\{\mathbf{n}_i\right\}_{i=1}^n</math> on the data points, we want to reconstruct an implicit curve from the given point cloud. To avoid a trivial solution, some offset points <math display="inline">\left\{\mathbf{Q}_l\right\}_{l=n+1}^{2n}</math> are added to the point cloud.<ref name=":5" /> They are offset by a distance <math display="inline">\sigma</math> along the unit normal vector of each point		The PIA format for implicit curve and surface reconstruction is presented in the following.<ref name=":5" /> Given an ordered point cloud <math display="inline">\left\{\mathbf{Q}_i\right\}_{i=1}^n</math> and a unit normal vector <math display="inline">\left\{\mathbf{n}_i\right\}_{i=1}^n</math> on the data points, we want to reconstruct an implicit curve from the given point cloud. To avoid a trivial solution, some offset points <math display="inline">\left\{\mathbf{Q}_l\right\}_{l=n+1}^{2n}</math> are added to the point cloud.<ref name=":5" /> They are offset by a distance <math display="inline">\sigma</math> along the unit normal vector of each point
	<math display="block">		<math display="block">
	\mathbf{Q}_l=\mathbf{Q}_i+\sigma\mathbf{n}_i,\quad l=n+i,\quad i=1,2,\cdots,n.		\mathbf{Q}_l=\mathbf{Q}_i+\sigma\mathbf{n}_i,\quad l=n+i,\quad i=1,2,\cdots,n.
Line 171:		Line 171:
	the iteration format is similar to that of the curve case.<ref name=":5" /><ref>{{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}}</ref>		the iteration format is similar to that of the curve case.<ref name=":5" /><ref>{{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}}</ref>

			=== Fairing-PIA ===
	=== Fairing-PIA<ref name=":7">{{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 \|doi=10.1007/s00371-023-02861-7 \|arxiv=2211.11416 \|issn=0178-2789}}</ref> ===

	To develop fairing-PIA, we first define the functionals as follows:<ref name=":7" />		To develop fairing-PIA, we first define the functionals as follows:<ref name=":7" />
Line 207:		Line 207:
	In this way, we obtain a sequence of curves <math display="inline">\left\{\mathbf{P}^{[k]}(t),\;k=1,2,3,\cdots\right\}</math>. The sequence converges to the solution of the conventional fairing method based on energy minimization when all smoothing weights are equal (<math display="inline">\omega_j=\omega</math>).<ref name=":7" /> Similarly, the fairing-PIA can be extended to the surface case.		In this way, we obtain a sequence of curves <math display="inline">\left\{\mathbf{P}^{[k]}(t),\;k=1,2,3,\cdots\right\}</math>. The sequence converges to the solution of the conventional fairing method based on energy minimization when all smoothing weights are equal (<math display="inline">\omega_j=\omega</math>).<ref name=":7" /> Similarly, the fairing-PIA can be extended to the surface case.

			=== IG-LSPIA ===
⚫	~~===~~ IG-LSPIA<ref name=":8">{{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 }}</ref> ===

		⚫	Isogeometric least-squares progressive-iterative approximation (IG-LSPIA).<ref name=":8">{{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 }}</ref> Given a [[boundary value problem]]<ref name=":14" />
	Given a [[boundary value problem]]<ref name=":14" />
	<math display="block">		<math display="block">
	\left\{		\left\{
Line 259:		Line 259:
	u_{j}^{(k)}=u_{j}^{*},\quad j\in J_{bd},\quad k=0,1,2,\cdots.		u_{j}^{(k)}=u_{j}^{*},\quad j\in J_{bd},\quad k=0,1,2,\cdots.
	</math>		</math>
	The <math display="inline">k</math>th blending function, generated after the <math display="inline">k</math>th iteration of IG-LSPIA, <ref name=":8" /> is assumed to be as follows:		The <math display="inline">k</math>th blending function, generated after the <math display="inline">k</math>th iteration of IG-LSPIA,<ref name=":8" /> is assumed to be as follows:
	<math display="block">		<math display="block">
	U^{(k)}(\hat\tau) = \sum_{j=1}^nA_j(\hat\tau)u_j^{(k)},\quad\hat\tau\in[\hat\tau_1,\hat\tau_m].		U^{(k)}(\hat\tau) = \sum_{j=1}^nA_j(\hat\tau)u_j^{(k)},\quad\hat\tau\in[\hat\tau_1,\hat\tau_m].

Jayowyn: Removed cluttering instances of term "(surface)" -- it's understood from the introduction that the fitting equations can represent either curves or surfaces

2025-01-10T23:14:09Z

Removed cluttering instances of term "(surface)" -- it's understood from the introduction that the fitting equations can represent either curves or surfaces

Show changes

Jayowyn: Pulled citations out of section headers; misc cleanup

2025-01-10T23:06:55Z

Pulled citations out of section headers; misc cleanup

Show changes

Jayowyn: Removed boldface from section headers

2025-01-10T22:35:30Z

Removed boldface from section headers

← Previous revision		Revision as of 22:35, 10 January 2025
Line 293:		Line 293:
	== Proof of convergence ==		== Proof of convergence ==

	=== ~~'''~~Non-singular case~~'''~~ ===		=== Non-singular case ===
	Let {{Mvar\|n}} be the number of control points and {{Mvar\|m}} be the number of data points.		Let {{Mvar\|n}} be the number of control points and {{Mvar\|m}} be the number of data points.

Line 383:		Line 383:
	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.		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.

	=== ~~'''~~Data fitting~~'''~~ ===		=== Data fitting ===
	* 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.<ref>{{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}}</ref>		* 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.<ref>{{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}}</ref>
	* 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.<ref name=":3" />		* 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.<ref name=":3" />
	* Local fitting: Based on the local property of PIA, a series of local PIA formats have been proposed.<ref name=":6" /><ref>{{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}}</ref>		* Local fitting: Based on the local property of PIA, a series of local PIA formats have been proposed.<ref name=":6" /><ref>{{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}}</ref>

	=== ~~'''~~Implicit reconstruction~~'''~~ ===		=== Implicit reconstruction ===
	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.<ref name=":5" />		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.<ref name=":5" />

	=== ~~'''~~Offset curve approximation~~'''~~ ===		=== Offset curve approximation ===
	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.<ref>{{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}}</ref>		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.<ref>{{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}}</ref>

	=== ~~'''~~Mesh generation~~'''~~ ===		=== Mesh generation ===
	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.<ref>{{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}}</ref>		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.<ref>{{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}}</ref>

	=== ~~'''~~Data compression~~'''~~ ===		=== Data compression ===
	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.<ref>{{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}}</ref>		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.<ref>{{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}}</ref>

	=== ~~'''~~Fairing curve and surface generation~~'''~~ ===		=== Fairing curve and surface generation ===
	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.<ref name=":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.<ref name=":7" />

	=== ~~'''~~Isogeometric analysis~~'''~~ ===		=== Isogeometric analysis ===
	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.<ref name=":8" />		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.<ref name=":8" />

Jayowyn: Copy edits for phrasing, punctuation, tone, and math formatting. Tried to clarify technical points when possible.

2025-01-10T22:33:36Z

Copy edits for phrasing, punctuation, tone, and math formatting. Tried to clarify technical points when possible.

Show changes

ShelfSkewed: Dab/fix links

2024-09-27T15:15:08Z

Dab/fix links

← Previous revision		Revision as of 15:15, 27 September 2024
Line 10:		Line 10:
	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 R. de Boor\|Carl de Boor]] in the 1970s.<ref name=":10" /><ref name=":11" /> In 1975, Qi et al. developed and proved the "profit and loss" algorithm for uniform cubic [[B-spline]] curves,<ref name=":10">{{Cite journal \|last1=Qi \|first1=Dongxu \|last2=Tian \|first2=Zixian \|last3=Zhang \|first3=Auxin \|last4=Feng \|first4=Jiabin \|year=1975 \|title=The method of numeric polish in curve fitting \|journal=Acta Math Sinica \|volume=18 \|issue=3 \|pages=173–184}}</ref> and in 1979, [[Carl R. de Boor\|de Boor]] independently proposed this algorithm.<ref name=":11">{{Cite journal \|last=Carl \|first=de Boor \|year=1979 \|title=How does Agee's smoothing method work? \|journal=Proceedings of the 1979 Army Numerical Analysis and Computers Conference, ARO Report.}}</ref> In 2004, Hongwei Lin and coauthors proved that non-uniform cubic B-spline curves and surfaces have the "profit and loss" property.<ref name=":1">{{Cite journal \|last1=Lin \|first1=Hongwei \|last2=Wang \|first2=Guojin \|last3=Dong \|first3=Chenshi \|date=2004 \|title=Constructing iterative non-uniform B-spline curve and surface to fit data points \|journal=Science in China Series F \|volume=47 \|issue=3 \|pages=315 \|doi=10.1360/02yf0529 \|s2cid=966980 \|issn=1009-2757}}</ref> 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).<ref name=":0" /> In 2007, Maekawa et al. changed the algebraic distance in PIA to geometric distance and named it geometric interpolation (GI).<ref>{{Cite journal \|last1=Maekawa \|first1=Takashi \|last2=Yasunori \|first2=Matsumoto \|last3=Ken \|first3=Namiki \|year=2007 \|title=Interpolation by geometric algorithm \|journal=Computer-Aided Design \|volume=39 \|issue=4 \|pages=313–323\|doi=10.1016/j.cad.2006.12.008 }}</ref> In 2008, Cheng et al. extended it to [[Subdivision surface\|subdivision surfaces]] and named the method progressive interpolation (PI).<ref>{{Cite book \|last1=Cheng \|first1=Fuhua \|last2=Fan \|first2=Fengtao \|last3=Lai \|first3=Shuhua \|last4=Huang \|first4=Conglin \|last5=Wang \|first5=Jiaxi \|last6=Yong \|first6=Junhai \|title=Advances in Geometric Modeling and Processing \|chapter=Progressive Interpolation Using Loop Subdivision Surfaces \|series=Lecture Notes in Computer Science \|date=2008 \|volume=4975 \|pages=526–533\|doi=10.1007/978-3-540-79246-8_43 \|isbn=978-3-540-79245-1 }}</ref> 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).<ref name=":9">{{Cite journal \|last1=Lin \|first1=Hongwei \|last2=Maekawa \|first2=Takashi \|last3=Deng \|first3=Chongyang \|title=Survey on geometric iterative methods and their applications \|journal=Computer-Aided Design \|date=2018 \|volume=95 \|pages=40–51 \|doi=10.1016/j.cad.2017.10.002 \|issn=0010-4485}}</ref>		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 R. de Boor\|Carl de Boor]] in the 1970s.<ref name=":10" /><ref name=":11" /> In 1975, Qi et al. developed and proved the "profit and loss" algorithm for uniform cubic [[B-spline]] curves,<ref name=":10">{{Cite journal \|last1=Qi \|first1=Dongxu \|last2=Tian \|first2=Zixian \|last3=Zhang \|first3=Auxin \|last4=Feng \|first4=Jiabin \|year=1975 \|title=The method of numeric polish in curve fitting \|journal=Acta Math Sinica \|volume=18 \|issue=3 \|pages=173–184}}</ref> and in 1979, [[Carl R. de Boor\|de Boor]] independently proposed this algorithm.<ref name=":11">{{Cite journal \|last=Carl \|first=de Boor \|year=1979 \|title=How does Agee's smoothing method work? \|journal=Proceedings of the 1979 Army Numerical Analysis and Computers Conference, ARO Report.}}</ref> In 2004, Hongwei Lin and coauthors proved that non-uniform cubic B-spline curves and surfaces have the "profit and loss" property.<ref name=":1">{{Cite journal \|last1=Lin \|first1=Hongwei \|last2=Wang \|first2=Guojin \|last3=Dong \|first3=Chenshi \|date=2004 \|title=Constructing iterative non-uniform B-spline curve and surface to fit data points \|journal=Science in China Series F \|volume=47 \|issue=3 \|pages=315 \|doi=10.1360/02yf0529 \|s2cid=966980 \|issn=1009-2757}}</ref> 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).<ref name=":0" /> In 2007, Maekawa et al. changed the algebraic distance in PIA to geometric distance and named it geometric interpolation (GI).<ref>{{Cite journal \|last1=Maekawa \|first1=Takashi \|last2=Yasunori \|first2=Matsumoto \|last3=Ken \|first3=Namiki \|year=2007 \|title=Interpolation by geometric algorithm \|journal=Computer-Aided Design \|volume=39 \|issue=4 \|pages=313–323\|doi=10.1016/j.cad.2006.12.008 }}</ref> In 2008, Cheng et al. extended it to [[Subdivision surface\|subdivision surfaces]] and named the method progressive interpolation (PI).<ref>{{Cite book \|last1=Cheng \|first1=Fuhua \|last2=Fan \|first2=Fengtao \|last3=Lai \|first3=Shuhua \|last4=Huang \|first4=Conglin \|last5=Wang \|first5=Jiaxi \|last6=Yong \|first6=Junhai \|title=Advances in Geometric Modeling and Processing \|chapter=Progressive Interpolation Using Loop Subdivision Surfaces \|series=Lecture Notes in Computer Science \|date=2008 \|volume=4975 \|pages=526–533\|doi=10.1007/978-3-540-79246-8_43 \|isbn=978-3-540-79245-1 }}</ref> 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).<ref name=":9">{{Cite journal \|last1=Lin \|first1=Hongwei \|last2=Maekawa \|first2=Takashi \|last3=Deng \|first3=Chongyang \|title=Survey on geometric iterative methods and their applications \|journal=Computer-Aided Design \|date=2018 \|volume=95 \|pages=40–51 \|doi=10.1016/j.cad.2017.10.002 \|issn=0010-4485}}</ref>

	PIA is now extended to several common curves and surfaces in the [[geometric design]] field,<ref name=":13">{{Cite book \|last=Hoschek \|first=Josef \|url=https://dl.acm.org/doi/abs/10.5555/174506 \|title=Fundamentals of computer aided geometric design \|date=February 1993 \|publisher=A. K. Peters, Ltd. \|isbn=978-1-56881-007-2 \|location=USA}}</ref> including [[Non-uniform rational B-spline\|NURBS]] curves and surfaces,<ref name=":2">{{Cite journal \|last1=Shi \|first1=Limin \|last2=Wang \|first2=Renhong \|year=2006 \|title=An iterative algorithm of NURBS interpolation and approximation \|journal=Journal of Mathematical Research with Applications \|volume=26 \|issue=4 \|pages=735–743}}</ref> [[T-spline]] surfaces,<ref name=":3">{{Cite journal \|last1=Lin \|first1=Hongwei \|last2=Zhang \|first2=Zhiyu \|title=An Efficient Method for Fitting Large Data Sets Using T-Splines \|journal=SIAM Journal on Scientific Computing \|date=2013 \|volume=35 \|issue=6 \|pages=A3052–A3068 \|doi=10.1137/120888569 \|bibcode=2013SJSC...35A3052L \|issn=1064-8275}}</ref> [[implicit]] ~~curves~~ and surfaces,<ref name=":5">{{Cite journal \|last1=Hamza \|first1=Yusuf Fatihu \|last2=Lin \|first2=Hongwei \|last3=Li \|first3=Zhao \|year=2020 \|title=Implicit progressive-iterative approximation for curve and surface reconstruction \|journal=Computer Aided Geometric Design \|volume=77 \|pages=101817\|doi=10.1016/j.cagd.2020.101817 \|arxiv=1909.00551 \|s2cid=202540812 }}</ref> etc.		PIA is now extended to several common curves and surfaces in the [[geometric design]] field,<ref name=":13">{{Cite book \|last=Hoschek \|first=Josef \|url=https://dl.acm.org/doi/abs/10.5555/174506 \|title=Fundamentals of computer aided geometric design \|date=February 1993 \|publisher=A. K. Peters, Ltd. \|isbn=978-1-56881-007-2 \|location=USA}}</ref> including [[Non-uniform rational B-spline\|NURBS]] curves and surfaces,<ref name=":2">{{Cite journal \|last1=Shi \|first1=Limin \|last2=Wang \|first2=Renhong \|year=2006 \|title=An iterative algorithm of NURBS interpolation and approximation \|journal=Journal of Mathematical Research with Applications \|volume=26 \|issue=4 \|pages=735–743}}</ref> [[T-spline]] surfaces,<ref name=":3">{{Cite journal \|last1=Lin \|first1=Hongwei \|last2=Zhang \|first2=Zhiyu \|title=An Efficient Method for Fitting Large Data Sets Using T-Splines \|journal=SIAM Journal on Scientific Computing \|date=2013 \|volume=35 \|issue=6 \|pages=A3052–A3068 \|doi=10.1137/120888569 \|bibcode=2013SJSC...35A3052L \|issn=1064-8275}}</ref> [[implicit curve]]s and [[implicit surface\|surfaces]],<ref name=":5">{{Cite journal \|last1=Hamza \|first1=Yusuf Fatihu \|last2=Lin \|first2=Hongwei \|last3=Li \|first3=Zhao \|year=2020 \|title=Implicit progressive-iterative approximation for curve and surface reconstruction \|journal=Computer Aided Geometric Design \|volume=77 \|pages=101817\|doi=10.1016/j.cagd.2020.101817 \|arxiv=1909.00551 \|s2cid=202540812 }}</ref> etc.

	== Iteration Methods ==		== Iteration Methods ==

GünniX: v2.05 - Fix errors for CW project (Heading hierarchy - Reference before punctuation)

2024-08-18T15:44:54Z

v2.05 - Fix errors for CW project (Heading hierarchy - Reference before punctuation)

Show changes

EagleZju: /* References */

2024-08-15T23:59:25Z

References

← Previous revision		Revision as of 23:59, 15 August 2024
Line 532:		Line 532:
	[[Category:Computational geometry]]		[[Category:Computational geometry]]
	[[Category:Geometric algorithms]]		[[Category:Geometric algorithms]]
			[[Category:Curve fitting]]