一种基于八叉树空间划分和顶点删除的三维模型简化方法

摘要

本发明属于计算机图形处理技术领域，涉及三维可视化模型简化技术。本发明采用八叉树的和定义新顶点权值的顶点抽取相结合的方法，首先通过八叉树将模型空间划分成一系列叶子节点区域，所有的顶点就分布在这些区域内，然后在这些叶子节点中，采用定义了新的顶点权值的顶点抽取算法对顶点进行删除，达到三维模型简化的目的。采用本发明提出的八叉树的和定义新顶点权值的顶点抽取相结合的方法，可以有效地提高三维模型简化的质量和简化速度。

主权项

1、一种基于八叉树空间划分和顶点删除的三维模型简化方法，包含以下步骤：步骤1.输入原始三维模型数据，获取其顶点序列V_list，对V_list进行初始八叉树空间划分，得到划分后八个卦限空间顶点序列V_k，其中k＝1，2，…8，将V_k依次放入空间待划分队列Q；步骤2.从空间待划分队列Q中取出一个划分空间的顶点序列Q(i)，如果该划分空间顶点个数N_Q(i)<N′，将Q(i)放入待简化队列P，否则对Q(i)进行八叉树空间划分，得到每个该空间划分后八个卦限空间顶点序列V_k，其中k＝1，2，…8，将V_k依次放入空间待划分队列Q；循环该步骤直到划分完所有空间待划分队列Q的顶点序列，得到最终的待简化队列P；步骤3.从待简化队列中依次取出顶点序列P(t)；步骤4.计算顶点序列P(t)中每个顶点权值W_q，顶点权值的表达式为$W_q=\underset{s\in {\eta }_q}{\max }\left(l_{q,s}\right)\times (\alpha -\beta \times \underset{s\in {\eta }_q}{\min }\left(c_{q,s}\right))+c\times e_q,$其中l_q，s为顶点邻域内的两顶点的欧氏距离，c_q，s是两顶点法线夹角的三角余弦值，e_q是边缘特征，η_q为顶点的邻域，max()是求最大运算，min()是求最小运算，α，β，c是取值范围为[0，1]的系数；并根据顶点权值大小进行快速排序，令有最小顶点权值的顶点为v；删除顶点序列P(t)中的顶点v，然后进行三角剖分，即在三角形网格中，用v顶点邻域内的具有最大顶点权值的顶点代替顶点v；重复步骤4中上述操作直到顶点序列P(t)的删除顶点数大于等于待删除顶点个数N，待删除顶点个数N为P(t)的顶点个数m的k倍，0<K<1，K为简化倍数；步骤5.重复步骤3和步骤4，直到处理完所有的待简化队列里面的每一个顶点序列；步骤6.删除网格中具有相同顶点的三角面片，得到新的三角面片列表F_list；步骤7.由待简化队列P和三角面片列表F_list经OpenGL显示函数得到简化的模型。