Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

Expected

I get this instead:

Actual

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
share|improve this question
    
For each of the six possible pairs of objects what's the result of the < operator? –  Adam Feb 23 '13 at 20:57
    
I'm pretty sure that comparison sequence is not what it actually is. –  Ali.S Feb 23 '13 at 21:27
    
This seems very much like a "debug my code for me" question. Voting to close as 'too localised'. My recommendation is to use a debugger to find your own bugs. –  Trevor Powell Feb 26 '13 at 23:43
add comment

closed as too localized by Sean Middleditch, Trevor Powell, bummzack, Josh Petrie, Ali.S Mar 15 '13 at 23:31

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 2 down vote accepted

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!

share|improve this answer
    
You suggested that after the queued sprites are sorted into collision groups, the groups would be sorted by texture. What if a group has sprites that come from different textures? –  Aaron Feb 24 '13 at 6:34
    
@Aaron That would be the case where they're ordered by z-order instead, so you can't sort by texture. It's true that you won't get optimal results, but I think they won't be far from optimal (unless you have large clusters of just-barely-touching sprites, e.g. swarms). –  Kevin Reid Feb 24 '13 at 16:52
    
I understand sorting the sprites within a group by z-order. For sorting the sprite groups could I, say, sort the groups whose sprites all come from the same texture and then leave the groups whose sprites come from different textures at the end? –  Aaron Feb 24 '13 at 19:16
    
@Aaron: Oh, I see where I was unclear; edited. You could do that, yes, but you might as well just sort the groups by the texture index of an arbitrarily-picked element of the group — the number of texture switches will be roughly the same. –  Kevin Reid Feb 24 '13 at 19:58
1  
@Aaron Sounds good; but in the non-overlap case you also need to compare the group's (arbitrarily picked) texture index, rather than the individual elements, to be consistent. Another way to express it would be "find group's texture index; if (group texture index is same) then {compare by z order} else {compare by group texture index}"; that's just a sort by two totally-ordered criteria and so is obviously consistent. –  Kevin Reid Feb 24 '13 at 20:17
show 1 more comment

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.
share|improve this answer
    
"This seems contradictory? If they are all in a texture atlas, you don't need to swap textures to draw them." I meant sprites that come from different texture atlases. –  Aaron Feb 24 '13 at 16:17
    
@Aaron can you combine atlases? Or, as you'll have at least 8 texture units, you load them all up at once and have an extra vertex attribute to pick the texture in the fragment shader. –  Will Feb 24 '13 at 17:36
1  
I'm actually generating atlases dynamically, up to the platform's maximum texture size. So what I'm really attempting to do here is handle the edge case where I have enough sprites that I end up with multiple atlases. –  Aaron Feb 24 '13 at 19:08
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.