大规模柔体的连续碰撞检测算法  

Continuous collision detection algorithm for large-scale deformable objects

作　　者：周清玲[1] 刘艳[1] 程天翔 

机构地区：[1]天津大学计算机科学与技术学院,天津300072

出　　处：《中国图象图形学报》2016年第7期901-912,共12页Journal of Image and Graphics

基　　金：国家自然科学基金项目(2013BAH62F02)~~

摘　　要：目的针对大规模复杂柔体碰撞检测中速率低的问题,在两级碰撞算法基础上加入新的剔除算法——过滤器,得到了更好的效率。方法在碰撞检测的高级阶段,通过实验确定基于离散导向多面体包围盒(26-DOPs)的包围盒层次树(BVHs);低级阶段,混合使用代表性三角形和孤集两种方法;增加新剔除算法——过滤器,针对已有的非共线性过滤器(NCF)的缺陷,提出解决方案;提出新的过滤器—条件过滤器(DCF),它在非穿透性过滤器(DNF)和NCF剔除之后生效,进一步提高算法效率。结果在cloth_ball数据集下,相比于仅使用DNF,使用DNF和NCFI(改进的NCF)时,点面碰撞(VF)测试数量减少了85.90%,而使用DNF+NFCI+和DCF时,这一比例为87.94%。结论本文算法对于一般情况下的大规模柔体的碰撞检测具有普适性,特别是碰撞处理中发生三角形翻转,DCF和NCF失效的情况下,本文提出的条件过滤器能起到很好剔除作用,提高总体效率。Objective In view of the proplem of low rate in collision detection of large-scale complex flexible bodies, a new algorithm based on two-phase algorithms is introduced, which are more effective than previous approaches. Method In the broad phase, we conducted an experiment to construct a 26-DOP bounding volume hierarchy. In the narrow phase, we com- bined a representative triangle and an orphan set. Subsequently, a new elimination algorithm was introduced. At the filter level, we described the drawback of the non-collinear filter （NCF） and provided a solution. In addition, a new filter named deforming conditional filter （DCF） was proposed and used after DNF and NCF to achieve a high interactive rate. Result We have implemented our algorithm in some numerical experiments, as described in the second and third parts of the exper- imental section, for the cloth_ ball data set, the use of DNF and NCFI allowed for the number of VF tests to be reduced by 85.90% compared with the use of DNF, whereas the use of DNF, NFCI, and DCF, allowed for a reduction of 87.94%. Conclusion The proposed approach for general large-scale deformable body collision detection has universality. Particularly in the case of collision processing of triangle flipping, in which DCF and NCF fail, the proposed conditions of the filters can ef- fectively achieve culling and improve the overall efficiency of the algorithm.

关 键 词：大规模柔体 碰撞检测 包围盒层次树 代表性三角形 孤集 过滤器 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]