Optimising the drawing of overlapping rectangles

Question

I have a large number of rectangles, and some overlap others; each rectangle has an absolute z-order and a colour. (Each 'rectangle' is actually the axis-aligned bounding box of a particle effect, mesh or texture and may be semi-transparent. But its easier to think abstractly about coloured rectangles as long as you don't try to cull rectangles behind others, so I will use that in the problem description:)

The cost of changing the 'colour' is quite high; its much faster to draw two blue rectangles in succession than it is to draw two different-coloured rectangles.

The cost of drawing rectangles that are not even on the screen is quite high too and should be avoided.

If two rectangles do not overlap, the order they are drawn relative to one-another is not important. Its only if they overlap that the z-order is important.

For example:

1 (red) and 4 (red) can be drawn together. 2 (blue) and 5 (blue) can also be drawn together, as can 3 (green) and 7 (green). But 8 (red) must be drawn after 6 (blue). so its either we draw all three red together and draw the blue in two sets, or we draw all the blue together and draw the red in two sets.

And some of the rectangles may move occasionally. (Not all of them; some rectangles are known to be static; others are known to move.)

I will be drawing this scene in JavaScript/webGL.

How can I draw the rectangles in a reasonable order to minimize colour changes, with a good trade-off of JavaScript culling code vs letting the GPU cull?

(Just working out which rectangles overlap and which are visible is expensive. I have a basic quadtree and this sped my scene drawing up immensely (compared to just emitting the draw-ops for the whole scene); now the question is how to minimize OpenGL state changes and concatenate attribute arrays as much as possible)

UPDATE I have created a very simple test app to illustrate the problem and serve as a basis for demonstration of solutions: http://williame.github.com/opt_rects/

The source-code is on github and can easily be forked: https://github.com/williame/opt_rects

It turns out its hard to make a little test app with sufficient state change to actually recreate the problem I see in my full game. At some point you'll have to take it as a given that state changes can be sufficiently expensive. What is also important is how to speed up the spatial index (quadtree in demo) and the overall approach.

Answer 1

You are making the very wrong assumption that the performance you will be getting on the desktop browser will somehow determine the performance on your iPhone. You need to understand that the iPhone hardware implements tile-based deferred rendering which means that the fragment shader is used very late in the pipeline anyway. As Apple themselves say (“Do not waste CPU time sorting objects front to back”), Z-sorting your primitives will get you little performance gain.

But here’s my suggestion: if changing the colour is expensive, just don’t change the colour: pass it as a vertex attribute, and merge the behaviours into one super shader so you can draw everything in one or a few batches without even sorting. Then benchmark and determine the optimal batch size for your platform.

Answer 2

Choose colours, not boxes!

At any point in time, one or more boxes will be paintable, i.e. they are able to be painted next without introducing problems (though possibly introducing a cost due to having a different colour from the most recently painted box).

The question at every point is: What colour should we pick to draw next? It's not necessary to think about picking individual paintable boxes to draw, because as soon as you pick a particular box to draw next, you might as well draw all available boxes of the same colour that can be drawn at that time. That's because painting a box never adds constraints to the problem, it only removes them; and choosing not to paint a paintable box when you could do so without changing the current colour cannot make the solution less expensive than it would otherwise be, since you will later have to paint this box and that may require a colour change. This also means it doesn't matter in which order we paint paintable boxes of the same colour, since we will paint all of them at once in a single "block" of box painting operations.

The dependency graph

Start by building a "lies underneath" dependency graph, where each coloured rectangle is represented by a vertex and there is an arc (arrow) from v to u if rectangle v overlaps rectangle u and lies underneath it. My first thought was to use this to build a "must be drawn before" dependency graph by finding the transitive closure, but actually we don't need to do this, since all the algorithms below care about is whether a vertex is paintable or not. Paintable vertices are the vertices that have no predecessors (in-arcs), and taking the transitive closure does not alter whether a vertex has 0 in-arcs or not.

In addition, whenever a box of a given colour has only boxes of the same colour as its ancestors, it will be painted in the same "block" -- since all those ancestors can be painted before it without changing colours.

A speedup

To cut down on computation, notice that whenever all paintable boxes of some particular colour have no different-coloured descendants, painting this colour won't open up any new opportunities for other boxes to become paintable, so we don't need to consider this colour when considering which colour to paint next -- we can always leave it till later with no risk of increasing the cost. In fact it's better to leave painting this colour till later, since by that time other boxes of this colour may have become paintable. Call a colour helpful if there is at least one paintable box of that colour that has a different-coloured descendant. When we get to the point when there are no helpful colours remaining (i.e. when all remaining boxes overlap only boxes of the same colour, or no boxes at all) then we are done: just paint the boxes of each remaining colour, picking colours in any order.

Algorithms

These observations suggest two possible algorithms:

1. A fast but possibly suboptimal greedy algorithm: Choose to paint next the colour that produces the most new paintable vertices. (This will automatically consider only helpful colours.)

2. A slower, exact DP or recursive algorithm: For each possible helpful colour c, consider the dependency graph produced by painting all paintable c-coloured boxes next:

   Let f(g) be the minimum number of colour-changes required to paint all boxes in the dependency graph g. Then

   f(g) = 1 + min(f(p(c, g)))

   for all helpful colours c, where p(c, g) is the dependency graph produced by painting all paintable boxes of colour c. If G is the dependency graph for the original problem, then f(G) will be the minimum number of changes. The colour choices themselves can be reconstructed by tracing backwards through the DP cost matrix.

   f(g) can be memoised to create a dynamic programming algorithm that saves time whenever 2 different permutations of colour choices produce the same graph, which will happen often. But it might be that even after DP, this algorithm could take an amount of time (and therefore space) that is exponential in the number of boxes... I will have a think about whether a nicer bound can be found.