How can I properly handle a table with clipper and TreeNode inside?

[Nitr0-G]

Version/Branch of Dear ImGui:

Version: 1.89.9
Branch: master

Back-end/Renderer/Compiler/OS
Back-ends: imgui_impl_win32.cpp + imgui_impl_opengl3.cpp
Compiler: MSVC/Clang-cl
Operating System: Windows 10

My Issue/Question:
Hello to all readers!
How can I properly handle a table with clipper and TreeNode inside? When I draw a table with a clipper like in the Demo example, namely Tables & Columns -> Tree view, when using clipper, there is a problem with drawing the table, and when I don't use it, everything is rendered fine, but I need to process the table using clipper, since I have there millions of rows.

Here is an example of the usual view without opening the tree node
1)usual view with clipper
When I open the tree node, this happens:
The first case(Those last lines disappear forever and there will always be an empty rectangle in that place until Child 0 is closed. For a more vivid example, I'll scroll it down)
The second case:
When I open something at the very end, the table does not expand(i.e. i can't scroll it down) and some rows disappear from me.

When I do this without a clipper, i.e. with a given number of rows, for example 1000, in the example with a clipper there are also 1000, then everything works fine
2)usual view without clipper
When I open the tree node everything works fine:
The first case without clipper(As you can see in the implementation of the code without clipper, everything works and child 4 and the very top of child 5 are completely shown to me)
When I open something at the very end, the table can expand(i.e. i can scroll it down).

Standalone, minimal, complete and verifiable example:

void GUI::StackWindowRender()
{
    static ImGuiTableFlags flags = ImGuiTableFlags_HighlightHoveredColumn | ImGuiTableFlags_SizingFixedFit | ImGuiTableFlags_ScrollY |
        ImGuiTableFlags_RowBg | ImGuiTableFlags_Resizable | ImGuiTableFlags_Reorderable | ImGuiTableFlags_Hideable;
    if (ImGui::BeginTable("MemoryMapTable", 5, flags))
    {
        ImGui::TableSetupScrollFreeze(0, 1);
        ImGui::TableSetupColumn("Address", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("Data", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("Comment", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("MapOfUse", ImGuiTableColumnFlags_WidthStretch);
        ImGui::TableSetupColumn("##", ImGuiTableColumnFlags_Disabled);
        ImGui::TableHeadersRow();

        ImGuiListClipper clipper;//
        clipper.Begin(1000);//
        while (clipper.Step())//
        {
            for (int row = clipper.DisplayStart; row < clipper.DisplayEnd; row++)//for (int row = 0; row < 1000; row++)
            {
                ImGui::TableNextRow();
                for (int column = 0; column < 5; column++)
                {
                    if (column < 3)
                    {
                        if (ImGui::IsItemHovered())
                        {
                            for (int column_ = 0; column_ < 5; ++column_)
                            {
                                ImGui::TableSetColumnIndex(column_);
                                ImGui::TableSetBgColor(ImGuiTableBgTarget_CellBg, 0x8f8f8f8f, column_);
                            }
                        }
                        ImGui::TableSetColumnIndex(column);
                        ImGui::PushStyleColor(ImGuiCol_HeaderActive, ImVec4{ 0.56,0.56,0.56,0.56 });
                        ImGui::PushStyleColor(ImGuiCol_HeaderHovered, ImVec4{ 0.56,0.56,0.56,0.56 });
                        ImGui::Selectable("56456456456", false);
                        ImGui::PopStyleColor(2);
                    }
                    else
                    {
                        ImGui::TableSetColumnIndex(column);

                        std::string treeNodeId = "Child" + std::to_string(row);
                        if (ImGui::TreeNodeEx(treeNodeId.c_str(), ImGuiTreeNodeFlags_SpanFullWidth | ImGuiTreeNodeFlags_SpanAvailWidth))
                        {
                            ImGui::Text("blah blah");
                            ImGui::TreePop();
                        }
                    }
                }
            }
        }
        ImGui::EndTable();
    }
}

[ocornut]

It’s not a simple problem to solve. Typically you would need to linearize your tree data, aka store a data structure to convert row to tree node. It’s the kind of code that’s natural put in place if you already have some generalized filtering/search system creating a need to create that indirection in order to get linear random access into the filtered set.

See #3823 and issues marked with the ‘Clipper’ label.

[GamingMinds-DanielC]

To add a little more information as to what is happening and why those problems occur...

The list clipper needs to assume that every row has the same height, that is required to be the case so that it can calculate the total height based on the number of rows, scroll position and row indices. You can specify the height explicitly, if you don't the clipper asks for row 0 and calculates the height based on the submitted items for your convenience.

When you don't specify the row height and submit the very first one expanded (more rows), the clipper then measures the height of both rows, thinks that this is the height of a single row (since that is what you submitted when it asked for row 0 only) and calculated which rows would be visible based on that height. That is why you loose the last few rows, there is empty space because of your rows being smaller than row 0. Without an explicit height, the clipper always requests row 0 as a reference even when it will not be visible, so that happens even when you scroll down after expanding it.

As for the items lost at the end, that is because of the same reason. If row 0 is not expanded, the later expanded rows will be higher than the reference. The total height of your rows will exceed the height calculated by the clipper, so everything beyond that height will be clipped away. After all, the clipper sets up scrolling based on height, not based on actual items it has no real knowledge about.

Because of this, you need to linearize like Omar said. Keep track of additional rows created by expanding items and submit them as individual rows, each of identical height.

Something important to note since you said you have millions of rows: be very aware of float precision. Once your total height exceeds 16777216 pixels, single precision floating point values will no be precise enough to hold odd values anymore. That will mess up calculations (like measuring the row 0 height) and giving an explicit item height is a must, even with linearized lists. And this will happen already with 1 million rows since they are 17 pixels each. Row 0 would be measured differently based on scroll position, so you can't rely on that.

[Nitr0-G]

To add a little more information as to what is happening and why those problems occur...

The list clipper needs to assume that every row has the same height, that is required to be the case so that it can calculate the total height based on the number of rows, scroll position and row indices. You can specify the height explicitly, if you don't the clipper asks for row 0 and calculates the height based on the submitted items for your convenience.

When you don't specify the row height and submit the very first one expanded (more rows), the clipper then measures the height of both rows, thinks that this is the height of a single row (since that is what you submitted when it asked for row 0 only) and calculated which rows would be visible based on that height. That is why you loose the last few rows, there is empty space because of your rows being smaller than row 0. Without an explicit height, the clipper always requests row 0 as a reference even when it will not be visible, so that happens even when you scroll down after expanding it.

As for the items lost at the end, that is because of the same reason. If row 0 is not expanded, the later expanded rows will be higher than the reference. The total height of your rows will exceed the height calculated by the clipper, so everything beyond that height will be clipped away. After all, the clipper sets up scrolling based on height, not based on actual items it has no real knowledge about.

Because of this, you need to linearize like Omar said. Keep track of additional rows created by expanding items and submit them as individual rows, each of identical height.

Something important to note since you said you have millions of rows: be very aware of float precision. Once your total height exceeds 16777216 pixels, single precision floating point values will no be precise enough to hold odd values anymore. That will mess up calculations (like measuring the row 0 height) and giving an explicit item height is a must, even with linearized lists. And this will happen already with 1 million rows since they are 17 pixels each. Row 0 would be measured differently based on scroll position, so you can't rely on that.

Thanks a lot for the detailed explanation!!!
I seem to have solved this problem, but then another one arose:
For some reason, after adding rows at the end of the table, it does not expand and I just lose some rows.


Without a clipper, such a problem does not arise and I think this is due to the fact that I have an unknown end and the total number of rows and they disappear from me because of this.

My current code:

void GUI::StackWindowRender()
{
    static ImGuiTableFlags flags = ImGuiTableFlags_HighlightHoveredColumn | ImGuiTableFlags_SizingFixedFit | ImGuiTableFlags_ScrollY |
        ImGuiTableFlags_RowBg | ImGuiTableFlags_Resizable | ImGuiTableFlags_Reorderable | ImGuiTableFlags_Hideable;
    if (ImGui::BeginTable("MemoryMapTable", 5, flags))
    {
        ImGui::TableSetupScrollFreeze(0, 1);
        ImGui::TableSetupColumn("Address", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("Data", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("Comment", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("MapOfUse", ImGuiTableColumnFlags_WidthStretch);
        ImGui::TableSetupColumn("##", ImGuiTableColumnFlags_Disabled);
        ImGui::TableHeadersRow();

        uint64_t ItemCount = 2'000;
        ImGuiListClipper clipper;//
        clipper.Begin(2'000, 17);//
        while (clipper.Step())//
        {
            for (int row = clipper.DisplayStart; row < clipper.DisplayEnd; row++)//for (int row = 0; row < 2'000; row++)
            {
                ImGui::TableNextRow(ImGuiTableRowFlags_None, 17);
                for (int column = 0; column < 5; column++)
                {
                    if (column < 3)
                    {
                        if (ImGui::IsItemHovered())
                        {
                            for (int column_ = 0; column_ < 5; ++column_)
                            {
                                ImGui::TableSetColumnIndex(column_);
                                ImGui::TableSetBgColor(ImGuiTableBgTarget_CellBg, 0x8f8f8f8f, column_);
                            }
                        }
                        ImGui::TableSetColumnIndex(column);
                        ImGui::PushStyleColor(ImGuiCol_HeaderActive, ImVec4{ 0.56,0.56,0.56,0.56 });
                        ImGui::PushStyleColor(ImGuiCol_HeaderHovered, ImVec4{ 0.56,0.56,0.56,0.56 });
                        ImGui::Selectable("56456456456", false);
                        ImGui::PopStyleColor(2);
                        if (ImGui::IsItemHovered())
                        {
                            if (ImGui::IsMouseReleased(ImGuiMouseButton_::ImGuiMouseButton_Left))
                            {
                                std::cout << "ImGuiMouseButton.LeftSingle | Index of table is " << ImGui::TableGetColumnIndex() << " and index of row is " << ImGui::TableGetRowIndex() << std::endl;
                            }
                            else if (ImGui::IsMouseReleased(ImGuiMouseButton_::ImGuiMouseButton_Right))
                            {
                                std::cout << "ImGuiMouseButton.RightSingle | Index of table is " << ImGui::TableGetColumnIndex() << " and index of row is " << ImGui::TableGetRowIndex() << std::endl;
                            }
                        }
                    }
                    else
                    {
                        ImGui::TableSetColumnIndex(column);
                        const std::string treeNodeId = "Child" + std::to_string(row);
                        ImGui::PushStyleVar(ImGuiStyleVar_IndentSpacing, 0.0f);
                        const int numItemsToAdd = 2;                     
                        if (ImGui::TreeNodeEx(treeNodeId.c_str(), ImGuiTreeNodeFlags_SpanFullWidth | ImGuiTreeNodeFlags_SpanAvailWidth))
                        {
                            for (int i = 0; i < numItemsToAdd; i++)
                            {
                                ImGui::TableNextRow(ImGuiTableRowFlags_None, 17);
                                for (int subColumn = 0; subColumn < 3; subColumn++)
                                {
                                    ImGui::TableSetColumnIndex(subColumn);
                                    ImGui::Selectable("blah blah", false);
                                }
                            }
                            ImGui::TreePop();
                        }
                        ImGui::PopStyleVar();
                    }
                }
            }
        }
        ImGui::EndTable();
    }
}

[GamingMinds-DanielC]

You are making the same mistake again. You have a tree node in a row and when it is expanded, you submit multiple rows for the one row the clipper asked for, making your "rows" a variable height. The solution is still what Omar said first: you need to linearize. If you have 2000 rows in root, one is expanded and adds 2 additional rows, you need to tell the clipper that there are now 2002 rows. And you need to index them properly. And every single row has to have the same height.

The basic approach is:

• have a structure that identifies a single row (in your case the root item index and a sub item index, -1 means root item)
• have an std::vector of that structure and a flag if it needs to be updated
• when an update is needed, clear and refill the vector with all rows you want to display, sub items push their own rows
• configure the clipper with the size of that vector
• when iterating ranges to display, remap into your data using that vector
• when the expansion state is toggled, set your flag to update the vector on the next frame

[ocornut]

It's pretty a little trickier than that because you need to account for opening during the frame.
I honestly haven't tried doing it yet so I don't know if there's a nice simple helper or idioms I could share.

[GamingMinds-DanielC]

It's pretty a little trickier than that because you need to account for opening during the frame.

Opening or closing during a frame is no problem with that approach, since the children are submitted individually in their own rows. Toggling a tree node will not change the displayed items for this frame, which is a good thing since the list clipper already has the old number of items configured, so even a rebuild of the vector on the spot wouldn't do. It would require a clipper that can have its item count updated while stepping. I don't think that the small latency reduction is worth that extra complexity. But with the single frame of latency, the update is deferred to the next frame before the clipper needs to be configured and stepped through. I think this frame of latency is totally acceptable.

[Nitr0-G]

You are making the same mistake again. You have a tree node in a row and when it is expanded, you submit multiple rows for the one row the clipper asked for, making your "rows" a variable height. The solution is still what Omar said first: you need to linearize. If you have 2000 rows in root, one is expanded and adds 2 additional rows, you need to tell the clipper that there are now 2002 rows. And you need to index them properly. And every single row has to have the same height.

The basic approach is:

* have a structure that identifies a single row (in your case the root item index and a sub item index, -1 means root item)

* have an `std::vector` of that structure and a flag if it needs to be updated

* when an update is needed, clear and refill the vector with all rows you want to display, sub items push their own rows

* configure the clipper with the size of that vector

* when iterating ranges to display, remap into your data using that vector

* when the expansion state is toggled, set your flag to update the vector on the next frame

Thanks! Thank you very much! But I had a couple of questions:
Why would I use a vector in this case?
What problem/possible bug does using a vector fix in this case?
I wrote this code.

uint64_t ItemCount = 2'000'000;
void GUI::StackWindowRender()
{
    static ImGuiTableFlags flags = ImGuiTableFlags_HighlightHoveredColumn | ImGuiTableFlags_SizingFixedFit | ImGuiTableFlags_ScrollY |
        ImGuiTableFlags_RowBg | ImGuiTableFlags_Resizable | ImGuiTableFlags_Reorderable | ImGuiTableFlags_Hideable;
    if (ImGui::BeginTable("MemoryMapTable", 5, flags))
    {
        ImGui::TableSetupScrollFreeze(0, 1);
        ImGui::TableSetupColumn("Address", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("Data", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("Comment", ImGuiTableColumnFlags_WidthFixed);
        ImGui::TableSetupColumn("MapOfUse", ImGuiTableColumnFlags_WidthStretch);
        ImGui::TableSetupColumn("##", ImGuiTableColumnFlags_Disabled);
        ImGui::TableHeadersRow();

        ImGuiListClipper clipper;
        static int SubRows = 0;
        static int lFrameCount = 0;
        clipper.Begin(ItemCount + SubRows, 17);
        while (clipper.Step())
        {
            for (int row = clipper.DisplayStart; row < clipper.DisplayEnd; row++)//for (int row = 0; row < 2'000; row++)
            {
                ImGui::TableNextRow(ImGuiTableRowFlags_None, 17);
                for (int column = 0; column < 5; column++)
                {
                    if (column < 3)
                    {
                        if (ImGui::IsItemHovered())
                        {
                            for (int column_ = 0; column_ < 5; ++column_)
                            {
                                ImGui::TableSetColumnIndex(column_);
                                ImGui::TableSetBgColor(ImGuiTableBgTarget_CellBg, 0x8f8f8f8f, column_);
                            }
                        }
                        ImGui::TableSetColumnIndex(column);
                        ImGui::PushStyleColor(ImGuiCol_HeaderActive, ImVec4{ 0.56,0.56,0.56,0.56 });
                        ImGui::PushStyleColor(ImGuiCol_HeaderHovered, ImVec4{ 0.56,0.56,0.56,0.56 });
                        ImGui::Selectable("56456456456", false);
                        ImGui::PopStyleColor(2);
                        if (ImGui::IsItemHovered())
                        {
                            if (ImGui::IsMouseReleased(ImGuiMouseButton_::ImGuiMouseButton_Left))
                            {
                                std::cout << "ImGuiMouseButton.LeftSingle | Index of table is " << ImGui::TableGetColumnIndex() << " and index of row is " << ImGui::TableGetRowIndex() << std::endl;
                            }
                            else if (ImGui::IsMouseReleased(ImGuiMouseButton_::ImGuiMouseButton_Right))
                            {
                                std::cout << "ImGuiMouseButton.RightSingle | Index of table is " << ImGui::TableGetColumnIndex() << " and index of row is " << ImGui::TableGetRowIndex() << std::endl;
                            }
                        }
                    }
                    else
                    {
                        ImGui::TableSetColumnIndex(column);
                        const std::string treeNodeId = "Child" + std::to_string(row);
                        ImGui::PushStyleVar(ImGuiStyleVar_IndentSpacing, 0.0f);
                        const int numItemsToAdd = 2;   
                        bool End = false;
                        if (clipper.DisplayEnd >= ItemCount + SubRows) { End = true; }
                        if (lFrameCount != clipper.Ctx->FrameCount)
                        {
                            SubRows = 0;
                            lFrameCount = clipper.Ctx->FrameCount;
                        }
                        if (ImGui::TreeNodeEx(treeNodeId.c_str(), ImGuiTreeNodeFlags_SpanFullWidth | ImGuiTreeNodeFlags_SpanAvailWidth))
                        {
                            for (int i = 0; i < numItemsToAdd; i++)
                            {
                                ImGui::TableNextRow(ImGuiTableRowFlags_None, 17);
                                for (int subColumn = 0; subColumn < 3; subColumn++)
                                {
                                    ImGui::TableSetColumnIndex(subColumn);
                                    ImGui::Selectable("blah blah", false);
                                }
                            }
                            if (End) { SubRows += numItemsToAdd; }
                            ImGui::TreePop();
                        }
                        ImGui::PopStyleVar();
                    }
                }
            }
        }
        ImGui::EndTable();
    }
}

So everything is fine, but if I open something on the border, for example Child1999997(The very first line under the heading MapOfUse.)

Then I get this error(I can't scroll down the screen and when I scroll down the screen, my lines start to behave too strangely)

Although they are indexed correctly by themselves, i.e. if I close Child1999998, then everything will be displayed normally and the end will be 2'000'004

If I redo it with a vector, then logically everything should turn out the same, since there will be exactly the same number of subrows as now in my implementation.

[Nitr0-G]

It's pretty a little trickier than that because you need to account for opening during the frame. I honestly haven't tried doing it yet so I don't know if there's a nice simple helper or idioms I could share.

If I still manage to do linearization without bugs, can I add it to the clipper support, as something like a flag for the clipper, which means that it processes the table in which the TreeNodes are located? I just don't want anyone to face a similar problem =)

[GamingMinds-DanielC]

Your solution doesn't work at all. Try other numbers where errors are more obvious. Let's say 100 rows only, then each expanded row adds 100 more sub rows. For sub rows, write the row and sub row index into the last column. Then you can test properly and the need for linearization with remapping (what you did is neither of those) should be obvious.