優化SphereInFrustrum檢查

我有這個SphereInFrustrum功能在這裏：優化SphereInFrustrum檢查

0.49% int FrustumG::sphereInFrustum(Vec3 &p, float radius) { 

     int result = INSIDE; 
     float distance; 

2.40% for(int i=0; i < 6; i++) { 
7.94%  distance = pl[i].distance(p); 
12.21%  if (distance < -radius) 
0.67%   return OUTSIDE; 
3.67%  else if (distance < radius) 
       result = INTERSECT; 
     } 
     return(result); 

     }

的數字是從我的代碼分析器。問題是，這個檢查比實際渲染花費的時間更長。實施幾何撲殺的關鍵在於我可以擁有非常高的水平。我真的只需要一種非常快速和骯髒的方式來查看AABB是否進入或退出。現在我給它提供立方體的半徑和中心。鑑於我的箱子是AABB，有沒有更快的方法來做到這一點？我贊成速度超過準確性。

感謝

如果我提供的多維數據集的最小值和最大值將使得它更快？我敢肯定，如果沒有使用平方根的距離公式，一定有辦法做到這一點;

float Plane::distance(Vec3 &p) { 

    return (d + normal.innerProduct(p)); 
} 


float Vec3::innerProduct(Vec3 &v) { 

    return (x * v.x + y * v.y + z * v.z); 
}

來源

2010-09-07 jmasterx

它看起來像你在使用這裏給出的截頭扭曲：http://www.lighthouse3d.com/opengl/viewfrustum/index.php?gimp。是對的嗎？ – 2010-09-07 22:23:12

很難相信簡單的float比較真的佔用了12.21％的執行時間。如果是這樣，那麼你的距離函數必須*該死*快（如在負時鐘週期快）。也許profiler將距離函數的執行部分歸因於這裏的'if'測試。你可以發佈'距離'的代碼嗎？我想那裏會有更多的優化機會。 – 2010-09-07 22:25:41

是的，這是正確的，它的效果很好，但是當我得到大量的物體時，檢查超過了渲染時間 – jmasterx 2010-09-07 22:26:29

我想只是發表評論問一個問題，但我只似乎能夠留下一個答案，這只是一個觀察：

此代碼是否真正做到你想做的事？

 int result = INSIDE; 
     float distance; 

2.40% for(int i=0; i < 6; i++) { 
7.94%  distance = pl[i].distance(p); 
12.21%  if (distance < -radius) 
0.67%   return OUTSIDE; 
3.67%  else if (distance < radius) 
       result = INTERSECT;

這個功能怎麼讀給我的是，假設球體內部，爲您的截每個點我，拿我和球P的中心之間的距離，如果距離小於負半徑。 ..在這裏我的範例被摧毀。

因此，如果您的負距離小於負半徑，那麼這會返回較早？那真的是你想要的嗎？

來源

2010-09-07 22:03:43 cirons42

所有我需要知道的是，如果它的內部或外部，我不在乎它是如何完成的， – jmasterx 2010-09-07 22:18:39

如果我必須猜測，我會說那些是飛機，而不是點，並且距離是正常化的。面向平截頭體內側的平面側上的點是正的，而面向平截頭體外側的平面側上的點是負向的。因此，如果球體的中心距離平面爲-40°，並且球體的半徑爲30°，那麼由於-40 <-30，它完全在平截頭體之外。 – 2010-09-07 22:19:31

@P爸爸：這比我想到的要多得多。感謝您的解釋。 – cirons42 2010-09-08 00:49:01

的幾點思考（爲了增加複雜性）

Elimintate分支 - 它可能會更快（具體取決於平臺和編譯器）來計算所有6米距離和返回基於最小其中。例如。在PowerPC上，minDist = (d < minDist) ? d : minDist可以用fsel指令計算並避開分支。
展開（第I部分） - 展開所有六個平面的循環可能會給編譯器更好的機會優化代碼（通過隱藏指令延遲）。
展開（第二部分） - 您可以一次處理多個球體嗎？同樣，您可能可以隱藏一些延遲。
SIMD - 如果您不介意用SIMD弄髒手，您可以將3架飛機的「轉置」存儲在4個四邊形中。這使您可以更輕鬆地計算點積，而無需執行「水平」SIMD操作。象徵性的，這看起來像

vec4 sphereX = sphere.splat(0); 
vec4 sphereY = sphere.splat(1); 
vec4 sphereZ = sphere.splat(2); 

vec4 dot = sphereX * planesX; // planesX is the x components of 3 planes 
dot += sphereY * planesY; 
dot += sphereZ * planesZ; 
dot += planesDistance; 
// dot now contains the results of 3 distances 
// now do the same for the other 3 planes

實際的SIMD代碼將取決於平臺和編譯器上。

還有一些方法可以在kd-trees上進行平截頭體查詢（即MLRTA） - 我從來沒有嘗試過它們，但它應該大大減少你需要查詢的球體數量。

希望有幫助，讓我知道如果有什麼不清楚。

來源

2010-09-08 08:14:10 celion

你真的在爲每個球體執行這段代碼嗎？如果你這樣做，難怪它會變慢。

您應該使用分層方法，它可以在一次調用中清除整個場景。例如，你可以使用四叉樹的球體。

來源

2010-09-09 11:36:00 Calvin1602

優化SphereInFrustrum檢查

回答

相關問題