How are semitransparent polygons rendered in the correct order?

Question

It is my understanding that while opaque triangles can be rendered in any order thanks to the Z buffer (especially when rendering in hardware), semitransparent triangles cannot. Instead, they need to be rendered from furthest to closest (from the camera's point of view) in order to get the correct result. If you render them in the wrong order, the result will be incorrect (and may even suddenly visually change if the rendering order changes as the camera moves).

Sorting polygons, even triangles, from furthest to closest is actually a difficult problem. In fact, in the general case it's an impossible problem (even with triangles) because in some pathological cases there is no unambiguous order in which they can be rendered correctly. For example, three triangles may overlap each other in a cyclic manner so that each one is partially in front of another (and thus it's impossible to render them without error, unless they are opaque and using a Z buffer, or without splitting at least one of the triangles). Using a naive sorting of triangles is very inefficient, especially if the need arises to split a triangle due to a cyclicity problem.

I know that there exist clever data containers that solve this exact problem and allow very quickly traversing the triangles from furthest to closest, regardless of where the camera is located, without the need to sort anything, and with any splitting of triangles already having been done in preprocessing. One example of such a data container (which name I can't remember now) is a binary tree where there's a triangle at each node which splits the entire space into two halves, with the rest of the triangles being on the left or right branches depending on which side of the plane defined by this triangle they are (and if a triangle intersects said plane, it's split in preprocessing into two using that plane). This binary tree allows traversing all the triangles from furthest to closest with a simple dot product (against the normal vector of the triangle) comparison at each node, regardless of where the camera is located.

While this construct is very clever, there's one problem with it: It only works with a completely static scene. The tree has to be precalculated (and triangles possibly split) as a preprocessing step (usually while building the project). Doing it at runtime on each frame would be madness.

But games use dynamic semi-transparent polygons all the time, for all kinds of particle effects etc. So how are they rendered properly?

Answer 1

TLDR; this is one of the holy grails of computer science.

It is very hard to correctly sort transparent polygons, especially when they intersect. See also painter's algorithm and this SO question.

There've been some advancements in this regard, such as detecting intersecting surfaces and automatically splitting these polygons so that they can be rendered in the correct sorting order, but I can't find that paper now, and it still doesn't help in the case of 3 mutually overlapping polygons as there's no intersection on which to split.

This paper suggests using a per-pixel sorting, effectively using a raycast to figure out which object is on top and sorting that way (however this is more computationally expensive, as it requires 2 or more render passes: one for the depth mask and then a second for the actual result). In any case, such solutions are often implemented at a very low level (e.g. within OpenGL) and not modifiable by a game developer in most cases.

Answer 2

Option 1: Additive blending

One easy trick you can use for explosions and such is using a special blend function.

glBlendFunc( GL_ONE, GL_ONE );

This is called additive blending, which is useful if you are drawing things that add luminosity. White smoke clouds, or fire particles would do well with this.

With additive blending, the order in which you draw does not matter. No sorting required, just draw them after the opaque stuff.

Option 2: screen door transparency

If you need to draw transparent objects that can darken what is behind it, like glass in buildings, you need something else.

In that case, you should consider screen-door transparency.

It is quite easy to achieve, just discard all fragments on a checker board pattern. This is easily achieved by testing the modulo 2 value of the fragment coordinate.

mediump float xm2 = mod( gl_FragCoord.x, 2.0 );
mediump float ym2 = mod( gl_FragCoord.y, 2.0 );
if ( int(xm2) != int(ym2) ) discard;

This option is even easier to use: not only can you skip the sorting of transparent objects. You don't even have to draw opaque before transparent geometry!

I find that especially in recent years, this has become more viable because our render resolutions are so much higher now. Take for instance iOS retina displays. The pixels are too small to see, so the checkerboard is no longer visible. You just see a transparent surface.

Answer 3

Thinking about this for a while, some ideas have come to mind to make the task easier. These are purely speculations of mine, and I have no idea if games actually do it like this, or if they do something completely different.

Firstly, rather than treat all the translucent triangles in the entire scene as one huge mesh to render, the scene could use distinct translucent objects (such as glassware, etc), and as long as no such objects ever intersect each other, it makes much easier to render entire objects in the correct order. In other words, you just need to sort entire objects from furthest to closest, and if the objects are not pathological (like two C-shaped translucent objects simultaneously overlapping each other), you can just render an entire object at a time without worrying about the others. (This is in no way a generic sureproof way because, as mentioned, you can create pathological cases with such objects where they simultaneously overlap each other even though they aren't intersecting. But the objects, levels and animations could be designed in such a manner that this never happens.)

Secondly, rendering one translucent object itself becomes easier depending on its geometry. If its geometry is simple enough, its triangles could be sorted by simply comparing their mid-points. (Again, this is in no way a generic solution, but if the objects are designed properly, it could work perfectly.) In fact, some data container similar to what I described above could be used to traverse the triangles in a simpler manner, without having to resort to an actual sort.

Even if the object is too complex for that to work, a binary tree like I described in my question could be used for it, if the object is rigid and never changes shape.

In some cases a changing translucent surface could perhaps still be rendered in the proper order without having to resort to complicated algorithms. For example, a waving water surface could probably be rendered with a naive sorting of the triangles, or even by simply traversing through them in the proper order (especially if they form a grid, which makes traversing them in a proper order very easy).

Answer 4

All the games I've worked on just relied on depth sorting, combined with some carefully control of render order. This works even on a game like Geon: Emotions which featured a transparent game board and overlaid particle effects above and below the board. The state of the art in rendering has changed quite a bit since I last worked on a game professionally, so there may be newer techniques that enjoy success, but I suspect for most games it's just not an issue.

You're correct that there are theoretically pathological states where depth sorting cannot work, issues with large transparent objects, and other edge cases. However, in practice, the solution is usually to just make sure these problems aren't encountered. Game developers can simply design their game to avoid the situations where these methods don't work happening much or, indeed, at all. This isn't unique to transparencies, all games and game engines have their limitations, so part of the skill of game development is to work around these limitations without it being obvious to the player.