Select Box optimization (Select Box/Select Cube/VertexData)

Hi all!

In this demo, I can change the color of the vertices by selecting them with a Select Box.

Everything works well except for the speed.

If you look at the pickAllArea function you will see that the scene is picking in turn on all xy coordinates of the Select Box. Because of this, everything takes a very long time.

How can this be optimized other than increasing x and y by the number n in the pickAllArea function
(Example: for (let x = tlx; x < brx; x+=n) ?

Or maybe there is another way that excludes the use of scene.pick?

the fastest would be to go through list of meshes,

  1. check if their bounding info are at least partially in the select area (if not discard the mesh)
    This can probably be done with unproject of the 8 corners of the bounding box
  2. for the one intersecting.
    If all coners are in select all vertices
    If not you will either need to unproject all vertices to know or use some kind of subdivisions of the space like octree.
1 Like

Okay thank you. I don’t know very well how to properly work with Unproject and Octree. Could you describe it in more detail?

So it would be project and not unproject: Scene 3d position to canvas 2d position

And octree, I do not know if you can use our builtin for it but it was more about the concept of subdividing space into smaller bounding areas to limit the amount of project you are doing.

1 Like

Is there any example of this? I mean Octree

Optimizing With Octrees | Babylon.js Documentation but you could try without first and see how this fits your needs.

1 Like

I have one big mesh with thousands of vertices. I see Octree being used for a lot of meshes. Most likely this will not suit me, because. i use one big mesh. The playground shows how to paint vertices with scene.pick. Can I somehow optimize or write my own analogue of this function? After digging through the code, I found this and did not understand how scene.pick works. Maybe if i use scene.pickWithRay it will be faster

I found this to be an interesting problem, so here is my solution:

This works by:

  • generating a frustum in world space (by projecting the selected rectangle) that runs from the near camera plane to the far camera plane
  • finding the meshes that intersect the frustum
  • for each mesh, it loops over all the vertices and checks if the vertex is inside the frustum to color it in red.

In the code, (va0, va1, va2, va3) are the points of the frustum that are on the near plane, and (vb0, vb1, vb2, vb3) the points on the far plane.

It then generates the frustum planes (in world space) in frustumPlanes.

To speed up the check that a vertex is in the frustum, we transform the frustum planes in the local space of the mesh only once (transfFrustumPlanes), instead of transforming each vertex in the world space.

markVertexes can operate in two modes:

  • fast mode (checkFaces==false). In this mode, each vertex is tested against the frustum. This means that vertices that relate to the back faces will also be colored red if they are inside the frustum.
  • Precise mode (checkFaces==true). In this mode, we loop over the faces instead of the vertices and check whether the face is a front or back face by projecting the 3 vertices and doing a cross product between the two projected edges. We do not check the vertices with respect to the frustum if the face is a back face, so only the “front” vertices will be colored in red. You could speed up this case by projecting the vertices once before the loop instead of projecting them inside the loop (which means that vertices that are shared by several faces will be projected several times).

Note: type doit() in the browser console to switch between the select mode / move camera mode


Nice !!!

The octree trick is still there if you happen to have way too many meshes @Nawar

1 Like

Wow! Brilliantly! This is 100% exactly what I need!

@Evgeni_Popov @sebavan Thanks guys!