基于二次误差度量的网格简化方法

网格简化方法"/>

基于二次误差度量的网格简化方法

网格简化是提高计算机处理复杂模型速度的有效方法，算法时间和空间复杂
性低、简化质量高且简化结果中三角形紧致性好。

1、术语及概念

向量均指三维列向量，顶点V的坐标为[x，y，z]，所指的边均为有向边，e=(V0,V1),记做v1-v0。把点到边所在直线的距离简称为点到边的距离. v*表示所有与顶点v相邻的边的集合。
边折叠操作如图
边v0v1折叠为折叠点，v引起网格局部形状的变化,（此时v1与v2经过折叠重合）如v0v1不是边界边,则一次边折叠减少2个三角形、3条边、1个顶点。（

2.误差度量

设边v0v1折叠为点v,定义v到v0和v1中各边距离的平方和为该折叠操作的误差。
设s0=v-v0,ti为v0中边的单位向量,则点v到v0中各边距离的平方和
记括号内为Q,则
同样,设s1=v-v1,可得点v到v1中各边的距离的平方和

中边v0v1折叠为点v,顶点v到v0和v*1中各边距离的平方和
以s0=v-v0,s1=v-v1代入上式
边v0v1折叠为点v的误差

3、折叠点坐标的确定

一般可选取折叠点v的坐标为v0,v1或(v0+v1)/2

4、边折叠消耗函数

误差度量Δ(v)仅表示一次边折叠前后局部网格的差异,而为了有效控制
简化后网格与原始网格的距离,就需要定义一个全局误差函数

其中　Δ(v)为本次折叠操作引起的误差,e(v0)与e(v1)分别为点v0与v1的历史记录误差.设m为常数,执行该边折叠操作后折叠点v的历史记录误差

随着边折叠操作的进行,每次折叠操作误差的积累,各边折叠的c(v)值将不断增大,因此,消耗函数c(v)即可作为本算法网格简化的全局误差函数.

5、算法流程

以边折叠为基本操作,以点到相关直线的距离的平方为误差度量,按边折叠消耗函
数值的大小将所有边排为升序优先队列,取队首元素执行边折叠操作,删除队列中无效的边,并重新计算与折叠点相邻的边的消耗函数值,将其插入队列。