ios - 确定一组像素的表面法线的最佳方法？

我目前的一项工作是为 iOS Cocos2D 创建一个 2D 可破坏地形引擎(参见 https://github.com/crebstar/PWNDestructibleTerrain)。毫无疑问，它处于婴儿阶段，但自几周前开始以来，我已经取得了重大进展。但是，我在计算表面法线时遇到了一些性能障碍。

注意:对于我的可破坏地形引擎，alpha 为 0 被认为不是实心地面。

下面发布的方法非常适用于小矩形，例如 n < 30。任何高于 30 的值都会导致帧速率下降。如果您接近 100x100，那么您不妨在 Sprite 尝试穿越地形时阅读一本书。目前，这是我能想到的最好的方法来改变 Sprite 在地形上漫游时的角度(要获得 Sprite 方向的角度，只需采用 100 * normal * (1,0) 向量的点积)。

-(CGPoint)getAverageSurfaceNormalAtCGPoint)pt withRectCGRect)area {

float avgX = 0;
float avgY = 0;
ccColor4B color = ccc4(0, 0, 0, 0);
CGPoint normal;
float len;

for (int w = area.size.width; w >= -area.size.width; w--) {
    for (int h = area.size.height; h >= -area.size.height; h--) {
        CGPoint pixPt = ccp(w + pt.x, h + pt.y);
        if ([self pixelAt:pixPt colorCache:&color]) {
            if (color.a != 0) {
                avgX -= w;
                avgY -= h;
            } // end inner if
        } // end outer if
    } // end inner for
} // end outer for

len = sqrtf(avgX * avgX + avgY * avgY);
if (len == 0) {
    normal = ccp(avgX, avgY);
} else {
    normal = ccp(avgX/len, avgY/len);
} // end if

return normal;
} // end get

我的问题是我的 Sprite 需要更大的矩形才能使其运动看起来更逼真。我考虑过缓存所有表面法线，但这会导致知道何时重新计算表面法线的问题，而且这些计算也非常昂贵( block 应该有多大？)。另一个较小的问题是我不知道如何正确处理长度 = 0 的情况。

所以我被困住了......来自社区的任何建议将不胜感激!我的方法是最好的吗？还是我应该重新考虑算法？我是游戏开发的新手，一直希望学习新的技巧和窍门。

---

Best Answer-推荐答案

有人在另一个论坛上回答了这个问题。我将发布修改后的 getSurfaceNormal 函数。这实现了 Nathan Reed 描述的第二种算法

-(CGPoint)getSurfaceNormalAtCGPoint)pt withSquareWidthint)area { //这个方法只看表面像素

int avgX = 0;
int avgY = 0;
CGPoint normal;
float len;
ccColor4B color = ccc4(0, 0, 0, 0);

for (int w = area; w >= -area; w--) {
    int h = area;
    do {
        if ([self pixelAt:ccp(w + pt.x, h + pt.y) colorCache:&color]) {
            if (color.a != 0) {
                if (w < 0) {
                    avgX -= w;
                    avgY -= h;
                } else {
                    avgX += w;
                    avgY += h;
                }
                break;
            } // end inner if
        } // end outer if
        h--;
    } while (h >= -area);
} // end for
int perpX = -avgY;
int perpY = avgX;
len = sqrtf(perpX * perpX + perpY * perpY);
normal = ccp(perpX/len, perpY/len);

return normal;
}

这里也是这个人的原始帖子:感谢 Nathan Reed 的回答

我认为你的基本想法是正确的。我将总结您当前的代码在做什么。要获得一个点周围区域内的平均法线，您需要收集以该点为中心的矩形中的所有像素。对于矩形中的所有实心像素，您将平均从像素到查询点的向量。实际上，您正在计算从附近实体像素的质心到查询点的向量。

我有两个一般性建议来加快速度。首先是您不需要查看搜索区域中的每个像素。通过使用稀疏采样，您可能会得到一个很好的近似值:只看几个孤立的像素，均匀分布在搜索区域中。例如，您可以在循环中以 2 到 5 个像素为单位，而不是 1 个像素；这会给你一个稀疏的网格采样，这可能足以让你侥幸逃脱。 Poisson disk sampling也是一种常见的稀疏采样方法，尤其是在用于软阴影、SSAO 等的像素着色器中。您预先计算泊松磁盘模式(只需将点存储在代码中的静态数组中)并将模式缩放到所需搜索的大小运行时的区域。

第二个建议是，您可以将 2D 搜索替换为一系列 1D 搜索。如果我理解正确的话，您并不真正关心地下是什么，您只关心地面surface 的方向是什么。因此，您可以在搜索区域的顶部选择几个点，然后从每个起点向下进行一维搜索，直到找到一个实心像素。在 ASCII 艺术中，

X   X   X   X
|   |   |   |
|   |   | ..*
| ..*...*....
*............

X 是起点，竖线是一维搜索，点是地面，星是搜索找到的地面点。一旦你有了这些点，你就可以计算从每个点到中心点的平均向量，但是对中心左侧的点的向量求反，而对于右侧的点则不理会它。这应该可以防止平均值出现为零，并会为您提供一个与地形相切的向量，指向右侧。计算垂直于这个向量的向量，你就会得到你的法线。

关于ios - 确定一组像素的表面法线的最佳方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17329741/