BVH Fastest way to check if contained in a box/geometry

[RenaudRohlinger]

Hello!

I was wondering what would be the fastest way to check if the geometry is colliding/contained in a box/geometry?

Right now I was doing it with this function that seems to work only with trimesh or shape more complex than a simple box:

platform.geometry.boundsTree.shapecast({
  intersectsBounds: (box) => {
    if (!hit) {
      hit = box.intersectsBox(tempBox);
    }
    return hit;
 })

But if I use this on a box geometry it will never return true.

https://codesandbox.io/s/test-contains-in-box-itrlx?file=/src/index.js:7249-7992 I made an example, if you enable "useSphere" to swap the geometry to a very low poly sphere it will work but I wonder why it does not work with a simple box geometry?

[gkjohnson]

Hello! So a threejs BoxBufferyGeometry is a unique case and it exposes a bit of an oddity to the behavior of the shapecast function, as well. Here are a couple things to note:

1. BoxBufferGeometry will be created with 6 groups -- one for each side of the geometry (2 faces per group).
2. In order to retain geometry group coherence MeshBVH will create a new BVH root for every group in a geometry. In this case that means a 6 BVH roots are created with just two faces each.
3. Due to the traversal algorithm of the shapecast function the first root bounding volume is not checked and instead the immediate two children are checked. In this case because the BVH hierarchies are so shallow there are no children bounding volumes to check so the triangles are checked immediately.

Spheres have no groups and a larger number of triangles so the above scenario does not happen. Point 3 is admittedly an odd case but in the typical scenario there will be more immediate child bounds to be checked and the intersectsBounds function would be called.

All that said can you explain how you're planning to use the shapecast function here? The intent in the design of the function is to quickly check triangle / shape intersections which requires providing a function to intersect triangles or triangle indices. I hadn't considered uses that would only provide intersectsBounds but if there's a compelling use case then I could see changing the design intent of the function. And either way it might be worth addressing point 3 above as an optimization for this kind of corner case.

I was wondering what would be the fastest way to check if the geometry is colliding/contained in a box/geometry?

The intersectsBounds function just checks the BVH hierarchy bounds which are not a tight fit -- they are just the acceleration structure -- so you need to check the triangles, as well. The characterMovement, physics, and shapecast example files should give more insight into how to detect precise intersection using shapecast.

contained in a box/geometry

Detecting whether an object is entirely contained within another box / geometry (not intersecting triangles) is a bit more complicated. Using a capsule as an example here are some steps:

• check for triangles intersections between the capsule and the geometry
• if they intersect then you have your answer
• if they don't intersect then pick one point you know is inside the capsule and cast a ray in any direction. If a back face is hit then you know it's inside. If no face or a front face is hit then it's out side. Of course this only works if your geometry is well formed.

Hopefully that's clear. Let me know if you need more detail!

[RenaudRohlinger]

Thanks for the clear explanation it really helped me understand how three-mesh-bvh is working, that's awesome!

I suppose that simply using the threejs Box3 methods such as containsPoint or containsBox would be the best solution to simply detect if a point or a basic shape is contained in the box.

In the case of something like a sphere or a box to take into consideration the radius of the active element, there could be a way of mixing the different intersections methods supplied by the Box3 class such as intersectsSphere and intersectsBox.

So if I'm not misunderstanding, I don't think three-mesh-bvh would be pertinent to identify the intersection of two simple boxes as the real benefits start with more complex geometry.

I think that perfectly answered my question and I will start to use Box3 methods for this case. Awesome and thank you so much for this! Feel free to close this issue if my answer did make sense 😄

[gkjohnson]

I think the short answer is that if you know an object is a simple geometric primitive like a box or a sphere it's best to use those kinds of geometry functions to determine intersections. They will always be faster than checking a triangulated version of the primitive. Physics engines often differentiate between a sphere / box collider and more generalized mesh collider specifically because checking because checking collisions between primitives is a lot faster and simpler.

So if I'm not misunderstanding, I don't think three-mesh-bvh would be pertinent to identify the intersection of two simple boxes as the real benefits start with more complex geometry.

That's right. Use cases like an environment mesh as are used in the physics and character demos, for example. Of course you can compose multiple of them into a single environment if some pieces are dynamic, etc.

Glad that helped! Looking forward to seeing more of what you're working on!