摘要
方向包围盒(Oriented bounding box:OBB)的构造以及包围盒的相交测试的计算量都比较大,严重影响了在模拟、仿真的应用,尤其是有变形物体的场景。引入近似凸包的思想提出一种快速构造方向包围盒算法,很大程度上减少了构造方向包围盒(OBB)层次结构的顶点数,改进后的算法在降低构造层次结构时间的同时,对方向包围盒的紧密性代价几乎没有影响,在有些时候还提高了包围盒的紧密性。在包围盒相交测试方面,提出了一种基于简单测度的相交预判方法,该算法在检测过程中省去了大量包围盒的相交测试计算,提高了相交测试的速度。最后将两种改进算法联合的碰撞检测框架与常用的基于均值和协方差矩阵的包围盒构造和基于分裂轴的算法进行比较,证明了算法具有高效性。
The heavy computation load for Oriented Bounding Box fitting and overlap testing limits its applications in simulations, especially for deformable soft objects, and two improved algorithm were proposed for the problems. Combining with approximate convex hull method, a fast Oriented Bounding Box fitting algorithm for oriented bounding box was proposed and the new strategy reduced the vertices for Oriented Bounding Box fitting. The new method not only reduced the fitting time greatly but also improved the compactness instead of paying compactness cost. A prejudgment basing on simple measure was proposed which improved the collision detection rate by abandoning lots of unnecessary computation for overlapping test. In the end, the comparison between the combination collision detection of the two improved method and the traditional strategies based on mean-variance matrix for bounding box fitting and separating axis for detection collision.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2011年第10期2169-2173,共5页
Journal of System Simulation
基金
国家自然科学基金面上项目(30570454)
上海市科学技术委员会国际合作项目(08410700800)
成都信息工程学院人才引进项目(KYTZ201040)
关键词
方向包围盒
凸包
简单测度
紧密性
预判
oriented bounding box
convex hull
simple measure
tightness
pre-judgment
