|
從根本上來講，分離軸定理（以及其他碰撞算法）的用途就是去檢測并判斷兩個圖形之間是否有間隙,。分離軸定理中用到的方法使算法本身顯得十分獨特。
我所聽到過分離軸定理的最好類比方式是這樣的：
假想你拿一個電筒從不同的角度照射到兩個圖形上,，那么會有怎樣的一系列的陰影投射到它們之后的墻壁上呢？
如果你用這個方式從每一個角度上對這兩個圖形進行處理，并都找不到任何的間隙，那么這兩個圖形就一定接觸,。如果你找到了一個間隙，那么這兩個圖形就顯而易見地沒有接觸,。
從編程的角度來講，從每個可能的角度上去檢測會使處理變得十分密集,。不過幸運的是,，由于多邊形的性質(zhì)，你只需要檢測其中幾個關(guān)鍵的角度,。
你需要檢測的角度數(shù)量就正是這個多邊形的邊數(shù),。也就是說，你所需檢測的角度最大數(shù)量就是你要檢測碰撞的兩個多邊形邊數(shù)之和,。舉個例子,，兩個五邊形就需要檢測10個角度。
這是一個簡易但比較啰嗦的方法,，以下是基本的步驟：
步驟一：從需要檢測的多邊形中取出一條邊,，并找出它的法向量（垂直于它的向量），這個向量將會是我們的一個“投影軸”,。
步驟二：循環(huán)獲取第一個多邊形的每個點,，并將它們投影到這個軸上。（記錄這個多邊形投影到軸上的最高和最低點）
步驟三：對第二個多邊形做同樣的處理,。
步驟四：分別得到這兩個多邊形的投影,，并檢測這兩段投影是否重疊。
如果你發(fā)現(xiàn)了這兩個投影到軸上的“陰影”有間隙，那么這兩個圖形一定沒有相交,。但如果沒有間隙,，那么它們則可能接觸，你需要繼續(xù)檢測直到把兩個多邊形的每條邊都檢測完,。如果你檢測完每條邊后,，都沒有發(fā)現(xiàn)任何間隙，那么它們是相互碰撞的,。
這個算法基本就是如此的,。
順帶提一下，如果你記錄了哪個軸上的投影重疊值最?。ㄒ约爸丿B了多少）,，那么你就能用這個值來分開這兩個圖形。
那么如何處理圓呢,？
在分離軸定理中,，檢測圓與檢測多邊形相比，會有點點奇異,，但仍然是可以實現(xiàn)的,。
最值得注意的是，圓是沒有任何的邊,，所以是沒有明顯的用于投影的軸,。但它有一條“不是很明顯的”的投影軸。這條軸就是途經(jīng)圓心和多邊形上離圓心最近的頂點的直線,。
在這以后就是按套路遍歷另一個多邊形的每條投影軸,，并檢測是否有投影重疊。
噢,，對了,，萬一你想知道如何把圓投影到軸上，那你只用簡單地把圓心投影上去,，然后加上和減去半徑就能得到投影長度了,。
二、代碼解析
1,、html代碼如下：
1 2 | <canvas width="800" height="500" id="mycanvas">Loading...</canvas>
<div id="select-box"></div>
|
2,、main.js主要是控制位移以及圓圈大小，代碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | var SHAPE_SIZE = 80, SHAPE_HANDLE_SIZE = 10;
var CANVAS_WIDTH, CANVAS_HEIGHT;
var renderer;
var shA = null, shB = null;
window.onload = function () {
var canvasTag = document.getElementById("mycanvas");
var canvas = canvasTag.getContext("2d");
CANVAS_WIDTH = canvasTag.width;
CANVAS_HEIGHT = canvasTag.height;
renderer = new Renderer(canvas);
setInterval(function () {
renderer.loopDraw();
}, 30);
MouseEvent.addEvents(canvasTag);
main();
};
function main () {
UIUtils.createSelect();
shA = UIUtils.createShape(150, 250, "shA-select");
renderer.add(shA);
shB = UIUtils.createShape(540, 250, "shB-select");
renderer.add(shB);
}
function getPolygonVertices (edges, r) {
var ca = 0, aiv = 360 / edges, ata = Math.PI / 180, list = new Array();
for (var k = 0; k < edges; k++) {
var x = Math.cos(ca * ata) * r,
y = Math.sin(ca * ata) * r;
list.push(new Vec2(x, y));
ca += aiv;
}
return list;
}
|
SHAPE_SIZE = 80, SHAPE_HANDLE_SIZE = 10 (SHAPE_SIZE設(shè)置外圓環(huán)大小,，SHAPE_HANDLE_SIZE設(shè)置內(nèi)圓大?。琔IUtils.createShape(150, 250, "shA-select")設(shè)置第一個圓的x軸,、y軸位移,，還有外圓環(huán)選擇的形狀是什么,，UIUtils.createShape(540, 250, "shB-select")設(shè)置第二個圓的x軸、y軸位移,，還有外圓環(huán)選擇的形狀是什么,。
3、SAT.js主要是控制拖動圓點時,，外框的顏色等,，部分代碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | var SAT = (function () {
function testCollision (A, B) {
var res, color = "#333333";
if (A.type == "polygon" && B.type == "polygon") {
res = polygonsCollisionTest(A, B);
} else if (A.type == "circle" && B.type == "circle") {
res = circlesCollisionTest(A, B);
} else {
var c, p;
if (A.type == "circle") {
c = A;
p = B;
} else {
c = B;
p = A;
}
res = circlePolygonCollisionTest(c, p);
}
if (res) {
color = "#FF0000";
}
A.color = B.color = color;
}
|
4、Circle.js是控制第二個圓的外框顏色等,，代碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | function Circle (r) {
this.objectIndex = Renderer.objectIndex++;
this.type = "circle";
this.r = r;
this.x = 0;
this.y = 0;
this.color = "#333333";
}
Circle.prototype = {
draw : function (c) {
c.arc(0, 0, this.r, 0, Math.PI * 2);
},
getProjection : function (axis) {
var pro = Vec2.dot(new Vec2(this.x, this.y), axis) / axis.length();
return {min : pro - this.r, max : pro + this.r};
}
};
|
5,、Polygon.js是控制第一個圓的外框顏色等，代碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | function Polygon (list) {
this.objectIndex = Renderer.objectIndex++;
this.type = "polygon";
this.vertices = list;
this.x = 0;
this.y = 0;
this.color = "#333333";
}
Polygon.prototype = {
getRootCoordinate : function () {
var list = this.vertices, res = new Array();
for (var i = 0, l = list.length; i < l; i++) {
var coord = list[i];
res.push(new Vec2(coord.x + this.x, coord.y + this.y));
}
return res;
},
draw : function (c) {
var list = this.vertices;
if (list.length <= 1) {
return;
}
c.moveTo(list[0].x, list[0].y);
for (var i = 1, l = list.length; i < l; i++) {
var coord = list[i];
c.lineTo(coord.x, coord.y);
}
c.closePath();
},
getSides : function () {
var list = this.vertices,
l = list.length,
res = new Array();
if (l >= 3) {
for (var j = 1, pre = list[0]; j < l; j++) {
var p = list[j];
res.push(Vec2.substract(p, pre));
pre = p;
}
res.push(Vec2.substract(list[0], list[l - 1]));
}
return res;
},
getProjection : function (axis) {
var list = this.getRootCoordinate(), min = null, max = null;
for (var i = 0, l = list.length; i < l; i++) {
var p = list[i];
var pro = Vec2.dot(p, axis) / axis.length();
if (min === null || pro < min) {
min = pro;
}
if (max === null || pro > max) {
max = pro;
}
}
return {min : min, max : max};
},
getNearestPoint : function (p1) {
var list = this.getRootCoordinate(), rP = list[0], minDis = Vec2.distance(p1, rP);
for (var i = 1, l = list.length; i < l; i++) {
var p2 = list[i], d = Vec2.distance(p1, p2);
if (d < minDis) {
minDis = d;
rP = p2;
}
}
return rP;
}
};
|
6,、Renderer.js是控制整體外框的屬性,，比如顏色邊框等，代碼如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | Renderer.prototype = {
loopDraw : function () {
var c = this.canvas;
c.fillStyle = "#ff0000";
c.fillRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
for (var i = 0, l = this.displayList.length; i < l; i++) {
var o = this.displayList[i];
c.save();
c.translate(o.x, o.y);
c.beginPath();
c.globalAlpha = 0.6;
c.arc(0, 0, SHAPE_HANDLE_SIZE, 0, Math.PI * 2);
c.fillStyle = "#0000FF";
c.fill();
c.beginPath();
c.globalAlpha = 1;
o.draw(c);
c.strokeStyle = o.color;
c.lineWidth = 2;
c.stroke();
c.restore();
}
},
add : function (o) {
this.displayList.push(o);
},
remove : function (o) {
for (var i = 0, l = this.displayList.length; i < l; i++) {
var child = this.displayList[i];
if (child.objectIndex == o.objectIndex) {
this.displayList.splice(i, 1);
break;
}
}
}
};
|
三,、文件以及演示截圖
1,、文件截圖
2、演示截圖
3,、雙擊index.html文件即可運行看效果
|
