Mesh selection performance and octrees

[fenomas]

Hi,

 

I'm rendering a scene with a few hundred separate 'chunks' of terrain, each of which contains several pieces of terrain. When constructed the naive way (one mesh for each piece of terrain), mesh selection got quite slow, so I switched to merging each chunk into a single mesh with submeshes for pieces of terrain.

 

However it would be valuable to keep everything as a separate mesh, and I figured Octrees might solve the problem. So instead of merging each chunk into one mesh, I made one OctreeBlock for each chunk and put them into a selection Octree. Since this means the same number of items to select from, naively one might expect performance to be similar. But after coding it all up, mesh selection (as reported in the debugLayer) was roughly twice as slow as when using submeshes.

 

Is it to be expected that selecting submeshes is much faster than selecting in an octree, or am I misunderstanding something?

 

 

(Side note: when testing my Octree scene I noticed that the debugLayer reported "active vertices" as being much larger than "total vertices". Bug in the debug layer maybe?)

 

[GameMonetize]

If there is no octree on a mesh (mesh.createOrUpdateSubmeshesOctree(capacity, maxDepth)) then there is no selection: ALL submeshes are checked against the frustrum

 

Mesh selection is the process of finding visible meshes (or submeshes). You can put a breakpoint there:

https://github.com/BabylonJS/Babylon.js/blob/master/Babylon/babylon.scene.ts#L1181

 

This will allow you to see if the octree is optimal (meaning how many meshes will be tested against the frustrum AFTER using the octree).

 

Octrees start to be optimal when there is more than 256 meshes (and this is an bold approximation, because it really depends on the computer used)

 

 

For your side note, this is expected has active vertices is the number of vertices on the scene whereas total vertices is the number of vertices used by the GPU (so number of facesx3)

[fenomas]

If there is no octree on a mesh (mesh.createOrUpdateSubmeshesOctree(capacity, maxDepth)) then there is no selection: ALL submeshes are checked against the frustrum

 

Err.. maybe I'm loopy. I thought "selection" was when something gets checked against the frustrum. I.e., if I define scene._selectionOctree to be an octree with one block, then that block's bounding volume would get checked against the frustum, and if it overlaps then all meshes in that block would be visible (without further checks). Is that not what's going on?

 

(To be clear, the case I'm asking about being slow does not use any submeshes. Although I'm surprised there too - I assumed that if a mesh has submeshes (but no octree), then whenever the mesh's bounding volume is inside the frustum all its submeshes would be assumed to be visible without checks. You're saying it checks the mesh's bounding volume and then checks all the submesh bounding volumes too?)

[fenomas]

For your side note, this is expected has active vertices is the number of vertices on the scene whereas total vertices is the number of vertices used by the GPU (so number of facesx3)

 

If "total vertices" is the number of vertices on the GPU, it should not go up and down just because the camera moves around, right? That's what I'm seeing when I use octrees.

[GameMonetize]

it *should* go up and down because it is the number of vertices SENT to the GPU for the rendering and not the number of vertices in GPU memory

[fenomas]

Okay, got it. And octrees/selection?

[GameMonetize]

What do you mean?

[fenomas]

I was wondering about the questions in the third post.

[fenomas]

Hurm. Well, after more source diving, I guess what I wasn't understanding was that octree checks only exclude meshes from being rendered - if the octree check returns true, then all meshes in the octree later get checked individually.

 

Is that correct? If so, what's the benefit of the second check? I thought the point of having an octree was to avoid checking each mesh individually?

[GameMonetize]

So

 

 

Err.. maybe I'm loopy. I thought "selection" was when something gets checked against the frustrum. I.e., if I define scene._selectionOctree to be an octree with one block, then that block's bounding volume would get checked against the frustum, and if it overlaps then all meshes in that block would be visible (without further checks). Is that not what's going on?

All meshes will then be checked individually against the frustum

 

 

 

Hurm. Well, after more source diving, I guess what I wasn't understanding was that octree checks only exclude meshes from being rendered - if the octree check returns true, then all meshes in the octree later get checked individually.

This is correct. The goal of the octree is to reduce the number of meshes to check. This is why an octree is useful when there is a lot of meshes

[fenomas]

Ok. So in general, visible mesh selection is always O(n) then?

 

I had thought that the point of octrees was to select visible meshes in O(log n)... perhaps I need to override _evaluateActiveMeshes or something.

[GameMonetize]

Yes or we can also think about a boolean on the scene to disable per mesh testing (But we need to figure out if this is really better)

[AussieKSU]

Fenomas,

A solution that I've been using for mesh selection is to use a single mesh, but keep a "dictionary" of vertex ranges to your separate objects as they exist in the merged mega mesh. This way, when a selection occurs, you can derive from the face in the selection information to which object the selection occurred. 

This allows me to reap the good performance of limited GPU pushes with a low amount of meshes in the scene, while supporting "single" mesh selection as well. 

I've gone so far as to support "highlighting" of parts of the mega mesh. This involves pulling out the verteces (normals, positions, uvs) from the mega mesh, and inserting them into a different mesh with the desired "selection" material.

There is a happy medium with the size of the mega mesh (with respect to vertex count), and the performance you want to achieve with the selection operation. The smaller the mega mesh, the better selection performance you will see, but the price will then be paid with a larger number of meshes in the scene (as you'll need to break up into smaller mega meshes).