找到网格交叉点的算法

我的游戏，高效的渲染和碰撞被划分成区域。每个地区都会有很多物体会动态移动。当他们移动时，我需要一种方法来快速确定它们所处的区域。

对象永远不会比区域更长或更宽。因此，它永远不会超过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

找到网格交叉点的算法

回答

相关问题