自顶向下建立OBB层次树改进分割算法研究.pdfVIP

ISSN 1∞弘3044 Computer Knowledge and Technology 咆麟知识与拢~ VoI.6.No.34, I)eeember 2010, pp.9746ω9748 自顶向下建立 OBB 层次树改进分割算法研究 杨舒瓶，妙全兴 (武警 γ.程学院，陕西西安 71ω86) E-maíl: xsjl@ http://www.ù.en Tel:+86…551 叩5690963 5690964 摘要:对 OB? 层次树在磁梭检测中的应用进行了研究，详细分析了自顶向下建立 OBB 层次树的过程 υ 介绍一种新的分割方法，可 以使分割后的也周金泛加紧密。实验通过与传统分割方法比较，证明了该算法可以有效地应用于集合中二角形分布较稀疏的情况。 关键词:虚拟现实;磁棱检测;包围金层次结构;层次包阁体树 中团分类号:TP391.9 文献标识码 :A 文意编号: 1009-3044(2010)34-9746-03 Research 00 New Splitting Methods of Top-Down OBB-Tree Construction YANG Shu-hao, MIAO Quan… xing (En伊leering College of Armed Políce Force，泪an 710086, China) Abstract: Invesrigaring the applícarion of O?B-丁ree in col1ision detecrion , and analyzing the proccdure of Top-f)own OBl王一Tree con- 阳ction. A new method for splítting disconnected s础。f triangles was introduced, which can make OBB 吨hter. Experiments were COID- pared with common splitting methods, and results show the new method can be used ωsplit 出e disconnected sets of triangles. Keywords: v放ωa1 reality; collision detection; bounding. volume hierarchy; bounding volume trees 碰攘徐测用于判定一对或多对物体在给~时间域内的同- .时刻是千tf di 1￥栩间区域。它是机器人运动规划、汁算机仿桌、虚拟现实、 游戏等领域不阳rrm避的问题之一[11。实时精确的碰攘检测对 f提高系统的拟真!茧，增强肘户对虚拟TI;境的沉竣感有辛苦豆豆关?在哥哥的作用。 随着虚拟现实技术的发展，虚拟环境的复杂度以及用户与虚拟环搅间的交互不断增加，从而对碰攒桥:测提出了更高的要求。 敢基本的碰撞检测算法是直接对物体|冽的所有几何J己家进行碰撞检测~遍历，这种算法精确皮最高.计算复杂皮也极高，不能达 到系统实时性的要求。目前使用的碰撞检测算法均采取速度与精度兼顾的折中方法，在牺牲一部分精确件的情况札挺商检测的速 度.从而提尚系统的实时性。 碰撞检测算法总体上分为静态碰撞检测算法和动态碰撞检测算法。静态碰撞检测算法检测在静止的环境中测试对象间是抒发 生碰撞的算法，要求很高的精度，不要求-tJ很高的实时性;动态碰撞检测算法针对的是环境中运动物体问以及物体相环境是沓发生 碰撞的算法。对实时件要求较高.如何在保证算法实时僻的前提下提高精度是研究的教点初难点。 动态仰撞枪测算法分为阕做碰撞检测算法和连续碰撞检测算法12J。其中连续碰撞检测算法由于计算复杂，建模剧难而没有广泛 使用，目前应用的较多的碰撞检测算法多属于·离散碰撞检测算法。服次包嗣盒法就是离散品It撞阶测算法中使用较多，技术成熟的算 法之一。 1 包围靠技术 包围食法出现较早，在碰攘检测系统中广泛使用，其核心思想是把复杂的对象用一个体积略大，可以包含该对象的几何特征简 单的包阁践表示。物体问碰撞检测只需对其相应的包阁命进行相交视IIJj式.从而减少计算复杂度，提尚算法实a.t性。 根据也网食的不|叶，可分为:包嗣j球131 (Sphere). 沿线你轴的包网愈 AABB阴 (A直i←Aligned Bounrling Boxes)，固定方向包国盒 FDH I51(Fíxed Dírectíons Huils ). JFn I蒋散方向也闸盒 K-DopI6~k Díscrete Orientatíon Polytope) , lí rtl钮闸盒 OBBI坷。)riented Boundín