Updated COctreeSceneNode class for Irrlicht 1.7.3

[CuteAlien]

It's not 8 groups - it's recursive each group can have another 8 groups etc.
And probably using internally arrays - which usually do not allocate exact numbers but over-allocate to avoid re-allocations.

[CuteAlien]

Btw, don't confuse COctreeSceneNode with octree triangle selectors. COctreeSceneNode is about speeding up rendering and you need to have very specific scenes for this to ever be faster than just marking a mesh as static. If you are not careful when to use that one it will make worst case situations (like when you have scenes where everything is visible at some point) even slower. It probably is mostly useful for scenes where the scene is noticably larger than the far-plane. Octree triangle selectors on the other hand will nearly always speed up collisions a lot (because collision areas tend to involve only a small fraction of a whole scene). My patch mentioned earlier where I tried to merge those - was basically a bad idea because I didn't really think through the stuff enough. In my game I no longer use my patch.

[robmar]

I have that clear, but what I'm uncertain about is the selector, because for a mesh that has 6 million primitives, it is using a triangle array that is consuming about 2 gigabytes of memory. The coctetnode is 80 bytes in size, with one for each primitive, and the buffer of kept triangles during a hit. The mesh takes 600MB which makes sense given 56 bytes for a cvector3df, but why is the triangle selector so vast?

[CuteAlien]

Likely the problem I mentioned above - lots of small arrays. Each one over-allocating memory.
I guess to have this optmized for memory it would have to be rewritten. Like using a single array for all triangles and the octree-nodes working with ranges into that array (which means the array will have to be sorted but never re-allocated). edit: Which might be impossible - I guess triangles can be in several octree nodes.

[robmar]

I saw in iarray.h it adds 30 bytes or something extra for each allocation, but didn't imagine that there wasn't a method to tighten that down for each of the triangle allocations. With 440,000 triangles, any excess padding would hurt!

[robmar]

I'd thought octree just split the mesh into octants, so just check which octant using it's bounding box, then check the triangles. Is the current method faster than that method would be?

[CuteAlien]

Quadrants would be quadtree, thought that's using the same principle as octree, just in 2D. And it does that split in the first step. But then it goes over each octant (or quadrant for quadtree) and if there are still lots of nodes in there (more than minimalPolysPerNode parameter in Irrlicht) it splits that octant/quadtrant again into 8 (octree) or 4 (quadtree) parts. And so on - recusively. The idea is that you have in the end small arrays to search for a triangle and reach those arrays with just a few checks.

But I also didn't think correct above - because a triangle can never be in more than one node. If it would touch more than one quadrant/octant it will just keep the triangle in the parent-node (I thought it would put them into all child-nodes it touches, but that's certainly not the case). So in theory the memory could be optimized by having a single sorted array and all nodes just using range-indices into that array. That would be adding one more indirection so maybe slower at runtime (likely very marginally). I guess creating it that way might be somewhat faster (more copying stuff around, but no memory allocations).

[robmar]

Sorry, I meant octants, and yes, each triangle should be only in one node specified for it's bounding box.
This seems, sorry, a bit of a disaster, a fairly simple mesh with 12,522 triangles, like the little dragon, ends up with a whopping 395 nodes!
Its looking like it really needs memory optimising, also seems that keeptriangles.setused(0) doesn't delete the previous entries, could it be?
I'd like to replace the recursive call which seems unnecessary, and just include the next iteration in an outer loop.

[robmar]

Bingo! That was a massive memory leak in constructOctree, the use of memcpy to nodes->Triangles then after using .set_used(0) doesn't free the memory.

On my big model, it's causing 1.2GB excess memory.

[CuteAlien]

keepTriangles is just a local variable - it will be cleaned when the function ends. Releasing the memory already in the loop would just slow things down as it would then allocate/release it 8 times per node instead of once. But that's not where the memory is lost.

The problem is most likely Triangles variable(s). As there are a lot of them and each one will over-allocate. Could release that memory in the end (by re-allocating the array), thought that's usually not done because it a) costs time b) might increase memory fragmentation (thought probably not in a really bad way in this case).
You could proably work around it by adding the following line at the end of COctreeTriangleSelector::constructOctree:

Code: Select all

 
Triangles.reallocate(Triangles.size(), true);
 

I didn't try... but should probably work (could maybe be a flag somewhere...).

edit: Should problably be:

Code: Select all

 
node->Triangles.reallocate(node->Triangles.size(), true);
 

Having 400 nodes for 12000 triangles sounds fine. The point of the octree is creating many nodes so it's faster to find the triangles. And because they are hierarchical you don't have to search all 400 nodes but maybe 3-4 of them to get the involved triangles.

[robmar]

But the array is memcpied over without deallocating first, then the size is reset, but that doesn't deallocate the memory. Take a look at those array functions.

[CuteAlien]

keepTriangles is deallocated when it's going out of scope. There is no good reason to do that earlier. The set_used is not meant to deallocate memory. You want to keep that memory around until the function is done or you get lots of unnecessary allocations/deallocations.

The trickier part is node->Triangles.set_used. Which works because it's using a number which can only shrink. Looping over octets in the outer loope and over triangles in the inner one is slightly strange, not sure why those loops are not flipped. But basically each loop over octet reduces the number of triangles kept and copies those which are kept to their old place. Which never makes the node->Triangles memory smaller, so adding the line I mentioned above (with some fix I just added now) would release that memory in the end (I'd consider adding that to Irrlicht, but would need time to test how much speed that costs, how much memory it brings back - and to optimize it might need some leeway that doesn't enforce reallocations just because of tiny changes in the arrays - in other words - it's a quick hack that would likely give you your memory back now if you need that, but not the cleanest solution I can think of - which would be to rewrite it all to use single array and ranges - for a start for the triangles - but also even the octree-nodes themself could really be in an array).

[robmar]

The bug is the memcpy, it copies the triangles over existing data, that was much larger, then reduces the size variable, but this does not free the overwritten larger data. I'm not sure how two allocation of different sizes sharing the same start address can get freed later.
This results in the smaller array having the same memory address as the older, causing a large memory overhead.
Try this as it is with a large mesh, say with a million polys. Check memory allocated.
Then add a line ->Triangles.Clear for the target array before the memcpy, then check how the memory allocated drops enormously.
I'm getting 1.2 GB back and triangle hits work fine.

[CuteAlien]

As I wrote already - it's not supposed to free the memory. memcpy does not allocate memory - it just overwrites it. The set_used has nothing to do with memory allocations - it just says how much of the allocated memory is used (there is another internal variable about allocated memory).

Triangles.clear should indeed reduce memory - thought it's a slower solution than the one I told you above. Basically that way you add reallocations several times (the very thing the memcpy + set_used combination is supposed to prevent) - while with my solution you would have it only done once (and with larger meshes we talk about noticable times for allocations here, that stuff can run for seconds).

edit: Uhm, wait - no. You if you use Triangles.clear - then do _not_ use memcpy! In that case you have to copy the arrray itself! Otherwise you overwrite random memory now - as you just released the memory into which memcpy is going to write now. If this still works - it's pure luck - this is going to crash badly sooner or later in unexpected ways.

[robmar]

I do this:

Code: Select all

 
node->Triangles.clear();
node->Triangles.set-used(keepTriangles.size());
 
memcpy(... Same line
 
KeepTriangles.clear();      // Keep memory use tighter
 
If (node->Child... Same as before