1

这是我的问题。

我的游戏，为了高效的渲染和碰撞被划分为区域。每个区域中都会有许多动态移动的对象。当他们移动时，我需要一种方法来快速确定他们所在的区域。

一个对象永远不能比一个区域更长或更宽。因此，它永远不能同时出现在超过 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);

}

这似乎相当快。

我想到了几种方法来做到这一点：

  1. 我生成 OBB 的边界矩形并找到该矩形的 4 个区域。这里的缺点是必须进行进一步的测试以确定对象是否真的在其中。
  2. 我确定 OBB 的每个角和每个中点的区域。

有没有更好、更快的方法来解决这个问题？我的任何一个解决方案都是好主意吗？

谢谢

在此处输入图像描述

4

1 回答 1

0

确定包含 OBB 的每个顶点的区域。

如果所有四个都在同一区域，则返回该区域。

如果所有四个都在共享 X 坐标或共享 Y 坐标的一对区域中，则返回该对区域。

如果它们位于四个不同的区域，则返回该组的四个区域。

如果这些条件都不适用，则您有两个不同的区域 X 坐标和两个不同的区域 Y 坐标，定义了在单个顶点 V 处相遇的一组四个区域。

如果 V 在 OBB 内，则返回所有四个区域。

如果 V 在 OBB 之外，并且 OBB 顶点位于三个不同的区域中，则返回这三个区域。

剩下的情况是一对对角相邻的区域包含OBB的顶点，V在OBB之外。选择连接不在同一区域中的顶点的 OBB 的一侧。返回两个包含顶点的区域，以及该线穿过的第三个区域。

我还没有解决例如 V 完全站在 OBB 一边的问题。这些情况的处理取决于程序约定。

于 2012-11-08T20:16:49.360 回答