# Sort Polygons in order - not working?

I'm fairly new to programming in a 3d world.

I'm trying to create a canvas where all the objects are drawn in order of furthest-to-closest and from bottom to top - so they don't overlap each other, but there are problems.

As you can see, some of the objects are overlapping each other. None of the objects in the screen will be moving so I was wondering: is there an algorithm available to sort the objects in the correct order? At the moment I have them sorting in the Z axis ascending, then X descending and Y descending.

-
i'm just going to arbitrarily ask, since you said you're new to 3d programming, doesn't the engine you're using support depth testing? depth sorting is only going to get you so far. even if you solve this one issue you're having, L or T shaped blocks, for example, will cause artifacting – dreta May 10 '12 at 16:50
+1 because this is a topic of broad interest to 3d in general and your illustration is great. – Patrick Hughes May 10 '12 at 17:28

As @dreta mentioned in the comments, the typical way 3D engines solve this is with a depth buffer and using the hardware depth test, which allows you to draw arbitrarily-shaped objects in any order and will keep track of the closest surface at each pixel. Manually sorting objects is also possible, but will not necessarily handle nonconvex objects or overlapping objects correctly.

However, if you do want to sort objects, you'll need to calculate a depth value for each object, then sort by descending depth. To get the depth, if you're using a typical 3D engine setup, you'll need to transform each object's center point through your view matrix (which goes from world space to view space), then take the negative of the Z coordinate of the result. (Negative because in right-handed coordinates with X and Y aligned with the screen, Z will be pointing out of the screen.)

If it's always an isometric view like this, you can probably get away with calculating depth = ±X ± Y - Z, where the ± means: pick the sign that makes depth increase as you get further away from the camera. That will depend on the orientation of your X and Y axes.

-
Even with an isometric view it's not possible to sort shapes using a depth value. The only thing you can do, provided the shapes and scene organisation aren't too convoluted (and they usually are), is build a partial order (ie. given two shapes, tell which one should be drawn first). From that, you would need to sort the shapes (using for instance topological sort) and that alone is usually a O(n²) operation when you are lucky but I'm betting on O(n²logn) instead. – sam hocevar May 10 '12 at 22:42
@SamHocevar Yes, as I noted in my answer, object sorting by depth will not handle all cases correctly, especially (but not limited to) nonconvex or overlapping objects. It's an approximation at best. BTW, I believe topologically sorting a graph can always be done in O(V+E) (it's pretty much just DFS). The edge count can be O(V^2) but I suspect it's usually not that bad. – Nathan Reed May 10 '12 at 23:15
@SamHocevar In an isometric view with all objects non-intersecting axis-aligned rectangles, though - which is what the example shows - it seems likely that you probably can sort shapes? Do you know of any construction of a figure that can't be sorted (e.g., something that has a cyclic overlap) under those constraints? – Steven Stadnicki May 10 '12 at 23:45
@StevenStadnicki Here's a case where naive sorting by depth wouldn't work. The correct draw order in that diagram would be red, green, blue, but depth sorting based on the center of each rectangle (black dots) would give you blue, green, red. (The dotted line runs perpendicular to the view, so you can clearly see the relationship between the depths of the centers.) Sam's topological sort would work here, given a way to determine the "is-behind" relations amongst the rectangles. – Nathan Reed May 11 '12 at 1:45
Here is an example of axis-aligned objects that you cannot sort: i.stack.imgur.com/jey1e.png – sam hocevar May 11 '12 at 5:32

Check out the Painters Algorithm and its disadvantages.

-

In general, the answer to your question ('is there an algorithm available to sort the objects in the correct order?') in arbitrary 3d settings is no - no such algorithm can exist, even when the objects are as simple as triangles. It's easy to construct three triangles with a cyclic overlap; for instance, imagine looking down the Z axis at three long, thin triangles:

• A: (2.1, 1.9, 1), (1.9, 2.1, 1), (-1, -1, 0)
• B: (-2.1, 1.9, 0), (-1.9, 2.1, 0), (1, -1, 1)
• C: (2.1, 1, 0), (1.9, 1, 0), (-2, 1, 1)

Then where A and B overlap on-screen (near the XY point (0,0)), B will be on top (have the higher Z value): its Z value will be approximately 0.66 whereas A's will be approximately 0.33. Similarly, where A and C overlap (near the XY point (1, 1)), A will be on top; and where B and C overlap (near the XY point (1, -1)), C will be on top. There's no way of ordering these three triangles such that drawing them to screen in the specified order will give the correct result.

As Nathan Reed suggests, the fact that you're in an isometric view means that you would probably be able to avoid this particular issue; the question is whether it's worth avoiding or not, and that's more contingent on your environment and the particular functionality you have available. Most platforms you could be developing on have at least some form of 3d rendering readily available, though, and my first inclination would be to just piggyback on top of that for your purposes.

-