1.4.c 碰撞检测算法:GJK代码解析

category
type
status
slug
date
summary
tags
password
icon
你我来自湖北四川广西宁夏河南山东贵州云南的小镇乡村, 曾经发誓要做了不起的人.
—你曾是少年 S.H.E
🏰代码及环境配置：请参考 环境配置和代码运行!
本节提供了GJK算法的代码测试.

1.4.c.1 GJK代码实现

tests/basic/gjk.py 提供了GJK算法的实现,该实现不仅仅返回碰撞结果,还计算了最小距离.
这里我们介绍一下主流程run_gjk() ,他接受两个二维凸集和一个初始方向作为输入.
  • 首先基于初始方向计算了shape1, shape2两相反方向上的边界点, 然后相减得到Minoski差集合的边界点的向量v().
  • 利用向量v,计算Minoski差集合边界上的第一个单纯形点w
  • 初始化单纯形S, S1和S2分别是单纯形S对应的 shape1和shape2上的原始点,因为算法需要计算最小距离
  • 进入循环,停止条件 代表当前最小距离的v.dot(v) > 代表新的最小距离的v.dot(w), 也就是无法找到更小距离的点了
  • 循环内find_first_unset使用了数学技巧来找b中第一个0的位置索引
  • 我们可视化了每一次迭代的w,a,b点
notion image
循环中调用了johnson算法来计算单纯形上与原点的最近距离的点,代码如下:

1.4.c.1 GJK代码测试

notion image
在tests/basic/gjk_collision_check_test.py 中,生成了随机的矩形和圆,调用gjk算法来计算最小距离和对应的点
上一篇
动手学控制理论
下一篇
端到端-理论与实战视频课程
Loading...