c++ - 改进碰撞检测

Question

我将使用两个函数来检查屏幕上对象之间的碰撞，因为这些函数是将要执行的很多东西，我想确保它们以最高效率运行，并且因为它们目前看起来非常困惑，我想知道是否可以得到你的帮助。

我的功能如下: 这是实际将在对象上调用的函数:

bool ScreenObject::intersects(ScreenObject & a,ScreenObject & b) {
    if(inter(a,b))
        return true;
    else
        return inter(b,a);
}

这是国际间:

bool inter(ScreenObject & a,ScreenObject & b) {
    if(a->getsx()>b->getsx()) {
        if(a->getsx()<b->getSxmax()) {
            if(a->getsy()>b->getsy())) {
                if(a->getsy<b->getSymax()) {
                    return true;
                }
            } else {
                if(b->getsy()>a->getsy())) {
                    if(b->getsy<a->getSymax()) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

getsx/getsy 返回x/y 的最小值(即对象的左下角)，而getSxmax/getSymax 返回最大值。我的问题是，有没有办法让这段代码变得更好，因为目前这似乎执行得很差。

Answer 1

你是对的。这很乱。您想要跟踪每个对象的矩形范围:

typedef struct range { int min, max; } RANGE;
typedef struct bb { RANGE x, y; } BOUNDING_BOX;

关键操作是通过确定对象 A 必须位于 B 的任一侧来发现在一个维度上没有重叠。这就是不相交:

bool disjoint(RANGE *a, RANGE *b) { return b->max < a->min || b->min > a->max; }

现在我们可以使用它两次来发现 2d 中没有重叠:

bool disjoint(BOUNDING_BOX *a, BOUNDING_BOX *b) {
  return disjoint(&a->x, &b->x) || disjoint(&a->y, &b->y);
}

当然碰撞是不相交的逻辑补充，至少对于矩形物体来说是这样。

对于其他形状，您仍然可以使用矩形范围来消除碰撞测试的大部分成本。如果范围不相交，则可以确定没有碰撞。如果它们不相交，那么您必须对一般多边形的碰撞进行更昂贵的测试。有一些基本信息here .但是有几本关于这个主题的大书。

对于不喜欢 C 约定的 @DanielKO，尽管对于这个问题，他们表达的计算比 OO 更简洁；还省略了构造函数和其他样板文件:

class Extent { 
  public:
    bool isDisjointWithRespectTo(Extent &other) {
      return max < other.min || other.min > max; 
    }
  private:
    int min, max;
}

class BoundingBox {
  public:
    bool isDisjointWithRespectTo(BoundingBox &other) {
       return x.isDisjointWithRespectTo(other.x) || y.isDisjointWithRespectTo(other.y);
    }
    bool intersectsWith(BoundingBox &other) { return !isDisjointWithRespectTo(other); }
  private:
    Extent x, y;
}

构造函数需要确保 min 和 max 在两个版本中都正确排序。