Optimize mesh partitions for picking and selections

Questions
1

Hi, I’m working on a project that needes improved performance when picking a certain area of the mesh and then selecting some surrounding vertices.

I’ve got a boost of performance adding subdivisions and octree to the mesh with model.subdivide() and mesh.createOrUpdateSubmeshesOctree(), and then using BABYLON.BoundingBox.IntersectsSphere with the submeshes bounding box.

But as the meshes I need to work on have a very high polygon count, this is still not quite efficient with the mesh partition that the “subdivide” function provides, because it’s based in a “vertex start” index and a vertex count (so, one after another) and not a user provided vertex list.

I’ve been trying to make partitions of the mesh with mesh.updateFacetData() and it does the grid-like partitions I was looking for, but I don’t know how to get these groups of faces/vertices into submeshes so I can put them into the octree in a performant way. Is this possible in some way within Babylon?

Here you have a small playground I’ve built with the left sphere showing the vertices in the submeshes and the right one showing the vertices in the facet partitions. I think it will be faster to loop through the vertices in the partitions than in the subdivisions when you need to check for vertices at a certain distance from a picked point (from scene.pick() for example), as the areas are smaller:

https://playground.babylonjs.com/#UXHPXC#1

Maybe is there some way to get the bounding boxes of the partitions in the right sphere to do the intersection checks? And them into the octree for speeding up the picking?

Thanks in advance!

2

Hi @Danim and welcome from me. Interesting problem. As far as I know there are no built in solutions. The following are just some wild thoughts that may be useful (or not)

Digest a mesh with SPS

https://playground.babylonjs.com/#UXHPXC#2

Create own bounding box data for each facet.

Deconstruct mesh into individual meshes Deconstruct Mesh - Babylon.js Documentation find bounding box data for each mesh. From this create partition as needed to spply to original mesh

  1. Form graph of vertices so that adjacent ones to a given vertex are known as in https://www.babylonjs-playground.com/#7YCXAI#1

  2. As 4 but using facetPosition from facetData rather than vertices

3 Likes
3

Thanks @JohnK for your suggestions. I think I’ll try to create bounding boxes for each face group and use them for checking the intersections.
The deconstruction of the mesh you mention may also be interesting to get smaller pieces and then add them to the scene octree for optimizing picking/selections (not sure if this is possible, but I’ll give it a try, as any increase in fps will be very welcome).

4

I’ve been working on this topic, but I’ve come to a new issue while trying to create bounding boxes for each partition. It seems that some partitions from mesh.getFacetLocalPartitioning() have facet indexes that are in opposite parts of the mesh.

I’ve created this playground to show the issue, painting certain partitions that have a minimum number of vertices:
https://playground.babylonjs.com/#UXHPXC#3

You can see that there are facets on the top and bottom of the sphere that are included in the same partition, and I think they should be in different ones (because then a custom created bounding box of that partition is as high as the whole mesh).

Is this maybe a bug? Or how can I get the correct partitions?

Thanks,
Daniel

5

We need @jerome’s help with this.

1 Like
6

@Danim it appears that @Jerome is not available at the moment.

Sorry I haven’t solved the problem. However here is a PG that gives more detail. It puts mini spheres in each facet for each block it is in

https://playground.babylonjs.com/#UXHPXC#5

So you can see that blocks share facets as you would expect since a partition ‘boundary’ could slice through a facet.

You can see that the smaller the partitions the less overlap (line 33)

https://playground.babylonjs.com/#UXHPXC#6

Still not sure what’s happening at the poles.

1 Like
7

Sorry
I’m not that available at this time. I’ll have a look later :slight_smile:

1 Like