一种基于多顶点对处理的三维模型边折叠简化的方法.docx

一种基于多顶点对处理的三维模型边折叠简化的方法专利名称：一种基于多顶点对处理的三维模型边折叠简化的方法技术领域：本发明涉及计算机技术领域，具体涉及一种基于多顶点对处理的三维模型边折叠简化的方法背景技术：随着当今科学技术飞速的发展进步，三维图形由于其更生动具体的立体效果，越来越倾向于取代二维图形在人们生活、工作领域的地位越来越多的三维图形出现在数字电视、动画游戏、地图绘制和医疗成像等领域中随着三维模型数据获取技术的不断提高，三维模型的精度也随之增长，这给处理能力有限的交互式设备带来了巨大的压力然而有些场合下并不需要有如此高精度的三维模型，因此需要对三维模型进行简化，从而加快交互终端的处理能力与二维图片用图像分辨率来表示图像精度的方法一样，三维图形也用模型分辨率来对应模型数据密度的大小模型数据密度大意味着模型分辨率高，模型比较精确精细；模型数据密度小意味着模型分辨率低，模型比较粗糙简陋因此三维图形网格简化的实质就是:对三维网格模型的点和三角面片进行处理，在尽量保持原始模型特征的情况下，去除不影响原始模型特征的多余的点和面片，从而减低模型的数据密度，获得能够满足需要的分辨率比较低的模型，使得三维图形在设备终端的显示和编辑变得容易并减少三维图形数据在因特网上传输的压力。

早在197 6年就有学者James Clark提出了三维模型简化的思想，近些年，随着计算机图形学的发展进步以及三维模型应用范围的拓展，越来越多的研究人员对三维模型简化进行了深入全面的研究，特别是采用网格来表示三维模型成为主流之后，涌现众多的三维模型简化算法现有的一个基于边折叠的特征保持的简化算法，以三维模型中点的相邻三角形的单位法向量的变化大小作为权值来对三维模型进行衡量和简化，其重点是考虑折叠前后对拓扑结构的影响该算法能够比较好的保持简化前后模型的拓扑结构，但是在选择顶点对时，该算法仅进行了非常简单的处理:从当前顶点所有未处理的非特征点的相邻顶点中选出距离最近的个顶点与当前顶点组成折叠操作输入的顶点对这种选择策略简易容易执行，但是由于每次选择都要遍历当前顶点所有相邻顶点一次，而最终却只选择了一个顶点进行处理这样使得每次遍历的结果没有得到充分的利用本专利将设计发明一个基于多顶点对处理的边折叠简化算法，在遍历一个顶点进行处理时，改变以往只处理一个顶点对的做法，同时处理多个顶点对来提升简化的时间效率对于现有的技术，该算法在顶点与其相邻顶点之间选择顶点对作为进行折叠操作的输入时，仅仅从当前顶点的相邻顶点中选取一对顶点进行处理最近而已。

然而在实际简化中，由于顶点起伏程度小的顶点最终都将合并到起伏程度较大的顶点中，所以可以在一次处理时，加入处理多个顶点，从而提升算法的时间效率发明内容本发明使得对三维模型的简化能够更快，同时也能够较好的保持模型原始的拓扑结构和特征点从而使得三维模型数据得到大量的减少，降低交互终端的处理压力，同时较高的时间效率能够加快交互终端的交互响应速度，适应将来更加快速的应用场景本发明实施例提供了一种基于多顶点对处理的三维模型边折叠简化的方法，所述方法包括:步骤一:读取三维模型的obj文件，求出平均起伏权值，确定参考阈值；步骤二:根据模型文件中点的次序循环遍历模型中的顶点V，全部遍历完则进入步骤七，否则进入步骤三；步骤三:通过将V的顶点起伏权值与参考阈值进行比较，判断该点是否是特征点，是则进入步骤二 ；如果该点已经进行了处理，同样进入步骤二 ；否则进入步骤四；步骤四:遍历该顶点V的所有相邻顶点，识别出未处理过的非特征顶点，并将该顶点与所有这些相邻非特征顶点均配对作为边折叠操作的候选顶点对；步骤五:采用算法I选择相应的顶点对作为折叠操作的输入；步骤六:将min_arr[]中的顶点依次合并到当前顶点V,再将顶点V合并到max_u ；然后转入步骤二，继续进行简化；步骤七:将简化后保留的顶点及面片信息保存到新的obj文件中，以供下一次简化使用。

通过实施本发明提供的方法，本发明首先通过对大数据量的三维图形进行特征保持的简化操作，能够在以减少图形分辨率的代价上降低三维图形的规模和精度，用较小规模的模型来代替高清模型，从而去除冗余数据，实现在三维图形终端能够顺畅处理和存储，同时也能够在英特网上自由传输的目的，其次，本发明提出的简化算法采用了一种多顶点对的处理方式，充分利用了每次遍历的结果，从中选择出多对顶点对作为折叠操作的输入，这使得简化算法的时间效率得到了极大的提高，基于边折叠的特征保持的简化算法运行一次简化程序只能达到43.4%左右的简化效率，而本发明的基于多顶点对处理的简化算法运行一次，能够达到60%的简化效率为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它的附图图1是本发明实施例中的基于多顶点对处理的三维模型边折叠简化的方法流程图具体实施例方式下面将结合本发明实施例中的附图 ，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。

基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围本发明使得对三维模型的简化能够更快，同时也能够较好的保持模型原始的拓扑结构和特征点从而使得三维模型数据得到大量的减少，降低交互终端的处理压力，同时较高的时间效率能够加快交互终端的交互响应速度，适应将来更加快速的应用场景本发明是一种基于多顶点对处理的三维模型边折叠简化算法该算法以现有最接近技术中的边折叠算法为基础，在选择顶点对上进行了改进每次遍历相邻顶点时，从中选择多对顶点对作为折叠操作的输入，这样每处理到一个顶点时，将会同时删减多个没必要的顶点，从而加快模型简化的速度，提高简化的时间效率进行多顶点对处理时，并不是简单的将所有满足条件的顶点都作为折叠操作的输入，而是分成两类顶点进行选择第一类顶点是能够合并到当前顶点的相邻顶点；第二类是将当前顶点合并到该顶点上的相邻顶点对于第一类顶点，可以尽可能多的进行选择，将其当做折叠操作的输入，对于第二类顶点，则只能选择其中一个，并且如果有多个满足条件的顶点，选择距离最近的一个顶点多顶点对处理的伪代码如下(算法I):申明变量min_arr []用来记录第一类顶点；申明变量max_u用来记录第二类顶点；申明变量min_d用来记录max_u与当前顶点的距离； for(点V的所有相邻顶点) { if(当前顶点u满足非特征点和未处理过的要求){ for ( 点V的所有相邻三角形) { 计算当前三角形单位法向量变化量； } 将所有变化量求和,用CQv表示; for(点u的所有相邻三角形) { 计算当前三角形单位法向量变化量；权利要求1.一种基于多顶点对处理的三维模型边折叠简化的方法，其特征在于，所述方法包括: 步骤一:读取三维模型的Obj文件，求出平均起伏权值，确定参考阈值； 步骤二:根据模型文件中点的次序循环遍历模型中的顶点V，全部遍历完则进入步骤七，否则进入步骤三； 步骤三:通过 将V的顶点起伏权值与参考阈值进行比较，判断该点是否是特征点，是则进入步骤二 ；如果该点已经进行了处理，同样进入步骤二 ；否则进入步骤四； 步骤四:遍历该顶点V的所有相邻顶点，识别出未处理过的非特征顶点，并将该顶点与所有这些相邻非特征顶点均配对作为边折叠操作的候选顶点对； 步骤五:采用算法I选择相应的顶点对作为折叠操作的输入； 步骤六:将min_arr[]中的顶点依次合并到当前顶点v,再将顶点v合并到max_u ;然后转入步骤二，继续进行简化； 步骤七:将简化后保留的顶点及面片信息保存到新的obj文件中，以供下一次简化使用。

全文摘要本发明公开了一种基于多顶点对处理的三维模型边折叠简化的方法，包括读取三维模型的obj文件，求出平均起伏权值，确定参考阈值；根据模型文件中点的次序循环遍历模型中的顶点v；通过将v的顶点起伏权值与参考阈值进行比较；遍历该顶点v的所有相邻顶点，识别出未处理过的非特征顶点；采用算法1选择相应的顶点对作为折叠操作的输入；将min_arr[]中的顶点依次合并到当前顶点v，再将顶点v合并到max_u；将简化后保留的顶点及面片信息保存到新的obj文件中通过实施本发明，能够在以减少图形分辨率的代价上降低三维图形的规模和精度，用较小规模的模型来代替高清模型。