Sorting objects to the front or back depending on their position

Question

I am trying to sort my renderables/actors correctly and noticed that I have some troubles with walls since they get sorted by their centerpoint. So I am sorting all my actors before I draw them depending on their distance to the camera with an insertion sort. After that, I am trying to determine if the wall should be drawn behind or in front of the gamefield. To explain this, the game takes place inside of a cube which is out of 6 planes. Since I can rotate the camera around that cube I need a sorting which would put the planes in front/back depending on that. So here is a picture so you know what we are talking about:

You can clearly see the rendermisstake whats happening at the front of those kind of snake.

Okay here is my current sorting:

//list of Actors the abstract class which Wall and cube and so on extend
void Group::insertionSort(vector<Actor *> &actors)
{
    int j;

    for (int i = 1; i < actors.size(); i++)
    {
        Actor *val = actors[i];
        j = i - 1;

        while (j >= 0 && distanceToCamera(*actors[j]) < distanceToCamera(*val))
        {
            actors[j + 1] = actors[j];
            j = j - 1;
        }
        actors[j + 1] = val;
    }
}

float Group::distanceToCamera(Actor &a)
{
    float result = 0;
    XMVECTOR posActor = XMLoadFloat3(&a.getPosition()); //here i get the centerpoint of the object
    XMVECTOR posCamera = XMLoadFloat3(&m_camera->getPosition());
    XMVECTOR length = XMVector3Length(posCamera - posActor);
    XMStoreFloat(&result, length);
    return result;
}

To determine if it's a Wall I used kind like this dynamic_cast<Wall*>(val) but I don't get them in front/back of the vector depending on that. To remember the objects return their centerpoint. Can anyone lead me to the right way?

Answer 1

It's difficult to answer your question because it is a complex system which you haven't fully explained here and which you should also reduce to something simpler before posting. Chances are that you would find a fix yourself on the way. Anyway, I'll do some guessing...

Now, the first thing I'd fix is the sorting algorithm. Without analysing it in depth whether it works correctly in all cases or not, I'd throw it out and use std::sort(), which is both efficient and very unlikely to contain errors.

While replacing it, you need to think about the ordering between two rendered objects carefully: The question is when exactly does one object need to be drawn before the other? You are using the distance of the center point to the camera. I'm not sure if you are sorting 2D objects or 3D objects, but in both cases it's easy to come up with examples where this doesn't work! For example, a large square that doesn't directly face the camera could cover up a smaller one, even if the smaller square's center is closer. Another problem is when two objects intersect. Similarly for 3D objects, if they have different sizes or intersect then your algorithm doesn't work. If your objects all have the same size and they can't intersect, you should be fine though.

Still, and here I suspect one problem, it could be that a surface of an object and a surface of the cube grid have exactly the same position. One approach is that you shrink the objects slightly or enlarge the outside grid, so that the order is always clear. This would also work around an issue that you suffer from floating point rounding errors. Due to these, two objects that don't have an order mathematically could end up in different positions depending on the circumstances. This can manifest as them flickering between visible to covered depending on the camera angle.

One last thing: I'm assuming you want to solve this yourself for educational reasons, right? Otherwise, it would be a plain waste of time with existing rendering toolkits in place that would even offload all the computations to the graphics hardware.