几何迭代法及其应用

相关工作

几何迭代算法的基本过程

插值型几何迭代算法近型几何迭代算法

几何迭代方法的应用07:55:11207:55:113相关工作相关工作

PIA:

Progressive

iteration

approximation(渐近迭代

近)→Geometric

iteration

method(几何迭代法)

Hongwei

Lin,

Hujun

Bao,

Guojin

Wang.Totally

Positive

Bases

and

ProgressiveIteration

Approximation.

Computersand

Mathematics

with

Applications,50(3-4),

575-586,

2005.4.07:55:114相关工作07:55:115相关工作⚫等,数学学报1975蔺宏伟,王国瑾,

(2004)证明了非均匀三次B样条曲线、曲面同样具有迭代插值性质，并且(2005)发现有归一化全正基的混合曲线、曲面都有性质;Lin

H.

et.al.

Science

in

China

2004

,

Lin

H.

et.

al.

CMA,

2005Profit

and

lossmodificationHongwei

Lin,

Guojin

Wang,

Chenshi

Dong.

Constructing

Iterative

-Uniform

B-splineCurve

and

Surface

to

Fit

Data

Points.

SCIENCE

IN

CHINA,

Series

F,

47(3),

315-331,

2004.3Hongwei

Lin,

Hujun

Bao,

Guojin

Wang.

Totally

Positive

Bases

and

Progressive

Iterationputers

and

Mathematics

with

Applications,

50(3-4),

575-586,

2005.4.(SCI/EI)等(1975)以及deBoor(1979)分别发现了三次均匀样条曲线的迭代插值性质，齐先生称其为盈亏修正;《分形》07:55:116相关工作等(1975)以及de

Boor(1979)分别发现了3次均匀B-spline的盈亏修正性质

蔺宏伟,

王国瑾, (2004)证明非均匀三次B样条曲线曲面的盈亏修正性质Lin

H.

et.

al.

Science

in

China,

2004

蔺宏伟等（2005）年提出PIA:Progressive

iteration

approximationLin

H.

et.

al.

Computers

and

Mathematics

with

Applications,

2015

史利民和

(2006)证明了有理B样条曲线、曲面同样具有该性质;史利民等，数学研究与评论，2006

蔺宏伟(2010)证明了混合曲线、曲面的局部性质;Lin

H.

CAGD2010和王国瑾(2011)证明了具有均匀参数的三角Bernstein-Bezier曲面具有PIA性质;Shen

J.

et.

al.

CAD

2011SPIA)

蔺宏伟等(2011)提出了 近型的PIA算法,

称为EPIA.Lin

H.

et

al.

Computers

&

Graphics

2011

邓重阳和蔺宏伟(2013)设计了迭代极限是最小二乘解的PIA算Deng

and

Lin,CAD

201407:55:117相关工作

Delgado

J.等(2007)通过研究比较不同基函数，发现了具有最快收敛速度的基函数;Delgado

J.

et.al.

CAGD

2007

Lu

L.(2010)提出了

PIA算法，加快了收敛速度;Lu

L.

CAGD

2010

Frank(Fuhua)Cheng(2008)等人将算法推广至Doo-Sabin和Loop细分曲面拟合，称为Progressive

Interpolation

(PI)算法;Cheng

F.

et.

al.

GMP'08,

JCST

2009

Zhongxian

Chen等人证明了Catmull-Clark细分曲面的PI拟合算法的收敛性。Chen

Z.

et.

al.

PG

200807:55:118相关工作自适应数据拟合

CAGD

2012大规模数据拟合SIAM

Journal

on

Scientific

Computing,

2013有质量保持的六面体网格生成算法

CAD

2015基于几何迭代的降阶

近,

多项式

近,

及等距曲线生成JCAM

2011,

AMC

2013插值给定位置,切向量,和曲率向量的几何迭代算法IEEE

TVCG

2012基于几何迭代的B样条曲面求交算法

IEEE

TVCG

2014保证拓扑正确的B样条曲面重建

CAD

2012基于几何迭代的噪声去除与对称曲面生成

CAD

2012基于几何迭代的B样条体生成方法

CAGD

201507:55:11907:55:1110几何迭代方法的基本过程插值算法07:55:1111近算法

两种差向量：

Difference

vectorfordata

point

Difference

vectorforcontrol

point

两个过程

Vector

distribution

Vect

athering07:55:111207:55:1113插值型几何迭代算法07:55:1114混合曲线的迭代格式及收敛性𝑖𝒓0

𝑡

=

𝑷0𝐵𝑖

𝑡给定初始点列*𝑸0,𝑸1,⋯,𝑸𝑛+赋予递增参数列𝑡0

<𝑡1

<⋯<𝑡𝑛构造初始混合曲线：𝑛𝑖=0𝑖其中,𝑷0

=

𝑸𝑖, 𝐵𝑖

𝑡

,

𝑖

=

0,1,

⋯

,

𝑛为基函数.07:55:1115全正基混合曲线的迭代格式及收敛性𝒓𝑘

𝑡

=

𝑷𝑘𝐵𝑖

𝑡𝑖混合曲线的PIA迭代序列为:𝑛𝑖=0𝑷𝑘−1

+

𝒅𝑘−1𝑖

𝑖=𝑖𝐵

(𝑡)𝑛0其中,

𝐵𝑖

𝑡

,

𝑖

=

0,1,

⋯

,

𝑛为基函数.差向量序列为:𝑖𝒅𝑘

=

𝑸𝑖

−

𝒓𝑘

𝑡𝑖

,

𝑖

=

0,1,

⋯

,

𝑘

=

0,1,

⋯全正基混合曲线的迭代格式及收敛性07:55:1116记𝐷𝑘

=𝒅𝑘,

𝒅𝑘,

⋯

,

𝒅𝑘0

1

𝑛,上述迭代格式的矩阵形式为：𝐷𝑘+1=𝐼

−

𝐶

𝐷𝑘,𝐵0

𝑡0𝐵1

𝑡0⋯𝐵𝑛

𝑡0𝐵0

𝑡1𝐵1

𝑡1⋯𝐵𝑛

𝑡1⋮⋮⋮⋮𝐵0(𝑡𝑛)𝐵1(𝑡𝑛)⋯𝐵𝑛(𝑡𝑛)其中,𝐼为单位矩阵,07:55:1117𝐶

=称为基函数*𝐵𝑖

𝑡,𝑖=0,1,⋯,𝑛+在参数列*𝑡𝑖,𝑖=0,1,⋯,𝑛+上的配置矩阵.全正基混合曲线的迭代格式及收敛性全正基混合曲线的迭代格式及收敛性𝑖如果𝐵𝑖

𝑡,𝑖=0,1,⋯,𝑛为归一化全正基(Normalized

Totally

PositiveBasis),则它的配置矩阵𝐶为全正矩阵，它的特征值𝜆𝑖,𝑖=0,1,⋯,𝑛满足,0

<

𝜆𝑖

<

1,

𝑖

=

0,1,

⋯

,

𝑛.根据上述结果可知,𝜌

𝐼

−

𝐶 =

max

1

−

𝜆𝑖

<

107:55:1218于是*𝐷𝑘+收敛到0向量,

从而迭代曲线序列插值于给定数据点列*𝑸𝑖,

𝑖

=

0,1,

⋯

,

𝑛+Bernstein基,B-spline基都是归一化全正基,所以Bezier曲线,B-spline曲线的PIA迭代格式都收敛𝑖数据点取齐次形式:

𝑸𝑖

= 𝜔𝑖𝑥𝑖,

𝜔𝑖𝑦𝑖,

𝜔𝑖𝑧𝑖,

𝜔𝑖

,

𝑷𝑖

=

(𝑥𝑖,

𝑦𝑖,

𝑧𝑖)齐次形式下的迭代格式与前述混合曲线的迭代格式一样齐次形式差向量取为:𝒅𝑘

=𝑸𝑖

−𝑹𝑘(𝑡𝑖)设第𝑘次迭

成的有理曲线的齐次形式为:𝑡 =

*𝜔𝑘

𝑡

𝑻𝑘

𝑡

,

𝜔𝑘

𝑡

+𝑹𝑘等价于:𝑻𝑘𝑡

=𝑘

𝑘𝜔

𝑷

𝐵

(𝑡)𝑛𝑖=0𝑖

𝑖

𝑖𝜔𝑘𝐵𝑖(𝑡)𝑛𝑖=0

𝑖𝑘,

𝜔

𝑡

=𝑛𝑖=0

𝑖𝑖𝜔𝑘𝐵

(𝑡).NURBS曲线的迭代格式和收敛性07:55:1219NURBS曲线的迭代格式和收敛性可以证明：有理曲线的齐次坐标形式的迭代格式收敛,lim

𝑹𝑘

𝑡𝑖

=

𝑸𝑖,

𝑖

=

0,1,

⋯

,

𝑛.𝑘→∞欧式空间中的迭代曲线也收敛,有,lim

𝑻𝑘(𝑡𝑖)=𝑷𝑖,并且,lim

𝜔𝑘(𝑡𝑖)=𝜔𝑖,𝑖=0,1,⋯,𝑛.𝑘→∞

𝑘→∞07:55:1220全正基混合曲线的迭代格式及收敛性迭代0次07:55:1921迭代4次迭代15次全正基混合曲面的迭代格式及收敛性给定一个数据点列𝑸𝑖𝑗,𝑖=0,1,⋯,𝑚,𝑗=0,1,⋯,𝑛赋予每一个数据点𝑸𝑖𝑗参数值𝑢𝑖,

𝑣𝑗

,

满足:𝑢0

<

𝑢1

<

⋯

<

𝑢𝑚,

𝑣0

<

𝑣1

<

⋯

<

𝑣𝑛构造初始混合曲面:𝒔0𝑷0

𝐵𝑖

𝑢

𝐵𝑗

𝑣

,07:55:1922𝑛𝑢,

𝑣

=𝑚𝑖=0

𝑗=0

𝑖𝑗𝑖𝑗其中,

𝑷0

=

𝑸𝑖𝑗,𝑖

=

0,1,

⋯

,

𝑚,

𝑗

=

0,1,

⋯

,

𝑛全正基混合曲面的迭代格式及收敛性𝒔𝑘𝑢,

𝑣

=𝑖𝑗𝑷𝑘

𝐵𝑖

𝑢

𝐵𝑗

𝑣𝑛𝑗=0𝑛混合曲面的PIA迭代序列为:𝑚𝑖=0𝑚=𝑷𝑘−1

+

𝒅𝑘−1𝑖𝑗

𝑖𝑗𝐵𝑖

𝑢

𝐵𝑗(𝑣)𝑗=0𝑖=0差向量序列为:𝑖𝑗𝒅𝑘=

𝑸𝑖𝑗

−

𝒔𝑘

𝑢𝑖

,

𝑣𝑗

,

𝑘

=

0,1,

⋯𝑖𝑗将𝒅𝑘

按下标的字典序组织成一维数组:𝐷𝑘

=𝒅𝑘07:55:192300

01

0𝑛

10

1𝑛

𝑚0,

𝒅𝑘

,

⋯

,

𝒅𝑘

,

𝒅𝑘

,

⋯

,

𝒅𝑘

,

⋯

,

𝒅𝑘𝑚𝑛,

⋯

,

𝒅𝑘

.矩阵形式的迭代格式为:𝐷𝑘+1

=𝐼

−

𝐶

𝐷𝑘

= 𝐼

−

𝑀⨂𝑁

𝐷𝑘其中,⨂为Kronecher积,𝑀为𝑢方向上的配置矩阵:𝑀

=𝐵0

𝑢0⋯𝐵0(𝑢𝑚)𝐵1(𝑢0)⋯𝐵1(𝑢𝑚)⋯

𝐵𝑚(𝑢0)⋯

⋯⋯

𝐵𝑚(𝑢𝑚)N为𝑣方向上的配置矩阵:𝐵0

𝑣0𝐵1(𝑣0)⋯𝐵𝑛(𝑣0)𝑁

=

⋯⋯⋯⋯𝐵0(𝑣𝑛)𝐵1(𝑣𝑛)⋯𝐵𝑛(𝑣𝑛)全正基混合曲面的迭代格式和收敛性07:55:2024全正基混合曲面的迭代格式和收敛性设矩阵𝑀,𝑁的特征值分别为𝜆

𝑀,𝜆(𝑁),则Kronecher积矩阵𝑀⨂𝑁的特征值为,𝜆

𝑀⨂𝑁 =

𝜆

𝑀

𝜆

𝑁

.由于矩阵𝑀,𝑁都是归一化全正矩阵,所以,0

≤

𝜆

𝐼

−

𝐶 =

1

−

𝜆

𝑀

𝜆

𝑁 <

1,因此,具有全正基混合曲面的PIA迭代格式收敛.Bezier曲面,B-spline曲面的PIA迭代格式都是收敛的.07:55:2025全正基混合曲面的迭代格式和收敛性迭代0次07:55:2426迭代3次迭代15次三角B-B曲面的迭代格式及收敛性

当数据点的参数值均匀排列时：单变量Bernstein算子𝐵𝑛:𝐶

0,1→

𝐶,0,1-:𝑛𝑘1

−

𝑥𝑥𝑘

𝑛−𝑘𝑓𝑘𝑛𝐵𝑛𝑓

𝑥

=𝑛𝑘=0,𝑖𝑛的特征值为:

𝜆

=

𝑛!

1𝑛−𝑖

!

𝑛!07:55:2427,

𝑖

=

0,1,

⋯

,

𝑛.三角B-B曲面的迭代格式及收敛性有𝑠+1

𝑠≥2

个变量的Bernstein算子𝑩𝑛为:𝐵𝑛𝑓𝑠+1

=𝑛𝜶1𝑥𝛼1

⋯

𝑥𝛼𝑠

1−

𝑥 −

⋯

−𝑥𝑠

1𝑠𝑛−𝑘𝑓(𝛼1,⋯,𝛼𝑠,𝑛−𝛼1−⋯−𝛼𝑠)𝑛

𝑛

𝑛𝑛𝑘=0

𝜶

=𝑘𝑖=0其中,𝑓是一个有𝑠+1个变量的函数,并且,𝜶

=

𝛼1,

𝛼2,

⋯

,

𝛼𝑠

,

𝜶

=𝑠𝛼𝑖

,𝑛𝜶=

𝑛!

.𝛼1!𝛼2!⋯𝛼𝑠!

𝑛−𝛼1−⋯−𝛼𝑠

!算子𝑩𝑛可以被对角化,且它的任一特征值必属于单变量Bernstein算子𝐵𝑛的特征值组成的集合,𝑖𝑛−𝑖

!

𝑛!07:55:2428𝜆𝑛

=

𝑛!

1

,

𝑖

=

0,1,

⋯

,

𝑛.

.07:55:2429三角B-B曲面的迭代格式及收敛性三角B-B曲面的PIA迭代格式的迭代矩阵为𝐼−𝐴,其中,𝐼为单位矩阵,𝐴为上述Bernstein算子对应的矩阵由于Bernstein算子的特征值大于0,且小于等于1,根据算子与其对应矩阵的关系,矩阵A的特征值也大于0且小于等于1所以,𝐼−𝐴的谱半径小于1,

从而均匀参数的三角B-B曲面的PIA迭代格式收敛.三角B-B曲面的迭代格式及收敛性

当数据点的参数值非均匀排列时：

已经证明了四次及四次以下的三角B-B曲面的PIA迭代格式是收敛的;

一般情况下的收敛性，还没有证明07:55:2430收敛速度假设N为迭代矩阵,线性迭代法的收敛速度有两个指标来衡量:k次迭代的平均收敛速度:𝑅

𝑁𝑘𝑘=

−𝑙𝑛𝑁𝑘渐进收敛速度:𝐴

𝑁 =

lim

𝑅

𝑁𝑘𝑘→∞07:55:2431=

−𝑙𝑛𝜌(𝑁)在PIA迭代格式中,迭代矩阵为𝐼−𝐶,所以收敛速度与𝐼−𝐶的谱半径有关,谱半径越小,收敛速度越快07:55:2432收敛速度如前所述,具有归一化全正基的混合曲线曲面的PIA迭代格式都收敛如下三种基,B-spline基,Bernstein基,和Said-Ball基都是归一化全正基,所以,这三种基函数生成的混合曲线曲面的PIA迭代格式都收敛在具有全正基的函数空间中,归一化B基形成的混合曲线曲面的PIA迭代格式的收敛速度最快迭代加速---方法PIA迭代格式可以通过对差向量

来加速收敛:𝑃𝑘+1

=

𝑃𝑘

+

𝜔𝑑𝑘,

𝑖

=

0,1,

⋯

,

𝑛,

𝑘

=

0,1,

⋯

;𝑖

𝑖

𝑖•迭代格式的矩阵形式为𝐷𝑘+1=𝐼

−

𝜔𝐶

𝐷𝑘,

𝑘

=

0,1,

⋯

;当𝜔

=21+𝜆𝑚𝑖𝑛(𝐶)时,

迭代格式取得最大收敛速度.此时,迭代矩阵的谱半径为:𝜌

𝐼

−

𝜔𝐶1+𝜆𝑚𝑖𝑛(𝐶)=

1−𝜆𝑚𝑖𝑛(𝐶).07:55:243307:55:2434几何迭代方法的局部性质Hongwei

Lin.

Local

progressive-iterative

approximation

format

for

blending

curvesand

patches.

Computer

Aided

Geometric

Design,

27(4),

322-339,

2010.几何迭代方法的局部性质PIA方法的局部性质:在迭代过程中,仅调整部分控制顶点,则,极限曲线曲面仅插值给定数据的相应子集几何迭代算法的局部性质将控制顶点分为两部分,移动控制顶点的指标𝑖∈*𝑖0,𝑖1,⋯,𝑖𝐼+,固定控制顶点的指标𝑗∈*𝑗0,𝑗1,⋯𝑗𝐽+仅调整移动控制顶点,记07:55:2636𝑇𝐷𝑘

= 𝐷𝑘,

𝐷𝑘

= 𝑑𝑘

,

𝑑𝑘

,

⋯

,

𝑑𝑘

,

𝑑𝑘

,

𝑑𝑘

,

⋯

,

𝑑𝑘𝐽

𝐼

𝑗0

𝑗1

𝑗

𝐽

𝑖0

𝑖1

𝑖𝐼几何迭代算法的局部性质局部PIA迭代格式的矩阵形式为,𝐷𝑘+1

=

𝐶𝐷𝑘,其中,𝐶

=𝐼

𝐵10 𝐼

−

𝐵2,𝐵1,𝐵2为配置矩阵,1𝐵 =

−𝐽,2𝐵 =

−𝐵𝑖𝐼

𝑡07:55:2637⋯

𝐵𝑖𝐼(𝑡)⋯

𝑡𝑗⋯⋯𝐵𝑖0

(𝑡)𝑡𝑗0𝐵𝑖0

𝑡𝑡𝑖0𝐵𝑖1

𝑡𝑡𝑗1𝐵𝑖1

𝑡𝑡𝑖1𝑡𝑖𝐼.几何迭代算法的局部性质𝑙如果上述矩阵𝐵2非奇异,移动控制顶点𝑷𝑘,𝑙∈*𝑖0,𝑖1,⋯,𝑖𝐼+对应的曲线上𝑘→∞的点收敛于数据点𝑸𝑙,即,lim

𝑷𝑘(𝑡𝑙)

=

𝑸𝑙.𝐽当𝑘→∞时,相应于固定控制顶点的差向量𝐷𝑘收敛,极限为:𝐽

𝐼𝐷𝐽

=

𝐷0

+

𝛬𝐷0,矩阵Λ可表示为,1Λ

=

𝐵

𝑋−1𝑑𝑖𝑎𝑔,1

11−𝜆0

1−𝜆1,

⋯

,11−𝜆𝐼𝑋,07:55:2638其中,𝑋为𝐵2的特征向量组成的矩阵.几何迭代算法的局部性质应用局部PIA格式,3次B-spline曲线插值3个顶点(红色)07:55:2639几何迭代算法的局部性质已经证明,双3次B-spline和NURBS曲面也具有局部PIA性质.07:55:2640几何迭代方法的局部性质局部性质是几何迭代方法的一大优点,有了局部性质,可以:分别控制每个点的拟合精度达到对数据点的自适应拟合可以用来求解一类带等式约束的优化问题07:55:264107:55:2642细分曲面的几何迭代算法细分曲面的几何迭代算法细分曲面:从初始网格出发,根据细分规则,生成光滑曲面.07:55:2643细分曲面的几何迭代算法插值型细分曲面:例如,Butterfly细分曲面,改进的Butterfly细分曲面,以及Kobbelt细分曲面优点:易于实现,插值于初始控制网格顶点缺点:对控制网格质量较为敏感

近型细分曲面:例如,Loop细分曲面,Doo-Sabin细分曲面,Catmull-Clark细分曲面优点:生成曲面光顺性较好缺点:收缩较为明显为了改善

近型细分曲面收缩的缺点,

常常使其极限曲面插值给定数据点07:55:2644细分曲面的几何迭代算法𝑖设第k次的控制网格为𝑀𝑘,控制网格顶点为𝑣𝑘𝑖

𝑖,∞首先,计算对应于控制顶点𝑣𝑘在细分曲面上的极限位置𝑣𝑘𝑖

𝑖

𝑖,∞其次,计算差向量𝑑𝑘

=𝑣0

−𝑣𝑘𝑖

𝑖

𝑖然后,计算新控制顶点位置𝑣𝑘+1

=𝑣𝑘

+𝑑𝑘,从而得到新控制网格𝑀𝑘+107:55:2645细分曲面的几何迭代算法经过上述几何迭代过程产生的极限细分曲面插值于初始控制网格顶点.07:55:2646细分曲面几何迭代算法的局部性质将控制顶点集合分成固定顶点集合与移动顶点集合迭代过程仅针对移动顶点集合提供一种形状控制

,

可生成丰富的几何形状07:55:2647近型几何迭代算法Hongwei

Lin,Zhiyu

Zhang.

An

extended

iterative

format

for

theprogressive-iterationputers

&

Graphics,

35(5),

967-975,

2011.Chong Deng,

Hongwei

Lin.Progressive

and

iterative

approximation

for

leastsquares

B-spline

curve

and

surface

fitting.

Computer-Aided

Design,

47(1),

32-44,2014.07:55:264807:55:2649EPIA:

Extended

Progressive-Iterative

ApproximationHongwei

Lin,

Zhiyu

Zhang.

An

extended

iterative

format

for

theprogressive-iterationapproximation.

Computers

&

Graphics,35(5),

967-975,

2011.基本思想数据点分组,每组对应一个控制点两种差向量：Difference

vector

for

data

point（DVD）Difference

vector

for

controlpoint

（DVC）两个过程:Vector

distributionVect

athering𝑖Vector

distribution:每个DVD乘以一个权因子𝑐𝑖𝒅𝑘,分配到它对应的控制点上Vectathering:

所有分配到某个控制点的DVD取

平均，得到它的DVC𝑖

𝑐𝑖𝒅𝑘𝐷𝑉𝐶

=

𝑖

𝑖

𝑐𝑖07:55:2650EPIA的收敛性迭代矩阵𝐷=𝐼−𝐶,(当权因子取1时),其中,𝐶

=𝐵0(𝑡𝑖

)07:55:2651𝑖

∈𝐼0

0

00𝑖

∈𝐼0

0𝐵𝑙(𝑡𝑖

)𝑖

∈𝐼0

0

0

1𝑘0

1𝑘1𝑖1∈𝐼1

𝐵0(𝑡𝑖

1

)⋮

1𝑘0

1𝑘1

1𝑘0

1𝑘1𝑖1∈𝐼1

𝐵𝑙(𝑡𝑖

1

)⋮1𝑘𝑙𝑙𝐵0(𝑡𝑖

)𝑖

∈𝐼𝑙

𝑙1𝑘𝑙𝑙𝐵1(𝑡𝑖

)𝑖1∈𝐼1⋮𝐵1(𝑡𝑖

)

⋯𝐵1(𝑡𝑖1)

⋯⋯⋯𝑖

∈𝐼𝑙

𝑙1𝑘𝑙𝑙𝐵𝑙(𝑡𝑖

)𝑖

∈𝐼𝑙

𝑙可以证明,𝐶是归一化全正矩阵因此,迭代矩阵𝐷的谱半径小于1,EPIA收敛EPIA:

近曲线插值某些点可以选择插值某些点，使算法更灵活初始控制多边形和初始曲线迭代10次最小二乘法生成的拟合曲线07:55:2652EPIA:拟合结果07:55:2653LSPIA:

Least-Squares

Progressive-Iterative

ApproximationChong Deng,

Hongwei

Lin.

Progressive

and

iterative

approximation

for

leastsquares

B-spline

curve

and

surface

fitting.

Computer-Aided

Design,

47(1),

32-44,

2014.07:55:2654LSPIA的迭代格式和收敛性𝑗控制顶点对应的差向量为：𝐷𝑉𝐶

=𝑖𝑖

𝑐𝑖𝒅𝑘𝑖

𝑐𝑖LSPIA的迭代格式,

对应

因子𝑐𝑖

=𝐵𝑗

𝑡𝑖

,

也就是说,第𝑗个控制点对应的基函数在第𝑖个数据点对应的参数值𝑡𝑖处的取值07:55:2655LSPIA的迭代格式和收敛性1

2

𝑛记:

Δ𝑘

= Δ𝑘,

Δ𝑘,

⋯

,

Δ𝑘𝑇,则LSPIA迭代格式的矩阵形式为:Δ𝑘+1=𝐼

−

Λ𝐴𝑇𝐴

Δk其中,𝐼为单位矩阵,Λ

=

𝑑𝑖𝑎𝑔,1

1𝑖∈𝐼0

𝐵0(𝑡𝑖)

𝑖∈𝐼1

𝐵1(𝑡𝑖),

⋯

,1𝑖∈𝐼𝑛

𝐵𝑛(𝑡𝑖),𝐴为配置矩阵,𝐴

=𝐵0(𝑡0)𝐵1(𝑡0)⋯𝐵𝑛(𝑡0)𝐵0(𝑡1)𝐵1(𝑡1)⋯𝐵𝑛

𝑡1⋯⋯⋯⋯𝐵0(𝑡𝑚)𝐵1(𝑡𝑚)⋯𝐵𝑛(𝑡𝑚)07:55:275607:55:2757LSPIA的迭代格式和收敛性如果矩阵A非奇异，那么，矩阵ΛATA是对称正定矩阵并且它的无穷大范数小于等于1于是，矩阵ΛATA的特征值大于0小于等于1,

LSPIA迭代格式收敛LSPIA迭代的极限曲线曲面收敛到最小二乘拟合曲线曲面LSPIA:拟合结果初始控制点列取为：首末控制点与输入点列首末点相同，其他控制点取为同一个点(100,1)07:55:2758细分曲面的近型几何迭代算法07:55:275907:55:2760几何迭代算法的应用几何迭代算法的应用应用于数据拟合领域:自适应数据拟合大规模数据拟合应用于网格生成领域:有质量保证的平面四边网格生成算法有质量保持的六面体网格生成算法应用于几何设计与计算领域:基于几何迭代的降阶

近,

多项式

近,

及等距曲线生成插值给定位置,切向量,和曲率向量的几何迭代算法基于几何迭代的B样条曲面求交算法应用于逆向工程领域:保证拓扑正确的B样条曲面重建基于几何迭代的噪声去除与对称曲面生成基于几何迭代的B样条体生成方法07:55:276107:55:2762几何迭代算法的应用几何迭代法应用的基本思路：由于迭代法有了几何意义，在迭代过程中，可以加入几何约束，逐步改善运算结果07:55:2763数据的自适应拟合Hongwei

Lin.

Adaptive

Fitting

by

theProgressive-iterative

Approximation.

ComputerAidedGeometric

Design,

29(7),

463-473,

2012.自适应的数据拟合技术基于局部性质的自适应数据拟合07:55:2764将数据点分为两部分,活动点和固定点.活动点为拟合精度未满足要求的点,固定点为拟合精度满足要求的点.只调整活动点对应的控制顶点,固定点对应的控制顶点不动.自适应的数据拟合技术07:55:276507:55:2766大规模数据(图像)拟合Hongwei

Lin,

Zhiyu

Zhang.

An

efficient

method

for

fittinglarge

data

sets

using

T-splines.

SIAM

Journal

on

Scientific

Computing,

35(6),

A3052-A3068,

2013.12.

.几何迭代用于大规模图像拟合T样条拟合节点

方法PIA算法的并行实现（4核8线程）07:55:2767几何迭代用于大规模图像拟合迭代速度与未知量个数无关PIA算法易于并行实现07:55:2768几何迭代用于大规模图像拟合Yixin

Chen,Washington

University

in

St.Louis

（2013.12，

第一届大数据学术会议，

）07:55:2769几何迭代用于大规模图像拟合

11747X5400RMS

error=3.73 time=318分钟原始图像07:55:2770从T-mesh中恢复的图像大规模图像拟合07:55:2771大规模图像拟合原始图像07:55:2772从T-mesh中恢复的图像time=81分钟Gauss-Seidel

1492分钟Conjugate

Gradient

2193分钟3674X2449RMS

=

5.88大规模图像拟合07:55:2773大规模图像拟合1680X1050 RMS

=

3.89time=30分钟Gauss-Seidel

711分钟Conjugate

Gradient

1327分钟07:55:2774大规模图像拟合1600X1200

RMS

=

2.07time=46分钟07:55:2775大规模图像拟合07:55:2776有洞数据的拟合07:55:2777有质量保证的四边网格和六面体网格生成算法78Hongwei

Lin,

Hongwei

Liao,

Chong Deng.

Filling

Triangular

Mesh

Model

withAll-Hex

Mesh

by

Volume

Subdivision

Fitting.

Technical

Report,TR-ZJUCAD-2012-002,UniversityHongwei

Lin,Sinan

Jin,Hongwei

Liao,

et

al.Quality

Guaranteed

All-Hex

MeshGeneration

by

a

Constrained

Volume

Iterative

Fitting

Algorithm

.

Computer-AidedDesign,

67-68,

107-117,

2015.Hongwei

Lin,

Qun

Jian,

Sinan

Jin.

Generating

quality

guaranteed

quadrilateral

mesh

onan

n0-7s:5i5d:2e7d

region

with

geometric

iterative

fitting.

Submitted有质量保证的六面体网格模型生成算法比值大于零的网格，才是在有限元分析中,只有六面体网格顶点处有效网格，可以用于有限元计算.很多六面体生成算法,虽然可以生成质量很好的六面体网格,但是不能从理论上保证生成的六面体网格顶点处的

比值都大于零.07:55:2779有质量保证的六面体网格模型生成算法边界四边形网格拟合边界网格顶点的移动扩散到 网格顶点顶点的移动受限,保证生成的六面体网格顶点处的比值大于零07:55:2780有质量保证的六面体网格生成算法Hongwei

Lin,

Hongwei

Liao,

Chong

Deng.

Filling

Triangular

Mesh

Model

with

All-Hex

Mesh

byVolume

Subdivision

Fitting.

Technical

Report,

TR-ZJUCAD-2012-002,

University07:55:2781有质量保证的六面体网格模型生成算法Hongwei

Lin,

Sinan

Jin,Hongwei

Liao,

et

al.Quality

Guaranteed

All-Hex

MeshGeneration

by

a

Constrained

Volume

Iterative

Fitting

Algorithm

.

Computer-AidedDesign,

67-68,

107-117,

2015..07:55:2782有质量保证的六面体网格生成算法

优点：

算法简单，易于编程实现

自动化程度高，人工交互少

从理论上保证生成

比值大于零的有效网格

缺点：

生成的六面体网格依赖于初始控制网格

生成的六面体网格中有极少数网格点处的比值很小

对这些点的位置进行轻微扰动，再用Mesquite进行优化，可以显著提高最小

比值07:55:2783有质量保证的六面体网格生成算法生成的六面体网格中有极少数网格点处的比值很小对这些点的位置进行轻微扰动，再用

Mesquite进行优化，可以显著提高最小雅克比值07:55:2884有质量保证的六面体网格生成算法Comparison

with

existing

method07:55:2885有质量保证的四边形网格生成算法07:55:2886有质量保证的四边形网格生成算法07:55:288707:55:2888几何迭代方法插值位置，切向量和曲率向量S.

Okaniwa,A.

Nasri,

Hongwei

Lin,

A.Abbas,

Y.

Kineri,

T.

Maekawa.

Uniform

B-splineCurve

Interpolation

with

Prescribed

Tangent

and

Curvature

Vectors.

IEEETransactionson

Visualiza