43

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:

Overlapping Rectangles

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.

27
  • 1
    How many rectangles you have? Max possible value. Jan 14, 2013 at 11:39
  • 2
    off my head: start with a topological sort of ascending z-order considering only pairs of rectangles that overlap. take the corner of an overlapping rectangle as the coordinate at which to split the overlapped rectangle into 2 or 3 smaller rectangles of the same color, one of which will be occluded completely (drop it at once) or partially (parts can be dropped later). update the toposort relation. repeat until the toposort relation is empty. at that time, there will be no overlaps, so draw by sets of same color. the final number of rects should be linear in the original number.
    – collapsar
    Jan 15, 2013 at 15:20
  • 1
    @Will Can you provide us with a self-contained example of your current method, so we can benchmark and compare improvements?
    – Alex L
    Jan 16, 2013 at 8:34
  • 1
    So would the appropriate metric be simply the number of color changes required to paint all the rectangles, or is there something more complicated to optimize? Jan 16, 2013 at 13:45
  • 1
    The "minimise colour changes" objective is clear, but it's not clear what "culling invisible rectangles" should mean. The latter seems to be a step that would precede the former. Do you have an axis-aligned bounding box representing the view, and want to find a nice data structure to quickly cull the boxes that are entirely outside this AABB? A quadtree seems ideal for this step. Jan 16, 2013 at 14:01

4 Answers 4

16
+500

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.

7
  • 1
    I think, because he uses quotes with 'colour', he's not referring to simple color, but possibly other state like a different shader.. Jan 17, 2013 at 9:08
  • @JariKomppa Sure, I understood it like that, too; which doesn't prevent merging those different shaders. I'll clarify my answer. Jan 17, 2013 at 9:37
  • @SamHocevar yes the question is how to merge those things that can be drawn with the same state and so to minimize batches... I cannot trivially draw different types of particle effect with the same shader or draw meshes with that same shader either, but I can try and draw as many of the same type of particle effects with the same shader at the same time rather than flipping between them...
    – Will
    Jan 17, 2013 at 10:27
  • 2
    @Will You will need to provide more information about what you wish to do, then, because using a large if() to merge several shaders is certainly trivial. If the idea of "colour" extends to render states then it's not the same question at all, especially if alpha blending is involved. Jan 17, 2013 at 10:55
  • 2
    @Will Yes, that's a whole deal of new problems to solve and compromises to make :-) But with the information you are providing, you'll only get general strategies for improvements, not full-featured solutions. Jan 17, 2013 at 15:56
12

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.

10
  • 1
    Good idea with the paintable boxes and the dependency graph. However, my gut tells me that building the graph will be expensive. The greedy algorithm can simply be proven to be suboptimal. The recursive algorithm could be expensive as well. Altogether this solution is possibly not a good tradeoff between js and gpu work. Code shall prove.
    – ilmiacs
    Jan 16, 2013 at 17:14
  • 2
    @ilmiacs: It seems to me that building that graph will be necessary in almost any approach that offers some algorithmic optimizations. But you need to do that work in any case, regardless of whether you store it in a particular data structure, so creating the graph should not add much overhead to any approach that has to understands which boxes overlap each other. But I agree that the recursive algorithm here is almost certain too expensive for reasonable sized data sets. Jan 16, 2013 at 17:49
  • 1
    @Will: I haven't looked at your sample yet (maybe from home this evening, maybe not until the weekend.) But if you have a tree structure, doesn't it already encapsulate the overlap? If so, you're most of the way to the graph. I actually wouldn't be surprised if j_random's greedy algorithm would be all you need to achieve the performance you want. Nor would I be surprised to find that the actual optimization problem is NP-complete. It has the feeling of that sort of problem. Jan 16, 2013 at 18:01
  • 1
    @Will Is 'your waffle' really necessary?
    – MrKWatkins
    Jan 17, 2013 at 17:43
  • 4
    Seems my comment was removed for being offensive. Let me try again: "@Will: My waffle? To answer your question, no, I won't be providing demo code for you. See if you can figure out why." Jan 17, 2013 at 21:47
2

Here's a possibility. You'll have to benchmark it to see if it's actually an improvement.

For all rectangles, back to front:
  If this rectangle has been marked as drawn, skip to the next one
  Set a screen-sized unseen surface to all black
  Call this rectangle's color "the color"
  For rectangles starting with this one and proceeding toward the front
    If (this rectangle's color is the color and
        all the pixels of this rectangle on the unseen are black) then
      Add this rectangle to the to-draw list
    Draw a white rectangle with this rectangle's shape on the unseen surface
    If the unseen surface is more than half white, break
  For all rectangles on the to-draw list:
    Draw the rectangle
    Mark it as drawn

It's not guaranteed to be the most optimal in terms of ordering, but I think it will come pretty close, and it's worst-case quadratic in the pre-drawing step. It does depend on readbacks from the graphics buffer being fast. One trick that might help there is to create a new one pixel surface that is a shrunken version of the area of interest. Its color will be the fraction of the original that was white.

2

Start by drawing in a random (but correct) order, for example in strict z order. When drawing each frame, either count the number of color changes, or possibly the actual time a complete frame takes. Each frame, try swapping the order of two rectangles. The rectangles to be swapped must not overlap, therefore they can be drawn in any order without violating correctness; aside from that they can be chosen at random, or do a linear pass through the list, or... If doing the swap reduces the number of color changes, keep the new order, if not revert it and try a different swap in the next frame. If doing the swap neither reduces nor increases the number of color changes, keep it with 50% odds. For any rectangles which did not overlap in a previous frame but which start overlapping due to a move, simply exchange them so they are in z order.

This has some relationship to sorting algorithms which swap pairs of items, except that we cannot compare items, we need to go through the whole list and count color changes. This will perform very badly at first but converge to a good order relatively quick, and will adapt to scene changes. I think it is probably not worth it to go through and calculate an optimum order every frame; this will get to, and maintain, a near-optimum order with very little extra work.

Referring to the drawing you have: Initial draw order picked at random: 1,6,2,4,5,8,3,7 (5 color changes). Swap 5,8. New order: 1,6,2,4,8,5,3,7 (4 color changes) => Keep new order.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.