面向Web的机械产品三维模型简化算法研究

齐洪方，汪 耀

(1.武汉华夏理工学院智能制造学院，湖北 武汉 430223；2.武汉理工大学机电工程学院，湖北 武汉 430070)

1 引言

随着信息技术的不断发展，分布式制造的时代已经到来，面向Web的机械产品三维CAD模型在线浏览需求越来越大。采用三维模型的在线浏览方式，用户无需安装大型三维软件，在浏览器中即可查看三维产品模型。

基于WebGL技术的机械产品三维模型Web显示，不仅可以实现3D模型的显示渲染，而且相对于其它Web3D技术而言，具有无需下载安装任何插件或函数库、兼容性好、支持跨平台显示和渲染效果逼真且速度快的特点。由于WebGL技术基于OpenGL ES 2.0，通过多个三角面片来描述一个三维模型实体[1]，随着三维实体模型的复杂程度不断增加，用来描述三维实体模型的面片数据也会随之增加，因此，为保证Web环境下三维模型数据传递和浏览器显示的流畅性，需要对三维模型数据进行简化，以保证浏览器能直接、快速的读取并显示。

本文选择OBJ格式作为通用三维模型格式，针对不同软件导出的OBJ文件内部数据格式不统一的问题，进行三维模型数据的预处理，在三维模型数据预处理的基础上，提出基于半边折叠的三维模型简化算法，该算法利用定点领域三角形的平均面积、定点领域三角形的法向量变化和折叠边的边长计算折叠代价值，并按值的大小进行排序，将折叠代价值最小的边折叠成一个点，并不断重复计算折叠代价值、排序和折叠简化这一过程，直到达到设定的简化要求。

2 三维模型格式预处理

OBJ是一种被普遍公认的模型数据交换格式[2]。OBJ文件通过保存面片信息的形式保存着模型所有几何信息，文件中每一行都通过一个关键字(Keyword)开头，用来区别这一行的数据类型，例如：某一行数据开头是字母v，则表示这一行数据为顶点坐标。OBJ模型文件中常用的关键字及含义见表1。

表1 OBJ模型常用关键字

OBJ文件数据一般都由顶点坐标数据、顶点法向量数据、面片索引数据和纹理坐标数据四部分组成。

但是不同三维CAD软件导出的OBJ文件在数据内容方面存在差异。例如：SolidWorks得到的OBJ文件包含顶点坐标、顶点法向量和顶点索引，但不包含三维模型Web显示所需的纹理坐标数据；Pro/E得到的OBJ文件包含四部分数据，但其纹理坐标数据以三维坐标形式存在，不符合Web环境下对模型进行纹理贴图的二维坐标数据要求；还有部分三维CAD软件以模型中的三角面为基本单元，造成顶点坐标数据、顶点法向量数据和面片索引数据重复出现的现象。综合以上，不同三维CAD软件导出的OBJ文件的差异主要集中在：是否有纹理坐标数据、纹理坐标数据是否为二位坐标数据和点坐标数据、顶点法向量数据和面片索引数据是否重复三个问题。本文借鉴文献[2]的方法，通过纹理坐标处理和数据化零为整处理，将不同三维CAD软件导出的OBJ模型转化为OBJ模型的标准格式，如表2中实例所示。

表2 OBJ标准格式实例

3 半边折叠算法原理

在保证原始模型几何形状不发生改变的前提下，采用适当的算法减少网格模型的面片数或顶点数，可以提高计算机图形绘制速度。常用的网格模型简化算法有顶点删除简化算法[3]，边折叠简化算法[4-5]，采样简化算法[6]，顶点聚类简化算法[7-9]和多边形合并简化算法[10]等。这些算法各有各的特点，在不同的网格简化情形得到相应应用，其中Hoppe提出的基于边折叠思想进行模型简化的算法简单高效是目前最常用的模型简化方法之一。边折叠算法示意图如图1所示，在对v1v2进行折叠时，利用能量优化确定新顶点v’的位置，由于边折叠算法在每一次折叠过程中将产生一个新的顶点同时删除原有的两个顶点，这样在新顶点产生的时候就需要进行顶点索引更新，这一过程将增加一定的计算量和存储量。

图1 边折叠算法示意图

半边折叠算法示意图如图2所示，在进行边uv的折叠时，u点将被删除，同时所有与顶点u相关的顶点将与顶点v相连，即v点起到了代替u点的作用。与边折叠算法不同，半边折叠算法在每一次执行半边折叠的过程中不会产生一个新的顶点，仅删除了一个原有的顶点，避免了计算新顶点位置带来的运输量和存储量。本文选择半边折叠算法作为三维模型简化算法，可以有效提升模型简化效率。

图2 半边折叠算法示意图

4 三维模型数据简化

通常边折叠算法有能量函数法和二次误差测量简化算法，Hope[4]提出的基于能量优化的方法来确定折叠顺序和新顶点位置的网格模型简化算法，通过构建计算网格简化误差的数学模型，来不断寻找使能量方程值最小的简化点。该算法能够实现质量很高的模型简化，但其缺点在于优化过程计算量大，自动化程度不高，耗费了大量的计算时间，不利于Web环境下三维模型的显示；而Garland提出的二次误差测量简化算法[5]通过计算顶点到相关平面距离的平方和作为误差测度，并使用二次误差测度作为边折叠代价，相对Hope提出的算法而言计算较快，也能生成较好质量的模型，但相对Web环境其同样存在着计算量较大的问题。综合上述分析，本文在保证模型显示精度的前提下，为了尽可能的减小计算量，在计算折叠代价时主要考虑了顶点领域三角形平均面积、顶点领域三角形的法向量变化和折叠边的边长三个方面因素。

4.1 顶点领域三角形的平均面积

为了保证模型显示的精度，在模型简化过程中应尽可能避开模型特征较为显著的区域。在网格模型的表达中，若顶点领域三角形的平均面积越小，则说明该区域的三角网格密度越集中，表示该区域的模型特征越显著；若顶点领域三角形的平局面积越大，则说明该区域的三角网格密度越稀疏，表示该区域的模型特征越不显著。因此，顶点的领域三角形的平均面积在一定程度上反映着该顶点处的模型特征的显著程度，如图3所示。

图3 领域三角形

图3中，图(a)和图(b)两个模型在顶点v1处的领域三角形总面积一样，但三角形数量不同，其中图(b)的网格更加密集。当对边(v1，v2)进行折叠操作时，与v1相连的所有顶点都将连接v2上。显然图(b)中的网格在折叠后对模型特征的影响会更大。所以图(b)中的边(v1，v2)比图(a)中边(v1，v2)具有更高的重要度，通过点的领域三角形的平均面积表示，如式(1)所示。

(1)

其中，num表示点vi的领域三角形中三角形的总个数，tj表示点vi领域三角形中的三角形，ARtj表示三角形tj的面积。

4.2 顶点领域三角形的法向量变化

人的视觉对三角面法向量方向的变化比较敏感[11]。边折叠后顶点领域三角形的法向量变化越小，模型的视觉变化影响越小；顶点领域三角形的法向量变化越大，说明模型特征损失较大。如图4所示的边折叠后顶点领域三角形的法向量变化。

图4 边(U，V)折叠后的领域三角形的法向量变化

(2)

4.3 折叠边的边长

在网格模型简化过程中，考虑顶点领域三角形的平均面积大小和法向量变化大小是为了在网格简化过程中尽量避免模型特征显著的区域被大量简化，从而丢失了模型的原始特征。但如果太过注重模型特征区域的保留，而大量删减非特征区域，就会造成简化后的网格模型出现模型整体特征的丢失。为避免这种极端化模型简化的出现，本文引入折叠边的边长这个影响因子。折叠边的边长可通过式(3)来求。

d(u，v)=u-v

(3)

其中，u-v为点u，v之间的欧式距离。

当网格中边的长度越大，折叠此边将引起更大的网格整体变动。因此，在模型简化操作过程中，应优先折叠边长较小的边。

4.4 折叠代价计算

对于网格中的任一条折叠边，折叠代价由顶点领域三角形的平均面积、顶点领域三角形的法向量变化和折叠边的边长三个部分组成，边折叠代价计算式如式(4)所示。

(4)

5 基于折叠代价的半边折叠算法设计

本文采用的半边折叠算法，首先，获取模型网格数据并构建网络拓扑结构。然后，根据折叠代价计算式(4)计算网格中每个顶点的对应边的折叠代价值，并按值的大小进行排序；取出代价值最小的边折叠成一个点，同时将原来与删除点关联的顶点相连到新顶点上删除旧的边；最后，更新折叠变化后受影响边的折叠代价值，并再次排序。重复这一过程，当网格模型简化到没有符合设定条件的半边时，就得到了简化后的网格。其算法流程如图6所示，具体算法步骤如下。

网格模型简化过程中的阈值设定，因考虑到机械产品模型对显示精度的要求，按照领域三角形法向量变化值为1-cos(10°)作为标准，即保证半边折叠后，三维模型的形状特征不会发生变化。

图5 半边折叠算法流程

6 算法实验

6.1 实验环境

在PC机(Intel i7、8G内存、Window10)上运行基于半边折叠算法的三维模型简化算法。简化对象为bunny.obj的三维模型文件。

6.2 实验及结果分析

从图6可以看出，两种算法简化率达到85%之后，兔子的眼睛、耳朵等特征就开始明显失真，当达到95%时，基本就不清晰了，但是本文算法与QEM算法相比较，特征部位的三角网格明显较为密集。由此可见，本文算法能较好的反映原模型的特征，保证模型显示的质量。

图6 模型简化对比

7 结论

本文主要研究Web环境下机械产品三维模型显示的简化算法。在OBJ文件数据规范化处理的基础上，利用半边折叠算法进一步优化，以顶点领域三角形平均面积、顶点领域三角形的法向量变化以及折叠边的边长，计算折叠代价，通过对折叠代价排序与预先设定阙值进行简化处理，减少模型的三角面片数量，较好的提升了机械产品三维模型在线浏览的流畅性，保证了机械产品三维模型的视觉效果，后续研究重点是对算法的进一步改进和完善。