# Javascript Octree vertices lag

## Recommended Posts

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

##### Share on other sites

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

Edited by ThorMalleuson

##### Share on other sites
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

##### Share on other sites

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

##### Share on other sites
3 hours ago, Bluntest said:

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﻿.﻿

Is this terrain mesh a regular grid, or a polygon soup? If it's a regular grid, picking which vertices are within an arbitrary area should be a trivial calculation based on the query coordinates, not something requiring an arbitrary-space, arbitrary-density search structure.

Have you actually measured how long octree.update() takes by calculating the difference in a window.performance.now() call before and after it? Are you sure that's where the slowdown happens, and not in another side-effect-related call within the same frame?

Is your code posted at the top hit by the .update() call, or is that genuinely called only once, ever? If it is oft-visited, you can cut the work done by at least a factor of five, and easily up to a factor counted in the dozens, with...

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

And for the love of pete, get that console.log() call out of there. The RAM cost alone of keeping an extra copy of that structure around in the console, independent of the copy actually in use by THREE.js...

Lastly, and I know I'm putting on my pedant pants here... "lag" is a delay between expected result and actual result, not the delay between action and result. The only way lag is the correct term here is if you already know how long the calculation should take, and you're measuring it as being longer than that by an unpredictable linear offset.

##### Share on other sites

Thanks for the replies everyone.

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

##### Share on other sites

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).

## Create an account

Register a new account

• 12
• 19
• 15
• 15
• 10