Optimized drawing of overlapping rectangles

Question

I have a large number of rectangles, and some overlap others; each rectangle has an absolute z-order and color. (Each "rectangle" is actually an axially aligned bounding rectangle of the particle effect, a grid or texture and can be translucent. But it’s easier to ignore the colored rectangles if you are not trying to drop the rectangles after the others, so I will use this in the description of the problem: )

The cost of changing the “color” is quite high; it is much faster to draw two blue rectangles in a row than to draw two multi-colored rectangles.

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

If the two rectangles do not overlap, the order they draw relative to each other is not important. Its only if they overlap is that z-order is important.

For example:

1 (red) and 4 (red) can be assembled together. 2 (blue) and 5 (blue) can also be brought together, as well as 3 (green) and 7 (green). But 8 (red) needs to be drawn after 6 (blue). therefore, we either draw all three red together and draw blue in two sets, or draw all blue together and draw red in two sets.

And some of the rectangles can sometimes move around. (Not all of them, some rectangles are known to be static, others are known to move.)

I will draw this scene in JavaScript / webGL.

How can I draw the rectangles in a reasonable order to minimize color changes, with a good compromise of the code for rejecting JavaScript and discarding the GPU?

(Just working on which rectangles overlap and which are expensive to see, I have a basic quadtree , and this accelerated my scene, draw-ops for the whole scene), now the question is how to minimize OpenGL state changes as much as possible and combine attribute arrays )

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

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

It turns out that it is difficult to make a small test application with enough state change to actually recreate the problem that I see in my full game. At some point you will have to take this as a task that state changes can be quite expensive. It is also important how to speed up the spatial index (quadtree in the demo) and the general approach.

Answer 1

You are making the very wrong assumption that the performance you get in your desktop browser will somehow determine the performance of your iPhone. You must understand that the iPhone hardware implements tile-based delayed rendering , which means that the fragment shader is used very late anyway. As Apple themselves say (“Don't waste time sorting time objects in front of the processor”), Z-sorting your primitives will give you a slight increase in performance.

But my suggestion: if the color change is expensive, just don’t change the color: pass it as an attribute of the vertex and combine the behavior into one super shader so that you can draw everything in one or more parts, without even sorting, then check and determine the optimal batch size for your platform.

Answer 2

Choose colors, not fields!

At any given time, one or more boxes will be drawn, i.e. they can be painted as follows without introducing any problems (although, perhaps, they can lead to cost due to the fact that the color is different from the most recently painted box).

The question is at each point: what color should I choose for the next? There is no need to think about choosing individual drawable drawers for drawing, because as soon as you select a specific box for drawing further, you can also draw all available drawers of the same color that can be drawn at this time. This is because when drawing a box, the limits on the problem are never added, it only removes them; and, not wanting to draw a painting box, when you could do it without changing the current color, cannot make the decision less expensive than otherwise, since later you will have to draw this field, and this may require a color change. It also means that it does not matter in which order we draw the drawers of the same color, since we will paint them all at once in one “block” of box painting operations.

Dependency graph

Start by building a false under dependency graph, where each colored rectangle is represented by a vertex and there is an arc (arrow) from v to u if rectangle v overlaps rectangle u and lies under it. My first thought was to use this to plot the “need to draw up” dependencies by finding a transitive closure, but in fact we do not need to do this, since all the algorithms described below are that Masked vertices are vertices that are have no predecessors (in arcs), and the transition of the transitive closure does not change whether the vertex has 0 in arcs or not.

In addition, whenever a box of a given color has only boxes of the same color as its ancestors, it will be painted in the same “block”, since all these ancestors can be painted in front of it without changing colors.

Acceleration

To cut out the calculations, note that whenever all the drawers of a certain color have no descendants of another color, drawing this color will not open any new possibilities for other fields to become beautiful, so we do not need to consider this color when considering what color should be painted next - we can always leave it longer, without the risk of increasing the cost. In fact, it is better to leave the color of this color until a later time, since by that time other boxes of this color may have become beautiful. Make the color useful if there is at least one coloring box of that color that has another color descendant. When we get to the point where there are no useful colors left (i.e., when all the remaining boxes overlap only the boxes of the same color or have no boxes at all), then we are done: just draw the fields of each remaining color, choosing colors in any order.

Algorithms

These observations suggest two possible algorithms:

• Fast, but possibly suboptimal, greedy algorithm: Choose to draw the next color, which creates the newest color peaks. (This automatically considers only useful colors.)

• Slower, more accurate DP algorithm or recursive:. For each possible useful color c, consider a dependency graph created by painting all painted c-color blocks as follows:

  Let f (g) be the minimum number of color changes needed to draw all the boxes in the dependency graph g. Then

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

  for all useful colors c, where p (c, g) is a dependency graph created by drawing all coloring boxes of color c. If G is the dependency graph of the original problem, then f (G) will be the minimum number of changes. The color choice itself can be restored by tracing back through the DP cost matrix.

  f (g) can be memoised to create a dynamic programming algorithm that saves time when two different color permutations choose the same graph, which often happens. But it may be that even after DP this algorithm may take some time (and therefore space), exponential in the number of boxes ... I will think about whether it is possible to find a more convenient link.

Answer 3

There is an opportunity. You will need to compare it to see if this is 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 color "the color" For rectangles starting with this one and proceeding toward the front If (this rectangle 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 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 is not guaranteed that this will be the most optimal from the point of view of the order, but I think that it will be quite close, and it is the worst quadratic at the stage of preliminary drawing. It depends on quickly reading reviews from the graphics buffer. One trick that can help is to create a new pixel surface, which is a shortened version of the area of ​​interest. Its color will be part of the original, which was white.

Answer 4

Start by drawing in an arbitrary (but correct) order, for example, in the strict order z. When drawing each frame, consider the number of color changes or, possibly, the actual time that a full frame takes. Each frame, try changing the order of two rectangles. The rectangles to be exchanged should not overlap, so they can be drawn in any order without violating the correctness; in addition, they can be selected randomly or linearly scroll through the list, or ... If the swap reduces the number of color changes, keep the new order if it does not return it and try another exchange in the next frame. If performing a swap does not reduce or increase the number of color changes, save it with a 50% ratio. For any rectangles that did not overlap in the previous frame, but which begin to overlap due to movement, just swap them so that they are in z order.

This has something to do with sorting algorithms that change pairs of elements, except that we cannot compare elements, we need to go through the entire list and count the color changes. At first it will be very bad, but converges to a good order relatively quickly and adapts to scene changes. I think that this is probably not worth it to go through and calculate the optimal order in each frame; this will make it possible to obtain and maintain an almost optimal order with very little extra work.

Referring to the drawing, you have: the initial knockout order is randomly selected: 1,6,2,4,5,8,3,7 (5 color changes). Exchange 5.8. New order: 1,6,2,4,8,5,3,7 (4 color changes) => Keep the new order.