HTML5画布中的像素完美碰撞检测

Question

我想在HTML5画布中检查两个精灵之间的碰撞。因此，为了讨论，假设两个精灵都是IMG对象，并且碰撞意味着alpha通道不为0。现在，这两个精灵都可以围绕物体中心旋转，但除此之外没有其他变换，如果这使得问题更容易解决。

现在，我想到的显而易见的解决方案是：

• 计算两者的变换矩阵
• 找出应该测试代码的大致估计区域（例如两个偏移量+计算的额外旋转空间）
• 对于相交矩形中的所有像素，变换坐标并测试在计算位置（四舍五入到最近的邻居）处的图像的alpha通道。然后在第一次命中时中止。

我认为这个方法存在的问题是：a）JavaScript中没有矩阵类，这意味着我必须在JavaScript中执行此操作，这可能会非常缓慢，我必须每帧测试碰撞，这使得这个过程非常昂贵。此外，我必须复制一些我已经在绘图上执行的操作（或者canvas为我执行的操作，设置矩阵）。

我想知道是否有更简单的解决方案来检测碰撞。

- Armin Ronacher

---

我找不到答案，我也在问这个问题 :( - user2039981

Answer 1

我不是JavaScript编程员，但我认为优化技巧对JavaScript和C++同样适用。

只需旋转精灵的角而不是每个像素。实际上，您将执行类似软件纹理映射的操作。您可以使用各种梯度信息计算给定像素的x、y位置。了解有关软件纹理映射的更多信息，请查阅相关资料。

如果将精灵分解成“命中”和“非命中”区域，则可以有效地检查给定四叉树分解是否全部为“非命中”，“全部命中”或“可能命中”（即包含命中和非命中像素）。前两个情况很容易通过。在最后一种情况下，您可以进入下一个分解级别并重复测试。这样，您只需检查需要的像素，并且对于大面积的“非命中”和“命中”，您不必进行如此复杂的检查。

无论如何，这只是几个想法。

- Goz

Answer 2

我需要在绘图上复制我已经有的东西。

您可以创建一个新的渲染上下文，在其上绘制一个旋转的白色背景掩码，将合成操作设置为“更明亮”，并在给定偏移量处在顶部绘制另一个旋转掩码。

现在，如果还有非白色像素，则存在命中。您仍然需要使用“getImageData”并筛选像素以找出结果。您可以通过将结果图像缩小（依靠抗锯齿来保持一些像素为非白色）来减少一些工作量，但我认为它可能仍然会很慢。

我必须每帧测试碰撞，这使得这个过程非常昂贵。

是的，我认为实际上您将使用预先计算的碰撞表。如果您有足够的空间，可以为每个精灵组合、相对旋转、相对-x-归一化到旋转和相对-y-归一化到旋转存储一个命中/未命中位。根据您拥有的精灵数量和旋转或移动的步数，这可能会变得相当大。

妥协方案是将每个精灵的预旋转掩码存储在JavaScript数组中（作为数字，为您提供32位/像素易于“&&”操作的数据，或作为字符串中的字符，为您提供16位），并将相交精灵掩码的每行进行“&&”。

或者，放弃像素，开始查看路径。

- bobince

Answer 3

同样的问题，另一种解决方案。首先，我使用getImageData数据来找到围绕精灵的多边形。在这里要小心，因为实现是针对具有透明背景且具有单个实体对象（如船）的图像。下一步是使用Ramer Douglas Peucker算法来减少多边形中顶点的数量。最后，我得到了一个非常少顶点的多边形，容易且便宜地旋转并检查每个精灵的其他多边形的碰撞。

http://jsfiddle.net/rnrlabs/9dxSg/

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

context.drawImage(img, 0,0);
var dat = context.getImageData(0,0,img.width, img.height);
// see jsfiddle
var startPixel = findStartPixel(dat, 0);
var path = followPath(startPixel, dat, 0);
// 4 is RDP epsilon
map1 = properRDP(path.map, 4, path.startpixel.x, path.startpixel.y);

// draw

context.beginPath();
context.moveTo(path.startpixel.x, path.startpixel.x);
for(var i = 0; i < map.length; i++) {
    var p = map[i];
    context.lineTo(p.x, p.y);
}
context.strokeStyle = 'red';
context.closePath();
context.stroke();

- rnrneverdies