StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POOptimising the drawing of overlapping rectangles
text
Body
copied!<p>I have a large number of rectangles, and some overlap others; each rectangle has an absolute z-order and a <em>colour</em>. (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:)</p> <p>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.</p> <p>The cost of drawing rectangles that are not even on the screen is quite high too and should be avoided.</p> <p>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.</p> <p>For example:</p> <p><img src="https://i.stack.imgur.com/Egmd7.png" alt="Overlapping Rectangles"></p> <p>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.</p> <p>And some of the rectangles may move occasionally. (Not all of them; some rectangles are known to be static; others are known to move.)</p> <p>I will be drawing this scene in JavaScript/webGL.</p> <p>How can I draw the rectangles in <em>a reasonable order to minimize colour changes</em>, with a good trade-off of JavaScript culling code vs letting the GPU cull?</p> <p>(Just working out which rectangles overlap and which are visible is expensive. I have a <a href="https://stackoverflow.com/questions/13906902/spatial-index-for-lines">basic quadtree</a> 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)</p> <p><strong><em>UPDATE</em></strong> I have created a very simple test app to illustrate the problem and serve as a basis for demonstration of solutions: <a href="http://williame.github.com/opt_rects/" rel="nofollow noreferrer">http://williame.github.com/opt_rects/</a></p> <p>The source-code is on github and can easily be forked: <a href="https://github.com/williame/opt_rects" rel="nofollow noreferrer">https://github.com/williame/opt_rects</a></p> <p>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. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload