A Linear Algorithm for Collision Detection of 3-Dimensional Convex Polytopes

Given two disjoint 3-dimensional convex polytopes P and Q and a straight direction along Which P moves in translation, this paper presents a linear algorithm for determining Whether P collides with Q, and the possible collision positions on P and Q. This result is achieved by using the hierarchicat representation of polytopes, of which the preprocessing time is linear with space.

凸包算法及其在计算机图形学中的应用

主要任务包括对凸包的定义与特性进行研究,介绍经典的Graham扫描算法,并探讨其在碰撞检测、物体选择与编辑、遮挡计算、手势识别等计算机图形学领域的应用。采用文献研究和算法分析的方法,通过查阅相关文献和深入理解凸包算法的原理,详细介绍了Graham扫描算法的实现步骤。提供了凸包算法的代码示例,并结合2D游戏碰撞检测的具体实践进行了讨论。凸包算法在计算机图形学领域有着广泛的应用,尤其在碰撞检测方面能够显著提高计算效率和准确性。未来的研究可以进一步探索凸包算法的改进,并在虚拟现实眼镜、物体交互、遮挡计算等领域进行更深入的应用,以提升虚拟体验的质量。

基于遗传算法的凸多面体间碰撞检测算法研究

将两凸物体间碰撞检测问题归结为一个带约束条件的非线性规划问题.对该问题进行适当的处理后,利用遗传算法对该问题进行求解.实例表明,遗传算法对该问题的求解比用传统的方法求解具有更高的计算效率和更快的计算速度.

基于自适应遗传算法的局部可重配置机床碰撞检验方法

为研究局部可重配置机床各模块间运动关系并防止模块间可能存在的碰撞干涉现象,针对局部可重配置机床部分模块需要更换或升级的特点,通过分析模块之间碰撞检验的拓扑结构,提取需要进行碰撞检验的模块的顶点坐标,运用构造凸包的方法,采用遗传算法计算凸包之间碰撞干涉情况,并使用自适应遗传算法对计算过程进行优化.结果表明该方法有效地提升了碰撞干涉计算效率和计算速度.

基于非线性规划的凸多面体间碰撞检测算法

为了提高碰撞检测算法的速度,提出用顶点的凸包表示凸多面体,将两个凸多面体间距离的问题归结为一个带约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解。利用模拟退火的接收准则进行交叉、变异,降低了时间复杂度。结果表明,模拟退火遗传算法计算效率高、速度快。

基于GJK的凸体快速连续碰撞检测研究

针对一段时间内的多个运动物体之间的碰撞检测,提出一种基于距离算法(Gilbert-Johnson-Keerthialgorithm,GJK算法)的凸体快速连续碰撞检测算法,该算法主要通过判断一段时间内两物体之间的最小距离是否为零来检测碰撞发生情况。首先利用GJK算法在有限步骤内计算得到最小距离,检测两物体是否发生碰撞;若两物体发生碰撞,进而利用ray-casting算法确定发生碰撞的精确位置,根据环境要求做出相应响应,调整运动物体位置。仿真结果表明,对多个运动物体间的连续碰撞检测,该算法有较高的实时性和准确性。

基于混合人工鱼群算法的凸多面体碰撞检测研究

提出了一种基于最短距离计算的凸多面体碰撞检测算法。该算法利用凸多面体三维空间顶点坐标的凸包表示凸多面体,将两个凸多面体间碰撞检测问题归结为一个带约束条件的非线性规划问题,采用混合人工鱼群算法对该问题进行求解,寻优过程前期利用人工鱼群算法快速找到全局极值的邻域,后期切换到模式搜索法,准确找到全局极值。实验表明,无论在计算精度还是在计算速度方面,混合人工鱼群算法比惩罚函数法和遗传算法有更加明显的优势,能够满足碰撞检测的实时性和精确性的要求。

基于可见性查询的凸体碰撞检测算法

虚拟制造、机器人路径规划等许多应用都需进行实时的碰撞检测。论文提出一种新的凸体碰撞检测算法,此算法基于主流图形硬件的可见性查询功能,克服了同类图像空间算法需从显存回读大量数据的缺点,并可一次提交多个物体对的碰撞检测。实验表明该算法有效提高了碰撞检测的效率。

基于混合猴群算法的凸多面体碰撞检测

将凸多面体表示为其三维空间顶点坐标的凸包,通过计算两凸多面体间最短距离进行碰撞检测,把凸多面体间最短距离计算问题转化为带约束条件的非线性规划问题,采用混合猴群算法求解。混合猴群算法将人工鱼群算法中的鱼儿追尾行为引入到猴群算法中,使猴群算法摆脱局部最优解,提高计算精度。实验结果表明,混合猴群算法相对于单纯的猴群算法在计算精度上有较大提高,相对于标准遗传算法在计算速度上有更大优势,能够满足碰撞检测精度性和实时性的要求。

基于模拟退火遗传算法的凸多面体间碰撞检测算法研究

提出用顶点的凸包来表示凸多面体,将两凸物体间距离的问题归结为一个带约束条件的非线性规划问题。利用模拟退火遗传算法对该问题进行求解,即利用模拟退火的接收准则来交叉、变异。结果表明,该算法有较高的计算效率和计算速度。

快速凸包并行设计与研究

凸包在计算几何中占有着重要地位,不仅仅是作为理论基础,其他研究领域内求解凸包的思想可以简化复杂的问题。传统的凸包生成算法在处理点集规模较大的数据时,消耗时间随之增多影响解决问题的高效性。本文基于三维快速凸包算法,通过对快速凸包算法深入分析,分割计算任务,进而提取算法能够并行部分。实验表明结合GPU并行计算能力可以降低大规模数量点集情况下计算消耗的时间,算法的时间性能上得到加速。