第30卷 第2期2006年4月
武汉理工大学学报(与工程版)
JournalofWuhanUniversityofTechnology
(TransportationScience&Engineering)
交通科学
Vol.30 No.2Apr.2006
碰撞检测中计算
*
两凸多面体间最短距离的算法研究
金汉均1,2) 李朝晖1) 王彦林2) 汪 琼3)
(华中科技大学水电与数字化工程学院1) 武汉 430074)
(华中师范大学计算机科学系2) 武汉 430079) (湖北省经济管理干部学院3) 武汉 430079)摘要:提出了一种计算两凸多面体间最短距离的算法.该算法用物体三维空间顶点坐标的凸包表示凸多面体,采用非线性规划方法来计算两凸多面体间最短距离,并通过最短距离来判断两凸多面体是否发生碰撞.实例证明这种方法的有效性.关键词:凸物体;凸包;碰撞检测;非线性规划;优化中图法分类号:TP391
在虚拟环境中,由于用户的交互和物体的运动,物体间经常可能发生碰撞,此时为保持环境的真实性,需要及时检测到这些碰撞,并计算相应的碰撞反应,否则物体间会发生穿透现象,破坏虚拟环境的真实感和用户的沉浸感.总体上讲,虚拟环境中碰撞检测的研究目标主要有三个:检测模型之间是否发生碰撞,报告发生或即将发生碰撞的部位,动态地查询模型之间的距离[1].
最著名的两种碰撞检测算法是LC(Linand
[2]
Cannyalgorithm)算法和GJK(Gilbert,John-
拟场景,几乎所有的干涉碰撞方法都使用层次包容体,具有简单形状的包容体被用来作为初步干涉测试[4].如果包容体之间不存在干涉,则可确保相应物体之间不存在碰撞,这样可以大大减少需检测物体的形状特征数,特别是当物体之间距离不近的情况.可供选择的包容体包括:轴对齐包容盒(AABBs)、有向包容盒(OBBs)、球、圆锥体、k-DOPs等.尽管包容体的使用可以大大缩短远距离物体之间干涉碰撞检测时间,但在两物体距离较近时,LC最近特征算法和GJK算法仍然是必须的.
本文从优化角度出发,将检测两物体是否发生碰撞问题转化为求两物体间最短距离的非线性规划问题,通过最短距离值判断某时刻两物体是否发生碰撞.
sonandKeerthi)算法,它们都属于路径跟踪算法[4].LC最近特征算法利用了瞬时相关性原理,最靠近的特征(面、边或顶点)在凸多面体沿细分离散路径非快速运动的情况下变化较小.根据Voronoi区域决定一组候选特征对(这一特征对的两个物征分别来自两个凸多面体),然后检测最近点是否落在这两个特征上.若不落在候选特征上,则对候选特征对的临近特征进行检测并且循环往复进行.GJK算法不是直接对两凸多面体进行搜索和跟踪,而是在它们的明氏距离多面体参数空间中搜索跟踪执行.为了有效地实现复杂虚
收稿日期:20051112
[3]
1 算法基础
k
定义1 若Vi∈V,Ki≥0,i=1,…,k,且∑Ki
i=1
k
=1,则称点V=
∑KV
i=1
ii
为Vi,…,Vk的凸组合.
金汉均:男,43岁,副教授,主要研究领域为虚拟现实技术及各种优化算法研究(:
华中科技大学 博士学位论文 虚拟环境中物体碰撞检测算法研究 姓名:金汉均 申请...检测两凸多面体间是否发生碰撞问 题转化为求目标函数为两凸多面体间最短距离的...
大基于AABB包围盒的碰撞检测算法的研究_IT/计算机_...跟踪并且计算两个或多个模型 问的最近特征(点、边...该包围盒是一种凸多面体。它的面由一些半空间所...
本文对碰撞检测 的算法和研究状况进行了详细的阐述,...[12]从求解物体的最短距离的角度判断物体碰撞的可能...金汉均,李朝晖,张晓亮等,基于遗传算法的凸多面体间...
大基于AABB包围盒的碰撞检测算法的研究_IT/计算机_...跟踪并且计算两个或多个模型 问的最近特征(点、边...该包围盒是一种凸多面体。它的面由一些半空间所...
热门文档