任意形状的三角形网格划分.pdf

__________________________________________________________ 第9卷　第5期 计算机辅助设计与图形学学报 V o l. 9,N o. 5 1997年9月 J. CAD CG Sep. , 1997 任意曲面的三角形网格划分 陈永府　张　华　陈　兴　李德群 (华中理工大学塑性模拟及模具技术国家重点实验室　武汉　430074) 摘要　把曲面分为可展曲面和不可展曲面, 对可展曲面用曲面展开算法展成平面, 对不可展 曲面用曲面分割算法转化成平面片, 在平面上运用D elaunay 三角划分法进行网格划分, 然后 把网格节点反映射到曲面上, 从而实现任意曲面的三角形网格划分。 关 键 词　 三角划分, 可展曲面, 不可展曲面, 曲面展开算法, 曲面分割算法。 D elaunay 1　引　言 网格划分是计算机图形学研究的重要内容。目前, 有很多种网格划分算法, 如拓扑分 解法、节点连接法、映射单元法、基于栅格法等。这些算法在二维网格划分上各有千秋, 但 对三维任意曲面的网格划分, 成功的例子却很少。俄国数学家D elaunay 在 1934 年就证明 了: 对于任意给定的平面点集, 有且仅有一种三解剖分方法能够满足“最大最小角”优化 准则, 即所有三角形的最小内角之和最大。Sib son [ 1 ] 证明了平面任意给定点集的D elauay 三角划分具有整体最优化的性质, 这就是说, 对于任意给定的平面点集, D elaunay 三角划 分能够得到整体最优的三角形网格, 能尽可能地避免病态三角形的出现。所以, D elaunay 三角划分在许多应用领域, 尤其是在实体几何造型和有限元网格自动生成等研究领域, 受 到广泛的重视。但是传统的D elaunay 三角划分不能对三维任意曲面进行网格划分, 为了 解决这个问题, 本文把曲面分为可展曲面和不可展曲面, 分别对可展曲面采用曲面展开算 法, 对不可展曲面采用曲面分割算法; 将曲面转化为平面, 然后在平面上利用D elaunay 三 ( 角划分的优化性质进行网格划分, 再将网格节点反映射到曲面上 限于篇幅, 本文略去网 ) 格节点反映射到曲面上的算法 , 从而实现任意曲面的三角形网格划分。 2　平面任意多边形域的D elaunay 三角划分 L aw son [ 2 ] 根据“最大最小角”优化准则, 通过“对角线交换”法则实现了二维给定点 集的D elaunay 三角划分。W atson [ 3 ] 首次提出“插入多边形”, 并在此基础上, 利用“外接 收稿,收到修改稿。本文得到“八五”重点攻关项目“注塑成形的计算机仿真与交互计算”资 助。陈永府, 1972 年生, 硕士研究生, 研究方向为注塑模CA E 的前处理。张　华, 博士研究生, 研究方向为注塑模CA E。 陈　兴, 副教授, 研究方向为注塑模 。李德群, 博士生导师, 研究方向为模具 、 、 。 CAD CAD CA E CAM © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. __________________________________________________________中国科技论文在线 5 期 陈永府等: 任意曲面的三角形网格划分 397 圆”准则, 实现了无约束的D elaunay 三角划分。而实际上, 网格划分总是有一定的边界约 束条件, 本文在W atson 算法的基础上, 实现了