Open nem0 opened 3 years ago
Another idea I recently stumbled upon is the following:
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.
Sometimes we will draw a tree to represent a scene
Most of the time ImGui::TreeNodeEx is the best way to render
But what if the scene is too large and the rendering performance drop!
Here is the code for demonstration
//A tree with 30000 leaf to draw
int nLeafNum = 30000;
ImGui::Begin("Large Tree");
if (ImGui::TreeNodeEx("Large Tree"))
{
for (int i = 0; i < nLeafNum; i++)
{
//the algorithm for rendering
//when index is a multiple of ten
//draw red as a key object
auto strLeafName = std::to_string(i);
bool bIsKey = i % 10 == 0;
ImGui::PushID(0);ImGui::PushStyleColor(ImGuiCol_Text,
bIsKey?ImVec4(1.0f, 0.0f, 0.0f, 1.0f): ImVec4(0.5f, 0.5f, 0.5f, 0.8f));
if (ImGui::TreeNodeEx(strLeafName.c_str(), ImGuiTreeNodeFlags_Leaf))
{
ImGui::TreePop();
}
ImGui::PopStyleColor(1);ImGui::PopID();
}
ImGui::TreePop();
}
ImGui::End();
It look like :
int nLeafNum = 30000;
ImGui::Begin("Large Tree Optimaize");
if (ImGui::TreeNodeEx("Large Tree"))
{
//query window and node info
ImVec2 vLastItem = ImGui::GetItemRectMax();
ImVec2 vItemSize = ImGui::GetItemRectSize();
ImVec2 vWindowPos = ImGui::GetWindowPos();
ImVec2 vWindowSize = ImGui::GetWindowSize();
//measure the number of node to draw
int nLeafStart = max(int((vWindowPos.y - vLastItem.y) / vItemSize.y), 0);
int nLeafCanDraw = min(int(vWindowSize.y / vItemSize.y), (int)nLeafNum - nLeafStart);
//blank rect for those node beyond window
if (nLeafStart > 0 && nLeafCanDraw > 0)
{
ImGui::Dummy(ImVec2(10.0f, float(nLeafStart) * vItemSize.y));
}
//all the node we could see
int nDrawLeaf = nLeafStart;
while (nDrawLeaf < nLeafCanDraw+ nLeafStart && nDrawLeaf < nLeafNum)
{
auto strLeafName = std::to_string(nDrawLeaf);
bool bIsKey = nDrawLeaf % 10 == 0;
ImGui::PushID(0); ImGui::PushStyleColor(ImGuiCol_Text, bIsKey ? ImVec4(1.0f, 0.0f, 0.0f, 1.0f) : ImVec4(0.5f, 0.5f, 0.5f, 0.8f));
if (ImGui::TreeNodeEx(strLeafName.c_str(), ImGuiTreeNodeFlags_Leaf))
{
ImGui::TreePop();
}
ImGui::PopStyleColor(1); ImGui::PopID();
nDrawLeaf++;
}
//blank rect for those node exceed window bottom
if (nDrawLeaf < nLeafNum)
{
ImGui::Dummy(ImVec2(10.0f, float(nLeafNum - nDrawLeaf) * vItemSize.y));
}
ImGui::TreePop();
}
ImGui::End();
Reposting some of the contents you posted to other thread (now deleted):
std::to_string()
contributes for more slowdown than the sum of all TreeNode()
calls! In my rough measurement about ~45 ms was TreeNode() cost and 90 ms was std::to_string()
cost. What would still be prohibitively too slow but technically three times fast. Also note that comparing FPS is very error-prone and misleading, you should always be comparing time per frame.ImGuiListClipper
to do exactly what you are doing, and it would handle slightly more edge cases, such as some peculiarities of keyboard navigation. It will work ok for tree with many nodes and few levels. TreeNodeGetOpen()
and maybe using the ImGuiListClipper in the special mode where items_count = INT_MAX
, aka "unknown until the end of iteration + call `SeekCursorForItem() after end of iteration". I am currently working a little on this problem and may post further ideas later.
As part of some research some for multi-select and demos I pushed some improvements with would facilitate some form of clipping.
(1) 8bab3ea, ImGuiListClipper
can more explicitly be used with an indeterminate items count, passing items_count=INT_MAX. This enables starting to use the clipper before knowing the items count. At the end of stepping you'll need to call clipper.SeekCursorForItem(items_count)
to adjust to items. This is useful if you want to use clipping by fast-forwarding through a non-trivial structure such as a tree.
(2) df38704: i have added a SetNextItemStorageID(ImGuiID storage_id)
. In various experiment related to tree nodes I realized it was advantageous or necessary to query the open/closed state. The problem is that ID is typically tied to the ID Stack which works with iterating the data but not as easily if you want to randomly get/set the idea as a different point in time. SetNextItemStorageID()
is a way to circumvent this issue.
(3) Attached is an experiment to implement clipper by "fast seeking forward" through a tree:
imgui-a483c5d-(WIP) Demo Property Editor with seeking tree clipper (v1).patch
imgui-1e3637c-(WIP) Demo Property Editor with seeking tree clipper (v2).patch
This is a zero-caching method. The general idea is:
// Use the clipper
// - with indeterminate count (items_count = INT_MAX, and we call SeekCursorForItem() at the end)
DrawCurrentIdx = 0;
DrawClipper.Begin(INT_MAX);
int root_n = 0;
while (DrawClipper.Step())
while (DrawCurrentIdx < DrawClipper.DisplayEnd && root_n < root_node->Childs.Size)
DrawTreeNode(root_node->Childs[root_n++]);
while (root_n < root_node->Childs.Size) // keep going to count
DrawTreeNode(root_node->Childs[root_n++]);
void DrawTreeNode(ExampleTreeNode* node)
{
// (..Filtering...)
const bool is_visible = (DrawCurrentIdx >= DrawClipper.DisplayStart && DrawCurrentIdx < DrawClipper.DisplayEnd);
DrawCurrentIdx++;
if (is_visible)
{
ImGui::SetNextItemStorageID((ImGuiID)node->UID); // use node->UID as storage id
//... various decorations
bool node_open = ImGui::TreeNodeEx(node->Name, tree_flags);
//... various decorations
if (node_open)
{
for (ExampleTreeNode* child : node->Childs)
DrawTreeNode(child);
ImGui::TreePop();
}
}
else if (node->Childs.Size > 0)
{
// Clipped
if (ImGui::GetStateStorage()->GetInt(node->UID) != 0) // are we open?
{
ImGui::TreePush(node->Name);
for (ExampleTreeNode* child : node->Childs)
DrawTreeNode(child);
ImGui::TreePop();
}
}
}
The wins comes from the fact:
ImGui::GetStateStorage()->GetInt(node->UID)
) instead of full on TreeNode()
which has more overhead.With this method, in the Property Editor tree with 18000 root items:
Again this is a zero-caching method. It's always more efficient if you can linearize your tree by creating an index, but then you need to have an event to notify of tree changes to rebuild the index. It also happens that to implement any form of non-trivial search you will want to have this index anyhow, at which point you can implement something that's much faster. This is why this is not committed in demo: I think it's nicer to bite the bullet and build the after-filter-index that a real/advanced application will use anyhow. I'll work on that.
(4) In ce3a8d7 I have pushed a demo to implement multi-select (with shift-selection, mouse drag selection) in a tree.
It's quite non trivial because of the same reason: lack of an index.
One interesting aspect of it is the helper function TreeGetNextNodeInVisibleOrder()
with gets the next sibling or child or parent in linear order and accounting for open/close state. This also uses SetNextItemStorageID()
.
It also implement a feature where when closing a close, it automatically close and unselect its child nodes, and select parent node if any child node was previously selected.
TL;DR; both (3) and (4) will be superseded by the use of an index. Working on that soon.
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.