XXHolic

XXHolic 查看完整档案

深圳编辑  |  填写毕业院校  |  填写所在公司/组织 github.com/XXHolic 编辑
编辑

个人动态

XXHolic 发布了文章 · 10月12日

碰撞检测 :Separating Axis Theorem

引子

Collision Detection :Transformation 中介绍了动态的碰撞检测,至此 CollisionDetection 项目的主要内容差不多都涉及了。在查询资料的时候,还接触到一些其它的检测方法,现在来看一下另外一种检测方法: Separating Axis Theorem 。

相关知识点

矢量和标量

简单的来说:

  • 矢量(vector)也称向量,有大小和方向的量,例如加速度、力。
  • 标量(scalar)只有大小(magnitude)的量,例如时间、温度。

在几何中,矢量用有向线段表示,表示如下:

64-vector

矢量 V 计算方法:

  • V = C2 - C1
  • V = (7-3,7-2)
  • V = (4,5)

法向量:向量的垂直向量,交换 xy 分量,然后将坐标 x 分量取反。上面 V 的法向量为 (-5,4) 。

64-perpendicular-vector

点积和投影

点积

两个矢量,可以用点积(Dot Product)的方式进行相乘,结果是一个标量。表示形式为: A · B 。

点积有两种计算方式:

方式一

A · B = Ax * Bx + Ay * By

方式二

A · B = |A| * |B| * cos(θ)
  • |A| 是矢量 A 的量值
  • |B| 是矢量 A 的量值
  • θ 是矢量 A 和 B 之间的角度

还需要了解的一个概念就是单位向量,单位向量计算方法:向量除以向量自身的量值。

A / |A|

更多信息见这里

投影

关于投影(Projection),先看下图:

64-projection

想象用一个发出平行光线的光源,照射到一个物体上,将在一个面上产生阴影。这个阴影是三维物体的二维投影。

类似的,二维物体的投影就是一维的“阴影”。

64-projection2

点积和投影的关系

利用点积可以得出一个矢量在另外一个矢量上的投影。通过简单的推导就可以明白。

64-dot

如上图所示,将 V 在 W 上的投影标量记为 Pw(V),可以得知:

Pw(V) = |V| * cos(θ)

根据点积计算方法得知:

V · W = |V| * |W| * cos(θ)
V * (W / |W|) = |V| * cos(θ)

因此可以得出:

Pw(V) = |V| * cos(θ) = V * (W / |W|)

多边形

凸多边形

一条直线穿过一个多边形时,如果该线与多边形相交不超过(包含)两次,则该多边形为凸多边形(​Convex Polygon)。

64-convex

凹多边形

一条直线穿过一个多边形时,如果该线与多边形相交超过两次,则该多边形为凹多边形(Concave Polygon)。

64-concave

Separating Axis Theorem

分轴理论(Separating Axis Theorem)由 Hermann Minkowski 提出,可用于解决凸多边形碰撞问题,该理论表明:

如果存在一条轴线,两个凸面物体在该轴上的投影没有重叠,那么这两个凸面物体就没有重叠。

这个轴线称为分轴。接下来进一步讨论一下。在下文中分轴理论简称 SAT 。

没有重叠

64-concave-shadow

在上图中,可以看到投影没有重叠,根据 SAT ,这个两个形状没有重叠。

SAT 在检测的时候,可能需要检测很多轴线,但只要检测到有一个轴线上投影没有重叠,就可以停止继续检测。由于这种特点,SAT 对于有很多物体但碰撞很少的应用(游戏、模拟等等)是理想的选择。

重叠

如果在所有分轴上,形状的投影都重叠,那么我们可以确定这些形状产生了重叠。示例如下:

64-concave-overlap

算法实现

有了上面的原理,接下来转换成算法需要考虑的问题有:

  1. 如何获取到所有潜在的分轴?
  2. 投影重叠判断依据是什么?

问题 1

通过查找资料,第一个问题的答案是:在 2D 中,所有潜在的分轴是形状每条边的法线。

法线简单来说就是没有方向的法向量。在前面的知识点中有介绍。下面是一个大概逻辑实现:

const vertices = [] // 顶点的坐标集合,假设已有值
const axes = [] // 存放分轴
const verticesLen = vertices.length;

for (let i = 0; i < verticesLen; i++) {
  const p1 = vertices[i];
  const p2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
  // 获取每条边的矢量代数表示,subtract 方法功能主要功能是 p2 的坐标与 p1 坐标分量相减
  const edge = subtract(p1,p2);
  // 获取法向量,normalAxes 方法主要功能: (x, y) => (-y, x) or (y, -x)
  const normal = normalAxes(edge);
  axes.push(normal);
}

问题 2

在上面的关于 SAT 的介绍中,在图示中可以比较明显观察到,在算法实现中,需要遍历形状所有的顶点与分轴执行点积,比较获得最小值和最大值。然后在一条轴线上大概标注出最小值和最大值,看是否有重叠的区间。

下面是一个大概逻辑实现:

假设有多边形 A 和多边形 B 。

const verticesA = []; // A 形状所有顶点坐标集合
const verticesB = []; // B 形状所有顶点坐标集合
const axes = [] // 存储获取的所有分轴
const axesLen = axes.length;

for (let i = 0; i < axesLen; i++) {
  const separateAxes = axes[i];
  // getProject 方法获取投影的最大和最小值
  const projectA = getProject(separateAxes,verticesA);
  const aMin = projectA.min;
  const aMax = projectA.max;
  const projectB = getProject(separateAxes,verticesB);
  const bMin = projectB.min;
  const bMax = projectB.max;
  // 符合该条件,表示投影重叠了。
  if ( (aMin <= bMax && aMin >= bMin) || (bMin <= aMax && bMin >= aMin) ) {
    continue;
  } else {
    return false;
  }
}

验证

根据上面的思路,以网页左上角作为坐标原点,水平向左作为 X 轴,垂直向下作为 Y 轴。根据 CSS 的单位描述坐标点。

这个是测试页面,移动端如下:

64-example

在上面测试页面中,以未重叠的投影数据为例,检测的数据投影到一条轴线上:

64-project

可以看出没有重叠。

参考资料

查看原文

赞 0 收藏 0 评论 0

XXHolic 发布了文章 · 10月5日

碰撞检测 : Transformation

引子

Collision Detection :Triangle 中对三角形的碰撞检测从另外一种思路进行思考,到目前为止介绍的都是静态的检测,接着来看一下动态的碰撞检测。

以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。

Transformation

这是示例页面

基于 canvas 的 translaterotatescale 三种转换形成的动画,看看如何进行动态的碰撞检测。

基于 canvas 的动画原理是每隔一段时间进行重绘,所以在检测的时候,实际上是在特定的时刻,进行静态的碰撞检测,所以之前介绍的方法同样适用,这里统一使用 Polygon/Polygon 中的方法。 检测方法有了,接着就是获取在屏幕中相关点动态变化的坐标。下面分情况进行说明。

translate

在 canvas 上进行绘制时,都是基于坐标系进行定位,画布左上角为坐标系原点,水平向右为 X 轴正方向,垂直向下为 Y 轴正方向。绘制一个矩形 rect(20, 20, 40, 40) ,在坐标系上是这样的:

63-origin

如果想要水平向右移动 60 像素,垂直向下移动 80 像素,可以直接进行坐标相加:rect(20 + 60, 20 + 80, 40, 40)

63-new-coord

但还有另外一种更有趣的方式:移动整个坐标轴。如果把整个坐标轴水平向右移动 60 像素,垂直向下移动 80 像素,在视觉上是完全一样的。 translate 方法就是使用这种方式。

63-moved-grid

从上图可以发现,这种方式不用考虑矩形的坐标变化,在处理比较复杂的图形时,会方便很多。

需要注意的是,在进行了 translate 后,需要重置坐标轴,因为可能还有其它图形存在,而且还是以原来的坐标轴作为参考。重置坐标轴使用 setTransform 方法:

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");

ctx.translate(50, 50);
ctx.fillRect(0,0,100,100);

// 重置
ctx.setTransform(1, 0, 0, 1, 0, 0);

// 其它处理

对于变化后的坐标,直接对平移的像素进行加减。

/**
 * 假设点 A(x,y),经过 translate(x1,y1) 后达到 B(m,n)
 */
 const m = x + x1;
 const n = y + y1;

rotate

rotate 方法与 translate 方法类似,通过旋转坐标轴实现。

63-rotate-grid

对于变化后的坐标,需要进行一些计算。

63-rotate-calculate

/**
 *
 * 圆心坐标 O(0,0),假设点 A(x,y) ,与 X 轴形成的角度为 α
 * 顺时针旋转角度 β 后达到点 B(m,n),下面来推导一下 B 点坐标
 *
 * A 到圆心的距离: dist1 = |OA| = y/sin(α)=x/cos(α)
 * B 到圆心的距离: dist2 = |OB| = n/sin(α-β)=m/cos(α-β)
 *
 * 只是旋转 所以 dist1 = dist2,建设旋转的半径为 r :
 * r = y/sin(α)=x/cos(α)=n/sin(α-β)=m/cons(α-β)
 * y = r * sin(α)  x = r * cos(α)
 *
 * 根据三角函数公式:
 * sin(α+β)=sin(α)cos(β)+cos(α)sin(β)
 * sin(α-β)=sin(α)cos(β)-cos(α)sin(β)
 * cos(α+β)=cos(α)cos(β)-sin(α)sin(β)
 * cos(α-β)=cos(α)cos(β)+sin(α)sin(β)
 *
 * 代入下面公式:
 * m = r*cos(α-β) = r * cos(α)cos(β) + r * sin(α)sin(β) =  x * cos(β) + y * sin(β)
 * n = r*sin(α-β) = r * sin(α)cos(β) - r * cos(α)sin(β) =  y * cos(β) - x * sin(β)
 *
 * 逆时针则相反:
 * m =  x * cos(β) - y * sin(β)
 * n =  y * cos(β) + x * sin(β)
 *
 */

scale

scale 方法 translate 方法类似,通过缩放坐标轴实现。

对于变化后的坐标,直接乘以对应缩放的倍数。

/**
 * 假设点 A(x,y),经过 scale(num1,num2) 后达到 B(m,n)
 */
const m = x * num1;
const n = y * num2;

Transformation Order

当连续进行多次不同变换时,顺序不同,结果可能会不一样。这是示例

这是因为连续进行变换时,都是基于上一次变换后的状态,再次进行变换。在进行计算的时候,需要多方面考虑。基于 transform 中的参数格式,进行计算会比较方便一些,translaterotatescale 的效果都可以转换为 transform 的形式。

/**
 * canvas.transform(sx, ry, rx, sy, tx, ty)
 * sx-水平缩放,ry-垂直倾斜,rx-水平倾斜,sy-垂直缩放,tx-水平移动,ty-垂直移动
 *
 */
function Transform() {
  this.reset();
}

Transform.prototype.reset = function() {
  this.transformData = [1,0,0,1,0,0];
};

Transform.prototype.translate = function(x, y) {
  let [sx,ry,rx,sy,tx,ty] = this.transformData;
  const newTX = sx * x + rx * y;
  const newTY = ry * x + sy * y;
  this.transformData = [sx,ry,rx,sy,newTX,newTY];
};

Transform.prototype.rotate = function(angle) {
  let c = Math.cos(angle);
  let s = Math.sin(angle);
  let [sx,ry,rx,sy,tx,ty] = this.transformData;
  let newSX = sx * c + rx * s;
  let newRY = ry * c + sy * s;
  let newRX = sx * -s + rx * c;
  let newSY = ry * -s + sy * c;
  this.transformData = [newSX,newRY,newRX,newSY,tx,ty];
};

Transform.prototype.scale = function(x, y) {
  let [sx,ry,rx,sy,tx,ty] = this.transformData;
  let newSX = sx * x;
  let newRY = ry * x;
  let newRX = rx * y;
  let newSY = sy * y;
  this.transformData = [newSX,newRY,newRX,newSY,tx,ty];
};

Transform.prototype.getCoordinate = function(x, y) {
  let [sx,ry,rx,sy,tx,ty] = this.transformData;
  const px = x * sx + y*rx + tx;
  const py = x * ry + y*sy + ty;
  return [px,py];
};

参考资料

查看原文

赞 1 收藏 0 评论 0

XXHolic 发布了文章 · 10月2日

碰撞检测 :Triangle

引子

Collision Detection :Polygon 中主要介绍了多边形相关的碰撞检测,接着来看看三角形的情况。三角形同样属于多边形,因此,多边形的方法对三角形都适用。在这里探讨一下另外一种思路。

以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。

Triangle/Point

这是示例页面

三角形与点的碰撞检测,可以从面积的角度进行切入,看下面的一张图:

62-tri-point

如果点在三角形内,那么与三角形顶点相连,切割成了三部分,这三部分的面积之和,如果跟三角形面积相等,那么就可以说明发生了碰撞。

计算三角形的面积可以使用叉积海伦公式:

62-math

/**
 * 叉积 用符号 x 表示
 * V 矢量
 * W 矢量
 * |V| |W| 矢量的模,就是线段实际长度
 * θ V 与 W 之间的角度
 */

V x W = |V| * |W| * sin(θ)

/**
 * 计算面积公式
 * a 底
 * h 高
 */
S = a * h * 1/2

从上图中可以看出 |W| * sin(θ) 的结果就是三角形的高 h ,也就是说:

S = a * h * 1/2 = V x W *1/2

基于上面的理论支持,下面是完整检测逻辑:

/*
 * points 三角形顶点坐标,形式为 [[x1,y1],[x2,y2]]
 * (px,py) 检测点坐标
 */
function checkTrianglePoint({points,px,py}) {
  const [point1,point2,point3] = points;
  const [x1,y1] = point1;
  const [x2,y2] = point2;
  const [x3,y3] = point3;
  // 原始总面积
  const areaOrig = Math.abs( (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1) );

  // 检测点与三角形顶点形成的面积
  const area1 = Math.abs( (x1-px)*(y2-py) - (x2-px)*(y1-py) );
  const area2 = Math.abs( (x2-px)*(y3-py) - (x3-px)*(y2-py) );
  const area3 = Math.abs( (x3-px)*(y1-py) - (x1-px)*(y3-py) );
  const areaTotal = area1 + area2 + area3;

  // 计算误差允许值
  const buffer = 0.1;
  if (areaTotal >= areaOrig-buffer && areaTotal<= areaOrig+buffer) {
    return true;
  }
  return false;
}

参考资料

查看原文

赞 0 收藏 0 评论 0

XXHolic 发布了文章 · 9月21日

碰撞检测 :Polygon

引子

Collision Detection :Line 中主要介绍了直线相关的碰撞检测,接着来看看更加复杂一些的多边形的情况。

以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。

Polygon/Point

这是示例页面

多边形与点的碰撞检测,需要每一条边与点进行检测,才能确定是否产生了碰撞:


const points = []; // 多边形顶点坐标

const pointsLen = points.length;

let collision = false; // 初始化碰撞状态

for(let index = 0; index < pointsLen; index ++) {

// checkCondition 边与检测点的判断

if (checkCondition()) {

collision = !collision;

}

}

假设一条边的一个端点的坐标为 [cx,cy] ,另一端点坐标为 [nx,ny],检测点的坐标为 [px,py] ,需要检测的条件为:


if ( ((cy > py) != (ny > py)) && (px < (nx-cx) * (py-cy) / (ny-cy) + cx) ) {

collision = !collision;

}

这里的判断条件做了两个检测,首先是检查检测点的 Y 坐标是否在两个端点的 Y 坐标范围内:


(cy >= py && ny < py) || (cy < py && ny >= py)

// 等同于

(cy > py) != (ny > py)

61-polygon-point

然后检查监测点的 X 坐标,依赖的方法是 Jordan Curve Theorem :


px < (nx-cx) * (py-cy) / (ny-cy) + cx)

每次检测后,符合条件都需要将 collision 的布尔值取反。直到检测所有的边后,最后的 collision 值才是最终结果。

下面是完整检测逻辑:


/*

* points 多边形顶点坐标,形式为 [[x1,y1],[x2,y2]]

* (px,py) 检测点坐标

*/

function checkPolygonPoint({points,px,py}) {

let collision = false;

const pointsLen = points.length;

for (let index = 0; index < pointsLen; index++) {

const currentPoint = points[index];

const next = index === pointsLen-1 ? 0:index+1;

const nextPoint = points[next];

const [cx,cy] = currentPoint;

const [nx,ny] = nextPoint;

const judgeX = px < (nx-cx)*(py-cy) / (ny-cy)+cx;

const judgeY = (cy >= py && ny < py) || (cy < py && ny >= py);

if (judgeX && judgeY) {

collision = !collision;

}

}

return collision;

}

Polygon/Circle

这是示例页面

多边形与圆的碰撞检测,可以分解为多边形的边与圆的碰撞检测,只要有一条边产生了碰撞,就可以进行判定。这个时候可以使用之前介绍的关于 Line/Circle 检测的方法。

下面是完整检测逻辑:


/*

* points 多边形顶点坐标,形式为 [[x1,y1],[x2,y2]]

* (cx,cy) 圆心坐标

* radius 圆半径

*/

function checkPolygonCircle({points,cx,cy,radius}) {

const pointsLen = points.length;

for (let index = 0; index < pointsLen; index++) {

const currentPoint = points[index];

const next = index === pointsLen-1 ? 0:index+1;

const nextPoint = points[next];

const [x1,y1] = currentPoint;

const [x2,y2] = nextPoint;

const collision = checkLineCircle({x1,y1,x2,y2,cx,cy,radius});

if (collision) {

return true;

}

}

return false;

}

Polygon/Rectangle

这是示例页面

多边形与矩形的碰撞检测,可以分解为多边形的边与矩形的碰撞检测,只要有一条边产生了碰撞,就可以进行判定。这个时候可以使用之前介绍的关于 Line/Rectangle 检测的方法。

下面是完整检测逻辑:


/*

* points 多边形顶点坐标,形式为 [[x1,y1],[x2,y2]]

* (rx,ry) 矩形左上角顶点坐标

* rw 矩形宽度

* rh 矩形高度

*/

function checkPolygonRectangle({points,rx,ry,rw,rh}) {

const pointsLen = points.length;

for (let index = 0; index < pointsLen; index++) {

const currentPoint = points[index];

const next = index === pointsLen-1 ? 0:index+1;

const nextPoint = points[next];

const [x1,y1] = currentPoint;

const [x2,y2] = nextPoint;

const collision = checkLineRectangle({x1,y1,x2,y2,rx,ry,rw,rh});

if (collision) {

return true;

}

}

return false;

}

Polygon/Line

这是示例页面

多边形与直线的碰撞检测,可以分解为多边形的边与直线的碰撞检测,只要有一条边产生了碰撞,就可以进行判定。这个时候可以使用之前介绍的关于 Line/Line 检测的方法。

下面是完整检测逻辑:


/*

* points 多边形顶点坐标,形式为 [[x1,y1],[x2,y2]]

* (x1,y1) 直线线端点坐标

* (x2,y2) 直线另一个端点坐标

*/

function checkPolygonLine({points,x1,y1,x2,y2}) {

const pointsLen = points.length;

for (let index = 0; index < pointsLen; index++) {

const currentPoint = points[index];

const next = index === pointsLen-1 ? 0:index+1;

const nextPoint = points[next];

const [x3,y3] = currentPoint;

const [x4,y4] = nextPoint;

const collision = checkLineLine({x1,y1,x2,y2,x3,y3,x4,y4});

if (collision) {

return true;

}

}

return false;

}

Polygon/Polygon

这是示例页面,刷新页面,会生成随机的多边形。

多边形与多边形的碰撞检测,思路是检测一个多边形任意边是否与另外一个多边形的任意边产生碰撞。这个时候可以使用前面介绍的关于 Polygon/Line 检测的方法。

下面是完整检测逻辑:


/*

* points1 多边形1顶点坐标,形式为 [[x1,y1],[x2,y2]]

* points2 多边形2顶点坐标,形式为 [[x1,y1],[x2,y2]]

*/

function checkPolygonPolygon({points1,points2}) {

const pointsLen = points1.length;

for (let index = 0; index < pointsLen; index++) {

const currentPoint = points1[index];

const next = index === pointsLen-1 ? 0:index+1;

const nextPoint = points1[next];

const [x1,y1] = currentPoint;

const [x2,y2] = nextPoint;

const collision = checkPolygonLine({points:points2,x1,y1,x2,y2});

if (collision) {

return true;

}

}

return false;

}

参考资料

查看原文

赞 1 收藏 0 评论 5

XXHolic 发布了文章 · 9月14日

碰撞检测 :Line

引子

Collision Detection :Rectangle 中主要介绍了矩形相关的碰撞检测,接着来看看直线的情况。

以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。

Line/Point

这是示例页面

线与点的碰撞检测,观察下面一张图:

60-line-point

从图中可以发现,当点在线上时,到两个端点的距离之和与线的长度相同。两点之间的距离,同样使用之前用到过的勾股定理。考虑到计算的精度误差,可以设置一个误差允许范围值,这样会感觉更加自然一些。


/*

* (x1,y1) 线的一个端点

* (x2,y2) 线的另一个端点

* (px,py) 检测点的坐标

*/

function checkLinePoint({x1,y1,x2,y2,px,py}) {

const d1 = getLen([px,py],[x2,y2]);

const d2 = getLen([px,py],[x2,y2]);

const lineLen = getLen([x1,y1],[x2,y2]);

const buffer = 0.1; // 误差允许范围

if (d1+d2 >= lineLen-buffer && d1+d2 <= lineLen+buffer) {

return true; // 发生碰撞

} else {

return false; // 没有碰撞

}

}

  

/*

* 勾股定理计算两点间直线距离

* point1 线的一个端点

* point2 线的另一个端点

*/

function getLen(point1,point2) {

const [x1,y2] = point1;

const [x2,y2] = point1;

const minusX = x2-x1;

const minusY = y2-y1;

const len = Math.sqrt(minusX*minusX + minusY*minusY);

return len;

}

Line/Circle

这是示例页面

直线和圆的碰撞检测,首先需要考虑直线是否位于圆内,因为有可能出现直线的长度小于圆的直径。为了检测这个,可以使用之前 Point/Circle 的检测方法,如果任意一端在内部,就直接返回 true 跳过剩下的检测。


const isInside1 = checkPointCircle({px:x1,py:y1,cx,cy,radius});

const isInside2 = checkPointCircle({px:x2,py:y2,cx,cy,radius});

if (isInside1 || isInside2) {

return true

}

接下来需要找到直线上离圆心最近的一个点,这个时候使用矢量的点积可以计算出最近点的坐标。下面是一个简单的数学推导过程。


/**

*

* a 代表线的向量

* t 系数

* p1 直线上任意一点

* p0 非直线上的一点

* pt 直线上离 p0 最近的一点

*

* pt = p1 + t*a // p1 和 pt 都在直线上,存在这样成立的关系系数 t

*

* (a.x,a.y)*(pt.x-p0.x,pt.y-p0.y) = 0 // 垂直的向量,点积为 0

*

* (a.x,a.y)*( (p1+t*a).x-p0.x,(p1+t*a).y-p0.y) = 0 // 带入 pt

*

* a.x *(p1.x + t*a.x - p0.x) + a.y *(p1.y + t*a.y - p0.y) = 0

* t*(a.x*a.x + a.y*a.y) = a.x*(p0.x-p1.x)+a.y*(p0.y-p1.y)

* t = (a.x*(p0.x-p1.x)+a.y*(p0.y-p1.y)) / ((a.x*a.x + a.y*a.y))

*

* 得出系数 t 的值后,代入到一开始的公式中,就可以得出 pt 的坐标

*/

然而得出的这个点可能存在这条线延伸的方向上,所以需要判断该点是否在所提供的线段上。这个时候可以使用前面介绍的关于 Line/Point 检测的方法。


const isOnSegment = checkLinePoint({x1,y1,x2,y2, px:closestX,py:closestY});

if (!isOnSegment) return false;

最后计算圆心到直线上最近点的距离,与圆的半径进行比较,判断是否碰撞。下面是主要逻辑:


/*

* (x1,y1) 线的一个端点

* (x2,y2) 线的另一个端点

* (px,py) 圆心的坐标

* radius 圆的半径

*/

function checkLineCircle({x1,y1,x2,y2,cx,cy,radius}) {

const isInside1 = checkPointCircle({px:x1,py:y1,cx,cy,radius});

const isInside2 = checkPointCircle({px:x2,py:y2,cx,cy,radius});

if (isInside1 || isInside2) {

return true

}

  

const pointVectorX = x1 - x2;

const pointVectorY = y1 - y2;

const t = (pointVectorX*(cx - x1) + pointVectorY*(cy-y1))/(pointVectorX*pointVectorX+pointVectorY*pointVectorY);

const closestX = x1 + t*pointVectorX;

const closestY = y1 + t*pointVectorY;

  

const isOnSegment = checkLinePoint({x1,y1,x2,y2, px:closestX,py:closestY});

if (!isOnSegment) return false;

  

const distX = closestX - cx;

const distY = closestY - cy;

const distance = Math.sqrt( (distX*distX) + (distY*distY) );

  

if (distance <= radius) {

return true; // 发生碰撞

} else {

return false; // 没有碰撞

}

}

  

Line/Line

这是示例页面

直线与直线的碰撞检测,需要借助数学的推导:


/**

*

* P1 P2 直线 1 上的两个点

* A1 代表直线 1 的向量

* t1 直线 1 的系数

*

* P3 P4 直线 2 上的两个点

* A2 代表直线 2 的向量

* t2 直线 2 的系数

*

* Pa = P1 + t1*A1

* Pb = P3 + t2*A2

*

* 相交时,Pa = Pb

* x1 + t1*(x2-x1) = x3 + t2*(x4-x3)

* y1 + t1*(y2-y1) =y3 + t2*(y4-y3)

*

* 剩下就是二元一次方程求解

* t1 = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3))/((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1))

* t2 = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1))

*

*/

计算出两条线的系数后,如果两条线相交,就要符合条件:


if (t1 >= 0 && t1 <= 1 && t2 >= 0 && t2 <= 1) {

return true;

}

return false;

下面是完整的判断方法:


/*

* (x1,y1) 线1的一个端点

* (x2,y2) 线1的另一个端点

* (x3,y3) 线2的一个端点

* (x4,y4) 线2的另一个端点

*/

function checkLineLine({x1,y1,x2,y2,x3,y3,x4,y4}) {

const t1 = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));

const t2 = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));

  

if (t1 >= 0 && t1 <= 1 && t2 >= 0 && t2 <= 1) {

return true; // 发生碰撞

} else {

return false; // 没有碰撞

}

}

Line/Rectangle

这是示例页面

直线与矩形的碰撞检测,可以转换为直线与矩形四条边的碰撞检测,使用前面介绍的关于 Line/Line 检测的方法即可。

60-line-rect


/*

* (x1,y1) 线的一个端点

* (x2,y2) 线的另一个端点

* (rx,ry) 矩形顶点坐标

* rw 矩形宽度

* rh 矩形高度

*/

function checkLineRectangle({x1,y1,x2,y2,rx,ry,rw,rh}) {

const isLeftCollision = checkLineLine(x1,y1,x2,y2, x3:rx,y3:ry,x4:rx, y4:ry+rh);

const isRightCollision = checkLineLine(x1,y1,x2,y2, x3:rx+rw,y3:ry, x4:rx+rw,y4:ry+rh);

const isTopCollision = checkLineLine(x1,y1,x2,y2, x3:rx,y3:ry, x4:rx+rw,y4:ry);

const isBottomCollision = checkLineLine(x1,y1,x2,y2, x3:rx,y3:ry+rh, x4:rx+rw,y4:ry+rh);

  

if (isLeftCollision || isRightCollision || isTopCollision || isBottomCollision ) {

return true; // 发生碰撞

} else {

return false; // 没有碰撞

}

}

参考资料

查看原文

赞 1 收藏 1 评论 0

XXHolic 发布了文章 · 9月7日

碰撞检测 :Rectangle

引子

Collision Detection :Point 中主要介绍了点的碰撞检测,接着来看看矩形的情况。

以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。

Rectangle/Point

这是示例页面

绘制矩形可以通过四个点的坐标进行绘制,也可以通过一个顶点的坐标,结合矩形的宽高进行绘制:

59-rect-bounding-box

矩形与点的碰撞检测,只要点的坐标在矩形的坐标范围之内即可:

/*
 * (px,py) 点的坐标
 * (rx,ry) 矩形顶点的坐标
 * rw 矩形的宽度
 * rh 矩形的高度
 */
function checkRectanglePoint({px,py,rx,ry,rw,rh}) {
  const isTrue = px >= rx && // 左边界
                 px <= rx + rw && // 右边界
                 py >= ry && // 上边界
                 py <= ry + rh; // 下边界
  if (isTrue) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

Rectangle/Rectangle

这是示例页面

矩形与矩形的碰撞检测,看下面一张图:

59-rect-rect

通过观察可以得知,两个矩形发生碰撞,需要符合的条件是:

/*
 * (r1x,r1y) 矩形1顶点的坐标
 * (r2x,r2y) 矩形2顶点的坐标
 * r1w r1h 矩形1的宽度和高度
 * r2w r2h 矩形2的宽度和高度
 */
function checkRectangleRectangle({r1x,r1y,,r1w,r1h,r2x,r2y,r2w,r2h}) {
  const isTrue = r1x + r1w >= r2x && // 矩形 2 左边界
                 r1x <= r2x + r2w && // 矩形 2 右边界
                 r1y + r1h >= r2y && // 矩形 2 上边界
                 r1y <= r2y + r2h; // 矩形 2 下边界
  if (isTrue) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

Rectangle/Circle

这是示例页面

矩形与圆的碰撞检测,思路是:

  1. 首先要确定圆处于矩形那个边界;
  2. 然后在边界上确定与圆心距离最短的点;
  3. 最后使用勾股定理计算出距离,与圆心半径进行比较。
/*
 * (cx,cy) 圆心的坐标
 * radius 圆的半径
 * (rx,ry) 矩形顶点的坐标
 * rw 矩形的宽度
 * rh 矩形的高度
 */
function checkRectangleCircle({cx,cy,radius,rx,ry,rw,rh}) {
  let nearestX = cx,nearestY = cy; // 初始化边界上离圆心最近的点坐标
  if (cx < rx) {
    nearestX = rx;
  } else if (cx > rx + rw) {
    nearestX = rx + rw;
  }
  if (cy < ry) {
    nearestY = ry;
  } else if (cy > ry + rh) {
    nearestY = ry + rh;
  }
  const distX = cx-nearestX;
  const distY = cy-nearestY;
  const distance = Math.sqrt( (distX*distX) + (distY*distY) );

  if (distance <= radius) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

参考资料

查看原文

赞 0 收藏 0 评论 0

XXHolic 发布了文章 · 9月1日

碰撞检测:Point

引子

Collision Detection 中对碰撞检测作了简单的介绍。在查询资料时,在 Github 上发现了 CollisionDetection 这个项目。查看之后,发现关于碰撞检测的讨论,由浅入深,很适合学习。在其基础上,做了 JavaScript 版本的实现。

以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。

Point/Point

这是示例页面

最早的碰撞检测是检测两个点的碰撞。为了检测它们是否接触,我们只需要检查它们的 X 和 Y 坐标是否一样。

/*
 * (x1,x2) 点的坐标
 * (y1,y2) 点的坐标
 */
function checkPointPoint(x1,x2,y1,y2) {
  if (x1 == x2 && y1 == y2) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

Point/Circle

这是示例页面

点与圆的碰撞检测,只需要比较点和圆心之间的距离 distance 是否小于或等于圆的半径 r

function checkPointCircle() {
  if (distance <= r) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

如下图所示,计算两个点之间的距离,在几何上进行转换,使用勾股定理(Pythagorean Theorem)可以得出:

a*a + b*b = c*c; // 勾股定理
a = px - cx; // 点 x 坐标与 圆心 x 坐标
b = py - cy; // 点 y 坐标与 圆心 y 坐标
c = Math.sqrt(a*a + b*b);

58-point-circle

带入到上面检测碰撞的逻辑中:

/*
 * (px,py) 点的坐标
 * (cx,cy) 圆心的坐标
 * radius 圆的半径
 */
function checkPointCircle({px,py,cx,cy,radius}) {
  const minusX = px - cx;
  const minusY = py - cy;
  const distance = Math.sqrt(minusX*minusX + minusY*minusY);
  if (distance <= radius) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

Circle/Circle

这是示例页面

圆与圆的碰撞检测,只需要比较两个圆心之间的距离 distance 是否小于或等于两个圆的半径之和 r1+r2

同样的使用到了勾股定理。

/*
 * (c1x,c1y) 圆心的坐标
 * (c2x,c2y) 圆心的坐标
 * r1,r2 圆的半径
 */
function checkCircleCircle({c1x,c1y,c2x,c2y,r1,r2}) {
  const minusX = c1x - c2x;
  const minusY = c1y - c2y;
  const distance = Math.sqrt(minusX*minusX + minusY*minusY);
  if (distance <= r1+r2) {
    return true; // 发生碰撞
  } else {
    return false; // 没有碰撞
  }
}

参考资料

查看原文

赞 0 收藏 0 评论 0

XXHolic 发布了文章 · 8月28日

Canvas 绘制 1 px 直线模糊(非高清屏)的问题

引子

Canvas 显示模糊问题 中解决了在高清显示屏上模糊的问题,最近碰到了绘制直线的情况,使用了同样的方案,一开始觉得影响不大,但时间长了,发现非高清屏幕上,直线模糊的感觉越来越明显,就去找了下资料,进行了处理。

问题

这是问题重现页面

在网上同样可以找同样的问题,从各种回答中,在 LET’S CALL IT A DRAW(ING SURFACE) 中找到较有说服力的解释:

把每一个像素想象为一个正方形。整数坐标(0,1,2…)是正方形的边。如果你在整数坐标之间绘制 1 像素的线,它将与相邻像素块的边重叠,生成的线将绘制两个像素宽度。

例如,如果你尝试绘制从点(1,0)到(1,3)的 1 像素线,浏览器将会在 x=1 坐标点的两边绘制 0.5 屏幕像素。由于屏幕不能显示半个像素,它将线扩展到包含 2 个像素。

75-pixels-1

处理方法

按照上面举例的解释,对应的处理方式是:

如果你尝试从点(1.5,0)到(1.5,3)绘制 1 像素的线,浏览器将会在 x=1.5 坐标点的两边绘制 0.5 屏幕像素,结果就是 1 像素的线了。

75-pixels-2

也就是说为了绘制只有 1 像素的线,你需要将坐标垂直于线的方向偏移 0.5 。这是按照这种方式处理后的页面

下面在非高清屏上展示对比:

75-compare

除了上面有些效果的方法外,尝试过但无效的方法有:

  • 使用 context.translate(0.5, 0.5)
  • 使用 scale

参考资料

查看原文

赞 1 收藏 0 评论 0

XXHolic 发布了文章 · 8月28日

Canvas 图像灰度处理

引子

在玩游戏的时候,碰到一个交互效果:背景一张看起来黑白的图,然后用擦除的交互,让图像变的有颜色。也想试试做这个效果,首先想到的是那个黑白的图是怎么形成的,于是就查资料,找到了用 Canvas 转换的方法。

思路

看起来是黑白的图像,其实是灰度图像,进一步说明见图像。这种图像的特点是像素的颜色分量取值都是一样的,而 Canvas 的方法 getImageData 可以获取到画布上的像素值数据,改变数据后,使用方法 putImageData 将数据绘制到画布上。这样就可以达到灰度图像的效果。

实现

这是示例页面,移动端访问如下:

65-gray

主要实现如下:

  /**
   * 图像灰度处理
   * @param {object} context canvas 上下文
   * @param {number} sx 提取图像数据矩形区域的左上角 x 坐标。
   * @param {number} sy 提取图像数据矩形区域的左上角 y 坐标。
   * @param {number} sw 提取图像数据矩形区域的宽度。这要注意一下,canvas 标签上 width 属性值,不是渲染后实际宽度值,否则在高清手机屏幕下且做了高清处理,只能获取到部分图像宽度。
   * @param {number} sh 提取图像数据矩形区域的高度。这要注意一下,canvas 标签上 height 属性值,不是渲染后实际高度值,否则在高清手机屏幕下且做了高清处理,只能获取到部分图像高度。
   */
  function toGray(context,sx, sy, sw, sh) {
    var imageData = context.getImageData(sx, sy, sw, sh);
    var colorDataArr = imageData.data;
    var colorDataArrLen = colorDataArr.length;
    for(var i = 0; i < colorDataArrLen; i+=4) {
      // 计算方式之一
      var gray=(colorDataArr[i]+colorDataArr[i+1]+colorDataArr[i+2])/3;
      colorDataArr[i] = gray;
      colorDataArr[i+1] = gray;
      colorDataArr[i+2] = gray;
    }
    context.putImageData(imageData,0,0);
  }

参考资料

查看原文

赞 0 收藏 0 评论 0

XXHolic 发布了文章 · 8月28日

canvas 文本坐标(0,0)显示问题

引子

在测试 canvas 文字显示的时候,发现坐标设为(0,0),文字显示会有问题。

文本坐标(0,0)显示问题

刚开始本以为使用 canvas 的方法不对,尝试改变坐标后,发现又可以显示。这是问题示例,扫描访问二维码如下。

27-qrcode-problem

查询资料,发现了类似的问题,原因是 canvas 中的文本坐标位置,是按照属性 textBaseline 设置的基线作为参考,默认值是 alphabetic。效果如下图。

27-img-textbaseline

当位置坐标为(0,0)时,文本基线以上的就不在 canvas 显示区域内了,详细文档见 MDN textBaseline。将 textBaseline 设置为 top 就可以正常显示,这是正常示例,扫描访问二维码如下。

27-qrcode-normal

在测试的过程中,发现英文可以正常显示,但中文,字体大小不同,顶部显示可能有稍微的截断。目前想到的解决方法有:

  • 调整到适当的字体大小。
  • 将文本显示的位置稍微的下移。

参考资料

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 15 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2018-03-30
个人主页被 460 人浏览