第40卷 Vol.40
第2期 No.2
·图形图像处理·
计算机工程 ComputerEngineering
文章编号：1000—3428(2014)02—0250—06
文献标识码：A
2014年2月 February 2014
中图分类号：TP911.73
基于八叉树的三维地质剖面生成算法
赵龙，闵世平，代强玲
(中国中铁二院工程集团有限责任公司，成都610031）
摘要：针对目前构建三维地质剖面算法复杂度高、效率低的问题，提出一种基于八叉树的三维地质剖面生成算法。利用八叉树算法对传统的地质剖面生成算法进行改进，使算法在搜索过程中的时间复杂度降低至O(log(n/M)，在算法中加入轮席边约束，对搜索到的边进行预处理，以保证边的正确性和有序性。采用八叉树为复杂三维地质体网格模型内的三角形创建空间索引，通过八叉树快速查找出经过剖面的三角形，计算交点并追踪出轮廊边界，通过画廊看守算法对追踪出的边界三角化并构建三维剖面。实
验结果表明，该算法具有复杂度低、鲁棒性强的特点，与传统的地质剖面生成算法相比，时间复杂度由O(r)降低到O(nlbn)。关键词：八叉树；三雄地质剖面；三维地质体网格模型；空间索引；面席看守算法；时间复杂度
3DGeological SectionGeneratingAlgorithmBased onOctree
ZHAO Long, MIN Shi-ping, DAI Qiang-ling
(China Railway Eeryuan Engineering Group Co., Ltd., Chengdu 610031, China)
[Abstraet] Aiming at the high-complexity and low-efficiency of constructing 3D geologic sections, an 3D geological section generating algorithm based on octree is proposed. It is an improvement of the traditional geologic sections generating method, which reduces the time complexity to O(logs(n/M) in the search process. Besides, it adds boundary constraints for preprocessing, guarantees the correctness and the order of the boundaries, and becomes more robust. The algorithm creates spatial index for triangles on complex 3D geologic body mesh models and searches triangles on geologic sections plane based on octree, then computes the intersection points and traces boundaries of geologic sections. The algorithm constructs 3D geologic sections, and uses gallery guard algorithm to triangulate the traced boundaries Experimental results prove that this method not only has advantages of high-efficiency and robustness, but also reduces the time complexity from O(n*) to O(nlbr) compared with traditional algorithm
[Key words] octree; 3D geological section; 3D geologic body mesh model; spatial index; gallery guard algorithm; time complexity DOlI: 10.3969/j.issn.1000-3428.2014.02.054
概述 1
在采矿、地质灾害治理、工程地质勘查、水利等行业经常用到地质剖面图，它是反映剖面上的矿(岩)体界线、地质体岩性、工程地质特征、水文特征、断层位置和构造形态等信息的重要图件之一川，传统的地质剖面图通过手工绘制的方法实现，计算机技术的发展使得海量三维地质体的生成和显示成为可能，通过计算机图形学、计算几何、数值分析等学科的技术自动生成的地质剖面图的方法将会逐渐取代手工绘制的方法，这将大大提高地质领域相关行业的效率。
目前，国内外很多学者对三维地质剖面算法进行了研究，GOCAD项目组-早在2000年就在其地质建模软件中集成了地质体副面生成的功能；文献[3则通过地质体网格
模型与平面求交运算实现了地质体剖面的生成。早期的算法均存在需要大量几何运算、时间复杂度过高的间题，后期很多学者对其进行了改进，如：文献[4]采用一种基于有向包围盒(OrientedBoundingBox，OBB)树的三角网切割算法来实现空间中2个三角网格的切割；文献[5]利用地理信息系统(Geographic Information System，GIS)的模版组件生成地质剖面图的算法；文献[6]提出了一种通过生成KD树的(K-dimensiontree)方法构建地质体剖面轮廊线的方法，这些算法基本是通过二叉树筛选的方法减少儿何运算和降低算法的复杂度，但是随着地质模型越来越复杂、构建树所费的时间及计算机内存也越来越多，成为算法的瓶颈，由于八叉树"的规模远远比二次树小，算法容易，在构建和查询时均比二叉树效率高，而且用途也越来越广泛，如文献[8] 在计算机图形学论坛中阐述了八叉树构建三维网格模型的
龙(1983一)，男，工程师、硕士，主研方向：三雄GIS，三维地质建模；闵世平，高级工程师、硕士；代强玲，
作者简介：越工程师、硕士
收稿日期：2013-01-05
修回日期：2013-03-16
E-mail;305024828@qq.com