kd-tree construction very slow

Question

I am trying to implement a kd-tree for my C++ (DirectX) project to speed up my collision detection. My implementation is a really primitive recursive function. The nth_element seems to be working okay (only 1 fps difference if i comment it out). I am not quite sure where the culprit it comming from.

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

I have overwritten the bool operator in the Ball class:

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

I am pretty sure that this is not an optimal way to handle the construction in real time. Maybe you can help me to get on the right track.

There is one other thing what i am really wondering about: Say i have a lot of spheres in the scene and i use a kd-tree. How do i determine in what leaf they belong? Because at the contruction i am only using the center position, but not their actual diameter? How do i go about this then? Thanks

EDIT: I've implemented all the suggested changes and it runs very good now. Thanks! Here is what i did:

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

As you can see i am not copying the vectors anymore and i am also passing the left and right child as reference so that they are not copied.

Answer 1

I see two possible problems:

1. Passing the vector to the function as a value (this effectively copies the whole vector)
2. Creating new vectors for the smaller and bigger elements, instead of some in-place processing

Basically the function copies all balls in the initial vector for every level of your kd-tree twice. This should cause some serious slow down, so try to avoid requesting so much memory.

One way to solve it would be to access the data of the vector directly, use nth_element etc. and only pass the indices of the subvectors to the recursive call.