Ideas to manage and clip very large trees (e.g. 100k+ nodes)

[nem0]

I made a simple tree view clipper for large trees, it can be found here https://gist.github.com/nem0/aa343f1c061db651569b5f68900ad63b

It has some downsides, mentioned in the gist.

• while static, performance is perfect and does not depend on number of root nodes
• dynamic (scrolling, collapsing, exapanding), performance is as bad as no clipping
• it only handles root nodes complexity, if there is a node with a lot of children, you are out of luck

[ocornut]

Another idea I recently stumbled upon is the following:

• If we consider the constraint that on any given tree level with "many nodes" (threshold up to app/user, e.g. may be 500) the user is only allowed to open one node at that specific level (aka sibling are automatically closed), then it becomes easier to implement a clipper by doing a little bit of bookkeeping. The constraint doesn't need to apply on level with a smaller number of nodes. And if you think about it it's a fairly reasonable and acceptable constraint since on a very large tree it is difficult to meaningfully open and view multiple siblings at e.g. root level. I'll try to toy with a proof of concept of this idea.

Some other thoughts:

• If your tree nodes have many decorations and extra calls, it is generally beneficial to handle coarse clipping e.g. IsRectVisible() before submitting the multiple-calls per node. I don't think this technique will get you nicely enough to "100k+ nodes" types of trees, but for smaller amount of nodes it is an easy way to reduce cost.

• Using OSX Finder style "one column per level, make new column visible and horizontally scroll then new levels are opened" is a way to completely bypass this problem. With this layout using a clipper becomes trivial. This is essentially a stricter variation of the first idea in my post.