作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 图形图像处理 • 上一篇    下一篇

基于八叉树的三维地质剖面生成算法

赵 龙,闵世平,代强玲   

  1. (中国中铁二院工程集团有限责任公司,成都 610031)
  • 收稿日期:2013-01-05 出版日期:2014-02-15 发布日期:2014-02-13
  • 作者简介:赵 龙(1983-),男,工程师、硕士,主研方向:三维GIS,三维地质建模;闵世平,高级工程师、硕士;代强玲,工程师、硕士

3D Geological Section Generating Algorithm Based on Octree

ZHAO Long, MIN Shi-ping, DAI Qiang-ling   

  1. (China Railway Eeryuan Engineering Group Co., Ltd., Chengdu 610031, China)
  • Received:2013-01-05 Online:2014-02-15 Published:2014-02-13

摘要: 针对目前构建三维地质剖面算法复杂度高、效率低的问题,提出一种基于八叉树的三维地质剖面生成算法。利用八叉树算法对传统的地质剖面生成算法进行改进,使算法在搜索过程中的时间复杂度降低至O(log8(n/M)),在算法中加入轮廓边约束,对搜索到的边进行预处理,以保证边的正确性和有序性。采用八叉树为复杂三维地质体网格模型内的三角形创建空间索引,通过八叉树快速查找出经过剖面的三角形,计算交点并追踪出轮廓边界,通过画廊看守算法对追踪出的边界三角化并构建三维剖面。实验结果表明,该算法具有复杂度低、鲁棒性强的特点,与传统的地质剖面生成算法相比,时间复杂度由O(n2)降低到O(nlbn)。

关键词: 八叉树, 三维地质剖面, 三维地质体网格模型, 空间索引, 画廊看守算法, 时间复杂度

Abstract: 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(log8(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(n2) to O(nlbn) compared with traditional algorithm.

Key words: octree, 3D geological section, 3D geologic body mesh model, spatial index, gallery guard algorithm, time complexity

中图分类号: