凹多边形如何做点包含与碰撞检测
哪些公司问过
答案要点
- 凸多边形的同侧判定、SAT、GJK 都依赖凸性,凹多边形不能直接套用
- 点包含改用射线法:交点奇数在内偶数在外,或用环绕数法
- 射线经过顶点时按半开区间计数,如边的 y 范围取 [ymin, ymax),防止重复计数
- 碰撞检测先凸分解:耳切法三角化后合并相邻三角形,3D 可用 V-HACD 近似分解
- 分解后作为复合碰撞体,先用子块 AABB 粗筛,再逐块做 SAT/GJK
易错点
- 直接对凹多边形用 SAT,会把凹陷处误判为相交
- 射线法不处理恰好穿过顶点的情况,导致计数错误
- 三角化前不统一顶点绕序或存在自交,剖分结果错误
面试官常见追问
- 耳切法的思路和复杂度?
- 凸分解块数太多怎么办?
- 射线法和环绕数法怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。