確定一組像素表面法線的最佳方法？

Question

我目前的工作之一是爲iOS Cocos2D創建2D可破壞地形引擎（請參閱https://github.com/crebstar/PWNDestructibleTerrain）。毫無疑問，它處於嬰兒階段，但自從幾周前開始以來，我取得了重大進展。但是，我遇到了一些表面法線計算的表現障礙。

注意：對於我的可破壞地形引擎，一個0的alpha值被認爲不是固體地面。

下面發佈的方法只適用於很小的矩形，比如n < 30.任何大於30的值都會導致幀速下降。如果你接近100x100，那麼當精靈嘗試遍歷地形時，你可能會讀一本書。目前這是最好的，我可以想出一個精靈角度變化，因爲它橫跨地形漫遊（以得到一個精靈的方向的角度只是100 *正常*（1,0）矢量的點積）。

-(CGPoint)getAverageSurfaceNormalAt:(CGPoint)pt withRect:(CGRect)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 

我的問題是我有精靈，需要更大的矩形，以便他們的運動看起來逼真。我考慮過對所有曲面法線進行緩存，但這導致了知道何時重新計算曲面法線的問題，而且這些計算也相當昂貴（塊應該多大？）。另一個較小的問題是，我不知道如何正確處理長度= 0時的情況。

因此，我卡住了......任何來自社區的建議將不勝感激！我的方法是最好的嗎？或者我應該重新考慮算法？我是遊戲開發新手，總是希望學習新的技巧和竅門。

Answer 1

有人在另一個論壇上回答了這個問題。我將發佈修訂後的getSurfaceNormal函數。這實現第二算法如由Nathan裏德

描述 - （CGPoint）getSurfaceNormalAt：（CGPoint）PT withSquareWidth：（int）的區域{ //該方法僅着眼於表面像素

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等的像素着色器中。您預先計算泊松圓盤圖案（只需將代碼中的點存儲在靜態數組中），然後將圖案縮放到所需的大小運行時搜索區域。

第二個建議是，您可以用一系列1D搜索替換2D搜索。如果我理解正確，你根本不在乎地面上有什麼，只關心地面的方位表面是什麼。因此，您可以在搜索區域頂部選取幾個點，然後從每個起點開始向下搜索一次，直到找到一個實心像素。在ASCII藝術，

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

x是出發點，垂直條是1D搜索，該點是地面，星星是通過搜索發現地面點。一旦你得到了這些點，你就可以計算出每個點到中心點的平均向量，但是否定了中心點左側的向量，並且讓它獨立於右邊的點。這應該防止平均值出現零點，並且會給你一個與地形正切的向量。計算與這個垂直的矢量，你就會有你的正常。