Best practices for octree-optimized collision detection

Questions
1

I want to use octree to optimize the collision detection of roaming space, now there are three problems

  1. Whether the space division is for the whole scene or the mesh for collision detection, I think it is the whole scene, but the api provided by babylon is createOrUpdateSubmeshesOctree

  2. How to visualize the space structure after division, is it correct for me to use the following code?

if (mesh for collison) {
        mesh.checkCollisions = true;
        mesh.isVisible = false;
        mesh.useOctreeForCollisions = true;
        if (mesh instanceof Mesh) {
          mesh.subdivide(80);
          const octree = mesh.createOrUpdateSubmeshesOctree(64, 2);

          octree.blocks.forEach(oc => {
          const { minPoint, maxPoint } = oc;

          let parent = new Mesh("parent", this.world.scene);
          parent.setBoundingInfo(new BoundingInfo(minPoint, maxPoint));
          parent.showBoundingBox = true;
          oc.entries.forEach(en => {
           const { maximum, minimum } = en.getBoundingInfo().boundingBox;
           let subParent = new Mesh("en-parent", this.world.scene);
           subParent.setBoundingInfo(new BoundingInfo(minimum, maximum));
           subParent.showBoundingBox = true;
           })
         })
        }
      }
  1. Suggestions on the value of capacity and maxDepth, how to achieve the optimal effect?
2

You can do both, as shown in the doc you linked. The scene partition is used for mesh selection (ie. for frustum culling), and you can also create an octree at the mesh level to speed up mesh collision / picking.

You visualize the bounding box of the submeshes, not the blocks of the octree. Also, your code should be recursive. Here’s what I came up with:

It will depend on your meshes, I guess, and the trade-off between perf and memory.

For eg, in my PG above, I put a quite low level for capacity (8) so that the tree subdivides at lest 4 times.

Capacity=8, depth = 4:
image

Capacity=32, depth = 4:
image
Note that using depth=2 will produce the same result, because each block at level 1 contains less than 32 submeshes, so there’s no need to subdivide more.

If the tree is not subdivided enough, the system will hold more sub-meshes at each block, which means it will spend more time checking each sub-mesh for collision. If the tree is more subdivided, the system will spend more time traversing the tree, but since there will be fewer sub-meshes in each block, it will spend less time checking for collisions. The assumption here is that traversing the tree is much faster than checking for collisions.

2 Likes
3

Thank you very much for your reply, it is very inspiring to me, and the playground code corrected my mistake. Based on this, I still have some questions to explore,

  1. For question 1, in terms of collision detection, will subdividing only one of the scene or mesh affect the efficiency?

  2. When performing collision detection between a moving object and a stationary object in the scene, is it necessary to divide the space of the moving object? Inside the babylon, how does the moving object determine the current part of the space that needs to be detected when it moves using moveWithCollisions? I’m more confused about this

4

The scene-level octree is used for frustum culling, not for collision detection. You should use mesh-level octrees to speed up collision detection.

Regarding point 2/, octrees only work if the object you are testing collisions against is static: the octree is created in the world coordinate system, if you move the object after its creation, the octree will not fit it anymore:

You can see that the octree is displayed at the position of the sphere (origin of the coordinate system) when the octree was created, not where the sphere actually is.

In this PG, if you move the sphere itself, it will work (uncomment line 84), because the collision system will test all the other objects in the scene with the sphere, and the octree of the sphere will not be used: in this case, we check the ellipsoid of the sphere with the other object geometries.

But in the opposite case (uncomment line 85 instead of 84), if you move the box, the system will check the ellipsoid of the box with the sphere, and since the sphere uses an octree for collision, it will use it. But the octree was created when the sphere was at the origin, so the collision detection will fail and the box will pass through the sphere.

5

Cool! Benefit a lot! Thanks a million！