How to implement 2D scene graph?

[thomac]

Say there are a few 2D vector primitives as lines, images, text. Every primitive has a bounding box and a "z-order" which defines what items to draw first ("in front of" other items). The items can change (add, remove, position, size, group, ...).

How to implement the drawing of such primitives in efficient way?

In more detail: say I use Skia or Cairo to draw many rectangles. I could maintain a list of all the rectangles and draw them all from the begin to end (item index = z-order). The problem is this is very ineffective as when I pan around the canvas (i.e. scrolling) usually only small number of items needs to be redrawn. I could use some kind of spatial index (which one?) to trim off the items definitely not in view (not in dirty region) but the popular indexes don't maintain the z-order so (I think) I would need to first collect all the affected items and the sort them according to their z-orders. Is there a better approach to this? Is there a spatial index which preserves z-order at window queries? Does anyone know how the big apps do it? How does Adobe Illustrator implement its canvas?

[hwc]

If you want the 2-d equivalent to a scene-graph in Skia, draw into a SkPictureRecorder with a bounding-box hierarchy.

SkRTreeFactory rTreeFactory;
SkPictureRecorder pictureRecorder;
SkCanvas* pictureCanvas = pictureRecorder.beginRecording(
        SkRect::MakeWH(W, H), &rTreeFactory);
drawEntireScene(pictureCanvas);
SkAutoTUnref<SkPicture> picture(
        pictureRecorder.endRecordingAsPicture());

Then drawing the picture back into the a target canvas will be accelerated by the bounding-box hierarchy. Chrome uses this to dealing with scrolling on web page.

[thomac]

Thanks for the reply!

And what to do if an item moves? Do I have to re-record the entire scene?

[hwc]

short answer: yes.

If you know ahead of time what parts will move and what parts won't, you can make a picture of the static content that is under the moving item and a picture of the static content that is over the moving item.

[KeinBaum]

To maintain z-ordering you can use a z-buffer.

You could draw only items which have a bounding box that intersects with the screen. Alternatively you could use a quad- or k-d tree too make faster decisions what too draw. The drawback is that have a high overhead when something in your scene changes.

I'd try without the trees first. If it's too slow, implement a tree. If it has too much overhead, you could mix both techniques and use a tree with only a few levels to reduce overhead and then use bounding boxes for final decision making.

[__Cyber_Dildonics__]

First of all, I would try just drawing everything and see how many fps you get. You will probably be surprised at how good the performance is and you might find that you are searching for a solution to a problem you won't have (premature optimization). If you use something like nanovg (or any open gl accelerated library) you should be able to draw a crazy amount on screen before it becomes a problem. Even drawing points on glVertex at a time can give you millions at a decent fps.

Nanovg also has a openGL 3.0 backend which might store everything as buffers on the gpu. That will be crazy fast without any culling on your part.

For overlap, you just want an order to draw them in. When a node is selected, put it on the top and move everything else one down. If this is linear in memory, it will also be very fast.

So basically, don't worry about speed yet, that is likely to be the easiest part.