algorithm - 给定非轴对齐矩形，如何在二维矩阵中找到样本子集？

Question

我正在编写一个小型视频游戏原型(prototype)，我有一个高度图(2D float 组)，它将被对象遍历。我希望能够在游戏中使用对象下的高度图数据。

我目前使用 AABB(轴对齐边界框)在我的对象下方获得高度图的子区域(黄色)，因为我将处理它们下方和周围的数据。那部分是微不足道的。

但是，在给定旋转边界框(未对齐轴)的情况下，我无法弄清楚如何在对象下找到样本(红色)。我该怎么做？

Answer 1

我可能会建议以下方案:

1. 计算轮子的 AABB(通过其顶点)。
2. 获取此 AABB 内点的矩形子网格。
3. 对于这些点中的每一个，检查它是否位于您的车轮内。

为了完成第 3 部分，您需要做一些数学运算。假设您知道车轮的单位方向矢量 D、车轮中心位置 C、半长 l 和半厚 w。对于点 P，您可以检查以下条件:

  abs(  dot(P - C, D)) <= l
  abs(cross(P - C, D)) <= w

这是解决问题的一种更复杂的方法，但效率更高。仅枚举通过 AABB 检查获得的子网格的行。对于每一行，您可以使用显式公式在 O(1) 时间内确定轮子中的点范围。然后你可以只枚举你的轮子内的点。总时间复杂度为 O(R + A)，其中 R 是车轮 AABB 内子网格中的行数，A 是轮内的总点数。

C# 中的示例实现:

if (Mathf.Abs(Vector3.Dot  (hfSampleGlobalPos - wheelPosePos, wheelPoseRot * Vector3.forward))   <= wheelRadius &&
    Mathf.Abs(Vector3.Cross(hfSampleGlobalPos - wheelPosePos, wheelPoseRot * Vector3.forward).y) <= wheelHalfWidth)
{
    // Do something with the sample under the wheel here
}