下载文档原格式
点云常⽤分割⽅法点云分割 点云分割可谓点云处理的精髓，也是三维图像相对⼆维图像最⼤优势的体现。
点云分割的⽬的是提取点云中的不同物体，从⽽实现分⽽治之，突出重点，单独处理的⽬的。
⽽在现实点云数据中，往往对场景中的物体有⼀定先验知识。
⽐如：桌⾯墙⾯多半是⼤平⾯，桌上的罐⼦应该是圆柱体，长⽅体的盒⼦可能是⽜奶盒......对于复杂场景中的物体，其⼏何外形可以归结于简单的⼏何形状。
这为分割带来了巨⼤的便利，因为简单⼏何形状是可以⽤⽅程来描述的，或者说，可以⽤有限的参数来描述复杂的物体。
⽽⽅程则代表的物体的拓扑抽象。
于是，RanSaC算法可以很好的将此类物体分割出来。
1、RanSaC算法 RanSaC算法（随机采样⼀致）原本是⽤于数据处理的⼀种经典算法，其作⽤是在⼤量噪声情况下，提取物体中特定的成分。
下图是对RanSaC算法效果的说明。
图中有⼀些点显然是满⾜某条直线的，另外有⼀团点是纯噪声。
⽬的是在⼤量噪声的情况下找到直线⽅程，此时噪声数据量是直线的3倍。
如果⽤最⼩⼆乘法是⽆法得到这样的效果的，直线⼤约会在图中直线偏上⼀点。
关于随机采样⼀致性算法的原理参考博客： 这个算法就是从⼀堆数据⾥挑出⾃⼰最⼼仪的数据。
所谓⼼仪当然是有个标准（⽬标的形式:满⾜直线⽅程？满⾜圆⽅程？以及能容忍的误差e）。
平⾯中确定⼀条直线需要2点，确定⼀个圆则需要3点。
1. 平⾯中随机找两个点，拟合⼀条直线，并计算在容忍误差e中有多少点满⾜这条直线2. 重新随机选两点，拟合直线，看看这条直线是不是能容忍更多的点，如果是则记此直线为结果3. 重复步骤⼆（循环迭代）4. 迭代结束，记录当前结果算法的优点是噪声可以分布的任意⼴，噪声可以远⼤于模型信息。
这个算法有两个缺点，第⼀，必须先指定⼀个合适的容忍误差e。
第⼆，必须指定迭代次数作为收敛条件。
综合以上特性，本算法⾮常适合从杂乱点云中检测某些具有特殊外形的物体。
PCL中基于RanSaC的点云分割⽅法：1. //创建⼀个模型参数对象，⽤于记录结果2. pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients);3. //inliers表⽰误差能容忍的点记录的是点云的序号4. pcl::PointIndices::Ptr inliers (new pcl::PointIndices);5. // 创建⼀个分割器6. pcl::SACSegmentation<pcl::PointXYZ> seg;7. // Optional8. seg.setOptimizeCoefficients (true);9. // Mandatory-设置⽬标⼏何形状0. seg.setModelType (pcl::SACMODEL_PLANE);1. //分割⽅法：随机采样法2. seg.setMethodType (pcl::SAC_RANSAC);3. //设置误差容忍范围4. seg.setDistanceThreshold (0.01);5. //输⼊点云6. seg.setInputCloud (cloud);7. //分割点云8. seg.segment (*inliers, *coefficients);除了平⾯以外，PCL⼏乎⽀持所有的⼏何形状。
Netgen网格划分程序采用的推进前线法算法实现步骤Netgen网格划分程序采用的推进前线法advancing front method算法方法是将具体规则与规则应用程序代码分离。
算法必须检查存储在数据结构中的规则。
因此，代码复杂度与规则的数量无关。
该算法复杂，但定义良好，至少在理论上可以实现故障保护。
特别是在3D中，具体规则的选择是基于启发式的，并将其放入一个易于维护的规则描述数据库中。
我们按以下步骤进行处理。
首先，我们描述了整个算法，接着是抽象规则描述和规则应用算法。
最后，我们集中讨论了曲面和体网格生成的扩展。
基本思路首先：建立模型，构造立体几何提供常用的基本单元：立方体圆柱椭圆球圆球长方体等等复杂的模型通过对基本单元的bool操作来建立。
（对于复杂几何模型，我们需要求解三元非线性方程组，来计算用于寻找边缘的起始点）一、求解相交点图相交点示意图求解相交点的方法采用基于几何测试的二分算法，其示意图如下图所示。
图二分法求交点示意图基于几何测试的二分算法的计算流程1 建立一个立方体，将整个几何模型包含在该立方体内2 沿立方体的八条边界的中点分别建立三个相互正交的平面，三个平面将立方体划分成八个大小相等的小立方体。
3 判断交点在哪一个小立方体内4 在该小立方体内重复第二步，第三步。
5 循环的结束条件为立方体的边长小于给定的精确度值6 求出交点的坐标位置图极坐标下中的相交点图两个相贯的圆柱二、计算边缘：使用求解非线性方程组的同伦方法进行计算跟踪曲线。
1 该方法的原理是：从曲线上一个给定的点X0开始，通过预估-矫正的方法，沿着曲线小步推进，直到到达曲线的终点。
2 方法步骤：首先从选定的初始点X0出发，沿着曲线的切向量方向其次确定相邻两点之间的递归关系假设已知当前点Xk，计算曲线在改点的单位切向量Tk，预估下一点的位置，对该点的位置进行修正，采用牛顿下山法，对于平滑曲线，有这样一个关系式，它可以用于适应性步长控制。
基于谱聚类的三维⽹格分割算法（SpectralClustering） 谱聚类（Spectral Clustering）是⼀种⼴泛使⽤的数据聚类算法，[Liu et al. 2004]基于谱聚类算法⾸次提出了⼀种三维⽹格分割⽅法。
该⽅法⾸先构建⼀个相似矩阵⽤于记录⽹格上相邻⾯⽚之间的差异性，然后计算相似矩阵的前k个特征向量，这些特征向量将⽹格⾯⽚映射到k维谱空间的单位球上，最后使⽤K-means⽅法对谱空间中的数据点进⾏聚类。
具体算法过程如下：⼀．相似矩阵 ⽹格分割以⾯⽚为基本单元，为了能使算法沿着⼏何模型的凹形区域进⾏分割，⽹格相邻⾯⽚之间的距离采⽤[Katz et al. 2003]中提到的⽅法，具体形式在“”中有所解释，距离由测地距离Geod_Dist和⾓度距离Ang_Dist两部分组成，如下所⽰： 上式中有两个重要的参数δ和η，参数δ通常取值范围为[0.01, 0.05]，其⽤于控制测地距离和⾓度距离之间的权重⽐例，参数η通常取值范围为[0.1, 0.2]，其使得分割边界更倾向于凹形区域。
计算完相邻⾯⽚之间的距离后，相似矩阵中对应位置的值由距离的⾼斯函数得到：其中：⼆．⽹格谱聚类 谱聚类⽅法在本质上都是类似的，都是利⽤相似矩阵的特征向量将原始空间中的数据映射到谱空间，并在谱空间中进⾏聚类。
⽹格上的谱聚类⽅法如下： 1 由上述定义计算相似矩阵W； 2 计算归⼀化矩阵N：N = D-1/2WD-1/2； 3 计算矩阵N的前k个最⼤特征向量e1, e2, … , e k，以这k个特征向量为列组成矩阵U = [e1, e2, … , e k]； 4 将矩阵U的每⼀⾏单位化后得到矩阵Ȗ； 5 提取出k个初始聚类中⼼⽤于K-means聚类，该过程先计算矩阵Q = ȖȖT，然后查找矩阵Q中的最⼩元素Q rs，那么r和s点就是两个距离最远的点，然后继续查找后续点； 6 以Ȗ的⾏向量为数据样本进⾏K-means聚类。
CosmosWorks网格划分、求解器、提示与技巧一、网格划分策略网格划分，更精确地说应该称为离散化，就是将一数学模型转化为有限元模型以准备求解。
作为一种有限元方法，网格划分完成两项任务。
第一，它用一离散的模型替代连续模型。
因此，网格划分将问题简化为一系列有限多个未知域，而这些未知域符合由近似数值技术的求解结果。
第二，它用一组单元各自定义的简单多项式函数来描述我们渴望得到的解(e.g位移或温度)。
对于使用者来说，网格划分是求解问题必不可少的一步。
许多FEA初学者急切盼望格划分为全自动过程而几乎不需要自己输入什么。
随着经验的增加，就会意识到这样一个现实：网格划分常常是要求非常苛刻的任务。
商用FEA软件的发展历史见证了网格划分对F EA 用户透明的诸多尝试，然它并不是一条成功的途径。
而当网格划分过程既简单又自动执行时，它也仍旧不是一个“非手工干涉”而仅靠后台运行的任务。
作为FEA用户，我们想要有一种可以和网格划分过程交互的方法。
COSMOSW orks通过将用户从那些纯粹网格细节意义上的问题中解脱出来，找到了良好的平衡点；并使我们在需要时可以控制网格划分。
几何体准备理想情况下，我们用SolidW orks的几何体，联入COSMOSWorks环境。
在这里，我们定义分析和材料的类型，施加载荷与约束，然后为几何体划分网格并得到求解。
这种方法在简单模型下能起作用。
对于更为复杂的几何体，则要求在网格划分前作些准备。
在FEA 的几何体准备过程中，我们从特定制造，CAD 几何体出发，为分析而特地构造几何体。
我们称这个几何体为FE A 几何体。
基于两者的不同要求，我们对CAD 几何体和FE A 几何体作一区别：CAD 几何体FEA几何体必须包含机械制造所需的所有信息必须可划分网格必须允许创建能正确模拟所关心资料的网格必须允许创建能在合理时间内可求解的网格通常，CAD 几何体不能满足FEA 几何体的要求。
第 3章 ANSYS 13.0 Workbench网格划分及操作案例网格是计算机辅助工程（CAE）模拟过程中不可分割的一部分。
网格直接影响到求解精 度、求解收敛性和求解速度。
此外，建立网格模型所花费的时间往往是取得 CAE 解决方案所 耗费时间中的一个重要部分。
因此，一个越好的自动化网格工具，越能得到好的解决方案。
3.1 ANSYS 13.0 Workbench 网格划分概述ANSYS 13.0 提供了强大的自动化能力，通过实用智能的默认设置简化一个新几何体的网 格初始化，从而使得网格在第一次使用时就能生成。
此外，变化参数可以得到即时更新的网 格。
ANSYS 13.0 的网格技术提供了生成网格的灵活性，可以把正确的网格用于正确的地方， 并确保在物理模型上进行精确有效的数值模拟。
网格的节点和单元参与有限元求解，ANSYS 13.0在求解开始时会自动生成默认的网格。
可以通过预览网格，检查有限元模型是否满足要求，细化网格可以使结果更精确，但是会增 加 CPU 计算时间和需要更大的存储空间，因此需要权衡计算成本和细化网格之间的矛盾。
在 理想情况下，我们所需要的网格密度是结果随着网格细化而收敛，但要注意：细化网格不能 弥补不准确的假设和错误的输入条件。
ANSYS 13.0 的网格技术通过 ANSYS Workbench的【Mesh】组件实现。
作为下一代网格 划分平台， ANSYS 13.0 的网格技术集成 ANSYS 强大的前处理功能， 集成 ICEM CFD、 TGRID、 CFXMESH、GAMBIT网格划分功能，并计划在 ANSYS 15.0 中完全整合。
【Mesh】中可以根 据不同的物理场和求解器生成网格，物理场有流场、结构场和电磁场，流场求解可采用 【Fluent】、【CFX】、【POLYFLOW】，结构场求解可以采用显式动力算法和隐式算法。
不同的 物理场对网格的要求不一样，通常流场的网格比结构场要细密得多，因此选择不同的物理场， 也会有不同的网格划分。
基于Netgen的四面体网格剖分算法及其应用魏斌;徐华【摘要】A Netgen-based tetrahedralization algorithm was proposed,which fulfilled the tetrahedralization based on complex TIN models after close,non-manifold and surface normal vector checks of TIN model through analysis of various kinds of mo-dels.No points were added on the constraint surface of TIN models in Netgen-based tetrahedralization,leading to the high con-sistency between the original surface and the tetrahedron shape,and ensuring the accuracy of the model and boundary consistency under coplanarity.A sample application in a mineral's formation data shows that the Netgen-based tetrahedralization algorithm is stable,efficient and ensures the boundary consistency and high quality of mesh.%通过对各类模型的分析和归纳,提出一种基于Netgen的四面体剖分算法,对不规则三角网(TIN)模型进行封闭性检查、非流形检查、表面法向量检查和相交性检查,实现基于TIN复杂模型的四面体剖分.进行四面体剖分时,不在模型的约束面加点,使原始曲面与四面体形状间高度吻合,确保模型精度,保证共面情况下的边界一致性.某矿地层数据的实例应用结果表明,使用该算法能够使边界一致,得到高质量网格,兼具稳定性和高效性.【期刊名称】《计算机工程与设计》【年(卷),期】2017(038)002【总页数】6页(P368-373)【关键词】四面体剖分算法;封闭性检查;非流形检查;表面法向量检查;相交性检查;边界一致性;单元质量【作者】魏斌;徐华【作者单位】北京化工大学信息科学与技术学院,北京 100029;北京石油化工学院信息工程学院,北京 102617【正文语种】中文【中图分类】TP391.41如何解决复杂模型剖分时的边界一致性和生成高质量单元是四面体剖分的难点之一。
一种基于热核的三维人体网格模型分割方法【摘要】提出了一种基于热核的三维人体模型分割方法。
首先计算三维人体模型顶点的热核签名值；然后采用阀值分割法利用设定的分割阀值对模型进行初始分割；最后对阀值分割结果中大于阀值的部分进行凝聚聚类，得到最终的分割结果。
实验结果表明，分割结果不仅符合视觉最小值原则，还具有很好的语义信息；同时分割结果具有与姿势无关和鲁棒性好的特点。
【关键词】热核签名；人体模型；模型分割；谱聚类1.引言随着三维人体扫描技术的发展，三维人体模型已经无处不在，广泛应用于人机工程、游戏、动画、服装等领域。
由于人体模型越来越精细，复杂度越来越高，为了简化人体结构的复杂性，同时更好地适用于其它应用领域的需求，通常要求将三维人体模型分割成头部、躯干、上肢和下肢等部分，为人体模型的高级表示和进一步的语义特征分析提供基础。
模型分割是形状特征分析的基础[1]。
由于人体外形受年龄、性别、姿态等的影响，人体模型的自动分割成为一个具有挑战性的问题，国内外学者对此问题进行了比较深入的研究。
Nurre等[2]应用一种六杆的棒形人体模板，通过整体几何的匹配来达到细节特征识别，进而把人体分成与模板对应的头、左臂、躯干、右臂、左腿、右腿六个功能部分；Wang等[3] 通过对水平面与人体模型相交的截面形状，应用模糊规则确定拐点位置来识别腋窝和胯特征点，然后把人体模型分割为与文献[2]相同的六部分；Werghi等[4]提出了一种基于Reeb图的三维人体分割算法。
通过选取测地距离函数作为莫尔斯函数建立Reeb图，该方法对体形、姿态等变化具有鲁棒性。
其缺点是计算量大，算法效率不高；Katz等[5]提出了一种通用的三维网格模型模糊聚类分割算法，该算法可以处理任意姿态、不同部件比例的模型，并且应用了层次分割的思想，在避免了过分割和边界锯齿的同时，能够得到不同粒度层次分割结果。
此算法应用与人体模型可以得到较好的分割结果。
本文以三维人体测量为背景，采用坐标无关、几何不变的模型特征描述子，实现一种基于热核的人体模型分割方法。
ANSYSWorkbenchMesh⽹格划分（⾃⼰总结）Workbench Mesh⽹格划分分析步骤⽹格划分⼯具平台就是为ANSYS软件的不同物理场和求解器提供相应的⽹格⽂件，Workbench中集成了很多⽹格划分软件/应⽤程序，有ICEM CFD，TGrid，CFX，GAMBIT，ANSYS Prep/Post等。
⽹格⽂件有两类：①有限元分析（FEM）的结构⽹格：结构动⼒学分析，电磁场仿真，显⽰动⼒学分析（AUTODYN，ANSYS LS DYNA）；②计算流体⼒学（CFD 分析）分析的⽹格：⽤于ANSYS CFX，ANSYS FLUENT，Polyflow；这两类⽹格的具体要求如下：（1）结构⽹格：①细化⽹格来捕捉关⼼部位的梯度，例如温度、应变能、应⼒能、位移等；②⼤部分可划分为四⾯体⽹格，但六⾯体单元仍然是⾸选；③有些显⽰有限元求解器需要六⾯体⽹格；④结构⽹格的四⾯体单元通常是⼆阶的（单元边上包含中节点）；（2）CFD⽹格：①细化⽹格来捕捉关⼼的梯度，例如速度、压⼒、温度等；②由于是流体分析，⽹格的质量和平滑度对结果的精确度⾄关重要，这导致较⼤的⽹格数量，经常数百万的单元；③⼤部分可划分为四⾯体⽹格，但六⾯体单元仍然是⾸选，流体分析中，同样的求解精度，六⾯体节点数少于四⾯体⽹格的⼀半。
④CFD⽹格的四⾯体单元通常是⼀阶的（单元边上不包含中节点）⼀般⽽⾔，针对不同分析类型有不同的⽹格划分要求：①结构分析：使⽤⾼阶单元划分较为粗糙的⽹格；②CFD：好的，平滑过渡的⽹格，边界层转化（不同CFD 求解器也有不同的要求）；③显⽰动⼒学分析：需要均匀尺⼨的⽹格；注：上⾯的⼏项分别对应Advanced中的Element Midside Nodes，以及Sizeing中的Relevance Center，Smoothing，Transition。
⽹格划分的⽬的是对CFD (流体) 和FEM (结构) 模型实现离散化，把求解域分解成可得到精确解的适当数量的单元。
基于凹凸性方法的杂乱场景点云分割算法黄镇;韩慧妍;韩燮【摘要】为了处理杂乱场景中多个物体的分割问题,提出了一种基于RGB-D点云数据的分割方法;该方法先将场景点云超体聚类分解为基于体素网格的邻接图,然后对邻接图的边缘进行分类创建凸度图,再通过区域生长合并具有凸关系的分块从而得到未知物体.此外,提出用欧几里得算法对区域生长进行改进,发现对于碗和杯子这类具有内部凹面的物体有较好地分割效果.在对象分割数据库和手动提取场景中的实验结果,表明该方法可以在杂乱的桌面场景中分割各种形状的对象.%In order to deal with the problem of segmentation of multiple objects in clutter scene , a segmentation method based on RGB-D point cloud data was proposed .The method firstly decomposed the scene cloud superclass cluster into the adjacency graph based on the voxel mesh , then classified the edge of the adjacent graph to create the convexity graph , and then merged the convexity with the convexity through the regional growth to get the un-known object .In addition , it was proposed to improve the regional growth with the Euclidean algorithm and found that the objects with internal concave surfaces such as bowl and cup had a better segmentation effect .The results in the object segmentation database and the manual extraction of the scene indicate that the method can segment ob -jects of various shapes in cluttered desktop scenes .【期刊名称】《科学技术与工程》【年(卷),期】2018(018)014【总页数】5页(P43-47)【关键词】计算机视觉;超体聚类;凹凸性;欧几里得;点云分割【作者】黄镇;韩慧妍;韩燮【作者单位】中北大学大数据学院,太原030051;中北大学大数据学院,太原030051;中北大学大数据学院,太原030051【正文语种】中文【中图分类】TP391.41尽管进行了很长时间的研究，将场景分割成物体仍是计算机视觉中比较有挑战性的课题之一[1]。
有限元网格剖分方法概述在采用有限元法进行结构分析时，首先必须对结构进行离散，形成有限元网格，并给出与此网格相应的各种信息，如单元信息、节点坐标、材料信息、约束信息和荷载信息等等，是一项十分复杂、艰巨的工作。
如果采用人工方法离散对象和处理计算结果，势必费力、费时且极易出错，尤其当分析模型复杂时，采用人工方法甚至很难进行，这将严重影响高级有限元分析程序的推广和使用。
因此，开展自动离散对象及结果的计算机可视化显示的研究是一项重要而紧迫的任务。
有限元网格生成技术发展到现在, 已经出现了大量的不同实现方法，列举如下：1．映射法映射法是一种半自动网格生成方法，根据映射函数的不同，主要可分为超限映射和等参映射。
因前一种映射在几何逼近精度上比后一种高，故被广泛采用。
映射法的基本思想是：在简单区域内采用某种映射函数构造简单区域的边界点和内点，并按某种规则连接结点构成网格单元。
也就是根据形体边界的参数方程，利用映射函数，把参数空间内单元正方形或单元三角形(对于三维问题是单元立方体或单元四面体)的网格映射到欧氏空间，从而生成实际的网格。
这种方法的主要步骤是，首先人为地把分析域分成一个个简单可映射的子域，每个子域为三角形或四边形，然后根据网格密度的需要，定义每个子域边界上的节点数，再根据这些信息，利用映射函数划分网格。
这种网格控制机理有以下几个缺点：（1）它不是完全面向几何特征的，很难完成自动化，尤其是对于3D区域。
（2）它是通过低维点来生成高维单元。
例如，在2D问题中，先定义映射边界上的点数，然后形成平面单元。
这对于单元的定位，尤其是对于远离映射边界的单元的定位，是十分困难的，使得对局部的控制能力下降。
（3）各映射块之间的网格密度相互影响程度很大。
也就是说，改变某一映射块的网格密度，其它各映射块的网格都要做相应的调整。
其优点是：由于概念明确，方法简单，单元性能较好，对规则均一的区域，适用性很强，因此得到了较大的发展，并在一些商用软件如ANSYS等得到应用。
C o n t i n u u m S t r u c t u r e [J ].J o u r n a lo f N o r t h e a s t e r U n i v e r s i t y,2011,32(9):1303‐1309.[12] 李景奎,张义民.非正态分布连续体结构可靠性拓扑优化设计[J ].机械工程学报,2012,48(3):153‐158,L i J i n g k u i ,Z h a n g Y i m i n .T h eR e l i a b i l i t y ‐b a s e dT o p o l o -g y O p t i m i z a t i o nD e s i g no fC o n t i n u u m S t r u c t u r ew i t h A b n o r m a l D i s t r i b u t i o n [J ].J o u r n a l o fM e c h a n i c a lE n g i -n e e r i n g,2012,48(3):153‐158.[13] 李好.基于变密度法的连续体结构拓扑优化方法研究[D ].武汉:华中科技大学,2011.[14] C h w a i lK ,S e m y u n g W.R e l i a b i l i t y ‐b a s e dT o p o l o g y O p -t i m i z a t i o nw i t hU n c e r t a i n t i e s [J ].J o u r n a l o fM e c h a n i c a lS c i e n c e a n dT e c h n o l o g y ,2006,20(4):494‐504.[15] M a u t eK ,F r a n g o p o lD M.R e l i a b i l i t y ‐b a s e dD e s i gno f M E M S M e c h a n i s m sb y T o p o l o g y O pt i m i z a t i o n [J ].C o m pu t e r s a n dS t r u c t u r e s ,2003,81(8):813‐824.[16] S e u n g J H ,S e o n h oC .R e l i a b i l i t y ‐b a s e d T o p o l o g yO p t i m i z a t i o n o f G e o m e t r i c a l l y N o n l i n e a r S t r u c -t u r e sw i t hL o a d i n g a n d M a t e r i a lU n c e r t a i n t i e s [J ].F i n i t e E l e m e n t si n A n a l y s i s a n d D e s i gn ,2004,41(3):311‐331.[17] Z h a n g B i n ,W a n g XJ ,S u nX Y.S t r u c t u r a lT o p o l o -g y O p t i m i z a t i o nC o n s i d e r i n g S t r e s sa n dR e l i a b i l i t y C o n s t r a i n t s [J ].M e t a l u r g i a I n t e r n a t i o n a l ,2014,ⅪⅩ(2):59‐63.(编辑 苏卫国)作者简介:吴劲松,男,1989年生㊂江苏理工学院机械工程学院硕士研究生㊂研究方向为先进再制造技术与装备㊂周金宇,男,1973年生㊂江苏理工学院机械工程学院教授㊁博士㊁硕士研究生导师㊂基于网格支配的微型多目标遗传算法符纯明 姜 潮 刘桂萍 邓善良湖南大学汽车车身先进设计制造国家重点实验室,长沙,410082摘要:提出了一种基于网格支配的微型多目标遗传算法,该算法在求解较多目标函数的优化问题时具有较好的收敛性和较高的计算效率㊂该算法引入网格支配概念并结合微型多目标遗传算法,在每一代进化种群中计算各个个体的网格值㊁网格拥挤距离和网格坐标点距离,根据网格支配分级和网格选择机制策略选取精英个体,并对其进行交叉和变异操作,使其朝前沿面收敛以获得P a r e t o 最优解㊂4个测试函数和2个工程实例验证了该算法的有效性㊂关键词:多目标遗传算法;网格支配;微型种群;P a r e t o 最优解;耐撞性中图分类号:T P 18 D O I :10.3969/j.i s s n .1004132X.2015.16.014M i c r oM u l t i ‐o b j e c t i v eG e n e t i cA l go r i t h mB a s e do nG r i dD o m i n a t i o n F uC h u n m i n g J i a n g C h a o L i uG u i p i n g D e n g S h a n l i a n gS t a t eK e y L a b o r a t o r y o fA d v a n c e dD e s i g n a n dM a n u f a c t u r i n g f o rV e h i c l e B o d y ,H u n a nU n i v e r s i t y ,C h a n gs h a ,410082A b s t r a c t :A m i c r om u l t i ‐o b j e c t i v e g e n e t i c a l g o r i t h m w a s p r o po s e d h e r e i nb a s e d o n g r i d d o m i n a t i o n t o s o l v em u l t i ‐o b j e c t i v e o p t i m i z a t i o n p r o b l e m s a n d i t h a d g o o d c o n v e r g e n c e a n d h i g h c o m p u t a t i o n a l e f -f i c i e n c y .T h em e t h o d c o m b i n e dw i t h t h e c o n c e p t o f t h e g r i dd o m i n a n c e a n dm i c r om u l t i ‐o b j e c t i v e g e -n e t i c a l g o r i t h m.I ne a c h g e n e r a t i o n ,t h e g r i dv a l u e ,t h e g r i dc r o w d i n g di s t a n c ea n d g r i dc o o r d i n a t e p o i n t d i s t a n c e o f e v e r y i n d i v i d u a l w e r e c a l c u l a t e d ,r e s p e c t i v e l y.T h e n e l i t e i n d i v i d u a l sw e r e s e l e c t e d t o d oc r o s s o v e ra n d m u t a t i o no p e r a t o r sb a s e do nt h e g r i dd o m i n a t i o ns o r t i n g a n d g r i ds e l e c t i o ns t r a t e -g i e s .T h e i n d i v i d u a l sw e r e i t e r a t e d t o w a r d t h eP a r e t o f r o n t a n d t h eP a r e t o o p t i m a l s o l u t i o n sw e r e o b -t a i n e d .F i n a l l y ,t h e p r o p o s e da l g o r i t h m w a sv e r i f i e de f f e c t i v e l y t h r o u ghf o u r t e s t f u n c t i o n sa n dt w o p r a c t i c a l e n g i n e e r i n gpr o b l e m s .K e y wo r d s :m u l t i ‐o b j e c t i v e g e n e t i c a l g o r i t h m ;g r i dd o m i n a t i o n ;m i c r o p o p u l a t i o n ;P a r e t oo p t i m a l s o l u t i o n ;c r a s h w o r t h i n e s s0 引言在实际工程设计中,经常遇到多目标优化问收稿日期:20140605基金项目:国家自然科学基金资助项目(11172096);国家自然科学基金优秀青年基金资助项目(51222502);教育部新世纪优秀人才支持计划资助项目(N C E T ‐11‐0124);湖南省杰出青年基金资助项目(14J J 1016)题(m u l t i‐o b j e c t i v e o pt i m i z a t i o n p r o b l e m ,MO P ),如汽车正面碰撞的结构优化设计中,轻量化与最大吸能为两目标优化问题,两者难以同时达到最优,只能获得一组无法进行简单比较的P a r e t o 解㊂多目标遗传算法可在无需考虑目标函数和约束函数满足连续性和可导性的条件下,对线性或者非线性目标函数进行有效求解,因而引㊃8022㊃中国机械工程第26卷第16期2015年8月下半月Copyright ©博看网. All Rights Reserved.起了众多学者的关注,并被广泛应用于求解实际工程问题[1‐3]㊂S c h a f f e r[4]1985年提出了向量评估遗传算法(v e c t o r e v a l u a t e d g e n e t i c a l g o r i t h m, V E G A),用于解决机器学习的多目标问题㊂随后,一系列的多目标遗传算法被提出和发展,其中以D e b等[5]的N S G A‐Ⅱ(n o n‐d o m i n a t e ds o r t i n g G A‐Ⅱ)算法和Z i t z l e r等[6]的S P E A2(s t r e n g t h P a r e t oE A2)算法应用最为广泛㊂在汽车碰撞安全性设计中,谢然等[7]将N S G A‐Ⅱ算法用于40%的偏置正面碰撞中,在满足6σ可靠性㊁扭转刚度和质量要求的约束条件下,提高了整车的碰撞安全性能㊂为提高计算效率,刘桂萍等[8‐10]将微型遗传算法(m i c r o g e n e t i c a l g o r i t h m,μG A)[11]引入多目标优化问题中,提出了微型多目标遗传算法(m i c r om u l t i‐o b j e c t i v eG A,μMO G A),该算法在计算效率㊁解的均匀性和工程实用性等方面具有较好的综合性能㊂Y a n g等[12]提出了基于网格支配的进化算法(g r i d‐b a s e d e v o l u t i o n a r y a l g o-r i t h m,G r E A),利用网格能同时反映收敛性和多样性的特点,使得个体朝着P a r e t o最优解方向迭代㊂本文在微型多目标遗传算法μMO G A的基础上结合网格支配的概念,提出了一种具有网格属性的多目标遗传算法G r‐μMO G A(μMO G A b a s e do n g r i dd o m i n a t i o n),与现有方法相比,该算法在求解较多目标函数问题时具有较好的收敛性和均匀性,并提高了计算效率㊂1 多目标优化相关概念多目标优化广泛存在于实际工程中,其优化目标函数之间可能不一致甚至相互冲突,因此难以获得一个类似于单目标的最优解,而只能获得一组无法进行简单比较的P a r e t o最优解㊂一般的MO P被定义为[13]m i n f k(x) k=1,2, ,ms.t.g i(x)≤0 i=1,2, ,ph j(x)=0 j=1,2, ,qx L≤x≤x U,x=(x1,x2, ,x n)üþýïïïïT(1)式中,f k(x)㊁g i(x)和h j(x)分别为目标函数㊁不等式约束函数和等式约束函数;m㊁p和q分别为目标函数㊁不等式约束和等式约束函数的个数;x㊁x L和x U分别为优化变量㊁优化变量的下界和上界㊂P a r e t o最优解的定义为[13]:设S⊆R n为MO P的可行域,f(x)∈R m为MO P的目标空间,若有~x∈S且不存在x∈S使得f k(x)≤f k(~x),则称~x为MO P的P a r e t o最优解㊂个体x P a r e t o支配个体y(记为x≺P y)定义为∀i∈(1,2, ,m):f i(x)≤f i(y)且∃j∈(1,2, ,m):f j(x)<f j(y)2 G r‐μMO G A算法及构造现有的多目标优化方法大都是针对二维目标函数问题,而对于较多目标函数问题通常难以获得较好的P a r e t o解㊂为此,本文构建一种新的基于网格支配的微型多目标遗传算法G r‐μMO G A,用于求解较多目标函数的一类实际工程多目标设计问题㊂网格支配在文献[12,14]被提出,通过该方法可保证较多目标函数下P a r e t o解集的计算精度;μMO G A算法由刘桂萍等[9]提出,通过小种群和重启动策略可有效保证多目标优化的计算效率㊂本文提出的G r‐μMO G A算法在求解较多目标函数问题时,将兼具精度和效率的双重优点㊂2.1 网格的概念及相关参数定义将各个个体划分在不同的网格内,从而通过网格值的大小决定个体是否继续进行遗传操作㊂图1所示为进化种群P在第k个目标函数的网格值,种群P在第k个目标函数的最大值和最小值分别记为f k m a x(P)和f k m i n(P)㊂将第k个目标空间根据函数值划分成D k个子空间,则第k个目标函数值的最小值和最大值b L k和b U k分别为b L k=f k m i n(P)-(f k m a x(P)-f k m i n(P))/(2D k)b U k=f k m a x(P)+(f k m a x(P)-f k m i n(P))/(2D k})第k个目标函数的网格间距d k为d k=(b U k-b L k)/D k则个体x在第k个目标函数空间的网格值G k(x)为G k(x)=f l o o r((f k(x)-b L k)/d k)(2)其中,f l o o r(㊃)表示最小取整函数,f k(x)为个体x在第k个目标函数的真实函数值㊂由式(2)知,图1中5个个体在第k个目标函数下的网格值G k(x)从左到右分别为0㊁1㊁3㊁3和4㊂图1 第k个目标函数赋予的网格属性个体x在m个目标函数下的网格值之和为G r(x)=∑m k=1G k(x)(3)根据个体网格值,类似地定义网格支配x≺g r i d y[12]为∀i∈(1,2, ,m):G i(x)≤G i(y)且∃j∈(1,2, ,m):G j(x)<G j(y)㊃9022㊃基于网格支配的微型多目标遗传算法 符纯明 姜 潮 刘桂萍等Copyright©博看网. All Rights Reserved.个体x和y在m个目标函数下的网格值之差定义为网格差值,记为G D:G D(x,y)=∑m k=1|G k(x)-G k(y)|(4)当个体y满足N(x)={y|G D(x,y)<m}时,则称个体y为个体x的邻居个体㊂个体x的网格拥挤距离d G C为d G C(x)=∑y∈N(x)(m-G D(x,y))(5)G r值和d G C值能较好地度量解的收敛性和多样性,但当两者值相等时则无法区分个体,故引入网格坐标点距离,记为d G C P:d G C P(x)=∑m k=1{[f k(x)-(b L k+G k(x)d k)]/d k}2(6)式中,d G C P为个体x在超方体中与理想点(超方体中所有目标函数值最小的点)的正则化欧拉距离㊂通过G r㊁d G C和d G C P值的比较与选择获得精英个体㊂以两目标函数为例,6个个体在网格中的G r值和d G C值分别如图2所示㊂如个体C 在网格中的G r值和d G C值计算式为:G r(C)=3+3=6, d G C(C)=(2-1)+(2-1)=2㊂图2 个体在网格中的G r值和d G C值2.2 算法流程以N S G A‐Ⅱ算法和S P E A2算法为代表的多目标进化算法通常采用大种群计算,计算量大,效率较低㊂G r‐μMO G A算法采用小种群[9](5~ 8个个体)结合重启动策略,并基于网格支配进行迭代进化,能提高效率并满足解的收敛性要求,其计算流程如图3所示㊂(1)在可行域空间产生5~8个个体形成初始种群P1㊂设外部种群P e大小为N,外部种群出现相同的连续代数的次数记为i f l a g㊂(2)网格支配分级㊂将外部种群P e和进化种群P t合并成R t,将R t进行网格支配分级(R1,, R m)㊂若P e=R1,则i f l a g+1㊂(3)当i f l a g大于设定值M(一般取值为2~9)时,则采用重启动策略㊂重新在可行域空间中产图3 G r‐μMO G A计算流程生进化种群P t,并加入R t中进行网格支配分级,否则进行网格选择机制㊂(4)网格选择机制㊂当|P t+1|+|R i|<N 时,则将第R i+1网格支配级根据G r值㊁d G C值和d G C P值进行择优筛选保存到外部种群,G r值越小越优㊂当G r值相等时,则根据d G C值选择,d G C值越小越优㊂当前两者值相等时,则选择d G C P值较小的㊂若三者值相等,则从中随机选择㊂若|P t+1|+|R i|=N,则直接将前i个网格非支配集加入到外部种群㊂(5)当进化代数大于设定的n值时终止进化,并输出外部种群个体,否则转(6)继续进化㊂(6)遗传操作㊂选择外部种群的精英个体进行交叉㊁变异等操作,从而生成子代种群P t+1,转(2)进行迭代进化㊂该算法采用小种群计算效率高的优点并结合重启动策略,避免了早熟收敛的特点,能有效地求解较多目标优化问题㊂3 测试函数及工程应用3.1 两目标测试函数选择文献[15]中Z D T1函数和Z D T2函数作为测试函数进行分析:Z D T1函数为f1(x)=x1f2(x)=z(x)[1-x1/z(x})](7) Z D T2函数为f1(x)=x1f2(x)=z(x)[1-(x1/z(x))2}](8)z(x)=1+9(∑n i=2x i)/(n-1)变量个数n=30,变量x i∈[0,1],i=1,2, , 30㊂在G r‐μMO G A算法中,其参数设置为:初始种群P1为8,外部种群P e为100,交叉概率P c为0.95,变异概率P m为0.1,外部种群出现相同次数M为3,每个目标空间划分成相等个数的子空间,取D k为5㊂采用N S G A‐Ⅱ算法作对比分析,其初始种群P1为50,其余参数设置与G r‐㊃0122㊃中国机械工程第26卷第16期2015年8月下半月Copyright©博看网. All Rights Reserved.μMO G A 相同,都采用单点交叉和位变异操作㊂理论上,Z D T 1函数的P a r e t o 前沿面为{(x 1,1-x 1)|x 1∈[0,1]},Z D T 2函数P a r e t o 前沿面为{(x 1,1-x 21)|x 1∈[0,1]}㊂图4所示分别为采用N S G A ‐Ⅱ和G r -μMO G A 算法求解Z D T 1和Z D T 2函数获得的P a r e t o 解,其中实线表示理论P a r e t o 前沿面㊂两种算法整体上都能收敛到P a r e t o 前沿面,但采用G r ‐μMO G A 算法在图4a ㊁图4c 所示的矩形框内的解(图4b ㊁图4d )相比采用N S G A ‐Ⅱ方法相对应的P a r e t o 解(图4a ㊁图4c )分布得更均匀㊂而且,G r ‐μMO G A 算法采用小种群迭代,在保证解的均匀性的同时,其计算效率相比于N S G A ‐Ⅱ算法大约提高了2倍㊂(a )N S G A ‐Ⅱ算法求解Z D T 1函数的P a r et o 解(b )G r ‐μMO G A 算法求解Z D T 1函数的P a r e t o 解(c )N S G A ‐Ⅱ算法求解Z D T 2函数的P a r e t o 解(d )G r ‐μMO G A 算法求解Z D T 2函数的P a r e t o 解图4 Z D T 1函数和Z D T 2函数的优化结果3.2 三目标测试函数采用文献[16]中的D T L Z 1函数和D T L Z 2函数进行分析,D T L Z 1函数为f1(x )=12x 1x 2(1+g (x m ))f2(x )=12x 1(1+g (x m ))f 3(x )=12(1-x 1)(1+g (x m ))0≤x i≤üþýïïïïïïïï1(9)i =1,2, ,nD T L Z 2函数为f 1(x )=(1+g (x m ))c o s (x 1π/2)c o s (x 2π/2)f2(x )=(1+g (x m ))c o s (x 1π/2)s i n (x 2π/2)f3(x )=(1+g (x m ))s i n (x 1π/2)0≤x i ≤üþýïïïï1(10)i =1,2, ,n式(9)和式(10)中的g (x m )分别为g (x m )=100[|x m |+∑x i ∈x m(x i -0.5)2-c o s (20π(x i -0.5))]g (x m )=∑ni =m(x i-0.5)2x m =(x m ,x m +1, ,x n )D T L Z 1函数中目标函数个数取为m =3,k =|x m |=5,设计变量个数n =m +k -1=7;其D T L Z 1函数的P a r e t o 前沿面为∑3i =1f i =0.5㊂D T L Z 2函数中目标函数个数取为m =3,k =|x m |=10,变量个数n =m +k -1=12;D T L Z 2函数的P a r e t o 前沿面∑3i =1f 2i =0.5㊂同样使用N S G A ‐Ⅱ算法及本文提出的算法对上述两个问题进行分析求解,参数设置与前两个算例一致㊂图5所示分别为采用N S G A ‐Ⅱ和G r ‐μMO G A 算法求解D T L Z 1和D T L Z 2函数获得的P a r e t o 解㊂可以看出,两算法在整体上获得的P a r e t o 解较好地分布于目标空间,但采用G r ‐μMO G A 算法求解D T Z L 2函数时获得的P a r e t o 解(图5d )相比采用N S G A ‐Ⅱ方法获得的解(图5c )分布得更均匀㊂而且,G r ‐μMO G A 算法结合小种群的优点,在保证分布性较好的条件下,相比于N S G A ‐Ⅱ算法,其计算效率大约提高了2倍㊂3.3 制动器多目标优化设计汽车盘式制动器相对鼓式制动器,具有散热能力强㊁结构简单以及较高的方向稳定性等优点,被广泛用于现代汽车制动系统中㊂制动器在汽车制动过程中起着关键性作用,制动器质量㊁制动时间㊁制动圆盘半径等设计参数直接决定制动器的制动性能㊂制动器的啮合力越大,制动时间就越短,则需要更大的质量承受较大的啮合力,故制动器的啮合力㊁制动时间和总质量为多目标优化问题㊂本文引入文献[17]中的盘式制动器的优化问题,设计变量为制动器圆盘内径㊁外径㊁啮合力㊁摩擦接触面的个数,其多目标优化模型为m i n f 1(x )=4.9×10-5(x 22-x 21)(x 4-1)f 2(x )=9.82×106(x 22-x 21)x 3x 4(x 32-x 31)f3(x )=x 3式中,f 1(x )为制动器的质量,k g ;f 2(x )为制动器的制动时间,s ;f 3(x )为制动器的啮合力,N ;x 1为制动器圆盘的内半径,mm ;x 2为制动器圆盘的外半径,mm ;x 3为制动器的啮合力,N ;x 4为摩擦接触面的个数㊂其几何约束g 1(x )和g 2(x )为g1(x )=(x 2-x 1)-20≥0g2(x )=30-2.5(x 4+1)≥0压力约束g 3(x )为㊃1122㊃基于网格支配的微型多目标遗传算法符纯明 姜 潮 刘桂萍等Copyright ©博看网. All Rights Reserved.(a)N S G A‐Ⅱ算法求解D T L Z1函数的P a r e t o 解(b)G r‐μMO G A算法求解D T L Z1函数的P a r e t o 解(c)N S G A‐Ⅱ算法求解D T L Z2函数的P a r e t o 解(d)G r‐μMO G A算法求解D T L Z2函数的P a r e t o解图5 D T L Z1函数和D T L Z2函数的优化结果g3(x)=0.4-x33.14(x22-x21)≥0温度约束g4(x)为g4(x)=1-2.22×10-3x3(x32-x31)(x22-x21)2≥0扭矩约束g5(x)为g5(x)=2.66×10-2x3x4(x32-x31)(x22-x21)-900≥0边界约束如下:55mm≤x1≤80mm,75mm≤x2≤110mm,1000N≤x3≤3000N,x4为[2, 20]之间的整数㊂将G r‐μMO G A算法用于求解制动器多目标优化问题,其P a r e t o最优解较好地分布于目标空间,如图6所示㊂表1给出了图6中的部分P a r e-t o解㊂当设计者偏重于考虑制动器产生的制动力较小时可以选择解1㊂解6的制动力为2988.4N,制动时间为2.1s,质量为2.9k g,其制动时间最短,有利于汽车在紧急情况下快速制动㊂最终,设计者可以根据不同的设计需求选择相应的P a r e t o最优解㊂图6 盘式制动器多目标优化结果表1 制动器多目标优化部分P a r e t o最优解序号质量(k g)制动时间(s)制动力(N)设计变量(x1,x2,x3,x4) 14.15.11365.556.6,108.1,1365.5,11 21.63.62085.469.5,90.3,2085.4,11 33.12.82265.775.3,109.9,2265.7,11 43.72.62490.866.7,110,2490.8,11 52.12.62821.965.4,93,2821.9,11 62.92.12988.477.3,109.8,2988.4,11 3.4 汽车高速和低速耐撞性多目标优化设计制动器具有较好的制动性,能有效地避免汽车发生碰撞㊂当碰撞无法避免时,其保险杠㊁防撞梁和吸能盒等相关部件应能最大限度地保护乘员和汽车,降低损伤成本㊂采用文献[18]中汽车高速和低速耐撞性多目标优化设计模型,其中选取保险杠厚度x1㊁吸能盒内板厚度x2㊁吸能盒外板厚度x3㊁前纵梁内板厚度x4和前纵梁外板厚度x5为优化设计变量,如图7所示㊂高速碰撞模型为汽车以56k m/h的速度100%正面刚性壁障碰撞;低速碰撞模型为R C A R(R e s e a r c h C o u n c i l f o rA u t o m o b i l eR e p a i r s)中的正面偏置碰撞,如图8所示㊂选取汽车保险杠和前纵梁等部件的轻量化设计与碰撞中座椅点的加速度积分均值为多目标优化问题,其优化模型为[18]㊃2122㊃中国机械工程第26卷第16期2015年8月下半月Copyright©博看网. All Rights Reserved.m i n a (x ),M (x )s .t .E (x )≤300J I u p (x )≤350mm I d o w n (x )≤200mm 2.0mm ≤x 1≤3.0mm 1.0mm ≤x 2,x 3≤2.5mm 1.5mm ≤x 4,x 5≤3.üþýïïïïïïïïï0mm (11)式中,a (x )为高速碰撞时后排左侧座椅点加速度积分均值,g ;M (x )为保险杠㊁吸能盒和前纵梁的质量,k g ;E (x )为低速碰撞时前纵梁内外板吸收能量,J ;I u p (x )㊁I d o w n (x )为高速时发动机上选择的两点的侵入量,mm ;x =(x 1,x 2,x 3,x 4,x 5)T,其变量单位都为mm ㊂图7优化设计变量图8 汽车偏置碰撞模型式(11)中的目标函数和约束函数采用有限元模型计算得到,其有限元碰撞模型由755个部件㊁998220个节点㊁977742个单元构成㊂采用本文的算法对汽车耐撞性优化模型进行计算,获得的P a r e t o 最优前沿面如图9所示,其解分布均匀㊂其部分P a r e t o 解见表2,其中解1和解10为图9图9 汽车耐撞性多目标优化结果的边界点㊂加速度积分均值a 最小可降低至28.82g ,其对应的设计变量值分别为(3.00,2.50,2.50,2.99,1.79)mm ;设计变量的总质量最小值为6.82k g,但对应的加速度积分均值为46.05g ,前纵梁等发生了较严重的变形㊂解5的加速度积分均值为36.43g ,总质量为10.28k g,对应的设计变量分别为(2.14,1.52,2.48,2.76,1.50)mm ,其解较好地平衡了总质量和汽车碰撞时的加速度值㊂最终工程师可根据P a r e t o 最优解结合工程经验和偏好信息,选择某一组解作为最终妥协解㊂表2 耐撞性优化部分P a r e t o 最优解序号加速度(g )质量(k g )(x 1,x 2,x 3,x 4,x 5)(mm )128.8213.013.00,2.50,2.50,2.99,1.79230.7612.082.66,2.50,2.48,2.98,1.58332.3811.652.57,2.49,2.47,2.83,1.50434.8710.722.26,1.50,2.49,2.93,1.51536.4310.282.14,1.52,2.48,2.76,1.50638.979.541.96,1.50,2.47,2.46,1.50741.289.061.87,1.50,2.19,2.27,1.50844.797.371.43,1.50,1.50,1.73,1.54945.527.081.28,1.50,1.51,1.68,1.621046.056.821.15,1.50,1.50,1.72,1.594 结语本文提出了一种基于网格支配的微型多目标遗传方法G r ‐μMO G A ,该算法可用于求解多目标函数的优化问题㊂测试函数的结果表明,该算法具有较好的收敛性,在保证解的均匀性条件下可提高计算效率㊂采用本文提出的算法求解制动器和汽车高低速耐撞性多目标优化设计问题,获得了较好的非支配解集㊂在实际工程设计中,工程人员可以根据不同的设计方案选择相应的P a r e t o 解以满足设计要求㊂参考文献:[1] 王炳刚,饶运清,邵新宇,等.基于多目标遗传算法的混流加工/装配系统排序问题研究[J ].中国机械工程,2009,20(12):1434‐1438.W a n g B i n g g a n g ,R a oY u n q i n g ,S h a oX i n yu ,e t a l .A MO G A‐b a s e d A l g o r i t h m f o r S e q u e n c i n g a M i x e d ‐m o d e lF a b r i c a t i o n /A s s e m b l y S ys t e m [J ].C h i n aM e c h a n i c a l E n g i n e e r i n g,2009,20(12):1434‐1438.[2] 张勇,李光耀,王建华.多目标遗传算法在整车轻量化优化设计中的应用研究[J ].中国机械工程,2009,20(4):500‐503.Z h a n g Y o n g ,L iG u a n g y a o ,W a n g J i a n h u a .D e s i g n O p t i m i z a t i o no nL i g h t w e i g h to fF u l lV e h i c l eB a s e d o n M u l t i ‐o b j e c t i v e G e n e t i c A l g o r i t h m [J ].C h i n a M e c h a n i c a l E n g i n e e r i n g,2009,20(4):500‐503.[3] 陈建岭,孙杰,李剑峰.钛合金铣削加工参数多目标优化研究[J ].中国机械工程,2014,25(2):169‐㊃3122㊃基于网格支配的微型多目标遗传算法符纯明 姜 潮 刘桂萍等Copyright ©博看网. All Rights Reserved.773.C h e nJ i a n l i n g,S u n J i e,L i J i a n f e n g.M u l t i‐o b j e c t i v eO p t i m i z a t i o no fC u t t i n g P a r a m e t e r sd u r i n g M i l l i n go fT i t a n i u m A l l o y s[J].C h i n aM e c h a n i c a l E n g i n e e r-i n g,2014,25(2):169‐773.[4] S c h a f e r JD.M u l t i p l eO b j e c t i v eO p t i m i z a t i o n w i t hV e c t o r E v a l u a t e d G e n e t i c A l g o r i t h m s[C]//P r o-c e ed i n g so f1s t I n te r n a t i o n a lC o nf e r e n c eo nG e n e t i cA l g o r i t h m s a n d T h e i r A p p l i c a t i o n s.P i t t s b u r g h,P A,U S A,1985:93‐100.[5] D e b K,P r a t a p A,A g r w a lS,e ta l.A F a s ta n dE l i t i s tM u l t i o b j e c t i v eG e n e t i cA l g o r i t h m:N S G A‐Ⅱ[J].I E E ET r a n s a c t i o n so nE v o l u t i o n a r y C o m p u t a-t i o n,2002,6(2):182‐197.[6] Z i t z l e rE,L a u m a n n sM,T h i e l eL.S P E A2:I m p r o-v i n g t h e S t r e n g t h P a r e t o E v o l u t i o n a r y A l g o r i t h mf o r M u l t i o b j e c t i v e O p t i m i z a t i o n[C]//E v o l u t i o n a r yM e t h o d sD e s i g nO p t i m i z a t i o nC o n t r o l,P r o c e e d i n g sE U R O G E N2001.A t h e n s,G r e e c e,2001:95‐100.[7] 谢然,兰凤崇,陈吉清,等.满足可靠性要求的轻量化车身结构多目标优化方法[J].机械工程学报, 2011,47(4):117‐124.X i eR a n,L a nF e n g c h o n g,C h e n J i q i n g,e t a l.M u l t i ‐o b j e c t i v eO p t i m i z a t i o n M e t h o d i nC a r‐b o d y S t r u c-t u r eL i g h t‐w e i g h tD e s i g n w i t h R e l i a b i l i t y R e q u i r e-m e n t[J].C h i n e s eJ o u r n a lo f M e c h a n i c a lE n i n e e r-i n g,2011,47(4):117‐124.[8] 刘桂萍,韩旭,姜潮.基于微型多目标遗传算法的薄板冲压成形变压边力优化[J].中国机械工程, 2007,18(21):2614‐2617.L i uG u i p i n g,H a nX u,J i a n g C h a o.O p t i m i z a t i o no fV a r i a b l e B i n d e r F o r c e i n S h e e t M e t a l F o r m i n gU s i n g t h eM i c r o M u l t i‐o b j e c t i v eG e n e t i cA l g o r i t h m[J].C h i n aM e c h a n i c a l E n g i n e e r i n g,2007,18(21): 2614‐2617.[9] L i uG u i p i n g,H a nX u,J i a n g C h a o.A N o v e lM u l t i‐o b j e c t i v e O p t i m i z a t i o n M e t h o d B a s e d o n a n A p-p r o x i m a t i o n M o d e l M a n a g e m e n t T e c h n i q u e[J].C o m p u t e rM e t h o d s i nA p p l i e dM e c h a n i c s a n dE n g i-n e e r i n g,2008,197(33):2719‐2731. [10] 刘桂萍,韩旭,官凤娇.基于信赖域近似模型管理的多目标优化方法及其应用[J].中国机械工程,2008,19(10):1140‐1143.L i uG u i p i n g,H a n X u,G u a nF e n g j i a o.A m u l t i‐o b j e c t i v e o p t i m i z a t i o n M e t h o dB a s e do nt h eT r u s tR e g i o n M o d e l M a n a g e m e n t F r a m e w o r k a n d I t sA p p l i c a t i o[J].C h i n a M e c h a n i c a l E n g i n e e r i n g,2008,19(10):1140‐1143.[11] K r i s h n a k u m a r K.M i c r o‐g e n e t i c A l g o r i t h m sf o rS t a t i o n a r y a n dN o n‐s t a t i o n a r y F u n c t i o nO p t i m i z a-t i o n[C]//S P I E P r o c e e d i n g s:I n t e l l i g e n tC o n t r o la n d A d a p t i v eS y s t e m s.P h i l a d e l p h i a,U S,1989:289‐296.[12] Y a n g SX,L iM Q,L i uX H,e t a l.A G r i d‐B a s e dE v o l u t i o n a r y A l g o r i t h mf o rM a n y‐O b j e c t i v eO p t i-m i z a t i o n[J].I E E E T r a n s a c t i o n so nE v o l u t i o n a r yC o m p u t a t i o n,2013,17(5):721‐736.[13] M i e t t i n e n K.N o n l i n e a r M u l t i o b j e c t i v e O p t i m i z a-t i o n[M].N e w Y o r k:K l u w e rA c a d e m i cP u b l i s h-e r s,1999.[14] L iM Q,Z h e n g J H,S h e nR M,e ta l.A G r i d‐B a s e d F i t n e s s S t r a t e g y f o r E v o l u t i o n a r y M a n y‐O b j e c t i v e O p t i m i z a t i o n[C]//P r o c e e d i n g so ft h e12t h A n n u a lC o n f e r e n c eo n G e n e t i ca n d E v o l u-t i o n a r y C o m p u t a t i o n.N e w Y o r k,2010:463‐470.[15] Z i t z l e rE,D e bK,T h i e l eL.C o m p a r i s o no fM u l-t i o b j e c t i v e E v o l u t i o n a r y A l g o r i t h m s:E m p i r i c a lR e s u l t s[J].I E E E T r a n s a c t i o n so n E v o l u t i o n a r yC o m p u t a t i o n,2000,8:173‐195.[16] D e b K,T h i e l eL,L a u m a n n s M,e ta l.S c a l a b l eM u l t i‐o b j e c t i v eO p t i m i z a t i o nT e s t P r o b l e m s[C]//P r o c e e d i n g s o f t h e2002C o n g r e s s o nE v o l u t i o n a r yC o m p u t a t i o n a l.H o n o l u l u,2002:825‐830.[17] O s y c a k aA,K u n d uS.A M o d i f i e dD i s t a n c eM e t h o df o r M u l t i c r i t e r i a O p t i m i z a t i o n U s i ng G e n e t i c A l-g o r i t h m s[J].C o m p u t e r s&I n d u s t r i a lE n g i n e e r-i n g,1996,30:871‐882.[18] 姜潮,邓善良.考虑车辆高速和低速耐撞性的多目标优化设计[J].计算力学学报,2014,31(4):474‐479.J i a n g C h a o,D e n g S h a n l i a n g.M u l t i‐o b j e c t i v eO p t i-m i z a t i o n a n d D e s i g n C o n s i d e r i n g A u t o m o t i v eH i g h‐s p e e da n dL o w‐s p e e dC r a s h w o r t h i n e s s[J].C h i n e s e J o u r n a l o f C o m p u t a t i o n a l M e c h a n i c s,2014,31(4):474‐479.(编辑 苏卫国)作者简介:符纯明,男,1987年生㊂湖南大学汽车车身先进设计制造国家重点实验室博士研究生㊂研究方向为差分进化算法㊁多目标优化㊂姜 潮(通信作者),男,1978年生㊂湖南大学汽车车身先进设计制造国家重点实验室教授㊁博士研究生导师㊂刘桂萍,女,1980年生㊂湖南大学汽车车身先进设计制造国家重点实验室讲师㊂邓善良,男,1987年生㊂湖南大学汽车车身先进设计制造国家重点实验室硕士研究生㊂㊃4122㊃中国机械工程第26卷第16期2015年8月下半月Copyright©博看网. All Rights Reserved.。
网格划分是进行有限元分析和计算的前提，也是最费时间最费精力的一项前处理技术，网格划分的质量对有限元计算的精度和计算效率都有着最为直接的影响，对于大变形的情况甚至影响到解的收敛性。
目前比较通用的分网软件主要有Hypermesh、ANSA、ANSYS、MARC等，本文就复杂模型的分网技术进行简明的阐述。
自由网格划分自由网格划分是自动化程度最高的网格划分技术之一，它在面上（平面、曲面）可以自动生成三角形或四边形网格，在体上自动生成四面体网格。
通常情况下，可利用Hypermesh的2D面板的automesh来对面和网格单元自动划分。
对于复杂几何模型而言，自动分网方法省时省力，但缺点是单元数量甚至会出现单元不能达到预想的效果，如在某些地方需要较少单元，而在另外的地方需要更多的单元时，通常不容易控制。
因此需要对面进行一些几何分块处理，以得到符合分网工作者的意愿的具有较高计算效率的网格。
对于三维复杂模型只能生成四面体单元，分网效率极高，只要设置相关参数就等得到较好的网格，但是网格数量取决于几何模型的最小特征，网格数量通常非常大，因此为了获得更高的计算效率的有限元网格，通常要对几何模型进行一些处理，和二维情况类似，可以进行分块处理，如进行局部细分。
映射网格划映射网格划分是对规整模型的一种规整网格划分方法，其原始概念是：对于面，只能是四边形面，网格划分数需在对边上保持一致，形成的单元全部为四边形；对于体，只能是六面体，对应线和面的网格划分数保持一致；形成的单元全部为六面体。
目前大多数分网软件对这些条件有了很大的放宽，包括：o面可以是三角形、四边形、或其它任意多边形。
o面上对边的网格划分数可以不同，但有一些限制条件。
o面上可以形成全三角形的映射网格。
o体可以是四面体、五面体、六面体或其它任意多面体。
o体上对应线和面的网格划分数可以不同，但有一些限制条件。
对于三维复杂几何模型而言，通常的做法是利用线面切割功能，将其切割成一系列四、五或六面体，然后对这些切割好的体进行映射网格划分。
基于径向基函数的高效网格变形算法研究谢亮;徐敏;张斌;安效民【摘要】在流固耦合时域仿真与气动外形优化中,网格变形技术得到了普遍应用.基于径向基函数的网格变形技术以其诸多优良的特性,在近年来得到了广泛的关注.其基本原理是采用物面网格节点的位移构造一个径向基函数序列,再利用此序列将物面的位移光滑的插值到空间网格上.其计算耗时与物面插值节点数与空间待插值节点数的乘积成正比,为了减少其计算量,目前多数文献集中于使用数据精简算法减少物面插值节点数.通过引入子空间逐级逼近思想,构造了一种精简空间待插值节点数的方案,该方案主要思想是采用多次插值,每一次插值的对象为上一次插值在物面产生的误差,并且通过限制每一次插值的插值区域来实现减缩空间节点的目的.计算结果表明此方案可以支持大变形运动,同时显著的减少了计算时间.【期刊名称】《振动与冲击》【年(卷),期】2013(032)010【总页数】5页(P141-145)【关键词】径向基函数;网格变形;数据精简算法【作者】谢亮;徐敏;张斌;安效民【作者单位】西北工业大学航天学院,西安710072;西北工业大学航天学院,西安710072;西北工业大学航天学院,西安710072;西北工业大学航天学院,西安710072【正文语种】中文【中图分类】O241.3在非定常流动模拟、流固耦合时域仿真、气动外形优化中，为了使得计算网格适应物面边界的变化，可以采用网格重构的方法，然而更广泛的是应用网格变形技术，这样可以保留原始网格的拓扑结构与密度、正交性等特性，不会在求解器中引入额外的误差，同时计算量较小。
目前存在多种网格变形方法，无限代数插值方法［1］计算量较小，然而却仅适用于结构网格，且难于处理复杂的拓扑结构，通用性不好。
对于非结构网格、混合网格，可以应用弹性体方法［2］、弹簧比拟法［3-4］以及Delaunay图映射［5］方法。
弹性体方法将网格所占据的区域比拟为一个弹性体，通过采用有限元或者边界元方法求解弹性体的变形来实现动态网格变形技术，通用性较好，效果优良，变形后的网格质量极好，尤其适用于大变形情况，然而计算量非常庞大。
第17卷第8期2005年8月计算机辅助设计与图形学学报JOURNAL OF COMPU TER 2AIDED DESIGN &COMPU TER GRAPHICSVol 117,No 18Aug 1,2005 收稿日期:2004-03-09;修回日期:2004-07-08 基金项目:国家“八六三”高技术研究发展计划重点项目(2001AA231031,2002AA231021);国家重点基础研究发展规划项目(G1998030608);国家科技攻关计划课题(2001BA904B08);中国科学院知识创新工程前沿研究项目(20006160,20016190(C ))三维网格模型的分割及应用技术综述孙晓鹏1,2) 李 华1)1(中国科学院计算技术研究所智能信息处理重点实验室 北京 100080)2(中国科学院研究生院 北京 100039)(xpsun @ict 1ac 1cn )摘要 对三维网格模型分割的定义、分类和应用情况做了简要回顾,介绍并评价了几种典型的网格模型分割算法,如分水岭算法、基于拓扑和几何信息的分割算法等;同时,对网格分割在几种典型应用中的研究工作进行了分类介绍和评价1最后对三维分割技术今后的发展方向做出展望1关键词 分割Π分解;三维分割;形状特征;网格模型中图法分类号 TP391A Survey of 3D Mesh Model Segmentation and ApplicationSun Xiaopeng 1,2) Li Hua 1)1(Key L aboratory of Intelligent Inf ormation Processi ng ,Instit ute of Com puti ng Technology ,Chi nese Academy of Sciences ,Beiji ng 100080)2(Graduate School of the Chi nese Academy of Sciences ,Beiji ng 100039)Abstract In this paper ,we present a brief summary to 3D mesh model segmentation techniques ,includ 2ing definition ,latest achievements ,classification and application in this field 1Then evaluations on some of typical methods ,such as Watershed ,topological and geometrical !method ,are introduced 1After some ap 2plications are presented ,problems and prospect of the techniques are also discussed 1K ey w ords segmentation Πdecomposition ;3D segmentation ;shape features ;mesh model1 引 言基于三维激光扫描建模方法的数字几何处理技术,继数字声音、数字图像、数字视频之后,已经成为数字媒体技术的第四个浪潮,它需要几何空间内新的数学和算法,如多分辨率问题、子分问题、第二代小波等,而不仅仅是欧氏空间信号处理技术的直接延伸[1]1在三维网格模型已成为建模工作重要方式的今天,如何重用现有网格模型、如何根据新的设计目标修改现有模型,已成为一个重要问题1网格分割问题由此提出,并成为近年的热点研究课题[223]12 网格分割概述三维网格模型分割(简称网格分割),是指根据一定的几何及拓扑特征,将封闭的网格多面体或者可定向的二维流形,依据其表面几何、拓扑特征,分解为一组数目有限、各自具有简单形状意义的、且各自连通的子网格片的工作1该工作被广泛应用于由点云重建网格、网格简化、层次细节模型、几何压缩与传输、交互编辑、纹理映射、网格细分、几何变形、动画对应关系建立、局部区域参数化以及逆向工程中的样条曲面重建等数字几何处理研究工作中[223]1同时,三维网格模型的局部几何拓扑显著性也是对三维网格模型进行检索的一种有效的索引[4]1与网格曲面分割有关、并对其影响巨大的一个早期背景工作是计算几何的凸分割,其目的是把非凸的多面体分解为较小的凸多面体,以促进图形学的绘制和渲染效率1该工作已经有了广泛的研究,但多数算法难以实现和调试,实际应用往往不去分割多面体,而是分割它的边界———多边形网格1多面体网格边界的分割算法有容易实现、复杂形体输出的计算量往往是线性的等优势[5]1另外一个早期背景工作是计算机视觉中的深度图像分割,其处理的深度图像往往具有很简单的行列拓扑结构,而不是任意的,故其分割算法相对简单[6]1三维网格模型的分割算法一般是从上述两类算法推广而来1心理物理学认为:人类对形状进行识别时,部分地基于分割,复杂物体往往被看作简单的基本元素或组件的组合[728]1基于这个原理,Hoffman 等[9]于1984年提出人类对物体的认知过程中,倾向于把最小的负曲率线定义为组成要素的边界线,并据此将物体分割为几个组成要素,即视觉理论的“最小值规则”1由此得到的分割结果称为“有意义的”分割,它是指分割得到的子网格必须具有和其所在应用相关的相对尺寸和组织结构1由于曲率计算方法不同,很多算法给出的有意义的分割结果也存在差异1诸多应用研究[10214]证明,网格模型基于显著性特征的形状分割,是物体识别、分类、匹配和跟踪的基本问题1而有意义的分割对于网格模型显著占优特征的表示和提取、多尺度的存储和传输以及分布式局部处理都是十分有意义的1211 网格分割的发展较早的三维网格分割工作可以追溯到1991年,Vincent 等[15]将图像处理中的分水岭算法推广到任意拓扑连接的3D 曲面网格的分割问题上11992年,Falcidieno 等[16]按照曲率相近的原则,把网格曲面分割为凹面片、凸面片、马鞍面片和平面片11993年,Maillot 等[17]将三角片按法向分组,实现了自动分割;1995年,Hebert 等[18]给出了基于二次拟合曲面片的曲率估计方法,并把区域增长法修改推广应用到任意拓扑连接的网格曲面分割问题中;1995年,Pedersen [19]和1996年Krishnamurthy 等[20]在他们的动画的变形制作过程中,给出了用户交互的分割的方法11997年,Wu 等[3]模拟电场在曲面网格上的分布,给出了基于物理的分割方法;1998年Lee 等[21]和2000年Guskov 等[22]给出了几个对应于简化模型的多分辨率方法;1999年Mangan 等[2]使用分水岭算法实现网格分割,并较好地解决了过分割问题;2001年,Pulla 等[23224]改进了Mangan 的曲率估计工作;1999年,Gregory 等[25]提出一个动画设计中的交互应用,根据用户选择的特征点将网格曲面分割为变形对应片;1999年,Tan 等[26]基于顶点的简化模型建立了用于碰撞检测的、更紧致于网格曲面分割片的层次体包围盒12000年,Rossl 等[27]在逆向工程应用中,在网格曲面上定义了面向曲率信号的数学形态学开闭操作,从而得到去噪后的特征区域骨架,并实现了网格分割;2001年,Yu 等[28]的视觉系统自动将几何场景点云分割为独特的、用于纹理映射和绘制的网格曲面片二叉树;Li 等[29]为了碰撞检测,给出了基于边收缩得到描述几何和拓扑特征的骨架树,然后进行空间扫描自动分割;Sander 等[30]使用区域增长法,按照分割结果趋平、紧凑的原则分割、合并分割片1所有这些方法都是为了使分割的结果便于参数化,即只能产生凸的分割片1由此产生边界不连续的效果12002年,Werghi 等[31]识别三维人体扫描模型的姿态,根据人体局部形状索引进行网格模型的分割;Bischoff 等[32]和Alface 等[33]分别给出了网格分割片光谱在几何压缩和传输中的应用;Levy 等[34]在纹理生成工作中,以指定的法向量的夹角阈值对尖锐边滤波,对保留下来的边应用特征增长算法,最后使用多源Dijkstra 算法扩张分割片实现了网格模型的分割;2003年,Praun 等[35]将零亏格网格曲面投影到球面上,然后把球面投影到正多面体上得到与多面体各面对应的网格模型分割,最后将多面体平展为平面区域以进行参数化,但其结果不是有意义的分割1212 网格分割的分类早期的网格分割算法多为手工分割或者半自动分割,近两年出现了基于自动分割的应用工作1从网格模型的规则性来看,可将分割算法分为规则网格分割、半规则网格分割和任意结构的网格分割算法,根据分割结果可以分为有意义的分割和非有意义的分割1同时,面向不同的应用目标出现了不同的分割策略(见第4节)1目前,网格分割的质量指标主要有三个方面:边界光顺程度、是否有意义、过分割处理效果1多数分8461计算机辅助设计与图形学学报2005年割算法以边界光顺为目标,采用的方法有在三角网格上拟合B样条曲面然后采样[20],逼近边界角点(两个以上分割片的公共顶点)间的直线段[30]等1近年来多数分割算法都追求产生有意义的分割结果1对于过分割的处理方法目前主要有忽略、合并和删除三种方式1多数三维网格分割算法是从二维图像分割的思想出发,对图像分割算法作三维推广得到其三维网格空间的应用1如分水岭算法[2,15,23224,36239]、K2 means算法[40]、Mean2shift算法[41]以及区域增长算法[18,30]等1同样,与图像处理问题类似,光谱压缩[33,42243]、小波变换[31]等频谱信息处理方法在三维网格分割中也有算法1除此之外,同时考虑几何与拓扑信息的分割会产生较好的结果1这方面的工作主要有基于特征角和测地距离度量[44]、基于高斯曲率平均曲率[45247]、基于基本体元[32]、基于Reeb图[48250]、基于骨架提取和拓扑结构扫描[27,29,51252]等使用三维网格曲面形状特征的算法1作为网格模型的基础几何信息,曲率估计方法目前主要为曲面拟合、曲线拟合以及离散曲率等三种1其中曲面拟合法较为健壮,但是计算量大;离散曲率法计算量小,但是除个别算法外都不是很健壮,且无主方向主曲率信息;曲线拟合的曲率估计方法则集中了上述两种方法的优势[3],实际研究中使用较多13 典型三维网格分割算法311 分水岭算法1999年,Mangan等[2]的工作要求输入的是三角网格曲面,以及任何一种可以用来计算每个顶点曲率的附加信息(如曲面法向量等),并针对体数据和网格数据给出了两种曲率计算方法;但是分水岭算法本身和曲率的类型无关1首先,计算每个顶点的曲率(或者其他高度函数),寻找每个局部最小值,并赋予标志,每一个最小值都作为网格曲面的初始分割;然后,开始自下而上或者自上而下地合并分水岭高度低于指定阈值的区域,有时平坦的部分也会得到错误的分割,后处理解决过分割问题1分割为若干简单的、无明确意义的平面或柱面,属于非有意义的分割1Rettmann等[36237]结合测地距离,并针对分水岭算法的过分割给出一个后处理,实现了MRI脑皮层网格曲面的分割12002年,Marty[38]以曲率作为分水岭算法的高度函数,给出了有意义的分割结果1 2003年,Page等[39]的算法同样只分割三角网格,依据最小值规则,他们试图得到网格模型高层描述1其主要贡献为:创建了一个健壮的、对三角网格模型进行分割的贪婪分水岭法;使用局部主曲率定义了一个方向性的、遵循最小值规则的高度图;应用形态学操作,改进了分水岭算法的初始标识集1文献[39]在网格的每一个顶点计算主方向和主曲率,根据曲率阈值,使用贪婪的分水岭算法分割出由最小曲率等高线确定的区域1形态学的开闭操作应用于网格模型每个顶点的k2ring碟状邻域,闭操作会连接空洞,而开操作会消除峡部1创建了标识集后,依据某顶点与其邻接顶点之间的方向,由欧拉公式和已知主曲率计算该顶点在该方向上的法曲率从而得到在该方向上、该顶点与邻接顶点之间的方向曲率高度图,并将其作为方向梯度1对该顶点所在的标识区域使用分水岭算法得到分割片1上述工作表明,分水岭算法在改进高度函数的定义后,可以得到有意义的分割效果1312 基于拓扑信息的网格分割基于几何以及拓扑信息的形状分割方法可以归结为Reeb图[50]、中轴线[52]和Shock图[53254]等1基于拓扑信息的形状特征描述主要有水平集法[55]和基于拓扑持久性的方法[56]11999年,Lazarus等[51]提出从多面体顶点数据集提取轴线结构,在关键点处分割网格的水平集方法,如图1所示1这种轴线结构与定义在网格模型顶点集上的纯量函数关联,称之为水平集图,它能够为变形和动画制作提供整体外形和拓扑信息1图1 人体网格模型及其水平集图文献[51]针对三角剖分的多面体,使用与源点之间的最短路径距离作为水平集函数,基于Dijkstra 算法构造记录水平集图的结构树,其根结点、内部结点和叶子分别表示源点、水平集函数的鞍点和局部最大值点1该工作可以推广到非三角网格模型1 2001年,Li等[29]基于PM算法[57]的边收缩和94618期孙晓鹏等:三维网格模型的分割及应用技术综述空间扫掠,给出了一个有效的、自动的多边形网格分割框架1该工作基于视觉原理,试图将三维物体分割为有视觉意义和物理意义的组件1他们认为三维物体最显著的特征是几何特征和拓扑特征,由此,定义几何函数为扫掠面周长在扫掠结点之间的积分为骨架树中分支的面积;定义拓扑函数为相邻两个扫掠面拓扑差异的符号函数,并定义了基于微分几何和拓扑函数的关键点1文献[29]首先基于PM算法将每条边按照其删除误差函数排序,具有最小函数值的边收缩到边中点,删除其关联的三角形面片;如果某边没有关联任何三角片则指定为骨架边,保持其顶点不变;循环上述过程,得到一个新的、通过抽取给定多边形网格曲面骨架的方法1其次,加入虚拟边连接那些脱节的骨架边,称这些虚拟边以及原有的骨架边组成的树为骨架树,即为扫掠路径1扫掠路径为分段线条1然后,定义骨架树中分支面积(扫掠面周长函数在扫掠结点之间的积分),分支面积较小的首先扫掠,以保证小的、但是重要的分割片被首先抽取出来,以免被其他较大的分割片合并1最后,沿扫掠路径计算网格的几何、拓扑函数的函数值1一旦发现几何函数、拓扑函数的关键点,抽取两个关键点之间的网格曲面得到一个新的分割片1整个过程无需用户干涉12003年,Xiao等[48249]的工作基于人体三维扫描点云的离散Reeb图,给出了三维人体扫描模型的一个拓扑分割方法:通过探测离散Reeb图的关键点,抽取表示身体各部分的拓扑分支,进而进行分割1水平集法具有较高的计算速度和健壮的计算精度1基于拓扑持久性的方法结合代数学,能更准确地计算形状特征,但是没有解决分割问题[55256]1 313 基于实体表示的网格分割2002年,Bischoff等[32]把几何形状分割为表示其粗糙外形的若干椭球的集合,并附加一个独立的网格顶点的采样集合来表示物体的细节1生成的椭球完全填充了物体的内部,采样点就是原始的网格顶点1该方法的步骤如下:Step11首先,在物体原始网格的每一顶点上生成一个椭球,或者随机在物体原始网格上采样选择种子点;每个种子点作为球面上的一个顶点,沿该点的网格法向做球面扩展,直至与网格上另外一个顶点相交;然后沿此两点的垂直方向将球面扩张为最大椭球,直至与第三个网格顶点相交;最后沿此三点平面的法向(即该三点所在平面的柱向)扩张,直至与第四个网格顶点相近,由此得到一个椭球1Step21对生成的椭球进行优化选择,体积最大的椭球首先被选中,以后每一次都将选出对累计体积贡献最大的椭球1如果有若干体积累计贡献相近的椭球同时出现的情况发生,则最小半径最短的椭球被选出1为了简化体积累计贡献的计算,对椭球体素化后计算完全包含在椭球内的体素的数目进行堆排序1发送方传送选出的椭球集合;接收方得到包含基本几何和拓扑信息的椭球集合后,使用Marching Cubes算法或者Shrink2wrapping算法抽取0等值面1显然即使部分椭球丢失,工作依然可以继续:因为椭球是互相重叠的,抽取等值面不影响它们的拓扑关系,而且如果重叠充分,丢失少部分椭球不会影响重要形状信息的重构1如图2所示1图2 以不同数目椭球表示的网格分割Step31在生成很好地逼近原始物体的初始网格后,开始将采样点(即原始网格顶点)插入网格[58]1为了提高最终重构结果的质量,由Marching Cubes算法生成的临时网格顶点在网格原始顶点陆续到来后,最终被删除,因为它们不是物体的原始顶点1314 基于模糊聚类的层次分解2003年,Katz等[44]提出了模糊聚类的层次分解算法,算法处理由粗到精,得到分割片层次树1层次树的根表示整个网格模型S1在每个结点,首先确定需要进一步分割为更精细分割片的数目,然后执行一个k2way分割1如果输入的网格模型S由多个独立网格构成,则分别对每个网格进行同样的操作1分割过程中,算法不强调每个面片必须始终属于特定的分割片1大规模网格模型的分割在其简化模型上进行,然后将分割片投影到原始网格模型上,在不同的尺度下计算分割片之间的精确边界1文献[44]算法优点是:可以对任意拓扑连接的或无拓扑连接的、可定向的网格进行处理;避免了过分割和边界锯齿;考虑测地距离和凸性,使分割边界通过凹度最深的区域,从而得到有意义的分割结果1分割结果适用于压缩和纹理映射14 三维网格分割应用411 三维检索中的网格分割算法在三维VRML数据库中寻找一个与给定物体0561计算机辅助设计与图形学学报2005年相似的模型的应用需求,随着WWW的发展正变得越来越广泛,如计算生物学、CAD、电子商务等1形状描述子和基于特征的表示是实体造型领域中基本的研究问题,它们使对物体的识别和其他处理变得容易1因为相似的物体有着相似的分割,所以分割结构形状描述子可以用于匹配算法1中轴线、骨架等网格模型拓扑结构的形状描述子在三维模型检索中也得到研究,它可以从离散的体数据以及边界表示数据(网格模型)中抽取出来1对于后者,目前还没有精确、有效的结果[39]1但我们相信,依据拓扑信息进行分割得到的分布式形状描述子也是一种值得尝试的三维模型检索思路1 2002年,Bischoff等[32]提出从椭球集合中得到某种统计信息,如椭球半径的平均方差或者标准方差,以及它们的比率,由于这些统计信息在不同的形状修改中都保持不变,作为一种检索鉴别的标识的想法1但是没有严格的理论或者实验结果证明1 2002年,Zuckerberger等[59]在一个拥有388个VRML三维网格模型的数据库上,进行基于分割的变形、简化、检索等三个应用1首先将三维网格模型分割为数目不多的有意义的分割片,然后评价每一个分割片形状,确定它们之间的关系1为每个分割建立属性图,看作是与原模型关联的索引,当数据库中检索到与给定网格模型相似的物体时,只是去比较属性图相似的程度1属性图与其三维模型的关联过程分为三步:(1)分割网格曲面为有限数目的分割片;(2)每一个分割片拟合为基本二次曲面形状;(3)依据邻接分割片的相对尺寸关系进行过分割处理,最后构造网格曲面模型的属性图1对分割片作二次拟合,由此产生检索精确性较差的问题;分割片属性图的比较采用图同构的匹配方法,计算量较大,且是一个很困难的问题;从其实验结果看,有意义的分割显然还不够,出现飞机、灯座等模型被检索为与猫相似的结构;区分坐、立不同的人体模型效果显然也很差等12003年,Dey等[4]基于网格模型的拓扑信息,给出了名为“动力学系统”的形状特征描述方法,并模拟连续形状定义离散网格形状特征1实验表明该算法十分有效地分割二维及三维形状特征1他们还给出了基于此健壮特征分割方法的形状匹配算法1 412 几何压缩传输中的网格分割健壮的网格模型压缩传输方法必须保证即使部分几何信息丢失,剩下的部分至少能够得到一个逼近原始物体的重构,即逼近的质量下降梯度,要大大滞后于信息丢失梯度1无论是层次结构的还是过程表示的多边形网格模型,它们的缺陷是:严格的拓扑信息一致性要求1顶点和面片之间的交叉引用导致即使在传输中丢失了1%的网格数据,也将导致无法从99%的剩余信息里重建网格曲面的任何一部分1对此可以考虑引入高度的冗余信息,即使传输中丢失一定额度的数据,接收方依然可以重构大部分的几何信息1问题的关键是将几何体分割为相互独立的大块信息,如单个点,这样接收方可以在不依赖相关索引信息的情况下,重构流形的邻域关系1为了避免接收方从点云重构曲面的算法变得复杂,早期的健壮传输方法总假设至少整体拓扑信息可以无损地传送1一旦知道了粗糙的形状信息,接收方可以插入一些附加点生成逼近网格12002年,Bischoff等[32,58]在网格分割工作中将每个椭球互相独立地定义自己的几何信息1由于椭球的互相重叠,冗余信息由此产生,因此如果只有很少的椭球丢失,网格曲面的拓扑信息和整体形状不会产生变化1冗余信息不会使存储需求增加,因为每个椭球和三角网格中每个顶点一样,只需要9个存储纯量1其传送过程如下:种子点采样生成椭球集合;传送优化选择的椭球子集;接收方抽取等值面重构逼近网格;以陆续到来的原始网格顶点替换临时网格顶点11996年,Taubin等[42]首先在几何压缩处理中提出光谱压缩,其工作在三维网格模型按如下方式应用傅里叶变换:由任意拓扑结构的网络顶点邻接矩阵及其顶点价数,得到网格Laplacian矩阵的定义及由其特征向量构成的R n空间的正交基底,相对应的特征值即为频率1三维网格顶点的坐标向量在该空间的投影即为该网格模型的几何光谱1网格表面较为光顺的区域即为低频信号12000年,Karni等[43]将几何网格分割片光谱推广到传输问题上1光谱直接应用于定义几何网格的拓扑信息时,会产生伪频率信息1对于大规模的网格,由于在网格顶点数目多于1000时,Laplacian矩阵特征向量的计算几乎难以进行,因此该工作在最小交互前提下,将网格模型分割为有限数目的分割片1该方法有微小的压缩损失,且在分割片边界出现人工算法痕迹12003年,Alface等[33]提出了光谱表示交叠方法:扩张分割片,使分割片之间产生交叠1具体方法是把被分割在其他邻接分割片中的、但与该分割片15618期孙晓鹏等:三维网格模型的分割及应用技术综述邻接的三角片的顶点,按旋转方向加入到该分割片中,从而由于分割片重叠搭接产生冗余信息,并称这种分割片扩展冗余处理的光谱变换为交叠的正交变换1该工作在几何网格压缩和过程传输的应用中明显地改进了Karni等的工作1显然上述工作的基础是良好的网格分割1建立分片独立的基函数将使得分割效果更为理想1413 纹理贴图中的网格分割如果曲面网格的离散化是足够精细的,如细分网格,那么直接对顶点进行纹理绘制就足够了;否则就要把网格模型分割为一组与圆盘同胚的、便于进行参数化的分割片,再对每片非折叠的分割片参数化,最后分割片在纹理空间里拼接起来1网格模型的分割显然会因其局部性而降低纹理映射纹理贴图、网格参数化的扭曲效果1面向纹理的分割算法一般要求满足两个条件:(1)分割片的不连续边界不能出现人工算法痕迹;(2)分割片与圆盘同胚,而且不引入太大的变形就可以参数化1不要求有意义的分割结果12001年,Sander等[30]基于半边折叠的PM算法,使用贪婪的分割片合并方法(区域增长法)对网格模型进行分割1首先将网格模型的每一个面片都看作是独立的分割片,然后每个分割片与其邻接分割片组对、合并1在最小合并计算量的前提下,循环执行分割片对的合并操作,并更新其他待合并分割片的计算量1当计算量超出用户指定的阈值时,停止合并操作1分割片之间的边界为逼近角点间直线段的最短路径,从而减轻了锯齿情况12002年,Levy等[34]将网格模型分割为具有自然形状的分割片,但仍然没有得到有意义的分割结果1为了与圆盘同胚,该算法自动寻找位于网格模型高曲率区域的特征曲线,避免了在平展区域内产生分割片边界,并增长分割片使他们在特征曲线上相交,尽量获得尺寸较大的分割片1414 动画与几何变形中的网格分割影视动画制作中,多个对象间的几何变形特技使用基于网格分割的局部区域预处理1如建立动画区域对应关系,对多个模型进行一致分割,然后在多个模型的对应分割片之间做变形,将提高动画制作的精度和真实性;且每个“Polygon Soup”模型都可用来建立分割片对应;模型间的相似分割有利于保持模型的总体特征1目前,多数的自动对应算法精度较低,手工交互指定对应关系的效率又太低1 1996年,Krishnamurthy等[20]从高密度、非规则、任意拓扑结构的多边形网格出发,手工指定分割边界,构造张量积样条曲面片的动画模型1文献[20]首先在多边形网格的二维投影空间交互选择一个顶点序列,然后自动地将顶点序列关联到网格上最近的顶点上;对于序列中前后两个顶点计算在网格曲面上连接它们的最短路径;对该路径在面片内部进行双三次B样条曲面拟合、光顺、重新采样,得到分割片在两个顶点之间的边界曲线1但计算量的付出依然是非常昂贵的11999年,Gregory等[25]在两个输入的多面体曲面上交互选择多面体顶点,作为一个对应链的端点,对应链上其他顶点通过计算曲面上端点对之间的最短路径上的顶点确定,由此得到这些顶点和边构成的多面体表面网格的连通子图;然后将每一个多面体分割为相同数目的分割片,每个分割片都与圆盘同胚;在分割片之间建立映射、重构、局部加细,完成对应关系的建立;最后插值实现两个多面体之间的变形12002年,Shlafman等[40]的工作不再限制输入网格必须是零亏格或者是二维流形1该算法通过迭代,局部优化面片的归属来改进某些全局函数,因此与图像分割K2means方法相近,属于非层次聚类算法1最终分割片的数目可以由用户预先指定,从而避免了过分割,且适用于动画制作的需求1分割过程的关键在于确认给定的两个面片是否属于同一个分割片1其分割工作是非层次的,因为面片可能会在优化迭代中被调整到另外一个分割片去1该工作表明,基于分割的变形对于保持模型的特征有着重要的意义1局部投影算法能够产生精细的对应区域,且能自动产生有意义的分割片1415 模型简化中的网格分割网格简化是指把给定的一个有n个面片的网格模型处理为另一个保持原始模型特征的、具有较少面片、较大简化Π变形比的新模型1三维网格分割显然可以被看作是一种网格简化,其基本思想是在简化中增加一个预处理过程,先按模型显著特征将其分割为若干分割片,然后在每个分割片内应用简化算法,由此保持了模型的显著特征,如特征边、特征尖锐以及其他精细的细节1例如,把曲率变化剧烈的区域作为分割边界,将曲率变化平缓的区域各自分割开来,就是基于曲率阈值的网格简化方法1网格曲面分割结果的分割片数目在去除过分割后被限制在指定的范围内12561计算机辅助设计与图形学学报2005年。
