含内孔多面体的约束Delaunay四面体剖分算法  

Algorithm for Dividing a Polyhedron with Holes into Constrained Delaunay Tetrahedrons

作　　者：李昌领[1] 张虹[1] 朱良峰[2] 

机构地区：[1]中国矿业大学环境与测绘学院,江苏徐州2210081 [2]华东师范大学地理信息科学教育部重点实验室,上海200062

出　　处：《武汉大学学报（信息科学版）》2014年第3期346-352,共7页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金资助项目(40902093)~~

摘　　要：针对四面体网格生长算法数据量大和效率低的问题,引入分离面的概念,建立了分离面定理、线段与平面不相交判定定理、三角面与平面不相交判定定理,把线段与三角面的不相交检测问题转化为较为容易计算的分离面与三角面的不相交检测问题。在此基础上,给出了一个完整的基于多面体内外边界面的三维约束Delaunay四面体网格直接生长算法。实验表明,算法运行稳定,剖分结果正确,较少用户干预,具有很高的自动化水平。To solve the problem of poor calculating efficiency caused by mass data existed in tetrahedral growth algorithm, the concept of a separating-plane is introduced while a separating-plane theorem, and theorems for segment-plane and triangle-plane disjoint tests are established. By transforming the segment-triangle disjoint test into the easier disjoint test between a separating-plane and triangle, a large amount of triangles to be intersected with a segment are eliminated efficiently, greatly shorten- ing testing time. On the basis of the above theorems, a complete algorithm for a direct constrained- Delaunay tetrahedralization based on the boundaries of a polyhedron is presented. Experimental re- sults show that the algorithm runs stably and correctly, has a higher level of automation because of less artificial intervention, and possesses higher efficiency compared with other similar algorithms.

关 键 词：多面体剖分 约束Delaunay四面体 顶点对可见性 分离面 分离面定理 

分 类 号：P208[天文地球—地图制图学与地理信息工程]