（1国网天水供电公司；2国网天水供电公司；3广州供电局有限责任培训与评价中心；
4北京科东控制系统有限责任公司）
摘要：针对三维模型简化的问题，提出了一种基于角度特征的半边折叠简化算法。使用边长和边的向量夹角确定存在数据冗余的折叠边，根据折叠边上顶点的方向向量与所有经过该顶点的边之间夹角的均值和方差确定简化后的顶点，将折叠边折叠到简化后的顶点处来简化三维模型。使用斯坦福三维数据模型测试，测试结果表明，该算法能够在保证模型视觉特征的基础上减少数据冗余。
关键词：三维模型简化；半边折叠算法；角度特征
0引言
本文提出了一种基于角度特征的半边折叠简化算法，使用边长和边的向量夹角确定存在数据冗余的折叠边，然后根据折叠边上顶点的方向向量与所有经过该顶点的边之间夹角的均值和方差确定简化后的顶点，将折叠边折叠到简化后的顶点处来简化三维模型。该简化算法执行速度较快，能够在保证模型视觉特征的基础上减少数据冗余。
1 边折叠算法
边折叠算法是一种常见的三维模型简化方法，它将三维模型中满足一定条件的一条边简化成一个顶点，将与该边两顶点相邻的所有顶点都和简化后的顶点相连，同时删除退化的顶点和三角面片。根据折叠后顶点位置的不同，边折叠算法可分为半边折叠算法和全边折叠算法。半边折叠算法使用三维模型中的原始顶点作为简化后的顶点，全边折叠算法使用新生成的顶点作为简化后的顶点，半边折叠算法可以避免新生成顶点位置的计算，还能够保留三维模型中原始顶点的法向、纹理等属性信息，数据存储时也不会产生额外的存储开销，所以本文使用半边折叠简化算法来简化三维模型。基于角度特征的半边折叠算法根据三维模型中边和顶点的角度特征，确定折叠边和简化后的顶点，将折叠边折叠到简化后的顶点处来去除数据冗余。
2 折叠边度量准则
现代设备的三维模型，普遍具有结构复杂、数据量庞大的特点，基于边长等距离特征的折叠边度量准则很难充分保留模型的视觉特征。为了在保证模型视觉特征的基础上减少数据冗余，本文在选择折叠边时充分考虑了以下两个因素：边长和边的向量夹角。首先选择边长最短的一条边作为折叠边，然后根据该边的向量夹角判断选择的折叠边是否正确。
2.1 边的向量夹角
2.2 确定折叠边
三维模型中相邻顶点之间的距离越短，两个顶点表示的细节特征越相似，存在数据冗余的可能性越大，可以根据三角面片的边长来判断该边附近区域是否存在数据冗余。但是在三维模型的拐点和尖锐边缘等位置，即使三角面片的边长很短，半边折叠后也有可能造成模型视觉特征的丢失。事实上，边的向量夹角能够反映该边附近区域表面的平滑情况：边的向量夹角越大，该边附近区域的表面越平坦；边的向量夹角越小，该边附近区域的表面越尖锐。所以本文使用边长和边的向量夹角作为折叠边的判别准则，首先根据边长确定需要折叠的折叠边，然后将折叠边的两个向量夹角与预设阈值进行比较，判断选择的折叠边是否正确。
3.2折叠限制条件
半边折叠的目的就是为了减少三维模型中相对不重要或比较平坦等区域范围内的顶点数量和三角面片数量，即在保证模型视觉特征的基础上，减少数据冗余。顶点夹角的均值能够反映顶点的方向向量与所有经过该顶点的边之间夹角的平均水准。顶点夹角的均值越大，其所在区域附近的表面越平坦；顶点夹角的均值越小，其所在区域附近的表面越尖锐。但是顶点夹角的均值并不能反映顶点周围区域的波动起伏，即顶点方向向量与每一条经过该顶点的边之间的夹角相对于平均夹角的波动程度。当顶点周围区域的波动起伏较大时，仅仅使用顶点夹角的均值来确定简化后的顶点，很可能造成模型简化后视觉特征的丢失。而方差能够反映一组数据的离散程度，方差越小，数据相对于平均值的波动程度越小，所以本文使用顶点夹角的均值和方差作为确定简化后顶点的度量准则。
4 算法的基本流程
基于角度特征的半边折叠算法的基本思想为：首先根据边长和边的向量夹角确定需要折叠的折叠边，然后根据半边折叠的限制条件来确定简化后的顶点，最后将折叠边折叠到简化后的顶点处，删除退化的顶点和三角面片。基于角度特征的半边折叠算法的流程，算法的具体步骤如下：
1：根据三维模型中顶点的空间坐标，计算得到所有相邻顶点之间的边长，然后对边长进行排序建立边长列表；
2、从边长列表中选择边长最小的边作为折叠边，计算该边的两个向量夹角；
3、将折叠边的两个向量夹角分别与预设阈值比较，如果两个向量夹角都大于预设阈值，折叠边的选择正确；否则，在边长列表中删除该边，跳至步骤2，重新选择折叠边；
4、根据公式（3）、公式（4）分别计算得到折叠边两个顶点夹角的均值和方差；
5、将折叠两个顶点夹角的均值和方差代入公式（5），分别与预设阈值 、 比较，选择满足折叠限制条件的顶点作为简化后的顶点；如果折叠边的两个顶点都满足折叠限制条件，选择夹角均值较小的顶点作为简化后的顶点；如果折叠边两个顶点都不满足折叠限制条件，从边长列表中删除该边，跳至步骤2，重新选择折叠边；
6、进行半边折叠，让与折叠边两个顶点相邻的所有顶点都和简化后的顶点相连，同时删除退化的顶点和三角面片。
7、在边长列表中删除折叠边，跳至步骤2，重新选择折叠边进行折叠，直至达到简化要求。
5 实验结果
本文提出的算法在HP PC机上使用VC++编程实现，使用斯坦福大学提供的Bunny三维数据模型对算法进行实验验证。实验时，折叠边的向量夹角预设阈值 ，顶点夹角均值的阈值 ，顶点夹角方差的预设阈值为 。
使用本文算法和二次误差算法分别将Bunny原始模型简化到相同的60%比例时，本文算法在视觉特征上更接近原始模型，特别是在模型表面波动起伏的眼部、腿部区域。由表1可知，本文算法在执行时间上要比二次误差算法要长，这是因为本文算法要进行额外的角度计算，但是本文算法也能满足三维模型实时简化的要求。实验结果表明，基于角度特征的半边折叠算法执行速度较快，能够在保证模型视觉特征的基础上减少数据冗余。
6 结论
本文针对三维模型简化算法存在的运行时间长、简化效果不理想等问题，提出了一种基于角度特征的半边折叠简化算法，使用边长和边的向量夹角来确定存在数据冗余的折叠边，根据折叠边上顶点的方向向量与所有经过该顶点的边之间夹角的均值和方差确定简化后的顶点。实验结果表明，该算法执行速度较快，能够在保证模型视觉特征的基础上减少数据冗余。
参考文献：
[1]赵沁平.虚拟现实综述[J].中国科学，2009，39（1）：2-46
[2]王蕊，李俊山，刘国庆，等.一种保持视觉特征的三维几何模型简化算法[J].光电工程，2008，35（7）：63-68.
[3]陆国栋，许鹏，温星.基于向量夹角的三角网格模型简化算法[J].工程设计学报，2005，12（2）：124-128.
论文作者:赵喜兰,马青,邝东海,高峰
论文发表刊物:《电力设备》2016年第22期
论文发表时间:2017/1/21
标签：顶点论文; 夹角论文; 算法论文; 向量论文; 边长论文; 模型论文; 半边论文; 《电力设备》2016年第22期论文;