Open phenomLi opened 5 years ago
分离轴算法只能检测圆形和凸多边形。对于凹多边形,要先将其分割为凸多边形。这里便涉及凹多边形判断和凹多边形分割算法。
对于多边形的判别,可以利用向量叉积来判断。
假设有两向量a,b。当aXb<0时(X就表示叉乘),b对应的线段在a的顺时针方向;当aX\b=0时,a、b共线;当aXb>0时,b在a的逆时针方向。
根据凸多边形的定义,凸多边形的每条邻边的必定具有相同的时针方向,因此,我们可以为多边形的每一条边建立一个向量,通过相邻边向量叉积运算来判断多边形凹凸性,凸多边形的所有边的向量叉积均同号,因此一个多边形的所有边向量的叉积结果不同号,则可判定其为凹多边形。
有了思路后要实现代码就很简单了:
/** * // 判断是否为凹多边形 * @param vexs 多边形顶点数组 */ function isConcavePoly(vexs: polygonVex): boolean { // prev: 上两邻边间叉乘结果;cur当前两邻边叉乘结果 let prev: number, cur: number; // 遍历所有顶点 for(let i = 1, len = vexs.length; i < len - 1; i++) { // 向量v1 = 当前顶点 - 上一顶点 let v1 = Vector.sub(vexs[i], vexs[i - 1]), // 向量v2 = 下一顶点 - 当前顶点 v2 = Vector.sub(vexs[i + 1], vexs[i]); // 计算两邻边向量叉积:若不为负则记为1,为负则记为-1 cur = Vector.cor(v1, v2) >= 0? 1: -1; // 若当前两邻边叉积结果与上两邻边结果不同号,即可判断为凹多边形 if(prev !== undefined && prev !== cur) { return true; } prev = cur; } // 不是凹多边形 return false; }
多边形的分割要比判别要难一些。判断到一个多边形为凹多边形后,则要将凹多边形分割为多个凸多边形。分割凹多边形可以利用旋转分割法。 旋转分割法的思想是沿多边形边的逆时针方向,逐一将顶点V移动到坐标系原点,然后顺时针旋转多边形,使下一个顶点V落在X轴上,如果再下一个顶点V位于X轴下面,则多边形为凹,然后我们利用X轴将多边形分割成两个新多边形,并且对着两个新多边形重复测试,一直重复到所有顶点均经过测试。
上面提到过,向量叉积可以判断两线的相对位置,因此,我们同样也可以利用向量叉积判断点与x轴的位置关系。下面放代码:
/** * 将凹多边形分割为多个凸多边形(旋转分割法) * @param vexs 多边形顶点 */ export function divideConcavePoly(vexs: polygonVex): polygonVex[] { // 分割多边形结果集,将拆分出来的多边形保存到这个数组 let polygonList: polygonVex[] = []; let i, j, len = vexs.length, flag = false; // polygon1和polygon2分别保存分割出来的两个多边形,polygon1初始化为原多边形,polygon2为空 let polygon1 = <polygonVex>arrayDeepCopy(vexs), polygon2 = []; // 遍历所有顶点 for(i = 0, len = vexs.length; i < len - 2; i++) { // 将当前顶点和下一个顶点的连线向量作为x轴 let vAxis = Vector.sub(vexs[i + 1], vexs[i]), // 当前顶点和下下顶点的连线向量 v = Vector.sub(vexs[i + 2], vexs[i]); // 若发现下下个顶点在x轴下方 if(Vector.cor(vAxis, v) < 0) { // 遍历余下的顶点 for(j = i + 3; j < len; j++) { // 找到余下的第一个不在x轴下方的顶点 v = Vector.sub(vexs[j], vexs[i]); if(Vector.cor(vAxis, v) > 0) { // 该点即为分割点。找到分割点即跳出循环 flag = true; break; } } if(flag) break; } } // 此时分割多边形的两个点分别为vexs[i + 1]和vexs[j] // 保存两个分割点 let dp1 = polygon1[i + 1], dp2 = polygon1[j]; // 从原来的多边形按照分割点分割出另一个子多边形保存到polygon2 polygon2 = polygon1.splice(i + 2, j - (i + 2)); // 子多边形也要补上分割点 polygon2.unshift(dp1); polygon2.push(dp2); // 将两个子多边形加入到分割多边形结果集 polygonList.push(polygon1); polygonList.push(polygon2); // 检测拆分出来的两个子多边形是否是凹多边形,若果是,继续递归拆分 if(isConcavePoly(polygon1)) { polygonList = polygonList.concat(divideConcavePoly(polygon1)); } if(isConcavePoly(polygon2)) { polygonList = polygonList.concat(divideConcavePoly(polygon2)); } // 返回结果集 return polygonList; } // 数组深拷贝 export function arrayDeepCopy<T>(arr): T { return arr.map(item => Array.isArray(item)? arrayDeepCopy(item): item); }
到此我们完成了凹多边形的判别与分割,有了这些基础,我们接下来可以对之前的一些代码进行改进。
首先,在多边形类Polygon中,我们在构造函数中加入多边形的判别,那么就可以在定义多边形对象时马上可以得出该多边形的类别:
Polygon
// 多边形 class Polygon extends Shape { // 多边形的顶点 private vexs: polygonVex; // 是否为凹多边形 private isConcavePoly: boolean; // 子多边形列表 private polygonList: polygonVex[]; constructor(x: number, y: number, vexs: polygonVex) { super(x, y); this.vexs = vexs; // 判断多边形类型 this.isConcavePoly = isConcavePoly(this.vexs); // 若是凹多边形,则进行分割 if(this.isConcavePoly) { this.polygonList = divideConcavePoly(this.vexs); } } }
到现在我们的分离轴算法可以支持凹多边形的碰撞检测了,由上面可知,凹多边形其实是由多个子凸多边形组成,那么只要在遇到凹多边形时遍历凹多边形的子多边形,对子多边形进行检测即可,只要有其中一个子多边形发生碰撞即可判断该多边形发生了碰撞。但是现在,我们的碰撞分类要分得更细。这里我们新加一个polygonContact函数,用作检测有多边形参与的碰撞。
polygonContact
// 检测有多边形参与的碰撞 function PolygonContact(obj1: Shape, obj2: Shape): boolean { let polygonList1 = [], polygonList2 = []; // 若obj1为多边形 if(obj1 instanceof Polygon) { // 若obj1为凹多边形,则保存其子多边形列表到polygonList1 if(obj1.isConcavePoly) { polygonList1 = obj1.polygonList; } // 若是凸多边形,为了方便运算,将其整个多边形视作一个子多边形,所以polygonList只有一个元素 else { polygonList1 = [obj1.vexs]; } } // 同上 if(obj2 instanceof Polygon) { if(obj2.isConcavePoly) { polygonList2 = obj2.polygonList; } else { polygonList2 = [obj2.vexs]; } } // 若obj1为圆形,obj2为多边形 if(obj1 instanceof Circle && obj2 instanceof Polygon) { // 遍历obj2的子多边形,检测碰撞 return polygonList2.some(polyItem => SAT(polyItem, obj1.circleInfo)); } // 若obj2为圆形,obj1为多边形 else if(obj1 instanceof Polygon && obj2 instanceof Circle) { // 遍历obj1的子多边形,检测碰撞 return polygonList1.some(polyItem => SAT(polyItem, obj2.circleInfo)); } // 若obj1和obj2都为多边形,则双重循环检测 else { return polygonList1.some(polyItem1 => polygonList2.some(polyItem2 => SAT(polyItem1, polyItem2))); } }
最后,我们修改SATDetection函数:
SATDetection
function SATDetection(obj1: Shape, obj2: Shape): boolean { // 若两个图形都是圆形,然后直接调用circleContact快速判断 if(obj1 instanceof Circle && obj2 instanceof Cricle) { return circleContact(obj1, obj2); } // 至少一个为多边形 else { return PolygonContact(obj1, obj2); } }
至此,我们的碰撞检测系统便可以说是基本完成了。对于简单图形的输入,都可以输出一个布尔值代表碰撞与否。但是要真正达到达到商业级碰撞检测系统,还有很长一段的距离,还有很多工作需要完成。比如:
图形相交深度计算
图形相交的处理
碰撞边计算
碰撞法线计算
碰撞点的寻找
碰撞类型(边-边碰撞,边-角碰撞,角-角碰撞)分类
静态碰撞的判断和特殊处理
性能优化
更多图形支持
等等。现在的系统只能检测两个简单图形是否碰撞,但是想要获得真实的碰撞反馈还需要上述工作的支持。这个碰撞检测系统是我的毕业设计的其中一部分,并且为了分享我修改了一部分代码,而且上述提到的工作在我的毕设中也基本实现了,但最终仍达不到我想要的效果。我说这么多其实想表达的是,要实现一个’‘基本能用’‘的物理引擎,并不是一件简单的事情,这是我做完我的毕设的感受,我当时选题时低估了其难度。难在什么地方呢?1:数学基础不够;2:力学物理基础不够;3:冷门,相关的文献,书籍都太少,可参考的东西不多,遇到难题基本都要靠自己摸索。而且,我做的这只是2D环境,若要做3D环境难度还会指数级增长,一个2D图形只能绕Z轴旋转,但一个3D图形能有无数个旋转轴,这就涉及到四元数的相关知识。。。
说的这些,只为感慨。以后若有时候,我会再去继续完善我的这个项目,让其能达到’‘基本能用’‘吧。
isConcavePoly函数里面,似乎少了第一个点前后两条边组成的向量叉积判断,这样会漏掉凹点是第一个点的情况
不太行,在某些情况下,两个割点形成的分割线会有部分在原始多边形外部,也就是说这种割法割出的多边形,面积总和会增加
分离轴算法只能检测圆形和凸多边形。对于凹多边形,要先将其分割为凸多边形。这里便涉及凹多边形判断和凹多边形分割算法。
凹多边形判别
对于多边形的判别,可以利用向量叉积来判断。
根据凸多边形的定义,凸多边形的每条邻边的必定具有相同的时针方向,因此,我们可以为多边形的每一条边建立一个向量,通过相邻边向量叉积运算来判断多边形凹凸性,凸多边形的所有边的向量叉积均同号,因此一个多边形的所有边向量的叉积结果不同号,则可判定其为凹多边形。
有了思路后要实现代码就很简单了:
凹多边形分割
多边形的分割要比判别要难一些。判断到一个多边形为凹多边形后,则要将凹多边形分割为多个凸多边形。分割凹多边形可以利用旋转分割法。
旋转分割法的思想是沿多边形边的逆时针方向,逐一将顶点V移动到坐标系原点,然后顺时针旋转多边形,使下一个顶点V落在X轴上,如果再下一个顶点V位于X轴下面,则多边形为凹,然后我们利用X轴将多边形分割成两个新多边形,并且对着两个新多边形重复测试,一直重复到所有顶点均经过测试。
上面提到过,向量叉积可以判断两线的相对位置,因此,我们同样也可以利用向量叉积判断点与x轴的位置关系。下面放代码:
到此我们完成了凹多边形的判别与分割,有了这些基础,我们接下来可以对之前的一些代码进行改进。
分离轴算法的改进
首先,在多边形类
Polygon
中,我们在构造函数中加入多边形的判别,那么就可以在定义多边形对象时马上可以得出该多边形的类别:到现在我们的分离轴算法可以支持凹多边形的碰撞检测了,由上面可知,凹多边形其实是由多个子凸多边形组成,那么只要在遇到凹多边形时遍历凹多边形的子多边形,对子多边形进行检测即可,只要有其中一个子多边形发生碰撞即可判断该多边形发生了碰撞。但是现在,我们的碰撞分类要分得更细。这里我们新加一个
polygonContact
函数,用作检测有多边形参与的碰撞。最后,我们修改
SATDetection
函数:总结
至此,我们的碰撞检测系统便可以说是基本完成了。对于简单图形的输入,都可以输出一个布尔值代表碰撞与否。但是要真正达到达到商业级碰撞检测系统,还有很长一段的距离,还有很多工作需要完成。比如:
图形相交深度计算
图形相交的处理
碰撞边计算
碰撞法线计算
碰撞点的寻找
碰撞类型(边-边碰撞,边-角碰撞,角-角碰撞)分类
静态碰撞的判断和特殊处理
性能优化
更多图形支持
等等。现在的系统只能检测两个简单图形是否碰撞,但是想要获得真实的碰撞反馈还需要上述工作的支持。这个碰撞检测系统是我的毕业设计的其中一部分,并且为了分享我修改了一部分代码,而且上述提到的工作在我的毕设中也基本实现了,但最终仍达不到我想要的效果。我说这么多其实想表达的是,要实现一个’‘基本能用’‘的物理引擎,并不是一件简单的事情,这是我做完我的毕设的感受,我当时选题时低估了其难度。难在什么地方呢?1:数学基础不够;2:力学物理基础不够;3:冷门,相关的文献,书籍都太少,可参考的东西不多,遇到难题基本都要靠自己摸索。而且,我做的这只是2D环境,若要做3D环境难度还会指数级增长,一个2D图形只能绕Z轴旋转,但一个3D图形能有无数个旋转轴,这就涉及到四元数的相关知识。。。
说的这些,只为感慨。以后若有时候,我会再去继续完善我的这个项目,让其能达到’‘基本能用’‘吧。