面向三维模型轻量化的自私羊群优化算法研究

朱惠娟，王永利，陈琳琳

1.南京理工大学紫金学院 计算机学院，南京210046

2.南京理工大学 计算机科学与工程学院，南京210094

1 引言

20世纪70年代中期，虚拟仿真技术[1]开始逐渐扩展到民用领域[2]。从最初的静态仿真模型展示，到如今人机交互、数据可视化于一体，仿真技术在各行业的应用越来越广泛。航空类的仿真培训系统、BIM建筑生命周期的管理平台、制造智能仿真系统等，都在研究如何将仿真技术更好地与行业需求相结合[3]。这些仿真系统的三维场景结构复杂、数据量大，对真实性要求高，渲染时间长。目前大多数场景仍然是纯手动生成阶段，大量重复劳动、效率低，往往花了大量的人力与时间，也得不到满意的效果，时常出现延时、丢帧、卡顿的现象，直接影响用户体验[4]。针对此问题，学者们纷纷提出模型轻量化的想法。

模型轻量化可以极大程度减少重复模型、多余的边和面，缩短渲染时间，降低对处理器计算能力的要求，降低传输成本[5]。以BIM为例，BIM是“建筑信息模型”的简称，是在建筑行业的一项新技术。BIM的核心是通过建立虚拟的建筑工程三维模型，利用数字化技术，为用户提供完整的数据模型[6]。由于模型链接模式比较复杂，中心模型拥有庞大的数据信息，对计算机硬件要求较高，因此进入BIM2.0阶段以来，加大了对BIM轻量化的研究，以此提高系统的运行速度、降低使用成本[7]。

本文以3D模型点、面数量最小为优化目标，采用自私羊群优化算法对模型进行轻量化设计，通过随机生成捕食者，为每个体分配生存值，得到羊群领袖和猎物的位置，从而删减不必要的点和面，经过多次迭代，实现模型的最优处理。为了验证算法的优化效果，在确保三维数据准确性的基础上，根据模型冗余的类型，基于3DMax脚本语言MAXScript对三维模型进行轻量化处理，实验证明，该算法收敛速度快，收敛精度高，稳定性强，可以智能减少场景的数据量、加快模型的优化速度、减少工作量，同时缓解计算机处理的压力。

2 相关工作

文献[8]通过点云降噪处理、逆向建模、构建合并和复杂构建减面的传统方法处理碎片化点云模型，减少模型个数和面数，这样做虽然模型体量变小，但是真实感也同时降低。文献[9]通过对三维模型的非结构化几何信息进行提取，采用压缩简化算法进行优化处理，提取标准化的标注、属性和检测等各类信息，同时对曲线、曲面压缩处理，最终得到数据量低的轻量化模型。文献[10]以基于IFC的进度资源信息模型为基础，通过分析IFC模型与离散时间仿真模型的异同，实现IFC模型向仿真模型的自动转换。

目前，物体建模的常用方法有通过三维软件建模、使用三维扫描仪器建模[11]。市场上有很多优秀的建模软件，较为知名常用的是3Dmax软件。3DMax中有一些基本的几何元素，比如立方体、圆柱体等，可以通过一系列几何操作，比如平移、布尔运算等进行模型的构建。实际工程应用中，大多数的建模方法是手动减面，耗时耗力，本文提出采用3DMax内置的脚本语言MAXScript进行批量减面，可以有效减少优化时间。

MAXScript[12]是3DMax内置编程语言，基于OpenGL和VC编制，可以调用3DMax的大多数功能，通过一个开放式界面自定义和编写。文献[13]在构建三维城市时，应用MAXScript对3DMAX对象进行开发，证明MAXScript在三维构建中有较好的适用性。文献[14]运用MAXScript生成了一个立体构成插件用于立体构成课程教学中。利用MAXScript可以快速实现传统模型优化过程中的大量操作[15]。

由于基于群体智能优化的方法可避免3D模型变量依赖于形状参数信息，且具有优化效率高，模型求解简单易行，便于实际工程应用等优点。众所周知，国内外尚未有利用群体智能优化算法解决3D模型轻量化问题的研究工作出现。Selfish Herd Optimizer（SHO）是一种新提出的群体智能优化算法，该算法主要模拟羊群受到捕食者攻击时的自私行为（尽量聚集到牧群中心远离捕食者），它具有易于理解和实施的特点。

3 基于自私羊群优化的大场景3D仿真模型轻量化方法

三维模型由网格和纹理构成。网格是通过物体中的点云而形成的，点云包括空间坐标信息、光线反射强度以及颜色信息，三维网格就是通过点到线、线到面、再由面构建成三维物体。越复杂的三维场景，需要点和面的数量就越多，当模型的精细复杂度达到一定程度，就会给CPU和显卡带来很大的负担，造成系统严重的卡顿甚至渲染报错现象。因此，在设计和规划场景时，要充分考虑到现实的需求，删除不需要的点和面，开展模型优化工作。

3.1 三维仿真模型轻量化问题及自私羊群优化形式化描述

本节首先形式化描述3D仿真模型轻量化问题，利用智能优化的3D仿真模型轻量化问题或数学模型可描述为：以3D仿真生成的点、面个数最小为优化目标，即：

3.2 基于自私羊群的3D仿真模型轻量化算法描述

自私羊群优化SHO算法是由Fausto于2017年提出的元启发式算法[16]，它主要基于汉密尔顿[17]提出的自私群理论来模拟猎物与捕食者之间的狩猎关系。当群体中的个体受到捕食者的攻击时，为了增加生存机会，群体中的个体产生聚集行为，个体更有可能移动到相对安全的位置（群体的中心位置），并且群体的边缘个体更容易受到攻击，这也导致群体的边缘个体逃离群体，以增加他们被捕食者攻击时的生存机会。该方法假设整个平原是一个解空间，该算法包含两个不同的搜索因子：被狩猎群和狩猎群。每个搜索因子通过一组不同的进化算子指导算法的计算，以便更好地模拟猎物与捕食者关系之间的关系。

（1）初始化种群个体

假设自私羊群体优化算法的群体集合是S，它包含N个种群个体，本文中个体对应三维网络中的面和点。种群中的每一个体被定义为Si=(si,1,si,2,…,si,n)，其代表个体在种群中的位置信息，n代表解决方案的大小（设计面总数）。整个种群组的初始化公式如下：

其中xlowj和xhighj 分别表示解空间的下限和上限。算法参数值的范围：i=1,2,…,N和j=1,2,…,n。rand()表示随机函数，生成值的范围落在区间[0，1]内。

在自私羊群优化算法中，整个种群S被分为两个子群：H和P(S=H∪P)，H(H=h1,h2,…,hNh)代表一群猎物，P(P=p1,p2,…,pNp)代表一群捕食者。在自然界中，猎物的数量通常多于捕食者的数量。在SHO中，猎物(Nh)的数量占总个体的70%～90%(N)，其余的个体被认为是捕食者(Np)。Nh和Np按以下公式计算：

其中，rand()表示一个随机数，其值范围为0.7到0.9，而floor(·)表示将实数转换为整数的函数。

整个过程都在不断优化点和面，任何形状的图形，捕食者都会遍历所有猎物的信息，因此，三维网格不分模型形状，将随机生成猎物和捕食者。

（2）分配生存价值

在SHO中，为整个种群(S)的每个体(si)分配一个生存值(SVsi)，其代表个体的生存能力，有机会在攻击中生存或成功杀死攻击中的猎物。生存价值的数学公式定义如下：

其中，f(·)代表目标函数，fbest和fworst分别代表目标函数的最佳值和最差值。对70%～90%的猎物计算生存价值，生存价值最高的为猎物领袖，生存价值越低的为最容易被捕获的猎物。

（3）算法的结构

基于SHO的3D模型轻量化算法的结构主要包括四个方面：①猎物（被捕食者）领袖的运动；②猎物追随者的跟随运动或逃脱运动；③捕食者的狩猎运动；④捕食阶段和恢复阶段。

①猎物领袖的运动

猎物的领导者被定义为猎物种群中最大的生存价值。

定义公式如下：

猎物领袖的位置更新如下：

α代表区间[0，1]之间的随机数，α越大，位置更新越快，捕获的猎物越多；α越小，捕获的猎物越少。φ代表个体之间的吸引力，pM代表猎物的相对危险位置，φ与pM定义如下：

②猎物追随者的跟随运动或逃脱运动

在猎物种群中，猎物追随者分为跟随猎物(HF)和逃生猎物(HD)，跟随猎物又分为优势猎物(Hd)和下属猎物(Hs)。

HF，HD，Hd与Hs定义如下：

其中SVhu代表猎物生存价值的平均值，定义如下：

跟随猎物的位置更新公式如下：

其中，β，γ和δ表示区间[0，1]内的随机数形式，hci表示局部最优个体，hM表示猎物的相对安全位置，其定义如下：

其中ri,j代表猎物个体之间的欧几里德距离。逃生猎物的位置更新公式如下：

其中，xbest表示全局最优位置，β和γ表示在区间[0，1]内的随机数，β表示距离猎物领袖位置，β越小，表示距离越近；γ表示控制随机偏移值的长短，γ越小，表示偏移值越小。ε表示空间解中的随机方向。

③捕食者的狩猎运动

在捕食者种群中，捕食者的位置更新公式如下：

其中，ρ代表区间[0，1]之间的随机数，ρ值越大，位置更新越远，越容易忽略猎物。hr是基于捕食概率从猎物种群中随机选择的猎物，捕食概率(θpi,hj)定义如下：

ωpi,hj表示捕食者和猎物之间的吸引力，吸引力的数学公式定义如下：

其中||pi-hj||2代表pi和hj之间的欧几里德距离。

④捕食阶段和恢复阶段

捕食阶段：每个猎物都有一个危险的区域，如果它属于这个领域，很可能被捕食者捕杀。危险域通常是一个圆，其半径定义为：

危险区域的猎物收集定义如下：

猎物在危险区域被猎杀的概率定义如下：

恢复阶段：在SHO中，被捕食者猎杀的所有猎物都将被新生的猎物所取代，新的猎物将通过交配操作产生，SHO通过交配概率选择交配猎物，其定义如下：

其中M代表一群没有被捕食者捕杀的猎物集，交配操作定义如下：

函数mix(·)用于从不同个体(s=r1,r2,…,rn)中选择维度组件。基于SHO的模型轻量化算法3DL-SHO如算法1所示：

算法1基于SHO的模型轻量化算法

1.Input 3D模型网络向量Si=(si,1,si,2,…,si,n)

2.Begin

3.利用公式（1）初始化所有个体S

4.定义羊群成员和捕食者的个数，利用公式（2）、（3）并将S分为两组：H与P

5.For entire S do

6.利用公式（6）计算生存值

7.End For

8.While（t＜Max number of iterations）

9.执行自私羊群移动操作

10. For each selfish herd

11. IF leader of the herd

12. 利用公式（8）为羊群领袖更新位置

13. Else

14. 利用公式（6）和（19）更新羊群跟随或逃离运动

15. End IF

16. End For

17.捕食者移动操作

18. For each predators

19. For each selfish herd

20. 利用公式（21）计算追逐概率

21. End For

22. 利用公式（20）更新捕食者位置

23. End For

24.利用公式（6）重新计算H和P中每个成员的生存值

25.利用公式（23）计算危险域半径R

26.利用公式（24）、（25）执行捕食阶段

27.利用公式（26）、（27）执行恢复阶段

28. t=t+1

29.End while

30.返回羊群领导者位置

31.Output点、面最优值

32.End

表1 实验中用到的测试函数

3DL-SHO运行中对模型优化的几个启发式原则包括：

（1）采用Polygon多边形建模方法，根据需要配合网格平滑生成曲面，制作出各种形状的三维物体。

（2）运用单面建模与多边形建模相配合，重点构建视觉范围内看到的模型，不在视觉范围内的模型可以适当减少模型面片。

（3）如果网格模型的面数减少对模型的轮廓没有影响，这些面就可以删除，或者用贴图来代替。

（4）贴图的大小直接影响显卡的处理速度，在达到显示效果的情况下，选用更少的材质、低分辨率的贴图。对于规则的模型，可以通过分析建筑模型网格生成的特征，生成网格遍历条件，利用MAXScript脚本语言，循环简化场景表面的细节，从而使场景的模型面数大大精简，最终实现轻量化的目标；对于不规则的模型，也就是包含了大量位置错乱的点、面时，可以通过删除错误的面，同时根据模型生成算法，在保持原有数据不变的情况下智能生成新模型，以替代旧模型的方式，从而达到优化的目的。

4 仿真与性能测试

4.1 自私羊群优化算法性能测试

为了验证基于自私羊群优化的3D模型轻量化方法性能，使用5个基准函数进行测试，该算法将与乌鸦搜索算法（记为3DL-CSA）[18]，粒子群优化[19]（记为3DL-PSO）进行比较，所有基准函数和算法的具体参数均参考文献[16]。所有算法的种群大小(N)设置为50个个体，最大迭代次数设置为1 000(T)[20]。实验中，所用机器配置是CPU是i7 4710，主频是2.5 GHz，970显卡，16 GB内存。基准函数如表1所示，实验数据如表2所示。

表2给出了实验结果，其中“f”代表基准函数，“BV”、“MV”和“SD”分别代表最佳解决方案的最佳值、平均值和标准偏差。

从表2可以看出，对于函数f1，3DL-SHO的平均值的准确度分别比其他两种算法的次优解高16和14个数量级，对于函数f2、f3和f4，3DL-SHO的平均值的准确度分别比3DL-CSA的次优解决方案高14、16和5个数量级。与3DL-PSO算法相比，平均值的准确度分别增加了7、8和1个数量级。

表2 算法优化实验结果

对于函数f5，3DL-SHO的平均值的准确度分别比3DL-CSA和3DL-PSO的次优解高13个数量级。在功能上，3DL-CSA的平均值的准确度最好，平均值为-3.99E+03。3DL-SHO的平均值为-1.25E+03，与3DL-PSO相比，平均值的准确度增加了1个数量级。从上述实验数据可以看出，所提出的算法与原算法和其他算法相比，对函数解的精度有很大的提高。

本文同时也测试了算法对应这几个基准函数的收敛图和标准方差图，通过结构的分析来评估所提方法的性能。该算法的收敛速度最快，具有很强的稳定性和最高的求解精度。可以看到所提算法的收敛速度和精度在第100次迭代后已经超过了其他算法。

PSO的收敛速度和精度稍微接近所提出的算法，但在迭代终止之前，其性能不超过所提出的算法。从上述实验数据和图片可以看出，与其他算法相比，3DLSHO该算法的性能在解决函数优化问题上具有很大的优势。该算法收敛速度快，收敛精度高，稳定性好。

为了验证本文提出的3D模型轻量化方法在实际应用中的效果，本文构建了两组3D模型仿真实验，分别对应最常见的两种3D模型冗余情况。

4.2 无规则的点、面冗余去除实验

无规则的点、面冗余，指的是模型有大量位置错乱的点和面，不但使模型体积变大，也影响了模型的UV展开和烘焙。如果直接把Revit模型导入交互引擎中，会出现不能贴图等问题，因此要将模型先导入3Dmax或类似的三维建模软件中优化。但是当把Revit模型导入3DMax中时，又会出现大量位置错误的点和面。如图1所示，尤其以圆柱体的模型，比如管线、弯头出现这样的现象最多。

图1 BIM模型

本文使用3DL-SHO智能方法解决此问题，主要思想是遍历待优化的模型，获得模型的位置等数据信息，根据模型生成的逻辑方式，调用3DL-SHO算法，自动在原位置上生成新的模型，并替代旧模型。

实验模型如图1所示，来自BIM房屋系统8层楼，用Revit建模，模型大小为10.7 MB，场景面数为122 224，顶点为70 576。每一层楼的内部空间如图2所示。

图2 内部模型

将场景导入3DMAX后，管线处生成了大量位置错误的点和面，如图3和图4所示，导入前是圆形，导入后，变成了正八边形。

实验操作如下：

图3导入3DMAX前

图4导入3DMAX后

（1）计算管线两底面的高度；（2）获取底面直径；（3）设定分段数；（4）调用3DLSHO算法，生成新管线替代旧管线。

优化之前，不规则的点、面，不适合展UV展开贴图，如图5所示；优化后，方便展UV贴图，在UV展开后输入了“消防水管”贴图，效果如图6所示。

图5优化前的UV

图6优化后的UV

从实验中看出，这种以机器建模替代旧模型的优化方式是根据模型的特征计算机出新的模型，同时不会改变模型的坐标等信息，比较好地保留了主要数据。如果手动在原模型上修改，重复工作量巨大；如果手动完全重新构建，就很难保证模型坐标的正确。实验前后对比数据如表3所示。

表3 优化前后对比数据

4.3 有规则的点、面冗余去除实验

有规则的点、面冗余，指的是多余的点、面有规律可循，但手动删除，仍然要花费大量的人力，本实验的主要思想是遍历所有待优化的模型，依次选择所有的点，自动进行优化操作。实验模型如图7所示，模型是一个水电厂的消防装置，面数为14 660、点数为43 980，模型的顶点都是离散的，不但占内存，也不方便贴图。如果手动焊接，工作量很大。

本实验将通过自动焊接，完成每个模型点的焊接，有规则的点面冗余去除优化步骤：

图7 消防装置

（1）根据条件遍历模型，转换成可编辑多边形；（2）在点的模式下，选择所有点；（3）调用3DLSHO算法，生成焊接的值，进行点的焊接；（4）进行平滑操作。

通过批量焊接点，顶点由43 980，优化到了7 730，对贴图效果有了大大的改进，如图8和图9所示。

图8优化前的UV

图9 优化后的UV

综上所述，本文所提方法在不影响显示效果的情况下，可以对模型有大量的优化，同时计算过程简单，占用内存空间较少。

5 结束语

综上所述，为了降低计算机的硬件负荷，在不影响仿真模型真实感的前提下，应当对数字化模型进行优化。针对当前优化方法不多的情况，提出了一种基于自私羊群智能优化的三维仿真模型轻量化方法，由于模型出现的问题都不相同，本文选用最有代表性的两类问题，分别是大量重复的规则的点、面以及不规则的点、面，以智能化构建新模型以及修改原模型两种解决方案，均实现了优化效果。研究结果证明，只要根据模型的特点，所提出的方法能快速优化模型，且实现过程较简单。