[Fixed] COctreeTriangleSelector.cpp problems

[Squarefox]

Hi Irrlicht community,

recently I have discovered some problems in COctreeTriangleSelector.cpp .
In my project, I use very large (2.5 million triangles) meshes, for which I create those triangle selectors.
I have got some problems with memory fragmentation and memory usage in general, which I tracked down to COctreeTriangleSelector.cpp.
After analysing the code, I discovered some things in the constructOctree function.

Here is the current code (trunk):

Code: Select all

 
void COctreeTriangleSelector::constructOctree(SOctreeNode* node)
{
    ++NodeCount;
 
    node->Box.reset(node->Triangles[0].pointA);
 
    // get bounding box
    const u32 cnt = node->Triangles.size();
    for (u32 i=0; i<cnt; ++i)
    {
        node->Box.addInternalPoint(node->Triangles[i].pointA);
        node->Box.addInternalPoint(node->Triangles[i].pointB);
        node->Box.addInternalPoint(node->Triangles[i].pointC);
    }
 
    const core::vector3df& middle = node->Box.getCenter();
    core::vector3df edges[8];
    node->Box.getEdges(edges);
 
    core::aabbox3d<f32> box;
    core::array<core::triangle3df> keepTriangles;
 
    // calculate children
 
    if (!node->Box.isEmpty() && (s32)node->Triangles.size() > MinimalPolysPerNode)
    for (s32 ch=0; ch<8; ++ch)
    {
        box.reset(middle);
        box.addInternalPoint(edges[ch]);
        node->Child[ch] = new SOctreeNode();
 
        for (s32 i=0; i<(s32)node->Triangles.size(); ++i)
        {
            if (node->Triangles[i].isTotalInsideBox(box))
            {
                node->Child[ch]->Triangles.push_back(node->Triangles[i]);
                //node->Triangles.erase(i);
                //--i;
            }
            else
            {
                keepTriangles.push_back(node->Triangles[i]);
            }
        }
        memcpy(node->Triangles.pointer(), keepTriangles.pointer(),
            sizeof(core::triangle3df)*keepTriangles.size());
 
        node->Triangles.set_used(keepTriangles.size());
        keepTriangles.set_used(0);
 
        if (node->Child[ch]->Triangles.empty())
        {
            delete node->Child[ch];
            node->Child[ch] = 0;
        }
        else
            constructOctree(node->Child[ch]);
    }
}
 

The problems are:

1. memory usage
set_used does not shrink the array.
So the memory that is used for each octree node is the maximum it ever had.
This leads to a memory consumption of O(n * log n).
If the array would be shrunk, the memory consumption would be only O(n), which would be a lot better.

2. memory fragmentation
Currently child nodes are created, without finishing the parent node first.
This leads to a quite chaotic allocation order and leads to more memory fragmentation.
This can be solved by finishing the parent node first and then do the child nodes.

I suggest the following code to fix the problems.

Code: Select all

 
void COctreeTriangleSelector::constructOctree(SOctreeNode* node)
{
    ++NodeCount;
 
    node->Box.reset(node->Triangles[0].pointA);
 
    // get bounding box
    const u32 cnt = node->Triangles.size();
    for (u32 i=0; i<cnt; ++i)
    {
        node->Box.addInternalPoint(node->Triangles[i].pointA);
        node->Box.addInternalPoint(node->Triangles[i].pointB);
        node->Box.addInternalPoint(node->Triangles[i].pointC);
    }
 
    const core::vector3df& middle = node->Box.getCenter();
    core::vector3df edges[8];
    node->Box.getEdges(edges);
 
    core::aabbox3d<f32> box;
    core::array<core::triangle3df> keepTriangles;
 
    // calculate children
 
    if (!node->Box.isEmpty() && (s32)node->Triangles.size() > MinimalPolysPerNode)
    {
        for (s32 ch=0; ch<8; ++ch)
        {
            box.reset(middle);
            box.addInternalPoint(edges[ch]);
            node->Child[ch] = new SOctreeNode();
 
            for (s32 i=0; i<(s32)node->Triangles.size(); ++i)
            {
                if (node->Triangles[i].isTotalInsideBox(box))
                {
                    node->Child[ch]->Triangles.push_back(node->Triangles[i]);
                    //node->Triangles.erase(i);
                    //--i;
                }
                else
                {
                    keepTriangles.push_back(node->Triangles[i]);
                }
            }
 
            node->Triangles.swap(keepTriangles);
            keepTriangles.clear();
        }
 
        for (s32 ch=0; ch<8; ++ch)
        {
            if (node->Child[ch]->Triangles.empty())
            {
                delete node->Child[ch];
                node->Child[ch] = 0;
            }
            else
                constructOctree(node->Child[ch]);
        }
 
    }
}
 

I have tested the code in my program.
Everything works correctly and the memory usage and fragmentation is a lot better.

Kind regards,
Squarefox

[CuteAlien]

Thanks. I've applied the split of the loop to avoid memory fragmentation.

For the first part, I've changed the code somewhat. I want to have less re-allocations going on as that will slow down the creation of the octrees. It will also increase memory fragmentation. Instead I allocate now enough memory for keepTriangles once so it will never re-allocate in the loop. But keep the memcpy code instead of using swap(). Then after the loop I clear memory early for keepTriangles so it's no longer around before children are checked. And reduce the memory use of the node at that point to the exact minimum it needs.

I hope it's fine that way, would be cool if you could test it with your test-case!

[Squarefox]

Hi CuteAlien,

your changes are even better .
I tested it with my program, everything works fine.
I loaded over 30 levels (with big meshes) successively and no problems occurred.
Without the fixes, the program crashed every 4 levels or so.

Kind regards,
Squarefox

[CuteAlien]

OK, great :-)