Updated COctreeSceneNode class for Irrlicht 1.7.3

You are an experienced programmer and have a problem with the engine, shaders, or advanced effects? Here you'll get answers.
No questions about C++ programming or topics which are answered in the tutorials!
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

This change reduces memory allocations afterwards from 2.4GB to 1.2GB and everything works well after cycle testing during hours.
I also free the keeptriangles using clear after the memcpy to protect system memory from running out on big meshes.
The mesh alone used in testing takes 380 MB.
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

Yeah, the set_used will create the memory again. It kinda does something similar like the change I proposed would have done. Except you add a few more re-allocations, but as long as it's not costing you too much time when creating the octree it will be fine.

You don't need the KeepTriangles.clear() by the way - it won't make a difference.
edit: yeah - might reduce intermediate memory usage somewhat - just no difference in the endresult.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

So how would you do it, with greater efficiency?
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

With the line of code I posted earlier. That will only resize the array once at the end.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

Reallocate it first, then memcpy, that's what my code does.
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

The difference is that my code can be at the end of the function. And only be called once.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

But the array becomes massive consuming more memory than needed, and for large meshes even exhausting all available memory.
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

Also reallocate copies all the old and redundant data very inefficiently, whereas clear and set are much faster.

Look at reallocate:


//! Reallocates the array, make it bigger or smaller.
/** \param new_size New size of array. */
00063 void reallocate(u32 new_size)
{
T* old_data = data;

data = allocator.allocate(new_size); //new T[new_size];
allocated = new_size;

// copy old data
s32 end = used < new_size ? used : new_size;

for (s32 i=0; i<end; ++i)
{
// data = old_data;
allocator.construct(&data, old_data);
}

// destruct old data
for (u32 j=0; j<used; ++j)
allocator.destruct(&old_data[j]);

if (allocated < used)
used = allocated;

allocator.deallocate(old_data); //delete [] old_data;
}
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

reallocate shouldn't be slower (and it would only be called once instead of 8 times).
Memory inside constructOctree will indeed get larger in between when it only cleans up at the end instead of after creating each node. Only end-result would be the same.

Anyway - best solution regarding memory - and avoiding all re-allocation for triangles would be to rewrite it to work with a single array. And all nodes just have range-indices into that array. Wouldn't even be that hard to write. Basically needs a sort function returning numbers for the octet they are in (like 0 for hitting several and 1-8 for some of the others). And that recursively again. But as usual the real work here is not in writing the code but in testing (aka - figuring out test-cases that give realistic speed-comparisons for real situations - and mainly of interest is certainly getTriangles speed and not creation and that might change, thought without profiling I wouldn't even guess if the effect would be positive or negative as there are arguments for both).
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

Fine if your meshes are small.

Why create another triangle buffer at all, the indices could index directly into the smesh buffers, just add a word in the indices array to indicate sub buffer.
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

Hm, can't avoid the copy as you need the sorting. One could use sorted indices, but I guess you wouldn't really save much that way.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

In the copy in iarray, can't parallel_for be used if the array is larger than a few hundred elements, get those other core working?
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

Different topic really :-)
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
robmar
Posts: 1125
Joined: Sun Aug 14, 2011 11:30 pm

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by robmar »

Of course, just an idea, as would be an easy boost to employ
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Updated COctreeSceneNode class for Irrlicht 1.7.3

Post by CuteAlien »

Did you ever try if that's really faster? And by try I mean - did you measure it? I didn't so far (I'm not really interested that much in compiler specific stuff usually as that kind of libs tend to get replaced with cross-platform libs). Given how good processors are in processing vectors my first guess would be that this is one of the cases where things would be somewhat tricky to improve easily by processing it parallel. But my knowledge of how multiple cores access shared memory and how caches are handled in that case is somewhat shallow. Guess I should read up on things like hyperthreading some day.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Post Reply