PyMeshGen 混合网格生成技术：三角形/四边形混合算法详解

PyMeshGen 实现了基于阵面推进法（Advancing Front Method）的三角形/四边形混合网格生成算法，参考Pointwise中的Advancing Front和Advancing Front Ortho方法能够生成尽量正交的三角形/四边形混合网格和随机的三角形/四边形混合网格。本文将深入解析这一核心算法的实现原理。

一、引言

在计算流体力学（CFD）和有限元分析（FEA）中，网格类型的选择对计算效率和精度有着重要影响：

• 三角形网格：适应性强，能够处理复杂几何，但数值耗散较大
• 四边形网格：数值精度高，单元质量好，但对几何适应性较弱

混合网格（Hybrid Mesh）结合了两者的优势：

• 在规则区域使用四边形，保证计算精度
• 在复杂区域使用三角形，提高适应能力
• 整体网格质量高，生成效率好

PyMeshGen 实现了基于阵面推进法（Advancing Front Method）的三角形/四边形混合网格生成算法，参考Pointwise中的Advancing Front和Advancing Front Ortho方法能够生成尽量正交的三角形/四边形混合网格和随机的三角形/四边形混合网格。本文将深入解析这一核心算法的实现原理。

二、算法总体框架

2.1 核心思想

混合网格生成的核心思想是：优先尝试生成四边形，失败时回退到三角形。

基本流程：

当前阵面 Front    ↓尝试生成四边形（2 个新点）    ↓质量检查 & 碰撞检测    ├─ 成功 → 生成四边形单元    └─ 失败 → 尝试生成三角形（1 个新点）            ↓        质量检查 & 碰撞检测            ↓        生成三角形单元

这种”优先四边形，回退三角形”的策略，能够在保证网格质量的前提下，最大化四边形的比例。

2.2 算法参数

PyMeshGen 中的混合网格生成算法通过多个参数控制网格生成过程：

classAdfront2Hybrid(Adfront2):def__init__(self, boundary_front, sizing_system, ...):# 四边形搜索范围系数        self.al = 0.8# 四边形搜索范围 = 0.8 × 当地步长# 质量折扣系数        self.discount = 0.8# Pbest 质量折扣，影响候选点选择概率# 网格类型标识        self.mesh_type = 3# 1-三角形，2-直角三角形，3-混合# 四边形质量阈值        self.quality_criterion = 0.5# 低于此质量的四边形将被舍弃# 邻近检查容差        self.proximity_tol = 0.5# 阵面与节点邻近的距离容差# 阵面排序控制        self.sort_front = False# 是否按阵面长短顺序推进

参数物理意义：

三、四边形生成算法

3.1 新点生成策略

四边形生成需要计算2 个新顶点。PyMeshGen 采用基于局部几何特征的智能策略：

几何示意：

算法步骤：

defadd_new_points_for_quad(self, spacing):"""计算四边形的 2 个新顶点"""# 基准参数    theta1 = 120# 小角度阈值    theta2 = 200# 大角度阈值    l = self.base_front.length  # 当前阵面长度    d0 = spacing  # 当地网格步长    d = d0  # 新点推进距离# 对当前阵面的两个端点分别计算新点for base_p in self.base_front.node_elems:# 获取左右邻阵面        neighbor1, neighbor2 = base_p.node2front# 计算邻阵面夹角        angle = calculate_angle(pb.coords, base_p.coords, pa.coords)# 根据夹角选择新点位置if angle < theta1:# 小角度：使用邻阵面的另一个端点            pnew_elem = pa 或 pbelif angle > theta2:# 大角度：沿法向推进            pnew = base_p.coords + normal_vec * d            pnew_elem = NodeElement(coords=pnew, ...)else:# 中等角度：沿角平分线推进            angle = np.radians(angle) / 2            rotated_vector = rotate(neighbor2.direction, angle)            pnew = base_p.coords + rotated_vector * d            pnew_elem = NodeElement(coords=pnew, ...)

角度选择策略：

3.2 候选点质量评估

生成 2 个新点后，需要在候选点列表中选择最优的 2 个点构成四边形。PyMeshGen 采用多源候选 + 质量评分的方法：

候选来源：

# 四种候选情况candidate_sources = [# 1. 常规候选对：从所有候选点中任选 2 个    ([(n1, n2) for n1 in candidates for n2 in candidates if n1 != n2], 1.0),# 2. Pbest[1] 组合：一个点来自候选列表，另一个为最优候选点 1    ([(n, self.pbest[1]) for n in self.node_candidates], 0.8),# 3. Pbest[0] 组合：一个点来自候选列表，另一个为最优候选点 0    ([(self.pbest[0], n) for n in self.node_candidates], 0.8),# 4. Pbest 对：两个点都是最优候选点    ([(self.pbest[0], self.pbest[1])], 0.64),  # 0.8^2]

质量评分：

scored_candidates = []for candidates, discount in candidate_sources:for elem1, elem2 in candidates:# 计算四边形质量（0~1，1 为最好）        quality = quadrilateral_quality2(p0, p1, elem2.coords, elem1.coords)# 应用质量折扣        discounted_quality = quality * discount# 只保留高于阈值的候选if discounted_quality > quality_criterion:            scored_candidates.append((discounted_quality, elem1, elem2))# 按质量降序排序（质量高的优先）scored_candidates.sort(key=lambda x: x[0], reverse=True)

质量折扣的物理意义：

• 新生成的点（Pbest）质量评分最高（折扣 1.0）
• 使用已有点时，质量评分打 8 折
• 鼓励使用新生成的点，提高网格规则性

3.3 几何检查

选择候选点时，需要进行多项几何检查，确保生成的四边形合法：

检查 1：方向检查

# 确保候选点在当前阵面的左侧（阵面推进方向）ifnot (is_left2d(p0, p1, node_elem1.coords) and is_left2d(p0, p1, node_elem2.coords)):continue# 排除方向错误的候选

检查 2：碰撞检测

defis_cross_quad(self, node_elem0, node_elem1):"""检查待生成四边形是否与已有单元/阵面相交"""# 检查新边是否与已有阵面相交    new_edges = [        LineSegment(node_elem0, p0),        LineSegment(node_elem1, p1),        LineSegment(node_elem0, node_elem1),    ]for front in self.front_candidates:        front_line = LineSegment(front.node_elems[0], front.node_elems[1])if any(front_line.is_intersect(edge) for edge in new_edges):returnTrue# 与阵面相交# 检查是否与已有单元相交    cell_to_add = Quadrilateral(p0, p1, node_elem1, node_elem0)for existed_cell in self.cell_candidates:if existed_cell.is_intersect_quad(cell_to_add):returnTrue# 与单元相交returnFalse

检查 3：邻近检查

defproximity_check(self, node_elem1, node_elem2, distance):"""检查新增阵面是否过于靠近已有节点"""# 检查新边到已有节点的距离    edges = [        (node_elem1, node_elem2),        (p0, node_elem1),        (p1, node_elem2),    ]for edge in edges:for node in self.node_candidates:            dis = point_to_segment_distance(node.coords, edge[0].coords, edge[1].coords)if dis < distance:returnTrue# 距离太近# 检查新节点到已有阵面的距离    nodes = [node_elem1, node_elem2]for node in nodes:for front in self.front_candidates:            dis = point_to_segment_distance(node.coords,                                            front.node_elems[0].coords,                                            front.node_elems[1].coords)if dis < distance:returnTrue# 距离太近returnFalse

检查 4：尺寸检查

defsize_too_big(self, node_elem1, node_elem2, spacing):"""检查四边形面积是否过大"""    p0 = self.base_front.node_elems[0].coords    p1 = self.base_front.node_elems[1].coords# 计算四边形面积    area = quadrilateral_area(p0, p1, node_elem2.coords, node_elem1.coords)# 面积阈值 = 1.3² × spacing²if area > 1.69 * spacing * spacing:returnTrue# 面积过大returnFalse

3.4 最优选择

通过所有检查后，选择质量最高的候选对：

self.pselected = Noneself.best_flag = [False] * 2for quality, node_elem1, node_elem2 in scored_candidates:# 依次进行各项检查ifnot is_left2d(...):continueif is_cross_quad(...):continueif proximity_check(...):continueif size_too_big(...):continue# 所有检查通过，选择该候选对    self.pselected = [node_elem1, node_elem2]break

四、三角形生成算法

4.1 回退机制

当四边形生成失败时，算法自动回退到三角形生成：

defgenerate_elements(self):while self.front_list:# ... 前置处理# 尝试生成四边形        self.add_new_points_for_quad(spacing)        self.search_candidates(self.base_front.al * spacing)        self.select_point_for_quad(spacing)# 四边形生成失败，尝试生成三角形        self.add_new_point_for_tri(spacing)        self.select_point_for_tri()# 更新数据        self.update_data_quad()  # 如果生成了四边形        self.update_data_tri()   # 如果生成了三角形

回退条件：

• 找不到满足质量要求的四边形候选点
• 所有候选点都未通过几何检查
• 碰撞检测或邻近检查失败

4.2 三角形生成逻辑

三角形生成与四边形类似，但只需要1 个新点：

defadd_new_point_for_tri(self, spacing):"""如果四边形生成失败，尝试生成三角形"""if self.pselected isnotNone:return# 四边形已成功，不需要生成三角形    self.mesh_type = 1# 标记为三角形    self.add_new_point(spacing)  # 生成 1 个新点defselect_point_for_tri(self):"""选择点生成三角形"""if self.pselected isnotNone:return# 四边形已成功    self.select_point()  # 从候选点中选择最优的 1 个点

4.3 数据更新

生成三角形后的数据更新：

defupdate_data_tri(self):if self.pselected isNone:return# 没有生成三角形if isinstance(self.pselected, list) and len(self.pselected) == 2:return# 已生成四边形，不需要更新三角形数据# 更新阵面    new_front1 = Front(        node_elem1=self.base_front.node_elems[0],        node_elem2=self.pselected,        ...    )    new_front2 = Front(        node_elem1=self.pselected,        node_elem2=self.base_front.node_elems[1],        ...    )    self.update_fronts([new_front1, new_front2])# 更新单元    new_cell = Triangle(        p1=self.base_front.node_elems[0],        p2=self.base_front.node_elems[1],        p3=self.pselected,        part_name="interior-triangle",        idx=self.num_cells,    )    self.update_cells(new_cell)

五、数据结构更新

5.1 四边形数据更新

defupdate_data_quad(self):# 检查是否生成了四边形if (self.pselected isNoneornot isinstance(self.pselected, list) or len(self.pselected) != 2):return# 更新节点    self.update_nodes()# 更新阵面（生成 3 个新阵面）    new_front1 = Front(node_elem1=p0, node_elem2=pselected[0], ...)    new_front2 = Front(node_elem1=pselected[1], node_elem2=p1, ...)    new_front3 = Front(node_elem1=pselected[0], node_elem2=pselected[1], ...)    self.update_fronts([new_front1, new_front2, new_front3])# 更新单元    new_cell = Quadrilateral(        p1=self.base_front.node_elems[0],        p2=self.base_front.node_elems[1],        p3=self.pselected[1],  # 注意节点顺序        p4=self.pselected[0],        part_name="interior",        idx=self.num_cells,    )    self.update_cells(new_cell)

节点顺序：

P0 (base_front 左端点) |P1 (base_front 右端点) |P3 (pselected[1]) |P2 (pselected[0])

5.2 阵面更新策略

每次生成单元后，需要：

1. 删除当前阵面（base_front）
2. 添加新生成的阵面
3. 重构 node2front 关系

defreconstruct_node2front(self):"""重构 node2front 列表"""    num_neighbors = 2for front in self.front_list:for node_elem in front.node_elems:if len(node_elem.node2front) == 0:                node_elem.node2front = [None] * num_neighbors# node_elem 在 front 中是起点，则 front 是在后面for i, node_elem in enumerate(front.node_elems):            node_elem.node2front[(i + 1) % num_neighbors] = front# 检查每个节点的邻阵面数量是否为 2for front in self.front_list:for node_elem in front.node_elems:ifnot all(node_elem.node2front):raise ValueError(f"节点 {node_elem.idx} 的邻阵面数量不足 2")

六、优化策略

6.1 阵面排序推进

为提高网格质量，PyMeshGen 支持按阵面长短顺序推进：

defcalculate_gap_criterion(self):"""计算不同部件阵面之间的最小距离"""if self.sort_front:return# 已开启排序# 每间隔一定单元数判断一次if self.num_cells % self.progress_interval != 0:return# 计算安全距离    safe_distance_sq = 0.3 * (width + height) / 2    safe_distance_sq *= safe_distance_sqfor front1 in self.front_list:for front2 in self.front_list:if front1.part_name != front2.part_name:# 检查不同部件阵面之间的距离if fast_distance_check(p0, p1, q0, q1, safe_distance_sq):                    info("部件之间阵面最小距离较小，按阵面长短顺序推进生成...")                    self.sort_front = Truereturn# 检查阵面长度比例if min(front1.length, front2.length) / max(front1.length, front2.length) > 0.8:                    info("部件之间阵面长度已接近，按阵面长短顺序推进生成...")                    self.sort_front = Truereturn

排序推进的优势：

• 优先处理长阵面，避免长阵面残留到最后
• 减少网格畸变，提高整体质量
• 适用于多部件复杂几何

6.2 质量评估函数

四边形质量评估采用综合指标：

quality = quadrilateral_quality2(p0, p1, elem2.coords, elem1.coords)

质量评估考虑以下因素：

• 内角偏差：越接近 90° 越好
• 边长比：四边长度越接近越好
• 面积：避免过小或过大的单元
• 雅可比：等参变换的雅可比行列式

七、算法性能

7.1 生成效率

混合网格生成算法的效率优势：

7.2 质量保证

通过多层检查机制保证网格质量：

质量保障体系：├── 候选点质量评分 (quadrilateral_quality2)├── 几何方向检查 (is_left2d)├── 碰撞检测 (is_cross_quad)├── 邻近检查 (proximity_check)└── 尺寸检查 (size_too_big)

八、总结

PyMeshGen 的混合网格生成算法具有以下特点：

1. 智能选择：优先四边形，失败回退三角形
2. 质量优先：多源候选 + 质量评分，确保最优选择
3. 严格检查：方向、碰撞、邻近、尺寸多层检查
4. 灵活适应：根据局部几何自动调整策略
5. 高效推进：支持阵面排序，提高整体质量

通过合理的参数设置和优化策略，混合网格算法能够生成高质量的计算网格，为 CFD/FEA 计算提供可靠的基础。

参考文献：

• 陈建军,郑建靖,季廷炜,等.前沿推进曲面四边形网格生成算法[J].计算力学学报,2011,28(05):779-784.

👇点击左下方“阅读原文”访问项目！

全文结束，感谢观看，创作不易。

😁😁

欢迎关注、留言、点赞、分享、推荐！

👇👇

【往期回顾】