找到網格交叉點的算法

我的遊戲，高效的渲染和碰撞被劃分成區域。每個地區都會有很多物體會動態移動。當他們移動時，我需要一種方法來快速確定它們所處的區域。

對象永遠不會比區域更長或更寬。因此，它永遠不會超過4個地區。

棘手的部分是對象的矩形是使用2D中單獨軸定理的定向邊界框，因此它們可以旋轉。

我曾想過這樣做的主要途徑是通過確定每個點的區域：

static public int colFromPos(float startX,float width, float x) 
{ 
    x -= startX; 
    return (int)Math.floor(x/width); 

} 

static public int rowFromPos(float startY,float height, float y) 
{ 
    y -= startY; 
    return (int)Math.floor(y/height); 

}

這似乎相當快。

我想到的幾種方法可以做到這一點是這樣的：

我產生OBB的矩形邊框，找到這個矩形的4個區域。這裏的缺點是，爲了確定對象是否真的在進行furthur測試，必須執行。

我確定每個角的區域和OBB的每個中點。

有沒有更好，更快的方法去做這件事？是我的解決方案好點子嗎？

由於

enter image description here

來源

2012-11-08 jmasterx

方法＃2可以給你不正確的答案。 – bdares

鑑於對象不能超過區域的大小，方法1是否完全正確以確定OBB在哪些區域？ – jmasterx

性能和替代方法實際上取決於對象的複雜性和性質......構建OBB可能是微不足道的，也可能過於昂貴，具體取決於。 – bdares

確定含有OBB的每個頂點的區域。

如果全部四個在同一個區域中，則返回該區域。

如果所有四個位於共享X座標或共享Y座標的一對區域中，則返回該對區域。

如果他們在四個不同的地區，返回該四個地區的組。

如果沒有這些條件適用，你有兩個不同的區域X座標和兩個不同的區域Y座標，定義一組在單個頂點滿足四個區域，五

如果V是OBB內，返回所有四個區域。

如果V位於OBB之外，且OBB頂點位於三個不同區域，則返回這三個區域。

其餘情況是一對對角相鄰的區域包含OBB的頂點，而V在OBB外。選擇連接不在同一區域中的頂點的OBB的一側。返回包含兩個頂點的區域以及該線所穿過的第三個區域。

我沒有解決例如V正好在OBB的一側。處理這些案件取決於計劃公約。

來源

2012-11-08 20:16:49

他如何避免重複檢查1-4個區域？ – Bytemain

找到網格交叉點的算法

回答

相關問題