C++ 如何在GJK算法基础上使用EPA算法求解碰撞穿透深度和法线-C++-PHP中文网

GJK仅判断相交并返回含原点的单纯形，无法提供穿透深度；EPA通过迭代膨胀该单纯形逼近Minkowski差边界，选取最近面片、计算支撑点、更新凸包，最终以其单位法向和到原点距离给出准确穿透深度与分离轴。

c++ 如何在gjk算法基础上使用epa算法求解碰撞穿透深度和法线

为什么GJK之后必须用EPA才能得到穿透深度

GJK算法只判断两个凸体是否相交，并在相交时返回一个包含原点的单纯形（通常是四面体），但它不提供任何关于“原点离Minkowski差边界有多远”的信息。穿透深度本质上是原点到Minkowski差边界（即两物体表面最近点对构成的曲面）的最短距离，而这个边界在相交时恰好是EPA所追踪的凸包面片集合。跳过EPA直接“估算”深度（比如用GJK最终单纯形顶点模长最小值）会导致法线错误、深度偏小，尤其在边-面或角-面接触时完全失效。

GJK 输出的是一个含原点的Simplex（3~4个支撑点），但该单纯形只是Minkowski差的一个内嵌近似，不是其真实边界
EPA从这个单纯形出发，不断向外“膨胀”——每次选离原点最近的面片，沿其法向求新支撑点，替换掉对面顶点，直到新面片足够接近原点
收敛时，最近面片的单位法向就是分离轴（即碰撞法线），其到原点的有符号距离就是穿透深度（正值表示穿透）

EPA核心循环：面片选择、支撑点计算与单纯形更新

EPA不是迭代优化单个点，而是维护一个凸多面体（初始为GJK终止单纯形），逐步细化它对Minkowski差的逼近。关键三步必须严格按序执行，否则会生成非法面片或陷入死循环：

遍历当前所有面片，计算每个面片平面方程 dot(n, x) = d，取 d / norm(n) 最小者（即离原点最近的面片）。注意：必须使用面片**朝外法向**（通过顶点绕序+叉积保证），否则 d 符号反转，选错面
调用和GJK相同的支撑函数 support(A, B, n)，传入该面片法向 n，得到Minkowski差上的新支撑点 s
若 dot(n, s) （即新点没明显“撑出”当前面），说明已收敛；否则移除该面片，将 s 与面片三条边分别组成三个新面片，加入凸包 —— 这里必须检查新面片是否退化（三点共线）、是否朝向一致，否则后续法向计算崩溃

示例片段（伪代码）：

Face closest = find_closest_face(polytope);
Vec3 n = closest.normal; // 已归一化且朝外
Vec3 s = support(A, B, n);
float dist = dot(n, s);
if (dist - closest.d <h3>常见失败场景与数值稳定性处理</h3><p>EPA对浮点误差极度敏感，实际工程中约70%的失败源于数值问题，而非逻辑错误：</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
														src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
													<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
												</div>
												<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>

support() 返回点与面片共面（dist ≈ closest.d）但因舍入误差略小，导致误判收敛——应在比较时用相对容差：dist
初始单纯形退化（如GJK终止于共面三角形）：需在传入EPA前检测并用随机扰动顶点修复，或升维补点（如添加原点微小偏移后的支撑点）
面片法向计算时叉积结果过小（norm(cross(e0,e1)) ）：直接丢弃该面片，避免后续除零或nan传播
迭代次数硬上限设为32~64次即可，超过说明输入本身病态（如极端扁平物体），应降级返回GJK估计值并告警

法线方向与深度符号的物理意义对齐

最终得到的 normal 是Minkowski差边界在最近点处的外法向，但碰撞响应需要的是“从A指向B”的分离方向。若支撑函数定义为 support(A,B,n) = a - b（标准Minkowski差），则EPA返回的 normal 就是B相对于A的分离方向。验证方法：用该法线分别对A、B调用支撑点函数，得 a = support(A, normal)、b = support(B, -normal)，则 a - b 应近似平行于 normal，且 dot(normal, a - b) > 0。

穿透深度为正数，但若需“将A沿法线推离B的距离”，位移量就是 depth；若需“将B沿反向推离A”，则用 -depth。这一步不能靠猜测，必须和支撑函数的符号约定严格绑定。

实际调试时，把EPA每轮的最近面片顶点和法向可视化出来，比看数字更早暴露朝向或退化问题。