I Have an interesting little problem, thought I’d throw it out there and see if it stirs up any discussion….

Graphics app, wherein the user can draw stuff - arbitrary vectors on a canvas. My bread-and-butter, really. Over the years of doing this, I’ve tried a variety of underlying storage schemes to ensure efficiency when the number of objects grows large. We’re talking 25,000 objects+, potentially.

One challenge is to avoid the need to iterate all 25,000 in order to figure out which ones need drawing for any given update/dirty rects. The naive approach of just storing an array and testing the bounding rects of every object bogs down fast above a few thousand.

So I use a spatial database which is an R-Tree [R-tree] - this rapidly eliminates vast numbers of objects by collecting objects into groups of bounding rects at each higher level of the tree. This works great - I can store tens of thousands of objects and drawing remains efficient provided the update area is small, which it typically is - the user will typically only zoom part of the canvas and work there, then scroll to a different part. There are remaining issues with drawing performance when zooming out to show the whole thing, etc, but that’s not the issue I want to talk about here (tiling helps a lot there).

Objects stored in the R-Tree are only sorted into groups according to their bounding rects, otherwise there is no ordering. Everything is implemented using sets, and the tree itself is very agnostic about what objects it references - as long as they conform to a very basic protocol, it’s happy:

The R-Tree’s only job is to (very quickly) return a set of objects that intersect a given rectangle. That could be the update area, or a selection rect, for example.

So the returned objects are unsorted.

For drawing, there is a specific Z-order that the objects need to be drawn in, so that the visual layering is stable. That’s no problem - each one has a ‘zOrder’ property which defines its level, and the objects to be drawn are sorted on that property, then drawn in order. This works no matter which set of objects is returned in any given update area - the zOrder value applies to the whole set of all objects (it is incremented as new objects are created), but in any subset, the order is the same even though the vast majority of objects are skipped and not drawn. So far, so good.

The user needs the ability to change the z-ordering of objects at will, usually implemented in terms of commands: “move to front”, “move to back”, “move forward”, “move backward”.

Moving to the front or back is straightforward; changing the z-order property to be zero or max is all that is required.

Moving back one or forward one is more problematic however. Classically, all objects were held in an array and this array defined the z-order. This means a huge array for one thing, but it is also a poor fit for sorting objects to be drawn. When each object has a zOrder property, that is trivial. But the zOrder property, if an array is used, means the index of the object in the array. Renumbering the zOrder of every object to match the array is slow. Looking up the index of the object in the array is slow (linear search). Just changing the value of ‘zOrder’ is simple, effective and extremely fast. No array required.

The problem is with moving back one or forward one zOrder position. What value do I give that? It can’t just be incremented or decremented, because that could mean that it now has the same zOrder value as another object. Furthermore, we don’t know WHICH other object it might clash with. It could be something nearby, or something somewhere else entirely. Without the array, we have no way to quickly find objects having similar zOrder values.

zOrder applies to the whole set of objects, but maybe it doesn’t need to. Vector apps have always taken the approach that zOrder is ‘global’ in this sense, but I’m wondering if that really makes sense. One effect is that move forward or move backward often have no visible effect, because the objects that they are ordered relative to don’t intersect it. In fact they could be miles away.

So I’m wondering if the solution to my data structure problem is not to come up with a way to mimic the ‘global zOrder’ behaviour of antiquity, but instead to make zOrdering changes very localised. In other words, only reorder objects relative to other nearby objects. This would be better behaviour in some ways, because it matches the user’s visual expectations - if they are reordering objects in z, it’s because they want to move something behind or in front of something else they can see there, not some unrelated object on the other side of the canvas. Finding a suitable value for zOrder in this situation is much easier, because I only need to renumber objects in a local group (or using a floating point value, it can be set to half way between two others). These may end up clashing with others elsewhere, but unless the user decides to move something to a part of the canvas where that becomes visible, they will never see it. This of course could occur - but then adjusting zOrder in THAT  local group would be straightforward too.

If you’ve read and understood this far, well done.. haha.

So my question for discussion, should anyone feel interested enough, is: should I try to find a data structure that allows me to do things the classic way, even though in some ways that’s less usable (but perhaps more in line with expectations), or should I change the way user interact with the zOrder and avoid the coding problem altogether?

—Graham