Question

拓扑优化

Answer 1

3.5.2.1 边交换

拓扑优化方法的思想通过改变网格的拓扑结构来提高网格质量。二维时，最常用的是边交换算法。类似于Delaunay三角剖分中涉及的最小角最大化特性，应尽量使三角网格中每个三角形单元避免出现狭长的角。二维三角形网格中，针对共用一条边的一对三角形组成的凸四边形，通过改变上述三角形对的共用边(即凸四边形的对角线)进行局部重构从而提高三角形对的质量。

图3.27 边交换方法

如图3.27所示，两个相邻三角形所形成的四边形的4个顶点分别为A、B、C和D，并且，∠ACB=α₁，∠ADB=α₂，A、B、C三点确定一个圆，D相对于此圆有3种情形，相应地，凸四边形的对角线也有3种选择:

(1)当点D位于圆上，即α₁+α₂=π时，理论上可以任意选择对角线，但为了获得最好的三角形形态，分别计算交换对角线之前的原三角形对的最小内角，再计算交换对角线之后形成的新三角形对的最小内角，比较两个情况下最小内角的大小，若交换对角线之前的最小内角大，则不用交换对角线，反之，交换对角线。

(2)当点D位于圆内，即α₁+α₂＞π时，交换对角线，删除三角形对ΔABC、ΔADB共用边AB，连接CD，组成新的三角形对ΔADC、ΔBCD。

(3)当点D位于圆外，即α₁+α₂＜π时，不需要交换对角线。

上述做法与Delaunay三角剖分方法中的Lawson算法的LOP方法基本相同，该方法需要计算三角形的外接圆和判断点是否落在圆内，下面给出一种直接根据三角形对的4个顶点坐标判断是否需要交换对角线的方法。

设A、B、C和D四个点的坐标分别为(x₁，y₁)、(x₂，y₂)、(x₃，y₃)和(x₄，y₄)，由余弦定理可得:

sin(α₁+α₂)=((x₁-x₃)×(y₂-y₃)-(x₂-x₃)×(y₁-y₃))+((x₂-x₄)×(x₁-x₄)+(y₂-y₄)×(y₁-y₄))+((x₁-x₃)×(x₂-x₃)-(y₁-y₃)×(y₂-y₃))×((x₂-x₄)×(y₁-y₄)-(x₁-x₄)×(y₂-y₄))

因此可以根据sin(α₁+α₂)的符号决定是否交换对角线:

(1)当sin(α₁+α₂)=0时，可任意选择对角线。

(2)当sin(α₁+α₂)＜0时，需要交换对角线。

(3)当sin(α₁+α₂)＞0时，不需要交换对角线。

实际应用时，不需要采用边交换方法使每个三角形都满足空外接圆特性，而只要针对某些明显需要边交换的三角形对，如两个三角形的最大角都为钝角且两个最大角对应的边为该三角形对的共用边，如图3.28所示，存在大量这样的三角形，此时，对上述三角形进行边交换将显著提高网格质量，同时为了避免交换后质量降低，判断交换前后三角形对的6个内角的最小角度的大小:若交换前三角形对的6个内角中的最小角小于交换后新的三角形对的最小内角，则交换对角线，反之，不交换。

图3.28 边交换方法优化三角形网格实例

在VC++环境下，上述算法的完整代码如下，其中函数EdgeSwap(CSurf*surf)为边交换主函数，进行边交换操作;该函数调用的MaxAngleInTrgl()和MinAngleInTrgl()的作用是分别计算一个三角形内最大角和最小角。

三维地质建模方法及程序实现

三维地质建模方法及程序实现

三维地质建模方法及程序实现

三维地质建模方法及程序实现

3.5.2.2 插入/删除点

网格单元中，往往要衡量单元某一边与边中点处期望长度的比例，二维中这个比例的理想值是1.53，如果这个比例太大就要将边分解，插入点可以用来改变这个比例，并且通过仔细选择点插入的位置可以控制单元的几何形状，达到单元优化的效果。网格加密方法中的二分法实质上也是一种通过插入某些边的中点的拓扑优化方法。

二分法是将边的中点作为加密点的一种递归算法。具体方法为:先将三角形网格中长度大于设定阈值的边的中点作为新结点，之后按照图3.29所列3种情况重新划分三角形并更新相应的三角形及边的邻接关系，并将新三角形投入下一循环进行边长判断，直到所有边长均小于或等于相应的阈值为止。

图3.29 二分法加密结点与单元重划分

删除点的操作主要是作为一种重定义技术。许多实例当中，通过删除一个区域的网格完成删除点的操作，然后重新选择长度比例对这个空腔进行网格重新生成。点删除技术的不同应用也可以用来改善单元的几何形状达到网格优化的目的。最常见的做法是当两点距离小于某一个阈值时，删除这两点，并加入这两点的中点，且更新通过上述两点的网格单元的拓扑。