Hey guys,

I've added every vertex of my terrain mesh into an octree so I can quickly pick which vertices are around me while moving. Issue is it's insanely laggy and I'm not sure why. There are tons of octree examples where it improves performance.

My project is in Three.js, I'm using threeoctree library provided by the developer. BufferGeometry doesn't have an array of vertices so I build it from the positions.

var vertices = Array();
            for(var i = 0; i < 100309; i++) {
                var vertex = new THREE.Vector3();
                vertex.x = node.geometry.getAttribute("position").array[(i*3)]*that.world_scale;
                vertex.y = node.geometry.getAttribute("position").array[(i*3)+1]*that.world_scale;
                vertex.z = node.geometry.getAttribute("position").array[(i*3)+2]*that.world_scale;
                vertices.push(vertex);
            }

            console.log(vertices);
            node.geometry.addAttribute( 'color', new THREE.BufferAttribute( colors, 3,true) );

            node.geometry.vertices = vertices;

            that.octree.add(node,{useVertices:true});

I feel like 100k vertices in an octree shouldn't be causing that much of an issue, after adding the vertices into the octree and updating the octree in the loop Im hovering at about 20fps. I have an i7-8700k and GTX1080. I don't think this should be lagging.

Should I be using an octree library that ignores the mesh/rendering completely?

Thanks

Not familiar with JavaScript, but if this were C++ this is where I see bottlenecks.

You are creating and allocating memory on the heap inside of a loop (100308 times).  You are using a string to look something up three times (three string compares 100308 times).  You are multiplying a scalar every time (does that.world_scale change a lot?). You are pushing the vertex object into an Array() - not sure with JavaScript, but there could be additional copy and allocations as the Array grows. After the loop you then make a copy of the Array to node.geometry.vertices - this too could be an additional allocation.  Memory stuff is slow, string compares are slower.  You may want to try a Structure of Arrays instead of Arrays of Structures to avoid CPU cache misses. https://en.wikipedia.org/wiki/AoS_and_SoA

6 minutes ago, ThorMalleuson said:

Not familiar with JavaScript, but if this were C++ this is where I see bottlenecks.

You are creating and allocating memory on the heap inside of a loop (100308 times).  You are using a string to look something up three times (three string compares 100308 times).  You are multiplying a scalar every time (does that.world_scale change a lot?). You are pushing the vertex object into an Array() - not sure with JavaScript, but there could be additional copy and allocations as the Array grows. After the loop you then make a copy of the Array to node.geometry.vertices - this too could be an additional allocation.  Memory stuff is slow, string compares are slower.  You may want to try a Structure of Arrays instead of Arrays of Structures to avoid CPU cache misses. https://en.wikipedia.org/wiki/AoS_and_SoA

 

This is like the "initializing" of my terrain, it all only happens once and it happens in less than a second. The world_scale never changes. Its just to scale the world so the positions aren't between 0,1 ( way too small ). I actually haven't look at how much memory it's using but I'm not sure thats the issue considering removing the octree.update in my render loop stops the lag. 

I will definitely keep the memory in mind though. I don't want that to be a later issue.

Thanks

Ok.  For the scaling then, multiply the vertices by the scale at initialization time, that will save you 300,924 multiplications every update too.

Thanks for the replies everyone.

I ended up just making my own octree library. Speed issue is resolved.

You got it.  Just as you posted I was reading this blog post that you may be interested in (it is C#, but may also hold true for JavaScript).

https://jacksondunstan.com/articles/3860