|
Thanks to everyone who chipped in so far — interesting ideas.
The zOrder is in fact a float (CGFloat, so 64 bit), but as Jens points out, it can’t go on indefinitely.
In experimenting with this, it turns out that limiting the reordering to just the objects that are visually intersected is a really, really nice behaviour from the user’s perspective. It means that every operation has a visible effect, rather than appearing to do nothing in the cases where you are reordering relative to an object some distance away. I believe from a usability perspective this is a good solution. I may add “global” reordering as an option, assuming I can find a solution I like. The trie idea is interesting, but possibly overkill for the feature… and tbh, learning enough about tries to implement one correctly is probably going to take more time than I’m willing to spend. Though I notice there is a class in Core Foundation - CFBurstTrie - that might fit the bill (not sure if it has a public interface however, seems it may be something private).
Regarding running out of precision when ’splitting the difference’ when reordering, the reality is that this is an uncommon operation in terms of sheer numbers. It probably comes up moderately frequently, but my feeling is that it would be unlikely to run out of numbers in most cases. Of course that’s not good enough - it means a potential bug in the limit when things don’t work as they should. But occasionally renumbering the whole stack is likely to work to solve that, and that can be done when the model is built or saved. Or Jens’ idea of using strings could work for reordering, but may be too slow to sort on that order for drawing (which is my main priority - drawing has to be fast). With local reordering, zOrder value clashes inevitably do occur, because objects further away are just not considered while the local renumbering is performed. Again, that doesn’t matter too much because nothing critical rests on this (unlike Jens’ To Do list example), the only time it would reveal itself is if the user drags an object across the canvas and it gets occluded by something and they didn’t expect that. But in an interactive drawing environment, I'd suggest that doesn’t especially matter - they can simply reorder as necessary in that new local area to get the visual result they want.
—Graham
On 24 Jul 2020, at 5:11 am, Jens Alfke < jens@...> wrote:
Are the zObjects integers? If so would it help to make them floats? Intial value 3.0; Back one 2.9 or 2.09; Forward one 3.1 or 3.01?
Sadly, this only postpones the problem — you run out of precision after a while. A 64-bit double only has about 52 bits of mantissa, meaning that some sequences of 52 reorders will cause a collision between adjacent Z values.
I've actually seen this exact problem in other domains — usually having to do with distributed algorithms for preserving ordering, as in a collaborative to-do list with offline support. IIRC it also shows up in some P2P distributed hash tables like Chord and Kademlia.
A workable way to do this is to use strings, since you never run out of room. So the initial objects are labeled A, B, C, D… When you need to put an object in between C and D, you label it CM. When something has to go between CM and D, you label it CS. Eventually you have to fit something between CR and CS, so you label it CRM. (In a real implementation you'd probably use bit-strings instead. Which you can also interpret as fractional binary numbers … exactly like your suggestion except using infinite precision instead of floating point.)
The eventual problem is that over time the Z labels get longer and longer. Probably not an issue for a graphics editor? The usual solution is to occasionally renumber everything with short strings, perhaps when saving.
This is probably equivalent to David Young's radix-trie suggestion … the trie is a more complex data structure than a sorted array, but performs better. Sliding a mere 25,000 pointers around in an array shouldn't take a noticeable amount of time, though (it's only 200KB) provided you only do it once per user command. (And actually, I believe NSArray already turns into something more tree-like when the count grows large, to make inserts/deletes faster.)
—Jens
|
|
|
Are the zObjects integers? If so would it help to make them floats? Intial value 3.0; Back one 2.9 or 2.09; Forward one 3.1 or 3.01?
Sadly, this only postpones the problem — you run out of precision after a while. A 64-bit double only has about 52 bits of mantissa, meaning that some sequences of 52 reorders will cause a collision between adjacent Z values.
I've actually seen this exact problem in other domains — usually having to do with distributed algorithms for preserving ordering, as in a collaborative to-do list with offline support. IIRC it also shows up in some P2P distributed hash tables like Chord and Kademlia.
A workable way to do this is to use strings, since you never run out of room. So the initial objects are labeled A, B, C, D… When you need to put an object in between C and D, you label it CM. When something has to go between CM and D, you label it CS. Eventually you have to fit something between CR and CS, so you label it CRM. (In a real implementation you'd probably use bit-strings instead. Which you can also interpret as fractional binary numbers … exactly like your suggestion except using infinite precision instead of floating point.)
The eventual problem is that over time the Z labels get longer and longer. Probably not an issue for a graphics editor? The usual solution is to occasionally renumber everything with short strings, perhaps when saving.
This is probably equivalent to David Young's radix-trie suggestion … the trie is a more complex data structure than a sorted array, but performs better. Sliding a mere 25,000 pointers around in an array shouldn't take a noticeable amount of time, though (it's only 200KB) provided you only do it once per user command. (And actually, I believe NSArray already turns into something more tree-like when the count grows large, to make inserts/deletes faster.)
—Jens
|
|
|
Graham,
I am picturing a radix trie with n-bit keys where n is 32 or 64—whichever suits your z-orders. Keys represent the z order. Each object is a leaf in the trie. In each object, store its z-order (key).
Say higher z is farther away. To move object X forward, first locate the preceding object, P, in the tree. If P does not exist, you’re done, because X is at the front. If P exists, swap the places in the tree of X and P. Swap the z-orders.
If you initially assign z-orders starting with 2^n - 1 and decreasing, then I don’t think you will have to re-z-order all objects.
You could use some balanced binary tree, too. That may be more suitable, actually.
Hope this helps.
Dave
Spilling kerrectud by iPhone
On Jul 22, 2020, at 7:22 PM, Graham Cox < graham@...> wrote: Hi all,
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:
@protocol GCRTreeStorable <NSObject, NSCoding>
- (CGRect) extent;
@end
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
|
|
|
Are the zObjects integers? If so would it help to make them floats? Intial value 3.0; Back one 2.9 or 2.09; Forward one 3.1 or 3.01?
Or have I not understood your architecture or the memory implications?
On Jul 22, 2020, at 8:22 PM, Graham Cox < graham@...> wrote:
Hi all,
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:
@protocol GCRTreeStorable <NSObject, NSCoding>
- (CGRect) extent;
@end
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
|
|
|
Hi all,
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:
@protocol GCRTreeStorable <NSObject, NSCoding>
- (CGRect) extent;
@end
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
|
|
|
