Defect in polygon sorting [closed]

Question

I have a 2D game with sprites that come from texture atlases. I'm trying to resolve the sorting of my sprites for rendering.

I want two sprites to be ordered by their order of insertion, or z-order, when they overlap. Otherwise I'd want to sort by their texture index to keep sprites from the same texture together. I use the std::sort function for sorting a vector of queued sprites.

When queueing a sprite I transform its vertices to screen-space vertices on the CPU. The resulting polygon is used in the overlap test, which is based on this post on Stack Overflow about rectangle intersection:

bool Polygon::overlaps(const Polygon &rhs) const
{
    return overlapCheck(rhs, *this) && overlapCheck(rhs, rhs);
}

bool Polygon::overlapCheck(const Polygon &rhs, const Polygon &current) const
{
    bool result = true;

    for (int i = 0; i < NUM_VERTICES; ++i)
    {
        int i2 = (i + 1) % NUM_VERTICES;
        glm::vec2 p1 = current.positions[i];
        glm::vec2 p2 = current.positions[i2];

        glm::vec2 normal(p2.y - p1.y, p1.x - p2.x);

        float minA, maxA;
        overlapCheckEdges(*this, normal, minA, maxA);

        float minB, maxB;
        overlapCheckEdges(rhs, normal, minB, maxB);

        if ((maxA < minB) || (maxB < minA))
        {
            result = false;
            break;
        }
    }

    return result;
}

void Polygon::overlapCheckEdges(const Polygon &poly, const glm::vec2 &normal, float &min, float &max)
{
    bool haveMin = false;
    bool haveMax = false;

    for (PosIterator it = poly.positions.begin();
      it != poly.positions.end(); ++it)
    {
        float projection = (normal.x * it->x) + (normal.y * it->y);

        if (!haveMin || (projection < min))
        {
            min = projection;
            haveMin = true;
        }
        if (!haveMax || (projection > max))
        {
            max = projection;
            haveMax = true;
        }
    }
}

My sprite comparison method:

bool Polygon::operator < (const Polygon &rhs) const
{
    if (overlaps(rhs))
    {
        return zOrder < rhs.zOrder;
    }
    else
    {
        return textureIndex < rhs.textureIndex;
    }
}

The problem, of course, is that something's wrong with the sorting. I render my scene like this:

Transform t;
t.position.x = 33.0f;
t.position.y = 33.0f;

// "wall" and "slug" comes from texture atlas #2
// "altar" comes from texture atlas #1

// Queued sprites are translated to polygons based on given matrix
renderer.queueSprite("wall", projection.getMatrix() * t.getMatrix());

t.position.x = 0.0f;
t.position.y = 0.0f;

renderer.queueSprite("slug", projection.getMatrix() * t.getMatrix());

renderer.queueSprite("altar", projection.getMatrix() * t.getMatrix());

renderer.draw(); // Sprites are sorted then drawn

The sprites have sizes of 32x32 units. This is what I expect to get:

I get this instead:

The pink slug and the white altar are in the wrong order. Oddly enough, if I put the dark wall at (32, 32) instead of (33, 33) so that it's just touching the slug and altar, I get the right order.

I've also noticed that in the comparison method the altar is only ever compared with the wall. In a single sort I see this sequence of comparisons:

slug, wall
slug, wall
altar, wall

Answer 1

I don't know if this is the actual cause of your problem, but your comparison function is invalid.

In most cases, including std::sort (which I assume you'd be using, though you didn't say), one should not assume that anything other than a strict weak ordering (that is, something that defines a unique (up to some equivalence class) rearrangement of the elements being sorted) can be used in a sorting algorithm.

According to Wikipedia, a strict weak ordering is a partial order “in which the relation ‘neither a < b nor b < a’ [incomparability] is transitive”. Your comparison function does not meet this criterion; for example, if three same-textured sprites A, B, C are positioned such that A and B overlap, but C is separated, then A and C are incomparable, as are C and B, but A and B are not, so incomparability is not transitive.

Another way to put it, also from Wikipedia, is:

If x < y, then for all z, either x < z or z < y or both.

That is, given any two objects, a third object is either before them, after them, or between (inclusive) them — it cannot be unspecified.

---

In general, I expect you will not be able to make a valid comparison function which directly conditions on sprites being overlapping, because overlapping is a non-transitive relation.

In order to dodge this, one solution would be, for example, to group together all sprites which overlap indirectly (i.e. transitive closure of overlapping); then sort the groups by the texture index of an arbitrary member of the group, and sort within the groups by z-order.

The grouping could be approximated cheaply: when a sprite starts to overlap another, merge the two sprites' groups, and when a sprite is not overlapping any others, put it in a new group by itself. You might even find tracking that information useful for collisions or other gameplay mechanics!

Answer 2

This sounds directly analogous to my question "Optimising the drawing of overlapping rectangles", where despite seeing benefits in sprite batching in my real game I had trouble inventing a micro-benchmark to illustrate it.

You say:

I have a 2D game with sprites that come from texture atlases

...

I want to sort by their texture index to keep sprites from the same texture together

This seems contradictory? If they are all in a texture atlas, you don't need to swap textures to draw them.

Generally, my advice is:

1. put all your sprite artwork into a single texture atlas, so you can draw all the sprites with a single draw-call
2. draw the scene with an orthogonal projection, but put the z into each sprite so that the GPU can do the depth sorting (fast GPUs just draw everything and let the depth buffer sort it out; weaker but cleverer GPUs do extra sorting steps which are going to be both correct and faster than whatever you mess around with on the CPU).
3. even if all your sprites are drawn individually with their own setting of texture and their own draw-call, even software renderers will easily keep up. I stopped needing to optimise this level of thing when we moved from 33Mhz phone GPUs interpreting Java! Oh I fondly remember the 33Mhz days. Top-down tile-based scenes are fast to draw even on the first pentiums.