How to sort/draw pseudo-3D buildings so as they don't visually overlap

I have vector data for buildings on my map and want them to appear extruded, depending on known height.

I know this is a common task, but i didn't find any satisfying solution.

I saw realization in mapnik, they use simple sort by minimum Y of all vertices in a polygon. As result, most are drawn right, but some are still overlapped (about 2-3%).

In most cases it is enough just to sort buldings well (somehow?) and draw them in appropriate sequence (for above case this sequence would be 3-2-1).

In more complex cases, when polygons are concave and too close to each other, every wall and cap (roof) should be drawn separately (see below).

UPDATED:

So, there are two kinds of segments to draw: walls and caps. Wall segments are easy to order (by minimum Y开发者_高级运维). I can't figure out how to order caps.

Thank you.

In the case of straight walls it is easy to sort them by depth. Consider just their bases which are straight line segments. Note that each line divides the plane in two parts, one of them is closer to the viewer and the other is farther. For any segment A, call the closer part A+ and the farther part A-. Now, for any two segments A and B, at least one of the propositions holds:

1. A lies entirely in B+
2. A lies entirely in B-
3. B lies entirely in A-
4. B lies entirely in A+
5. One segment is parallel to the line of sight and the other is entirely to the left or entirely to the right of it
6. A and B intersect

In cases 1 and 3, B should be drawn before A (A may occlude B, but B may not occlude A); in cases (2) and (4) A before B; in case 5, it doesn't matter; and 6 should not occur for normal walls.

You can now do a topological sort of the walls, and draw them from furthest to closest.

As for roofs, this is not possible for concave buildings, since a part of the roof can be obscured by a wall which obscures another part of that same roof. Imagine a low U-shaped building, visible from its side, with a tall tower in the middle of the U. The tower will both obscure and be obscured by the U-roof, so in whatever order you draw them, the picture will be wrong.

So you will have to subdivide concave roofs into convex polygons. Then it should be easy to sort them together with the walls, along the same principles.

A totally another method is to use a Z-buffer, which frees you from thinking about the order. It is my impression that you can get Z-buffer on the lowest of the low-powered cell phone graphic cards these days.