一种改进的不规则三角网格曲面切割算法

花卫华; 邓伟萍; 刘修国; 尚建嘎

一种改进的不规则三角网格曲面切割算法

花卫华^{1, 2,},
邓伟萍³,
刘修国^{1, 2},
尚建嘎^{1, 2}

1.
中国地质大学信息工程学院, 湖北武汉 430074
2.
武汉中地数码科技有限公司, 湖北武汉 430074
3.
湖北经济学院计算机科学学院, 湖北武汉 430000

基金项目:

国家大型“863”计划: 面向网络海量空间信息的大型GIS 2002AA135140

详细信息

作者简介:
花卫华(1977-),男,助教,主要从事三维图形处理、三维地质建模与可视化方面的教学和科研工作.E-mail: mycug@163.com

中图分类号: TP393
计量
- 文章访问数: 144
- HTML全文浏览量: 50
- PDF下载量: 3
- 被引次数: 0
出版历程
- 收稿日期: 2006-05-30
- 刊出日期: 2006-09-25

Improved Partition Algorithm between Triangulated Irregular Network

HUA Wei-hua^{1, 2
,},
DENG Wei-ping³,
LIU Xiu-guo^{1, 2},
SHANG Jian-ga^{1, 2}

1.
Faculty of In for mation Engineering, China University of Geosciences, Wuhan 430074, China
2.
Wuhan Zondy Cyber-Tech Co., Ltd., Wuhan 430074, China
3.
Faculty of Computer Science, Hubei University of Economics, Wuhan 430000, China

摘要

摘要: 三角网切割是实现三维地质建模和模型分析的关键算法, 它的效率直接决定了建模算法的效率.通过建立三角网的方向包围盒(oriented bounding box, OBB) 树实现曲面间的碰撞检测, 然后对发生相交的三角形对统一计算交点, 通过对顶点坐标归一化完成曲面切割后的快速重构, 并针对不同的曲面类型采用不同的切割分类方法进行2侧切割结果的划分.阐述了算法的实现过程并展示了切割后的图形效果.
- TIN /
- 相交 /
- OBBT /
- 归一化 /
- 分边 /
- 投影
Abstract: The partition algorithms between triangulated irregular network are key algorithms for building and analyzing 3D geology models. Their efficiency determines the model building efficiency. To improve the algorithm, this paper first realizes collision detection by building OBB (oriented-bounding box) trees, and then calculates the intersection points of cutting triangle pairs. Through normalizing the vertex coordinates, the algorithm provides a method for the rapid reconstruction of the geology model. The algorithm uses different partition methods based on different partition types. This paper gives a detailed description of the algorithm's process and demonstrates a cut effect of triangulated irregular network.
- TIN /
- intesection /
- OBBT /
- normalization /
- partition /
- projection

HTML全文

图 1 TIN切割示意

Fig. 1. Schematic diagram of cutting TIN

下载: 全尺寸图片幻灯片

图 2 OBB的分解过程

一条短线段代表一个三角形

Fig. 2. Course of decomposeing OBB

下载: 全尺寸图片幻灯片

图 3 OBB树建树流程

Fig. 3. Diagram of composing OBB tree

下载: 全尺寸图片幻灯片

图 4 OBB树碰撞检测流程

Fig. 4. Examining collision of OBB tree

下载: 全尺寸图片幻灯片

图 5 切割算法流程

Fig. 5. Diagram of cutting algorithm

下载: 全尺寸图片幻灯片

图 6 多个地层面的切割线框模式(a, b) 和实体模式(c, d)

下载: 全尺寸图片幻灯片

参考文献(10)

[1]	Ding, Y. X., Xia, J. C., Wang, Y., et al., 1994. Arbitrary polygon delaunay triangulation. Joural of Computer, 17 (4): 270 -275 (in Chinese with English abstract).
[2]	Gottschalk, S. G., Lin, M., 1996. OBB tree: A hierarchical structure for rapid interference. ACM Siggraph' 96, [s. n. ]. 171 -180.
[3]	Lindenbeck, C. H., 2002. A program to clip triangle meshes using the rapid and triangle libraries and the visualization toolkit. Computers & Geosciences, 28: 841 -850.
[4]	Paul, B., 1989. Intersection point of two lines (2 dimensions). http://local.wasp.uwa.edu.au.
[5]	Ren, J. B., 2005. Irregular triangulation based on plane polygon. Journal of Gansu Sciences, 17 (1): 65 -68 (in Chi-nese with English abstract).
[6]	Tomas, M., 1997. A fast triangle-triangle intersection test. Journal of Graphics Tools, 2 (2): 1 -5. doi: 10.1080/10867651.1997.10487470
[7]	Yang, J., 2000. Simple polygon triangulation based on scraggy vertex determinant. Minitype Computer System, 21 (9): 974 -975 (in Chinese with English abstract).
[8]	丁永祥, 夏巨谌, 王英, 等, 1994. 任意多边形的Delaunay三角剖分. 计算机学报, 17 (4): 270 -275. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX404.004.htm
[9]	任建波, 2005. 基于平面多边形的不规则三角网分割. 甘肃科学学报, 17 (1): 65 -68. doi: 10.3969/j.issn.1004-0366.2005.01.018
[10]	杨杰, 2000. 基于凸凹顶点判定的简单多边形的三角剖分. 小型微型计算机系统, 21 (9): 974 -975. doi: 10.3969/j.issn.1000-1220.2000.09.022