sat判断两凸多边形相交只需检查所有边的法向量方向共n+m条轴,2d中每条边e对应轴(-e.y,e.x),需去重平行边,轴无需归一化。

两个凸多边形用 SAT 判断相交,只需检查边法向量轴
对两个凸多边形 A 和 B,分离轴就是它们所有边的法向量方向——不是边本身,也不是任意方向。每条边 e = v1 - v0 对应一个候选轴 glm::vec2(-e.y, e.x)(2D)或归一化后的垂直向量(3D)。A 有 n 条边、B 有 m 条边,总共最多检查 n + m 条轴,不是 n×m。
常见错误是把“边向量”直接当轴用,或者漏掉某个多边形的某条边;更隐蔽的是没做去重:平行边产生的法向量可能完全相同或反向,glm::all(glm::epsilonEqual(a, b, 1e-6f)) 或 glm::all(glm::epsilonEqual(a, -b, 1e-6f)) 必须检查。
- 2D 场景下,用
glm::vec2足够,避免升维引入冗余计算 - 轴无需归一化——投影区间只依赖点积的相对大小,归一化纯属浪费 cycles
- 若某边长度
,跳过其法向量计算,防止除零或 NaN 传播
非凸多边形不能直接套 SAT,必须先分解
SAT 仅对凸形状有效。遇到凹多边形或带孔多边形,硬上 SAT 会漏判——比如两个“U”形多边形开口相对,投影在所有边法向上都重叠,但实际不相交。
真实数据里,建模导出的多边形常含凹点。别试图用“顶点凹凸性检测+局部修正”绕开,稳定性差。稳妥做法是用耳切法(ear clipping)或单调链剖分,将原始多边形拆成若干个凸多边形,再两两做 SAT。
- 推荐轻量库如
poly2tri或手写耳切(注意处理共线顶点和极小面积三角形) - 若只是粗筛,可先用 AABB 包围盒快速排除:
!aabb_intersect(aabb_a, aabb_b)直接返回 false - 拆出的凸片数量爆炸时(如百顶点多边形),考虑降级为边-边穷举:对所有边对调用
segment_intersect()
投影区间计算必须覆盖全部顶点,且带浮点容差
每个轴上,必须对多边形**所有顶点**计算 glm::dot(p, axis),取 min/max 得到 [min, max]。常见错误是只投前三个点、或误以为三角形就只投三个点而忽略其他顶点——多边形顶点数不固定。
区间比较不能用 proj_a_max 这种裸比较:浮点误差会让本该重叠的区间被判为分离。正确写法是:
if (proj_a_max + 1e-6f
- epsilon 值选
1e-6f足够,比FLT_EPSILON更鲁棒(后者约 1e-7,但累积误差常更大) - 不要用
std::minmax_element——它对 size - 投影值本身无需 clamp 或 abs,点积可正可负,min/max 自然捕获范围
退化边与共线顶点必须前置过滤,不能等 crash 再处理
真实输入常含三点近似共线的“扁平”三角形、重复顶点、或导出时精度丢失导致的微小边长。这些会直接让 glm::normalize() 返回 vec3(0,0,0),后续点积全 NaN,整个检测失效。
防护必须放在 SAT 主循环之前:对每条边,先算长度;对每个面(若 3D),先算叉积模长。面积 就视为退化,跳过对应轴或整个多边形。
- 2D 边长检查:
glm::length(v1 - v0) - 3D 面积检查:
0.5f * glm::length(glm::cross(v1-v0, v2-v0)) - 退化多边形可降级为线段集:提取所有非退化边,再做 O(n²) 边相交检测
最易被忽略的是:共面但非共线的多边形,在 3D 空间中仍要走 3D SAT 流程——哪怕 z 坐标全为 0。强行降维到 2D 只适用于明确已知共面且无 z 噪声的场景。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











