一种改进的动态OBB层次结构碰撞算法.pdf

《一种改进的动态OBB层次结构碰撞算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京石油化工学院学报第19卷第1期VoI．19No．1JournalofBeijingInstituteof2011年3月Mar．2011Petro—chemicalTechnology一种改进的动态OBB层次结构碰撞算法*黄松柏(北京化工大学信息科学与技术学院，北京100029)摘要在虚拟场景中普遍采用基于OBB包围盒的碰撞检测技术，然而传统算法对于大数据量模型的检测仍然效率不高，难以保证实时性。在分析了OBB及其改进算法的基础上，采用改进的OBB中心计算方法．使包围盒能够更紧密的包围模型，提高碰撞检测的准确性和时间效率。在碰

2、撞检测过程中动态地建立OBB层次结构，减少了时间复杂度和空间复杂度。分析和实验结果证明，改进后的算法在处理一般曲面模型尤其是大数据曲面模型时，碰撞检测的稳定性和效率都有明显提高。关键词OBB；动态层次结构；碰撞检测；大数据曲面模型中图法分类号TP301．6碰撞检测在计算机图形学、计算机动画、虚它的相交测试变得复杂。尽管()BB间相交测试拟现实等应用系统中具有广泛的应用，一直是的代价比较大，但它的紧密性是最好的，可以成研究热点之一。碰撞检测算法主要有基于包围倍地减少参与相交测试的包围盒的数目和基本盒的碰撞检测算法、基于距离计算的碰

3、撞检测几何元素的数目，在大多数情况下其总体性能要算法以及基于维诺图的碰撞检测算法等三类，优于AABB和包围球。其中前两种算法只能解决凸多面体之间的碰撞基于OBB的碰撞算法已经有很多改进。检测并且难以进行精确的计算；基于包围盒的根据曲面特征和应用不同提出的改进算法，如碰撞检测算法不仅可以检测凸多面体，同时也针对复杂形状改进的OBB碰撞算法[4j，提高可以检测凹多面体，是一种比较有效的快速碰OBB层次结构树的更新速度_s]，修改OBB层撞检测算法。比较典型的包围盒有沿坐标轴次结构树的遍历策略6，基于虚拟环境的OBB的包围盒AABB(

4、Axis—AlignedBounding碰撞算法等。显然，由于OBB层次结构树的Box)、包围球(Sphere)、方向包围盒OBB内在并行性，并行技术可以提高算法效率。王(OrientedBoundingBox)、固定方向凸包FDH兆其等在基于并行处理技术提高OBB算法的(FixedDirectionConvexHul1)、离散方向包围运行效率方面给出了一种面向对象的碰撞算盒K—DOP(Diserete()rientationPolygons)等。法L8。，讨论了分布式环境中碰撞检测的完全方向包围盒OBB是基于分离轴的相交测试理

5、性和唯一性问题j。改进的并行碰撞算法如使论，由S．Gottschalk在1996年实现的RAPID用并行处理中的流水线技术，算法可运行于多(RobustandAccuratePolygonInterference处理器或单处理器上；将复杂的凸多面体剖Detection)系统中首先提出]。一个给定对象的分为简单四面体，利用基于MPI(MessageOBB被定义为包含该对象且相对于坐标轴方向PassingInterface)并行处理的方法来提高效任意的最小的正六面体。OBB最大特点是它的率，解决复杂多面体碰撞检测时间过长的缺方向的任

6、意性，这使得它可以根据包围盒对象的陷u；面向动态复杂场景采用层次的适应空间形状特点尽可能紧密地包围对象，但同时也使得剖分构建物体的平衡包围树，然后通过并行遍历包围盒树来加速碰撞检测⋯]；面向动态复杂收稿日期：20101017场景采用层次的自适应空间剖分方法构建物体*北京市科技发展计划项目．项Et号：2008。的平衡包围盒树，然后并行遍历来加速碰撞检第1期黄松柏．一种改进的动态OBB层次结构碰撞算法17测口。每种包围盒都有自己的优势，将一些包不均匀或不对称，有的三角形尺寸大，有的三角围盒的优势特点混合起来使用也是一种方法，形尺寸小

7、，这样计算出来的包围盒的中心会向如先用包围球进行碰撞排除，再运用OBB进行着三角形尺寸小且密集的部分偏移，构成的对相交判断口引。象模型包围盒不能够完全包围，如果这样的包对于大曲面模型(包含的三角形大于围盒进行碰撞检测，其结果不能完全体现出实10)，传统的碰撞算法在时间复杂度和空问复际模型的相交情况，这对最后碰撞检测的结果杂度方面都难以满足实际需求。传统OBB碰也会有影响。为了提高改进算法的效率、准确撞算法都先建立层次结构树，然后再包围盒相性和稳定性，笔者采用文献[14—163中的解决方交测试[zls]。对三角形较少的模型，能够快

8、速法，修正OBB计算。采用以下改进算法：获得相交结果，但是对三角形较多的模型，需用Step1：计算几何模型凸包上第i个三角面较多的时间和空间去建立层次结构树，而一般片中心点0、表面积S、凸包的总面积Sums：情况下相交的区域很有可能只是其中小部分区三角面片的中心