基于三维网格模型的网格排布优化技术综述

网格化算法在三维模型构建中的应用随着科技的不断发展，三维模型构建已经成为了极为普及的技术。

在这一领域中，网格化算法是一种非常重要的算法，它被广泛应用于三维模型的构建、分析和处理。

本文章将为您详细介绍网格化算法在三维模型构建中的应用。

一、网格化算法介绍网格化算法是一种将连续的物理空间离散化成有限数量的网格的算法。

这种算法可以将一个复杂的物理结构转换成一系列简单的网格单元。

网格化算法的实现涉及到以下几个过程：1. 空间分割：将三维图形分割成多个小三角形或小四面体。

可以有不同的分割方法，如球形分割、射线法分割等。

2. 网格单元定义：根据所采用的空间分割方法，定义出网格单元（三角形或四面体）。

3. 网格生成：按照不同的算法，以空间分割和网格单元定义为基础，生成网格。

二、网格化算法在三维模型构建中的应用1. 三维扫描的网格化处理当我们需要将一个物体转换成三维模型时，常常需要先进行三维扫描。

扫描完成后，我们需要进行网格化处理，得到三维网格模型。

这个过程需要使用到网格化算法。

2. CAD设计的网格化处理CAD设计软件中通常进行建模操作时，是将实体模型转化成集合模型（如B-Rep模型），而网格模型又是集合模型与体数据之间的重要接口。

在实现CAD建模过程中，经常需利用网格化算法将B-Rep模型转化为网络模型，这都需要采用网格化算法。

3. 游戏开发的网格化处理在游戏的开发过程中，需要使用三维模型作为游戏场景的背景，如角色模型、场景模型等。

这些模型通常需要进行网格化处理，用于在游戏引擎中呈现。

4. 建筑学的网格化处理建筑学中也常常使用三维模型构建出建筑物的形状。

在这个过程中，也需要使用到网格化算法，将实体模型转化为网格模型。

三、网格化算法的优势与挑战1. 优势a. 精度高：网格化算法可以将复杂的图形分割成相对简单的网格单元，精度较高。

b. 方便优化：网格化算法将三维图形转换成了网格单元，在优化数据时，可以针对单个网格单元进行操作，具有方便优化的特点。

基于栅格法的三维六面体网格质量优化黄丽丽　赵国群山东大学,济南,250061摘要:对三维六面体网格质量优化技术进行了研究,分析了基于栅格法生成六面体网格的拓扑关系,提出了适合于六面体网格凸特征边界单元的四种点插入新单元模式和五种边界插入新单元模式、适合于凹特征边界为直线或者曲率变化较小时的四种单元退化模式,以及适合于凹特征边界曲率变化较大时的三种单元插入与退化结合模式。

并将拉普拉斯节点平滑技术和优化技术结合使用,以确保获得的六面体网格符合有限元数值模拟计算的要求。

若干实体模型算例表明,该算法实用性强,效果良好,通过优化能够得到较高质量的网格。

关键词:六面体网格;拓扑关系优化;插入新单元技术;单元退化技术中图分类号:TP391 文章编号:1004—132X (2009)21—2603—06Optimization of G rid -based Three -dimensional H exahedral MeshesHuang Lili Zhao GuoqunShandong U niversity ,Jinan ,250061Abstract :This paper st udied t he optimization technique for t hree -dimensional hexahedral ele 2ment mesh and analyzed t he topological connection of hexahedral element mesh generated by grid -based met hod.The proposed four new element point inserting modes and five new element edge inser 2ting modes are suitable for hexahedral element s on t he convex characteristic edges.The propo sed four element collap sing modes are suitable for hexahedral element s on t he straight or small curvat ure con 2cave characteristic edges.Three new element inserting combined wit h element collap sing modes suit 2able for hexahedral element s on t he concave characteristic edges of large curvat ure were propo sed.To insure t he generated mesh to satisfy finite element simulation ,Laplacian smoot h met hod was adopted in combination wit h optimization technique.Some examples were given to demonst rate t he effective 2ness and robust ness of t he met hod.K ey w ords :hexahedral element mesh ;topology optimization ;inserting technique ;collap sing technique收稿日期:2008—12—30基金项目:国家自然科学基金资助项目(50875155)0　引言有限元法是科学研究和工程应用领域中重要的数值模拟方法。

1引言近几年，随着光电技术和计算机技术的进步，三维数字化设备日益普及。

物体的三维数字化包括以下几个过程：三维传感、网格配准、网格合并和网格优化。

首先使用非接触式三维传感器得到物体多个侧面的扫描网格[3，21]，这些扫描网格包括物体表面的三维采样点和这些点如何连接的拓扑信息。

从不同侧面得到的扫描网格通过网格配准算法[5，18，10]被对齐，然后再通过网格合并被合并成一个单一的网格模型。

从三维扫描仪获得的扫描结果往往包含着噪声，而且在合并的过程中还会产生不规则的三角面，为了消除这些噪声和不规则三角面，最后还需要对合并后的网格进行优化。

文献[8，11，12]采用基于vironoi和deIaunay的方法从三维点云中重建网格模型，这类算法有严格的数学基础，成熟可靠，效果好，但是速度不高，而且忽略了扫描网格的拓扑信息。

文献[2]提出一种体合并算法，该算法的借鉴雕刻的方法，首先建立一个包含所有扫描网格的体素空间，然后逐个加入扫描网格。

每加入一个扫描网格，用合适的距离函数对体素累积特定的贡献值。

所有的网格加入完毕后，通过提取等值面得到物体表面的网格模型。

该算法简单，效果好，但是由于采用体素化处理，因此空间复杂度和时间复杂度较高。

文献[1]中提出一种直接在网格上进行操作的合并算法-zipper，该算法包括腐蚀和拉链两个步骤。

腐蚀就是交替删除待合并网格的冗余三角形直到它们的边界相交为止；拉链在腐蚀之后进行，先用其中一个网格的边界裁剪另一个网格的边界三角形，再用裁减得到的新顶点分割两个网格的边界三角形。

该算法的优点是直接在网格上进行处理，因此速度快，其缺点是裁剪操作会在“合并接痕”处产生大量细碎的三角面。

文献[13]提出一种基于光栅化的算法，该方法借助图形显示硬件将网格投影到屏幕上使其光栅化，然后在光栅化的深度图像上进行各种操作，包括重采样（重扫描）、网格合并等。

该方法简单快速，但是所能处理的网格密度受显示器分辨率的限制，因此只能处理比较简单的网格模型。

基于Opennesh的三维网格简化算法优化作者：丁文文来源：《电脑知识与技术》2017年第17期摘要：针对二次误差测度算法折叠排序代价计算标准单一导致模型在具有复杂结构的情况下特征难以保持的不足，提出了基于OpenMesh的三维网格简化算法。

在二次误差测度的基础上，通过引入折叠点度和折叠边长度作为计算折叠代价的辅助因素，较好地对网格进行了简化。

另外通过判断点、边和面是否处于边界来保持边界尽可能不变，以达到视觉特征基本不变的效果。

实验结果表明该算法在较好地保持模型视觉特征的情况下可以快速地对模型进行简化。

关键词：半边折叠；顶点度；折叠边长度；网格简化中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）17-0200-031概述随着计算机技术的快速发展，虚拟现实技术逐渐步人大众的视线。

但是在充分利用虚拟现实技术之前却面临着巨大的挑战。

一个主要的因素是虚拟现实中的模型通常非常巨大，这对硬件的要求往往会超过普通用户的承受标准，甚至有些场景即使当今比较先进的硬件也难以流畅地渲染，因此三维模型的简化仍需要继续研究。

例如斯坦福大学的数字米开朗琪罗计划中的大卫雕像的三角面片数高达20亿，远远超出了一般显卡的处理能力。

实际上早在20世纪七十年代就已经有了关于模型简化的讨论，也就是后来广泛应用的多细节层次（Levels of Detail，LOD）技术。

该技术通过简化模型细节来降低场景复杂度，从而保证场景能流畅地进行渲染和加载，尤其适合运用于当今火热发展的虚拟现实技术中。

根据简化机制，有学者将常用的简化算法分为顶点聚类（Veriex Clustering）、增量式简化（Incremental Decimation）、采样（Sampling）和自适应细分（Adaptive Subdivision）。

Schroeder首先提出了顶点删除的网格模型简化算法，随后基于边折叠、基于三角形删除等方法相继被提出，这些方法的共同点是删除网格模型中对外观影响较小的面片。

第28卷第12期计算机辅助设计与图形学学报Vol. 28 No.12 2016年12月Journal of Computer-Aided Design & Computer Graphics Dec. 2016三维有限元网格尺寸场光滑化的优化模型和算法王丁丁1), 肖周芳2,3), 陈建军2,3)*, 刘智伟2,3) , 余闯1)1) (温州大学数学与信息科学学院温州 325035)2) (浙江大学航空航天学院杭州 310027)3) (浙江大学工程与科学计算研究中心杭州 310027)(chenjj@)摘要: 针对单元尺寸值过渡剧烈会导致有限元网格包含低质量单元的问题, 提出基于优化原理的单元尺寸场光滑化理论及对应的几何自适应四面体网格生成算法. 首先输入CAD模型, 生成一套覆盖模型内部的非结构背景网格; 然后结合用户参数计算背景网格点上的曲率和邻近特征, 以获得自适应CAD模型几何特征的初始单元尺寸场; 再以最小化初始单元尺寸场的改变为目标, 以单元尺寸值过渡受控为约束, 通过求解一类凸优化问题光滑初始尺寸场; 最后以光滑后的尺寸场为输入, 先后在CAD模型表面与内部生成曲面网格和实体网格. 实验结果表明, 文中算法仅需5个用户参数, 即可在给定CAD模型内部全自动生成高质量的四面体网格.关键词：网格生成; 四面体; 单元尺寸; 自适应; 非线性规划中图法分类号：O242.21An Optimization Model and Algorithm for the Smoothing of Sizing Functions of Three-Dimensional Finite Element MeshesWang Dingding1), Xiao Zhoufang2,3), Chen Jianjun2,3)*, Liu Zhiwei2,3), and Yu Chuang1)1) (College of Mathematics and Information Science, Wenzhou University, Wenzhou 325035)2) (School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027)3) (Center for Engineering and Scientific Computation, Zhejiang University, Hangzhou 310027)Abstract: To avoid the generation of low-quality elements in regions where abrupt changes of element sizes are defined, a nonlinear programming problem (NLP) is formulated to help smooth the sizing function de-fined on an unstructured background mesh, and a geometry-based adaptive tetrahedral mesh generation al-gorithm is thus set up with this novel element-sizing smoothing algorithm as one of the key ingredients. The proposed algorithm inputs a valid and closed CAD model and creates an unstructured background mesh to cover the problem domain defined by this CAD model. Then, an initial sizing function can be set up by cal-culating a sizing value at each background mesh node. Note that this size value is adapted to the curvature and proximity features of the CAD model. After that, a convex NLP is solved to smooth this sizing function such that the changes of element scales are under control. By using the smoothed sizing function to control the distributions of element scales, high-quality surface and volume meshes can finally be produced on the surface and interior of the CAD model, respectively. Numerical experiments show that, the proposed algo-rithm can be executed in a fully automatic fashion, and the user could manipulate the results of this algo-收稿日期: 2016-05-12; 修回日期: 2016-07-14. 基金项目: 国家自然科学基金(11432013, 11172267, 51578427, 41372264); 浙江省自然科学基金杰出青年科学基金(LR16F020002). 王丁丁(1988—), 男, 硕士研究生, 主要研究方向为网格生成; 肖周芳(1986—), 男, 博士研究生, 主要研究方向为网格生成; 陈建军(1979—), 男, 博士, 副教授, 博士生导师, CCF高级会员, 论文通讯作者, 主要研究方向为网格生成、计算力学与高性能计算; 刘智伟(1991—), 男, 硕士研究生, 主要研究方向为网格生成; 余闯(1977—), 男, 博士, 教授, 硕士生导师, CCF高级会员, 主要研究方向为计算岩土力学.2098 计算机辅助设计与图形学学报第28卷rithm through five global user parameters.Key words: mesh generation; tetrahedra; element sizing; adaptive; nonlinear programming有限元分析已广泛应用于科学研究与工程设计和分析. 网格生成是有限元分析的前置处理步骤, 也是其主要性能瓶颈. 好的有限元网格需用尽量少的自由度获得尽量高的模型精度. 在问题域的不同位置采用不同尺寸的单元, 以适应几何特征(曲率、邻近等)和物理量梯度在问题域(指有限元分析涉及的几何区域)的变化, 是平衡自由度和模型精度双重目标的必然要求[1].初始单元尺寸场通常由用户指定, 或基于几何和物理特征自适应生成. 一般情形下, 初始单元尺寸场不满足光滑过渡的要求, 导致距离靠得很近的点其单元尺寸值相差很大, 不可避免地产生质量很差的过渡单元[2]. 因此, 如何合理地光滑化初始单元尺寸场, 使自适应于光滑后单元尺寸场的网格不包含质量很差的过渡单元成为网格生成领域的一个重要课题[3-17].与有限元数值解的定义类似, 有限元网格的尺寸场通常也“分片”定义在一套覆盖问题域的网格上. 为区分于有限元网格本身, 称这套网格为背景网格.三维问题中, 常用的背景网格形式有半结构化的八叉树网格[4-7]与非结构化的四面体网格[8-10,13-14]. 为获得光滑的单元尺寸定义, 八叉树网格要求相邻单元在树型数据结构中的深度值之差小于1, 这一要求使得单个单元细化操作需拓展到相邻单元, 容易造成网格规模庞大, 定义在其上的计算时空效率不佳. Pirzadeh(服务于美国航空航天局的一套非结构网格生成程序VGRID的主要开发者)正是因为这一理由放弃采用八叉树型的背景网格去控制体网格的尺寸场[5]. 非结构背景网格拓扑连接灵活, 不存在上述缺陷, 吸引了不少研究者的关注.本文探讨基于非结构背景网格的单元尺寸场光滑化算法. Borouchaki等[9]最早提出利用H- Variation和H-Shock变量衡量一维域(即直线)单元尺寸的变化快慢程度, 基于一套类似拉普拉斯光滑化的策略, 通过迭代修改已有网格点上的尺寸值来保证所有背景网格边上的H-Variation和H- Shock变量值小于用户指定的阈值(相应算法被称为H-Correction算法). 由于H-Correction算法并不能确保尺寸值在背景网格单元内部的变化也满足光滑过渡要求, Pippa等[10]以曲面问题为例(相应的背景网格单元为三角形单元), 在单元尺寸线性过渡的假设条件下提出了三角形背景网格单元内部尺寸场过渡受限时, 定义在单元节点上的单元尺寸场需要满足的不等式条件, 基于该条件以及与H-Correction类似的拉普拉斯光滑化过程; 他们还开发了一类被称为GradH-Correction的单元尺寸光滑化算法. 经GradH-Correction算法光滑的单元尺寸场在整个区域都能满足单元尺寸梯度受限的要求, 但由于该算法的启发式特性, 很容易过多地改变初始尺寸场, 导致自适应于光滑后尺寸场的有限元网格存在局部加密的缺陷. 显然, 网格规模的不必要加密对后续计算分析的效率不利. 此外, Persson[11]将单元尺寸过渡受控问题等价为一类Hamilton-Jacobi方程, 在背景网格上求解该方程的稳态解即可得到过渡受控的单元尺寸场. PDE方程的求解通常对计算网格单元的质量有特殊的要求, 应用该算法的困难主要在于如何构建高质量的背景网格.最近, Chen等[13-14]针对曲面网格生成问题, 以定义在背景网格节点上的尺寸值为设计变量, 把Pippa等[10]提出的三角形背景单元内部尺寸过渡受控作为约束条件, 把最小化单元尺寸场的改变作为目标建立优化模型, 将单元尺寸场光滑化问题等价为该优化问题的求解; 并从理论上证明了该优化模型的凸性和全局最优解的唯一性, 解决了H-Correction算法存在的背景网格单元内部单元尺寸不受控[9]与GradH-Correction算法存在过度细化的缺陷[10]. 与Persson[11]提出的PDE方程求解算法相比, Chen等提出的新算法已被证明可适应于以狭长面片为主的背景网格, 这放松了新算法在实际应用中对背景网格的要求. 在文献[13-14]中, 新算法被成功应用于全自动的几何自适应曲面网格生成.本文工作是文献[13-14]算法在三维体网格生成问题中的拓展:1) 三角形背景单元内部尺寸过渡受控不等式被拓展应用于四面体单元, 以其为约束条件, 以最小化单元尺寸场的改变为目标建立优化模型, 三维单元尺寸场光滑化问题等价为优化问题的求解.第12期王丁丁, 等: 三维有限元网格尺寸场光滑化的优化模型和算法 2099本文将从理论上证明该优化模型的凸性和全局最优解的唯一性.2) 为验证本文算法的适用性, 将其应用于几何自适应单元尺寸场的全自动生成, 结合Delau-nay 体网格生成算法[18-21], 实现了全自动、高质量的非结构有限元网格生成.最后, 通过多个有限元网格生成实例结果及分析对比, 验证本文算法的有效性.1 优化模型的推导和证明第1.1, 1.2节通过引入单位网格与等比网格的概念, 最终网格为单位网格且为等比网格是优化模型推导的2个假设条件(另一个假设条件是尺寸函数为线性函数). 基于上述假设条件, 第1.3节推导建立了直线边上尺寸过渡受控的不等式条件; 进一步, 第1.4节则推导建立了四面体背景单元内部尺寸过渡受控的不等式条件. 以第2类不等式条件为约束, 以最小化初始单元尺寸场的改变为优化目标, 第1.5节建立了与三维单元尺寸场光滑化问题等价的优化模型. 最后, 第1.6节证明了此优化模型是一个凸规划, 存在唯一全局最优解.1.1 单位网格如图1所示, 假设图中直线上的尺寸函数是()([0,1])h t t ∈, 直线的长度是l , 那么这条线上的网格段数101d ()n l t h t =⎰ (1) 每一条网格边表示为11d 1,1,2,,()i i t t l t i n h t +==⎰ (2) 给定一个定义在此直线上的矩阵2[1/()]h t =M , 那么在M 定义的空间内这条网格边的长度, 由式(2)知11()d 1,()1,2,,.i i iit t i t t l t l t h t i n ++∆====⎰⎰M 上述性质表明: 由M 定义的空间内一条理想的网格边的长度是单位1, 称之为单位网格[1,9,21].如果()h t 是一个线性函数, 0()(1)n h t t h th =-+, 代入式(1)可得0000/,ln(/)/(),n n n n l h h h h n l h h h h h h ==⎧=⎨⨯-≠⎩(3)假设网格段i a a i -1的长度是i l ∆, 则有1111/,,1ln(/)/(),,1,2,,i i i i i i i i i i l h h h h l h h h h h h i n ----∆==⎧⎪=∆⨯-≠⎨⎪=⎩(4) 1.2 等比网格和准等比网格在如图1所示的网格中, 1.0β∀≥, 如果111,,1,2,,11,,i i i i i i l l l i n l l l +++∆∆⎧∆⎪==-⎨∆<∆∆⎪⎩≥ββ, 则称这样的网格为等比网格, 其中β是等比因子.如果仅仅要求11,1,2,,1i il i n l +∆=-∆ ≤≤ββ, 则称这样的网格为准等比网格.1.3 直线边上尺寸过渡受控不等式条件假设图1的网格满足以下3个假设: 1) 单位网格; 2) 等比因子为β的等比网格; 3) 尺寸函数为线性函数.不失一般性, 假设0n h h >, 且1/,1,2,,1i i l l i n +∆∆==- β,根据式(4)可得111ln(/)ln(/)i i i i i i h h h h h h β++-∆=∆ (5) 其中, 11i i i h h h ++∆=-且-1i i i h h h ∆=-.由于尺寸遵循线性变化, 因此11//i i i i h h l l β++∆∆=∆∆= (6)根据式(5), (6)可得11//i i i i h h h h +-= (7) 假设0n h h h ∆=-, 直线边上任意一点尺寸为00(1),1,2,,i i i n i h w h w h h hw i n =-+=+∆= (8) 其中, 1//(1)/(1),1,2,,ii n i i j j w l l l l i n ===∆=--=∑ ββ (9)根据式(7)~(9)可得201111(2)/()i i i i i i h h w w w w w w -+-+∆=+-- (10) 将式(9)代入式(10), 化简后可得000(1)n n n n h h h h h h ββ∆=-=-⇒= (11)最后, 根据式(3), (11), 一条直线两端点间的尺寸差值与直线的长度的关系可以表示为0/ln n h l h h β∆=-= (12)尽管上述推导假设0n h h ≠, 式(12)也适用于=n h0h 情形. 此时=1β, 图1所示网格为均匀尺寸网格.Borouchaki 等[9]称/h l ∆为H-变量(H-Variation), 记为0()v n h a a , 其中0a 和n a 是直线边上的2个端点.2100计算机辅助设计与图形学学报 第28卷图1 直线边网格划分结果示意图当l 趋近于0时, H-variation 表示尺寸函数在某点的导数值.由此, 为限制图1所示网格相邻网格边长之比小于β, 直线边的H-Variation 需满足0()/ln v n h a a h l β=∆≤ (13) 1.4 背景单元内部尺寸过渡受控不等式条件 对于一个背景网格单元, 其单元边上的尺寸定义满足式(13)并不意味着单元内部的尺寸过渡也是受控的. 为说明这点, 图2给出了一个三角形背景单元, 其3条边的H-Variation 值满足式(13)(取=1.2β). 但是如图2a 所示, 在背景单元内部尺寸场的过渡很剧烈, 导致自适应于该尺寸场的网格包含很多狭长单元.本文考虑的是三维体网格生成问题[16-17,22-24],采用非结构四面体网格作为背景网格, 有必要讨论四面体单元内部单元尺寸过渡受控的条件. 如图3所示, 记四面体单元为T , 其覆盖的区域为TΩ, 在T Ω内任意一点p 的尺寸值可利用自然坐标计算.3T 0(,,)(,,),(,,)i i i h x y z x y z h x y z ωΩ==∈∑ (14)其中(0~3)i h i =为定义在4个节点上的尺寸值,(,,)(0~3)i x y z i ω=为p 点的体积坐标.四面体单元内部单元尺寸过渡受控的充要条件是T Ω内任意两点1p 和2p 满足式(13), 即122112()()()ln()v h p p h p h p p p β=-≤.其中, 12()v p p h 为直线边12p p 的H-variation; β≥1.0为等比因子; 1p 趋近于2p 时, 12()v h p p 表示尺寸函数(,,)h x y z 沿12p p 方向的方向导数.由于12p p 是沿着点1p 的任意方向, 可知211T 12max ()ln ,p hh p p ∀∈∂∇=∀∈∂≤ΩβΩp p T (15) 由式(14), 已知414141(,,)(,,)16(,,)i i i i i i i i i h x y z b h x h x y z h c h y V h x y z d h z ===⎛⎫⎛⎫∂ ⎪ ⎪ ⎪∂ ⎪ ⎪∂ ⎪ ⎪∇== ⎪∂ ⎪ ⎪ ⎪∂ ⎪ ⎪ ⎪ ⎪∂⎝⎭⎝⎭∑∑∑ (16) 其中V 为四面体体积. 取0~3i =, (1)%4j i =+,(2)%4k i =+, (3)%4m i =+, 则有11(1)11j j i i k k m my z b y z y z +=-, 11(1)11jj i i kk m mz x c z x z x +=-, mm k kj ji i y x y x y x d 111)1(1+-=. 其中, )3~0)(,,(=i z y x i i i 是4个节点的坐标.将式(16)代入式(15), 并经化简后可得四面体单元内部尺寸过渡受控不等式条件()2T 2ln h ∇=≤βH KH(17)图2 三角形域内的尺寸场及自适应于该场的网格第12期王丁丁, 等: 三维有限元网格尺寸场光滑化的优化模型和算法 2101其中, T 0123(,,,)h h h h =Η, 0,3ij i j k ⎡⎤=⎣⎦≤≤K 且2()/(36).ij i j i j i j k b b c c d d V =++很明显, K 是对称矩阵, 且主对角线元素都大于0.因此, 背景网格单元内部的尺寸场是否满足式(17)取决于等比因子β的取值(β代表和同1个点相邻的2条网格边边长的比值). 图2a 对应的尺寸场仅当 3.16β≥时才满足式(17)(实际为式(17)的二维版本), 这解释了为什么其对应的网格包含大量狭长单元. 图2b 中, 通过将三角形单元上部顶点的尺寸值从1.12调整为0.34, 对应的尺寸场当 1.2β≈时即可满足式(17), 相应地, 自适应调整后尺寸场的网格其质量得到大幅提高.1.5 单元尺寸场光滑化的约束优化模型假设{}|1,2,,i E e i m == 为背景网格的单元集合, {}|1,2,,i P p i n == 为节点集合. 给定用户参数 1.0β>, 根据式(17), 单元尺寸场过渡受控的必要条件是22()ln (),i i h e e E β∇∀∈≤ (18)其中, ()i h e ∇为背景单元i e 的尺寸梯度(式(16)).初始单元尺寸场通常不满足式(18), 通过求解下列约束优化问题, 通过调整节点上的尺寸值, 可使得基于优化解的新尺寸场满足式(18)()()120022min 0min ()()s.t ln (),()(),n i i i i i i i i h p h p h e e E h h p h p p Pβ-=⎧-⎪⎪⎨∇∀∈⎪⎪⎩∀∈∑≤≤≤ (19)其中, 0()i h p 和()i h p 分别是在节点i p 的初始尺寸值和最终尺寸值; min h 为用户参数, 防止单元尺寸值过小. 注意到初始尺寸值一般通过计算某些几何和物理特征得到, 最终的尺寸值应当不大于初始尺寸值, 以避免降低网格的分辨率, 最终影响分析精度. 与此同时, 最小二乘优化目标函数的设定可避免过度改变初始尺寸场.1.6 优化模型的数学性质首先证明式(19)代表的非线性规划问题(nonli-near programming problem, NLP)为凸规划, 进而证明式(19)存在唯一全局最优解. 不失一般性, 证明中假设β>1.0. 需要说明的是, 证明的结论也同样适用于β=1.0的特殊情形. 此时当0001011()min((),(),,()),i n h p h p h p h p p P -=∀∈时, 式(19)取得最优解.引理1. 式(19)的可行域是一个凸集. 证明. 假设011((),(),,())n u h p h p h p -= 是式(19)的解, 解的可行域12ΩΩΩ+=. 其中,}{T 21|ln , , 1,2,,)i i i i u e E i m Ωβ=∀∈=≤H K H ,}{2min 0|()(), , 1,2,,i i i u h h p h p p P i n Ω=∀∈=≤≤ . 定义在背景单元i e 的约束条件为T 220123(,,,)36ln ()i i i F F h h h h V *==-≤0.βH K H其中, V 是i e 的体积, 03~h h 是i e 的4个节点上的尺寸值, 而*2*0,336i i jk j k V k ⎡⎤==⎣⎦≤≤K K ,*()jk j k j k j k k b b c c d d =++.展开0123(,,,)F h h h h 可得T 01230123(,,,,1)(,,,,1)F h h h h h h h h =M ,其中[]0,4ij i j m =M ≤≤, 而22, 0,336ln (),4,40,.i j i j i j ij b b c c d d i j m V i j β++⎧⎪=-==⎨⎪⎩≤≤其他由此, 0123(,,,)F h h h h 的Hessian 矩阵为2T H 22F =∇==M M A A .其中,01230123212300b b b b c c c c d d d d ⎛⎫ ⎪⎪= ⎪ ⎪⎝⎭A . 因为T T 4H 2()()0 (,0)=∀∈≠≥ x M x Ax Ax x x ,所以H M 是一个半正定矩阵. 因此, 函数F 是一个凸函数, 凸函数的下水平集0F ≤是一个凸集[25]. 显然, 由m 个这样凸集组成的交集1Ω也是一个凸集.由于2Ω是由n 个箱型约束组成的凸集, 因此,可行域12=+ΩΩΩ是一个凸集.证毕.引理2. 式(19)为凸规划. 证明. 式(19)的目标函数201()(()())ni i i f h p h p ==-∑v是一个二元函数, 其Hessian 矩阵为2()2f f u =∇=M I .其中I 是单位矩阵. 因为T 40 (,0)f >∀∈≠x M x x x ,所以目标函数是凸函数[25]. 再由引理1, 可知式(19)是一个凸规划. 证毕.2102计算机辅助设计与图形学学报 第28卷定理 1. 式(19)存在可行解, 且其局部最优解即为其全局最优解.证明. 注意到min h 为用户参数, 因此总可以调整min h 的值, 使得 min 01020min((),(),,())n h h p h p h p <成立. 存在实数δ, 满足min 01020min((),(),,())n h h p h p h p << δ.1.0β∀≥. 向量12((),(),,())(,,,)n h p h p h p δδδ== v满足不等式2T 2()0ln (), .i i i i i h e e E ∇==∀∈≤βH K H因此, v 是式(19)的可行解. 如果 1.0β>, v 严格满足的约束式(19)条件, 这意味着它是式(19)可行域的一个内部点.易知, 可行域存在至少1个内部点的凸优化问题, 其局部最优解即为其全局最优解[25]. 证毕.2 几何自适应网格生成输入CAD 模型, 执行图3所示的算法流程, 即可输出最后的几何自适应体网格. 整个算法步骤如下:Step1. 背景网格生成. 获得CAD 曲面模型的STL 表征(主要由狭长三角面片构成), 随即调用约束Dela-unay 四面体算法(不生成内部Steiner 点)[18-19]获得覆盖问题域的非结构背景网格(由狭长的四面体单元组成).Step2. 初始尺寸场定义. 针对位于曲面模型上的每个背景网格点, 计算该点的曲率自适应尺寸值和邻近自适应尺寸值[1,14,26]. 该点的初始尺寸值为上述计算获得值的最小值; 此外, 该值还必须限定在用户定义的最大和最小尺寸值(max h 和min h )之间.Step3. 尺寸场光滑化. 利用内点法求解式(19). 当前, 本文利用开源程序IPOPT 求解[27-28].Step4. 曲面网格生成. 输入CAD 模型和光滑后的尺寸场, 调用自主开发的基于前沿推进法的曲面网格生成程序离散所有参数曲面[1,14,26,29].Step5. 体网格生成. 输入曲面网格和光滑后的尺寸场, 调用自主开发的基于Delaunay 三角化理论的四面体网格生成程序生成体网格, 结合网格光滑化和拓扑变换操作优化网格质量[1,18-19].该算法中, 用户需要输入5个全局参数. 除以上提及的等比因子β与最大、最小尺寸值(max h 和min h )外, 用户还需要定义曲率自适应参数c ϕ与邻近自适应参数d μ[1,14,26]. 多数情形下(包括第4节的所有实验), c ,βϕ与d μ可取其缺省值1.2, 10°和2, 分别代表期望的相邻网格边长比最大值、多少曲率圆心角对应1条网格边(c 10ϕ=︒代表一个完整的圆周需要离散成36段), 以及邻近的2条曲线之间的界面上期望的网格边数(d 2μ=代表离散成2段);max h 和min h 则和模型的尺寸、用户对整体网格规模的期望相关. 一般而言, max h 决定了无几何特征图3 全自动几何自适应体网格生成算法流程第12期王丁丁, 等: 三维有限元网格尺寸场光滑化的优化模型和算法 2103区域的网格尺寸, minh则是为了防止不稳定的曲率计算使得局部单元尺寸过小.除上述5个参数外, 图3所示算法流程执行过程中不再涉及任何人工干预, 完全自动运行.如图3所示, 曲面网格和体网格都是在光滑后的尺寸场控制下生成的, 以保证网格的高质量. 曲面网格生成采用的是间接法, 即先利用前沿推进技术在曲面的参数空间生成网格, 随即将网格点反投影到曲面的实空间[1,14,26]. 体网格采用的是Delaunay三角化算法[1,18-19], 它以曲面网格生成结果为输入, 步骤如下:Step1. 获得输入点集的Delaunay三角化.Step2. 恢复所有的遗失边界边和边界面.Step3. 根据单元尺寸要求自动在问题区域内部步骤点, 并利用Delaunay三角化算法插入这些点.Step4. 优化初始网格质量.注意, 曲面以及实体网格生成算法均需频繁调用如下关键函数: 给定一个点, 求解该点上的尺寸值. 最简单的办法是遍历背景单元列表, 直至找到包含该点的背景单元(称之为基单元), 随即利用线性插值计算给定点的尺寸值. 但是, 该算法寻找基单元时的线性搜索效率是无法忍受的, 利用Walk-through技术可将搜索长度(即搜索一个基单元平均需遍历的背景单元数)降低到个位数[1,14].Walk-through技术的实现主要包含2步:Step1.给定一个单元, 作为基单元的初始猜测;Step2.利用背景单元的拓扑相邻关系, 从基单元的初始猜测出发, 沿一条“最短”的路径找到真正的基单元.基单元的初始猜测是否靠近真正的基单元是决定上述算法效率的关键. 无论是基于前沿推进法还是基于Delaunay三角化算法, 都可以在利用Walk-through技术查询某个网格点的尺寸值时给出很好的初始基单元猜测.前沿推进法的关键步骤是选定一条活跃前沿边(三维为面), 然后尝试生成一个新网格点, 新网格点和选定的前沿形成一个几何质量最优的单元. 此时, 网格生成算法需计算新网格点的尺寸值. 以选定前沿边(三维为面)的端点对应的基单元(在前面的计算中已得到)为新网格点基单元的初始猜测, 很快就可找到新网格点的真正基单元.本文实现的Delaunay网格生成算法采用在网格单元(称之为母单元)的重心处插入新网格点、不断细化网格的策略[1,18-19]. 以母单元的端点对应的基单元(在前面的计算中已得到)为新网格点基单元的初始猜测, 很快可找到新网格点的真正基单元.上述讨论的是内部网格点尺寸值的快速查询,边界点的快速查询可采用如下策略:Step1. 对所有边界点进行某种排序(如希尔伯特排序), 保证几何邻近的点排列在一起.Step2. 计算后面点的尺寸值时, 以前面相邻点对应的基单元(已经预先计算得到)为新网格点基单元的初始猜测.网格优化算法主要利用光滑化与局部重连操作,只在少量存在极差单元的区域结合边重叠和边分裂操作进一步优化网格质量. 优化后的网格与尺寸场的自适应程度会有降低, 但由于网格点的规模基本保持不变, 优化后的网格基本还是和用户期望的尺寸变化一致的, 且相比初始网格, 网格的单元质量会有大幅度的提升.3 实验结果及分析选取8个模型, 图4给出了本文算法的网格生成结果. 本文实验在一台ThinkPadE431便携式电脑上完成(2.6 GHz, 4 GB CPU).水泵齿轮发动机圆圈鱼缸钢圈筒子螺丝钉图4 算例的网格生成结果所有实验中, 用户仅需给定CAD模型与5个全局参数, 本文算法即可全自动运行, 中间无需任何人工干涉. 从表1所示的单元质量数据可以看出, 自动生成的网格没有12°以下的角, 各模型网格中,最小角为12°~24°的单元所占百分比最高也仅0.95%(螺丝钉模型), 而最小角为24°以上的单元所占百分比均超过99%. 基于以往的经验, 这样的网格完全可以满足有限元分析对单元质量的要求.表1同时列出了算法执行的总时间以及其中尺寸场光滑化所消耗的时间. 相对其他步骤, 式(19)的求解是比较耗时的. 但考虑到整个算法的全自动特性, 相对于传统的需要人工干涉定义尺寸2104计算机辅助设计与图形学学报 第28卷表1 网格基本数据、单元质量数据与网格生成主要时间数据模型 曲面单 元数目体单元 数目最小内角/(°) 最大内角/(°)0°~12°数目 占比/%12°~24°数目占比/%生成网格 时间/s 优化时间/s占比/%水泵 18 818 56 925 9.35 166.100 0 179 0.09 26.743 18.501 69.18 齿轮 19 906 156 891 15.01 152.3008 8.50E -6 26.962 15.641 58.01发动机 93 600 1 068 014 15.02 160.120 0 2 534 0.04 209.332 98.771 47.18 圆圈 23 080 104 021 15.43 160.950 0 749 0.12 26.215 15.875 60.56 鱼缸 38 370 121 496 15.11 157.210 0 549 0.09 31.174 20.860 66.91 钢圈 43 788 185 227 15.15 158.680 0 883 0.07 45.859 25.376 55.33 筒子 6 842 14 763 19.00 150.230 0 37 0.04 2.434 1.425 58.55 螺丝钉2 678 12 448 12.41 166.70703 0.95 7.257 5.412 74.58场的方式, 本文算法有更大的应用潜力. 为进一步说明这点, 图5给出了利用传统网格源方式控制水泵模型网格生成的效果[1,5], 其中, 图5a 展示了网格源配置, 它在自主开发的前处理软件高端数字样机系统(high end digital prototyping, HEDP)中利用交互式界面工具完成[30], 包含22个线源. 多年的经验表明, 即使是HEDP 软件的熟练操作者, 人工交互过程通常需耗时1 h. 而在全自动模式下, 这一过程仅耗时约27 s. 此外, 图5b, 5c 对比了利用网格源生成的网格和本文算法生成的网格, 可以看出, 两者规模大致相当(体单元数: 56265 vs.56925), 本文算法生成的网格单元最小角略大(7.38° vs. 9.35°), 且最小角12°以下的单元更少(18 vs. 0).a. 网格源配置b. 基于网格源算法c. 本文算法图5 2种算法控制的水泵模型体网格生成结果对比为验证选取合适的尺寸场光滑化算法的重要性, 本文选取发动机模型, 分别对比了初始尺寸 场、H-Correction 算法[9]优化后的尺寸场(以初始尺寸场为输入), 以及利用本文算法光滑后的尺寸场对应的网格生成结果. 图6~7分别给出了不同尺寸场云图以及自适应于不同尺寸场的体网格局部剖切图. 从图7可以看出, 本文算法对应的网格单元尺寸过渡控制良好; 而其他2套网格均存在尺寸剧烈过渡的情形, 导致网格中不可避免地包含了质量很差的单元.为定量衡量单元尺寸场的过渡效果, 本文将不等式(17)变化为等式2T 2ln h β∇==H KH .给定一个尺寸场, 针对每个背景网格单元, 可以计算其对应的“真实等比因子”β=.据此, 可以设计一个“累计比”函数()r x β( 1.0)x ≥, 统计真实等比因子小于x 的背景网格单元占背景网格单元总数的百分比. 图8a 给出了图6所示不同尺寸场累计比函数的曲线, 可以看出, 初始尺寸场的真实等比因子分布很不理想, 其最大值为42.32, 且真实等比因子小于 1.2(用户给定的最大值)的背景单元百分比仅为40%左右; H-Correction 算法将真实等比因子的最大值减少为28.18, 但真实等比因子小于1.2的背景单元百分比仍然为40%左右; 而本文算法光滑得到的尺寸场所有背景单元的真实等比因子被控制在1.2之下.上述差别最终体现在网格的单元质量上. 图8b 对比了自适应于上述不同尺寸场的体网格的单元二面角分布. 可以看出初始尺寸场及H-Correction 算法光滑后的尺寸场对应的体网格中均包含非常小(0.07°)和非常大的二面角(179.79°), 利用本文算法产生的网格最小和最大角分别为15.02°和160.12°; 此外, 本文算法生成的体网格单元二面角40°以下、105°以上的角度的数量远少于另外2套网格.。

改进的三维ODT四面体网格质量优化算法1. 引言1.1 背景介绍1.2 研究意义和目的1.3 国内外研究现状1.4 本文主要内容和贡献2. 相关理论知识和算法2.1 四面体网格概述2.2 三维ODT方法简介2.3 基础的质量优化算法2.4 瓶颈问题和改进思路3. 改进的三维ODT质量优化算法设计3.1 优化方法的基本思路3.2 改进后的算法原理分析3.3 算法细节设计3.4 算法流程介绍4. 仿真实验及结果分析4.1 仿真实验介绍4.2 对比实验设计4.3 结果分析和比较4.4 实验数据可视化和解释5. 结论和展望5.1 主要研究成果回顾5.2 存在的不足和改进方向5.3 未来研究展望6. 参考文献第一章节为“引言”，对本文的研究背景、意义、目的、国内外研究现状和本文主要内容和贡献做出概述和介绍。

在本文中，我们将介绍一种改进的三维ODT四面体网格质量优化算法。

本文的主要目的是针对四面体网格存在的质量劣化问题，基于三维ODT方法设计一种高效、自适应的质量优化算法，以提高四面体网格的质量。

在三维无结构网格中，四面体网格是广泛应用的一类，因其拓扑性质、性能受力均匀等特点，在模拟各种工业、物理、生物过程中具有重要应用价值。

然而，四面体网格的质量缺陷多、不均匀的特征，限制了其在实际应用中的进一步应用。

因此，开发高效的质量优化算法，增强四面体网格的质量，具有重要的理论和实用意义。

目前国内外关于四面体网格质量优化算法的研究，主要集中在基于数学优化方法、逆距离加权法和三角网格上的辅助四面体加密等方法。

综合这些方法的优缺点，进一步提高四面体网格质量的一种有效方法是采用三维ODT方法进行质量优化。

本文提出的改进算法，基于三维ODT方法，对四面体网格的质量进行有效提升。

具体而言，我们通过对三维ODT方法的改进，增强算法的自适应能力和优化速度，并在此基础上导出一套适用于四面体网格的优化算法。

算法包括以下两个基本过程：（1）优化网格点的分布；（2）通过对网格的局部细化和缩减，实现网格的自适应优化。

目录第一章 空间网格结构体系简介与设计要点 (5)1.1 空间网格结构体系简介 (5)1.2 空间网格结构体系设计要点 (7)第二章 网架与网壳结构功能说明 (12)2.1 结构建模 (12)2.2 显示查询 (22)2.3 构件属性 (22)2.4 荷载编辑 (23)2.5 内力线性及非线性分析 (24)2.6 设计验算 (24)2.7 节点设计 (25)2.8 施工图 (41)第三章 桁架结构功能说明 (46)3.1 结构编辑 (46)3.2 显示查询 (49)3.3 构件属性 (49)3.4 荷载编辑 (49)3.5 内力线性及非线性分析 (50)3.6 设计验算 (50)3.7 桁架节点验算 (50)3.8 后处理 (53)3.9 施工图 (67)3.10 相贯加工 (70)第四章 屋架结构功能说明 (76)4.1 结构编辑 (76)4.2 杆件设计 (76)4.3 实体模型 (78)4.4 节点设计 (83)4.5 施工图 (86)第五章 例题 (95)5.1 螺栓球网架 (95)5.2 焊接球网架 (102)5.3 网架下部为橡胶支座带混凝土柱网架 (102)5.4 网架模块的加锥、及模型包络的功能例题 (107)5.5 网架模块加吊车、辅助孔以及基准孔拟合功能例题 (109)5.6 直线空间桁架 (112)5.7 曲线空间桁架 (118)5.8 四边形廊桥模型及出相贯下料数据 (121)5.9 部分相贯桁架节点 (127)5.10 钢网架设计与分析 (129)5.11 网架-框架混合结构分析与设计 (139)5.12 带橡胶支座的网架结构分析与设计 (145)第六章 空间网格建模常见问题 (148)第一章 空间网格结构体系简介与设计要点1.1空间网格结构体系简介空间网格结构(space frame structures)是空间结构的一种，也是我国空间结构中发展最快、应用最广的结构形式。

三维空间实现全覆盖的传感节点优化分布算法
王亚丽;周运
【期刊名称】《河南师范大学学报：自然科学版》
【年(卷),期】2012(40)3
【摘要】针对无线传感网中重要的覆盖问题,已有多种算法来解决这个问题.通过分析这些算法,提出了一种三维空间下的基于网格点的随机算法的改进算法.算法分为两个阶段,初始阶段采用随机算法获得一个初始部署集以实现完全覆盖,在此基础上对初始部署集进行优化,达到在满足完全覆盖的前提下部署集的最小化.实验结果显示了算法在实现最大覆盖的基础上部署集优于已提出的贪心算法和线性规划算法.【总页数】4页(P166-169)
【关键词】传感网络;覆盖;部署集;随机分布;三维空间
【作者】王亚丽;周运
【作者单位】河南师范大学计算机与信息技术学院
【正文语种】中文
【中图分类】TP393.1
【相关文献】
1.基于遗传算法实现确定性区域覆盖的传感器节点部署方法 [J], 张雅楠;
2.无线传感器网络中的最优感知节点分布及分布优化算法 [J], 闻英友;冯永新;王光兴
3.改进遗传算法的传感器节点覆盖优化策略 [J], 向才辉
4.改进人工鱼群算法的无线传感器网络节点覆盖优化 [J], 张微微;杨海宁
5.分布式无线传感器节点覆盖集近似算法研究 [J], 洪刚;汤宝平;裴勇
因版权原因，仅展示原文概要，查看原文内容请购买。