Painter algorithm vs. 3D rendering with Z-buffer when drawing 2D Sprites

Question

I'm currently developing a tile base engine. I want it to look like your average old school tilebased RPG like Zelda - Link to the past (orthographic projection, squared tile texture, textures overlapping each other, alpha channels, etc.). The twist is that the world is internally 3d meaning that every tile has an elevation and entities are moving in a 3d space. Reason for this is beyond the scope of this question but I'm struggling on comparing the follow two ideas for the rendering. I'm using OpenGL with libGDX in Java but wouldn't mind writing my own code to interface OpenGL. That's also why I didn't tag it.

A screenshot of "Zelda - Link to the past" in case you don't know what it looks like.

Painter algorithm

Disable Z-Buffer and use painter algorithm to draw from back to front in the appropriate order with some overdraw and a lot of texture rebinding. I know a texture atlas can minimize the texture rebinding but the engine is supposed to act more like a sandbox so I don't want to rely too heavily on assumptions like a efficient texture atlas that I might not have all the time.

Pro: Easy to implement and very straight forward.

Con: I've no idea how big the impact will be since almost every sprite will cause a texture rebinding. And I don't know how to predict the performance costs of that many texture bind calls.

---

Full blown 3D

Rotate the camera 45 degrees up around the x axis with an orthographic projection matrix. Then use the 3d information from the game world to draw the tile textures with billboarding at the real position in the worlds 3d space. Same for entities and such. This way I can gather all sprites and then render them sorted by their texture which means one texture bind per texture and reduced overdraw due to usage of the Z-buffer

Pro: I can use a freecam to debug render problems. I assume it's significantly faster that the painter algorithm.

Con: Some sprites might share the same place which could lead to Z-fighting. I'm thinking about how to use multiple layers on a tile. For instance you may have a bridge tile with a railing where the railing is always overlapping an entity on the bridge but the floor of it is always overlapped by the entity. So I would have to add a little offset to different layers in the 3d space. I'm not really sure how that would work out and to be honest had a hard time figuring out how old games did it so maybe I'm overthinking it.

---

I guess I have a very rough idea of how each method will work out but I don't know how much the texture rebinding (or sorting and preparing the sprites for the 3d approach) is affecting the performance and while it's easy to find information regarding large 3D scenes I found it difficult to get information about 2D scenes with way less polygons.I hope this question is not too much a subject of personal preference. I know that Premature optimization is the root of all evil but due to how the decision is affecting almost the entire rendering process I don't want to make the wrong call.

I deliberately didn't mention any OpenGL functions mainly because I've mostly used the libGDX API which hides the function calls behind it's wrappers but generally I know how the internals work and just got into the internals and how the OpenGL API works. I don't think specific OpenGL calls do matter for the question but feel free to use them for your answer I'll just look them up.

Answer 1

One downside to Z-buffering vs sorting not mentioned by the other answers can and most likely will happen when using Z-buffering with images whose pixels are not fully transparent or fully opaque. Alpha-blending said pixels correctly is dependent on the order they are drawn. Say you have a half-transparent green square and a half transparent red square in the same location, with the green square having a z value closer to the view (so overlapping, with green square being on top). If you draw the red square first, and then the green square second, blending will be done correctly as the green square with a closer z value gets drawn on top of the red square further away. But, if you draw in the reverse order, the red square will not get drawn at all since the its z value is further than the z value of the green square previously drawn! So instead of the nice blending you got before, you now only get the green square. In fact, this same issue can occur if you have a fully transparent pixel that you do not discard (so it does not write to the depth buffer). So in this case, you would need to sort the images by their z to ensure the proper blending is done.

Answer 2

Use Z-buffering. You can test this out, but in principle for your application you should end up with no Z-fighting!.

(In either approach, you need to keep track of which things you want in front of other things; attaching a Z value per tile is straightforward. This answer is really just striking one of your "cons" for z-buffer.)

Z fighting happens because the Z interpolation of two surfaces has minute errors where sometimes it's a little high and sometimes it's a little low.

But for your 2d, flat tiles, the Z values for all vertices of the tile will be the same. The interpolation will be perfect, and will give the same value for the entire triangle, and be the same for the whole tile. So for any two tiles, one of them will be visibly in front of the other.

If it matters which, be sure to give them different Z values, or manipulate the draw order appropriately for the depth function used.

---

Addendum -- I'm not sure I grok, but you mentioned something about "rotate the camera 45 degrees"... if you're trying for an ortho projection, you may want to implement something like

transformedP.xy = p.xy + orthoAmt * vec2(p.z, p.z);
transformedP.z = p.z;

So, very specifically, not "full 3d", to guarantee perfectly flat (z-constant) polys.

Answer 3

Since the entire world is 3d, and orthographic, a simple "cheat" could be made to avoid all z buffering problems, and maximize efficiency over the painterly algorithm.

First, for every tile in the game, give it a height. This shows where is over relative to the objects directly above and below it. For example, a bust over grass. The grass, on the bottom, would have a height of 0. The bush would have a height of 1. This means that the bust is above the grass, and will be rendered on top of it.

If you want move objects, just keep stacking the height. Lets say you want to add berries on the bush. Then make the berries a height of 2. While on another area the berries have a height of 1, and the bush has a height of 2. On that once, the bush is above the berries. Always, until you say otherwise.

Now, for each possible type of object in the game, assign a very small, unique value between 0 and 1, exclusive. Which means ALL berries have a uuid of 0.1, and ALL bushes have a uuid of 0.15, and so on. The actual values don't really matter, as long as it's always different. (Note, REALLY close together values may still cause issues. Like 0.1 and 0.0999999.) Do this for every tile, entity, and sprite in the game.

When you assign an object's height, always add this number. After doing this, the bush example above would look more like:

Grass Tile = 0.1  (Uuid of 0.1, height of 0)
Bush = 1.2        (Uuid of 0.2, height of 1)
Berries = 2.3     (Uuid of 0.3, height of 2)
Player = 3.4      (Uuid of 0.4, height of 3)

Now, your problem is solved. Z-Fighting will not occur between two objects of the same texture, as it will always be the same texture on both sides, so nothing flickers.)

The whole uuid system can be erased if you can confirm that no two tiles can share the same x, y, and z. If none do, then get rid of the system above.

Now, for best performance, render all solids first, then all transparents. Make sure to do as little texture switching as possible. Meaning render all grass tiles in one go, then all sand, then all bushes, then all berries.

Skip any textures not currently on screen.

Good luck!