# Defect in polygon sorting [closed]

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:  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

• 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. – Ali1S232 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

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!

• 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
• @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

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.