GridTree DevLog 015: Move Aside, Refocus!

This update is a little late, and represents what I was working on a few weeks ago. I’ll try to send another update soon for the last couple of weeks, in which I get mathy.

You see, I knew I was running out of time to work on the “Move” function, and it ended up being a lot more complicated than I thought. (I thought I was already close to finished, before, but I was wrong.) I was splitting my time between getting the move function working and trying to test multi-directional pushes. (Instead of all child regions moving apart in the same direction, as done below, this would be each child region trying to move in a smarter way. NOT algorithmically simple.)

Anyway, I kept running into problems with both Move and multi-directional cascades, and eventually had to step away from this part to move on with things that were really necessary before my next publication deadline, because they’re going in the paper, and this might not.

But, before then I did make some excellent progress! There was a lot of supporting code to write, and an enormous amount of debugging, and now I am (once again) almost done with the Move function. Have I ever mentioned my difficulty getting my brain to switch tasks?

Well, I got distracted for a brief while first, fixing something that’s been bugging me for ages…

Sometimes when I’m transitioning to a new topic (like doing the math proofs and laying out clear algorithms to include in my next publication), I first go on a few tangents—difficulty starting new things and all…

Do you remember me saying in some previous post that GridTrees have no absolute positioning? There is no coordinate system for the entire tree. Having one would make moving a branch an O(n) operation, and would make so many things less scalable. Instead, every node is placed relative to its parent, with coordinates only for its children, and it communicates with nodes above it to make sure that nothing overlaps. This means that I can pick any node, put it at any position and any size, and just start drawing. The origin of the tree is whatever you choose it to be, making infinite zoom and pan a possibility. It begins at that node, and iterates down to draw descendants. If the “focus” node has a parent, it iterates upward as well. If the branch being drawn is out of the view box, it stops iterating. If it’s too small to draw, it stops iterating. And, if it’s all in-view, it stops checking, saving time when drawing the rest of the branch. When locating the node under the mouse position, it uses a similar process, rather than registering all in-view nodes as separate UI elements with their own bounding boxes.

When I finally wrap the GridTree into a neat software library, this means that the whole view would act as a single UI element, rather than each node, which may complicate some forms of software development, but it could well save a lot of UI computation and rendering time. I think. At that point, I’ll make it so the TreeView has an iterator available for all nodes in view, which returns node places, sizes, and interaction properties as well, so that whatever app is using it can render those rectangles and connectors however it desires.

So, I’ve had all of this capability in there for a while. I knew I would need it because, when generating a large tree while interacting with it, I would often be looking somewhere down in the weeds when my entire branch shifted out of view suddenly, caused by an ancestor way higher up, moving. This was because the view was being drawn relative to the root. The trickiest part of solving that, the part I hadn’t done yet, was finding a reliable algorithm for automatically shifting the origin, or “focus” node. Should it be the node at the center of the view? What about the one under the mouse? What if that node is tiny and out of sight?

What I landed on was a happy medium. I didn’t want it to be the node at the center of the view, in case the user was about to click and drag something, and the movement made them click the wrong thing. I also didn’t want to just do the node under the mouse exactly, because it might be some tiny branch too small to read labels on. So, I made it automatically switch to the smallest labeled ancestor of the node under the mouse, for now at least. I might make it do the center node if the mouse is not in the view, or other similar modifications, but for now, I finally have a stable view, even when huge changes occur higher in the tree, so that it shifts the origin silently in the background (nothing you see changes, because it recalculates where the new origin is relative to the old one before switching). In a way, this makes all drawing relative to the view, which is what I was going for. Although a lot of the code for this was already written, it was actually a complicated change that took a while to debug, mainly because of the relative jump from one origin to another without shifting the view, I think, and calculating the shifts up and down the tree properly.

With this, and only minor additional changes that were also annoying to debug, comes the ability to select a node to “follow” (currently by double-clicking on it). This means that the view centers on and is fitted to that node’s Grid, so the view shifts and resizes to keep the node fitted—a convenient feature for watching dynamic ongoing changes in a lower part of the tree, as well as for instantly zooming to a particular node. You might also imagine this being used later on to “jump to” a place in the tree, such as by selecting an item in a favorites list, or similar mechanic.

There’s another reason I’ve been meaning to finally complete this feature, and that is to make zoom effectively infinite, so that my viewing system will work even with very large and deep datasets. Of course, it is still limited by the algorithmic complexity, since transitioning from one origin node to another requires an O(log(n)) common-ancestor-finding algorithm, but this isn’t an issue since trees are only so deep, and this will only need done once per view per refocus—even thousands of levels deep would be no real issue there.

So, why wasn’t it just as “infinite” before? Because items are drawn with a scaling factor, and we run into floating point precision problems. For those of you unfamiliar with this, let me explain. If the root node is the origin, and it’s 5 levels above the node being drawn, then the root node’s size is 2⁵=32 times the size. If it is 40 levels above, that’s 2⁴⁰=1,099,511,627,776 times the size. Now, I’m only drawing the part of each rectangle that’s in the view, so that’s not the issue. The problem is partly that computers only effectively store numbers up to certain sizes, without really tricky and fairly slow workarounds. The other problem is that while floating point numbers (decimals) store very large values, up to exponents in the hundreds, they lose precision doing so - and when you’re trying to accurately scale from a large node down to a small node, you need more precision. This means that not only node sizes aren’t being stored properly after a certain depth, but the scale factor itself, and node places, are not being stored properly, and things get really wonky. This is the same problem in games like Minecraft which creates strange “Far Lands”, with bad terrain generation and jumpy positions there, when you go tens of millions of blocks away from the origin.

Let me demonstrate, starting with a simple-to-create test that goes hundreds of levels deep in a nice repeating pattern, at several points, just so I can see how different junctures of distant branches fare. Some show very high up and very deep nodes next to each other, and others show distant small descendants next to each other whose common ancestor is the root node way above.

(As an aside, this allows you to see the geometric series nature of continually halving grid cells. These branches could be generated effectively infinitely deep, and still fit in that tiny space.)

Before, with GridTrees, using this test I’d start to notice weird anomalies at around 30-40 levels deep, which are tiny pixel shifts at first, then getting worse and worse the deeper you go, until it crashes, having overloaded some part of the system or trying to divide by zero somewhere in my code or something. The top and bottom branches shown below are supposed to be sandwiched up next to each other, as they are in the image above.

But now, with the origin node continually changing to follow the view, I can actually go deeper, theoretically without limit, though I need to alter it to stop iterating after a certain point (just not drawing the other branch that isn’t in focus), because otherwise we will still have similar problems because of the distance it has to go up and then back down to draw adjacent branches. But I consider it an OK loss to not draw a neighboring branch so unrelated, like trying to claim a cousin that’s thirty times removed as close family… I’m afraid at that point, in these rare adjacent cases, you’ll just have to zoom out to jump branches, my friend. (Unless I later do the really crazy thing and implement a draw-positioning system that counts levels and grid cell distances instead of a scaling factor. If that ever happens, it’s a long way off.) As it is, have fun exploring thousands of levels deep… but I’ll tell you what, it takes a long time just to zoom in to 50 levels deep!

Sometimes little tangential things are difficult to justify taking my time and attention, even though they are what I want to work on, to see my work take shape and become more usable. I can argue that stable views are important for my Stability claims in my paper, and I can argue that infinite zoom is important for some datasets, or that multi-directional cascades create better layouts, but in truth these are not urgent, because while they are important to an eventual product, they may not represent sufficiently novel ideas to be more than a blurb in a larger publication, and therefore do not really represent direct progress in my dissertation. One day I hope to be able to create more freely, and be funded to do so, but for now I must work mostly within the confines of academic research. All of these features are important to one day creating an open GridTree software library, which could represent a publication, and so I prepare for that in a piecemeal fashion, in little spurts between progress that counts in the here-and-now.

That being said, my PhD work is moving forward. I’m working on taking a rejected publication, and adding to it, perhaps even splitting it into two papers. Two papers that are a necessary requirement for my degree. All the “rejected” work is by no means wasted, and is quite publishable—in the right place, at the right time.

And, after next semester, I should be done with my coursework, and be able to focus even more fully on those publications, and on my dissertation. We’re getting there!