kd-tree строительство очень медленное

Я пытаюсь реализовать kd-tree для своего проекта C ++ (DirectX), чтобы ускорить обнаружение столкновений. Моя реализация - действительно примитивная рекурсивная функция. Кажется, что nth_element работает нормально (разница только в 1 кадр / с, если я закомментирую это). Я не совсем понимаю, откуда это произошло.

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));
}

Я перезаписал оператор bool в классе Ball:

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));
}

Как вы можете видеть, я больше не копирую векторы, и я также передаю левый и правый дочерние элементы в качестве ссылки, чтобы они не копировались.