c++ - kd-tree 构建非常慢

Question

我正在尝试为我的 C++ (DirectX) 项目实现一个 kd-tree 以加速我的碰撞检测。我的实现是一个非常原始的递归函数。第 nth_element 似乎工作正常(如果我将其注释掉，则只有 1 fps 的差异)。我不太确定罪魁祸首来自哪里。

KDTreeNode Box::buildKDTree(std::vector<Ball> balls, int depth) {
    if (balls.size() < 3) {
        return KDTreeNode(balls[0].getPos(), KDTreeLeaf(), KDTreeLeaf());
    }

    Variables::currAxis = depth % 3;
    size_t n = (balls.size() / 2);
std::nth_element(balls.begin(), balls.begin() + n, balls.end()); // SORTS FOR THE ACCORDING AXIS - SEE BALL.CPP FOR IMPLEMENTATION
    std::vector<Ball> leftSide(balls.begin(), balls.begin() + n);
    std::vector<Ball> rightSide(balls.begin() + n, balls.end());
    return KDTreeNode(balls[n].getPos(), this->buildKDTree(leftSide, depth + 1), this->buildKDTree(rightSide, depth + 1));
}

我已经覆盖了 Ball 类中的 bool 运算符:

bool Ball::operator < (Ball& ball)
{
    if (Variables::currAxis == 0) {
        return (XMVectorGetX(this->getPos()) < XMVectorGetX(ball.getPos()));
    } else if (Variables::currAxis == 1) {
        return (XMVectorGetY(this->getPos()) < XMVectorGetY(ball.getPos()));
    } else {
        return (XMVectorGetZ(this->getPos()) < XMVectorGetZ(ball.getPos()));
    }
}

我很确定这不是实时处理构造的最佳方式。也许你可以帮助我走上正轨。

还有一件事我真的很想知道:假设我在场景中有很多球体并且我使用了 kd-tree。我如何确定它们属于哪片叶子？因为在施工时我只使用中心位置，而不是它们的实际直径？那我该怎么做呢？谢谢

编辑:我已经实现了所有建议的更改，现在运行良好。谢谢!这是我所做的:

KDTreeNode Box::buildKDTree(std::vector<Ball>::iterator start, std::vector<Ball>::iterator end, int depth) {
    if ((end-start) == 1) {
        return KDTreeNode(balls[0].getPos(), &KDTreeLeaf(), &KDTreeLeaf());
    }

    Variables::currAxis = depth % 3;
    size_t n = (abs(end-start) / 2);
    std::nth_element(start, start + n, end); // SORTS FOR THE ACCORDING AXIS - SEE BALL.CPP FOR IMPLEMENTATION
    return KDTreeNode(balls[n].getPos(), &this->buildKDTree(start, (start+n), depth + 1), &this->buildKDTree((start+n), end, depth + 1));
}

如您所见，我不再复制 vector ，而且我还将左右子节点作为引用传递，这样它们就不会被复制。

Answer 1

我看到两个可能的问题:

1. 将 vector 作为值传递给函数(这有效地复制了整个 vector )
2. 为越来越小的元素创建新的 vector ，而不是进行一些就地处理

基本上，该函数会为您的 kd 树的每个级别复制初始 vector 中的所有球两次。这应该会导致严重的速度下降，因此请尽量避免请求太多内存。

解决它的一种方法是直接访问 vector 的数据，使用 nth_element 等，并且只将子 vector 的索引传递给递归调用。