如何处理像素完美的旋转碰撞检测?

有没有人有任何想法如何去实现旋转像素完美的碰撞检测与Android中的位图? 或者一般来说呢? 我目前有像素数组,但是我不知道如何根据任意的度数来操作它们。

我不熟悉Android,所以我不知道你有什么工具可以使用,但我可以告诉你一个通用的方法。 这将是多么容易取决于Android为您提供什么。 你将需要matrix,或者至less他们会简化计算。

对于初学者,为了避免进一步的计算,做一个边界框碰撞检查,并立即返回,如果它们不碰撞。 这是合乎逻辑的,因为如果边界框不碰撞它保证没有像素会碰撞。

之后,如果需要像素完美的碰撞检查,那么最重要的一点是您必须在相同的空间中执行该检查。 这可以通过从精灵A中获取每个像素,应用一系列变换以使其进入精灵B的局部空间,然后检查它是否与精灵B上该位置上的任何像素碰撞来完成。当两个像素检查是不透明的。

所以,你需要的第一件事就是为每个精灵建立一个世界matrix。 网上可能有教程教你如何创建一个,但它应该基本上是按照以下顺序连接几个简单的matrix:

Translation(-Origin) * Scale * Rotation * Translation(Position) 

这个matrix的效用是通过在局部空间乘以一个点 – 例如,如果使用像bitmap.getPixelAt(10,20)这样的方法获得像素,则在局部空间中定义10,20 – 由相应的世界matrix将它移入世界空间:

 LocalA * WorldMatrixA -> World LocalB * WorldMatrixB -> World 

如果你反转matrix,你也可以沿着相反的方向进行,即根据你使用的matrix将世界空间的点转换成每个精灵的局部空间:

 World * InverseWorldMatrixA -> LocalA World * InverseWorldMatrixB -> LocalB 

因此,为了将精灵A的局部空间中的一个点移动到精灵B的局部空间中 ,首先使用精灵A的世界matrix将其转换为世界空间,然后使用精灵B的世界matrix将其转化为精灵B的本地空间:

 LocalA * WorldMatrixA -> World * InverseWorldMatrixB -> LocalB 

转换之后,检查新的点是否在精灵B的边界内,如果是,则检查像这个位置的像素,就像精灵A做的那样。这样整个过程就变成了这样的样子(伪代码,未经testing) :

 bool PixelCollision(Sprite a, Sprite B) { // Go over each pixel in A for(i=0; i<a.Width; ++i) { for(j=0; j<a.Height; ++j) { // Check if pixel is solid in sprite A bool solidA = a.getPixelAt(i,j).Alpha > 0; // Calculate where that pixel lies within sprite B's bounds Vector3 positionB = new Vector3(i,j,0) * a.WorldMatrix * b.InverseWorldMatrix; // If it's outside bounds skip to the next pixel if(positionB.X<0 || positionB.Y<0 || positionB.X>=b.Width || positionB.Y>=b.Height) continue; // Check if pixel is solid in sprite B bool solidB = b.getPixelAt(positionB.X, positionB.Y).Alpha > 0; // If both are solid then report collision if(solidA && solidB) return true; } } return false; } 

尽管David Gouveia的回答听起来不错,但从演出的角度来看,这不是最好的解决scheme。 有几个重要的优化你需要做:

  1. 通过首先检查一个简单的圆形碰撞来清理和避免不必要的检查:在任何旋转中得到你的精灵的中心和半径,得到所有4个(已经旋转的)顶点的极小值和极大值x和y坐标:然后你可以构造通过以下方式closures精灵的一个圆圈:

    center = max_x-min_x / 2,max_y-min_y / 2

    半径= max(max_x-min_x,max_y-min_y)

  2. 现在应该没有太多候选人通过使用简单的仿射纹理映射algorithm来对已经变换的(旋转的)图像进行光栅化检查。 基本上,每个光栅化精灵跟踪4行:从顶点a到下一个顶点(b和c)的2条线从顶点u1 / v1进入“位图空间”到下一个顶点u2 / v2和u3 / v3:注:我GOOGLE了这个图像,它显示了一个三角形,你的盒子只是两个三角形。 这个algorithm绘制水平线 (这就是为什么称为“ 光栅化器 ”)是非常重要的,以避免由于四舍五入误差导致位图内的“空洞”。 通过使用bresenhamalgorithm计算线条,每个像素只需要4个添加和4个比较(有时还需要两个额外的添加,具体取决于斜率)。您所做的是编写自己的多边形纹理贴图器,但是不需要昂贵的(和困难的以优化)3d校正。 仿射纹理映射

  3. 您可以轻松降低碰撞位图的分辨率(例如因子2),并节省更多时间。 一半分辨率的碰撞检查是不明显的。

  4. 如果使用graphics加速,可以使用某种HW加速缓冲区检查(模板?)来避免自己对光栅器进行编码。

主要的问题是:Java访问存储在二维数组中的位图数据时速度不是很快。 我建议将数据存储在一维数组中,以避免每次访问至less有一次indexOutOfBounds检查。 也可以使用2的幂(如64×64,128×128等),通过这个可以通过位移而不是乘法来计算偏移量。 您也可以优化第二个纹理访问权限,只有当第一个纹理访问权限值为0时=(透明)

所有这些问题都是在软件渲染引擎中解决的,查看源代码可能是有用的