3
\$\begingroup\$

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.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – mklingen
    Commented Feb 11, 2015 at 21:45
  • \$\begingroup\$ @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? \$\endgroup\$
    – Ecir Hana
    Commented Feb 11, 2015 at 22:12
  • \$\begingroup\$ 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. \$\endgroup\$
    – mklingen
    Commented Feb 11, 2015 at 22:16
  • \$\begingroup\$ @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... \$\endgroup\$
    – Ecir Hana
    Commented Feb 11, 2015 at 22:26
  • \$\begingroup\$ 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. \$\endgroup\$
    – mklingen
    Commented Feb 11, 2015 at 22:33

1 Answer 1

Reset to default
1
\$\begingroup\$

Submitting my earlier comment as an answer:

So you are doing rasterization manually, without the use of a graphics library. If that's the case, you can emulate the depth buffer yourself. In addition to the color buffer, also store a z value in a separate image. Only write to the color buffer if the incoming z-value is less than or equal to the current z-value. If you don't have semi-transparent lines, this is probably the correct way to do it, as it requires no sorting.

If you want semi-transparency (and to some extent, anti-aliasing), you might have to sort the lines manually first.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the reply but as I said above, yes, it contains semi-transparency. \$\endgroup\$
    – Ecir Hana
    Commented Feb 12, 2015 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .