# Planar scene graph

Suppose there are many line segments on a plane (2D scene) and I would like to redraw only small portion ("window") of the whole scene. The scene is dynamic, meaning one can add/remove/transform lines. Also, this being about drawing, it matters in what order the lines have to be redrawn (painter's algorithm, z-index). It is also possible to move a line in front of / behind of another line, effectively changing its painting order.

What data structure is suitable for this kind of problem?

I would like both the scene modifications and finding of the affected lines to be as quick as possible. One way to implement such scene graph is to use a simple list of line segments, sorted by z-index and during the redraw iterate through the list and if a segment fits the window, redraw. However, this has linear time complexity, and I would like to know if there is a faster way, preferably logarithmic.

• I was about to suggest using a quad tree, but there is the complication that your lines could cross the screen without having endpoints visible. The only thing I can think of is to rasterize each line by storing all the 2D "bins" it intersects . Then, render all the lines that pass through the "bins" the screen intersects. No need to explicitly store a big grid for this -- it can be done with a hash map. Performance would be constant-time to determine which lines to draw -- but insertion will be linear. Commented Feb 11, 2015 at 21:45
• @mklingen ad quad tree: if the lines were always inside the screen, how would I combine it with z-index? I mean, quad tree is build with respect to positions of bounding rectangles of the lines, how to build and query the quad tree so that it reports the result in z-order? Ad "bins": you mean hash grid or uniform grid, correct? Again, how to perform a query on grid so that the result is z-index sorted? Commented Feb 11, 2015 at 22:12
• z-sorting is another issue entirely. I was talking about how to decide which lines to draw. After you've decided on the lines, you have to z-sort them. Honestly the fastest way to do that would be to use an orthographic camera, and give your lines a z coordinate. The depth buffer will automatically sort them in hardware. Commented Feb 11, 2015 at 22:16
• @mklingen: unfortunately I don't use a "camera". There are many data structures (quad tree, R-tree, BVH, ...) which allow me to find the windowed lines. I was just hoping there is a data structure which is able to report the results already z-sorted, as opposed to first find the items, copy to an array, and then sort. I'm asking because if the window was enclosing all the lines then the z-sorting would take O(n log n). I trying to find a structure which keeps the lines sorted at all times... Commented Feb 11, 2015 at 22:26
• Ok. If you really want to sort them on the CPU instead of the GPU (and I would not recommend this unless your "lines" are actually semi-transparent sprites or something), you can just take the 2D concept and extend it to 3D. Just stick them into an octree or a 3D spatial grid. Then, when reading out the lines for rendering go from the bottom of the data structure (furthest from the viewer) to the top (closest to the viewer). Note that this may end up being much slower than sorting them unless you have many many lines. Commented Feb 11, 2015 at 22:33