Octrees to find ray intersections in large static meshes

Feature requests
1

I am not sure if this is already implemented under the hood but I decided to ask away anyway.

My use case is large environments and camera & AI agent collision detection.

Doing ray intersects on large mesh is quite slow and perhaps applying octree on triangle level could give one or two orders of magnitude performance boost. This would work by placing mesh triangles in octree and find matching triangles by ray bounding box in mesh local coordinates. Then you could still move the mesh around freely if needed without need to update the octree. Only changing mesh content would require updating the octree.

Even if you create specialized collision shapes they can get quite complex and costly on large levels.

Submeshing in turn seems to affect overall performance adversely and collision engine with submeshing did not really solve my performance issues. I am still planning to try the webworker collision detection but I am afraid the ray intersect cost is still order of magnitude too large.

Kind regards,
Tommi

2

Done a little bit of work that might be useful towards placing triangular facets into an octree Mesh subdivisions in a grid-like style partitions - #4 by JohnK

3

Any opinion on this? I am thinking about this because in some other webgl framework the ray intersection implementation was order of magnitude faster. I could ray pick against all my models in scene (500k triangles) 60 times per second and use that for camera collision detection. Would like to achieve something like that with babylon.js as well if possible.

When I do intersection in babylonjs against 40k triangles the time spent is around 100ms.

4

I am thinking of writing implementation for faster mesh intersect. It would be nice to test WebAssembly for this. Any opinion what would be best language for babylon.js plugins. I considering golang as I have been writing a bit with it but there is no convenient binding implementation for it at the moment. Rust could be cool or c++?

Rust at least has some useful libraries:

https://docs.rs/bvh/0.2.1/bvh/ray/struct.Ray.html#method.intersects_triangle

Kind regards,
Tommi

5

I wonder if we could just put the triangles directly to rust bvh:

https://docs.rs/bvh/0.2.1/bvh/index.html

This recastJsPlugin code can be used as basis to get the triangle positions and indexes out of the mesh and that data could be fed to bvh perhaps.

Br,
Tommi

6

Octrees came up in @jerome’s to do list and prompted by your questions have been doing some reading around, eg https://pdfs.semanticscholar.org/7110/e0181ac9b2d3f2c51414873094ebd728a18f.pdf

It seems a lot can be done using the GPU. Now I am a long way from attempting any GPU work but am interested in seeing if I can eventually do something with CPU side but it may take a long time.

Rust I do not know about. Sorry.

1 Like
7

Hi JohnK

We are working on this with JRuiseco using rust bvh implementation if you are interested.

Cheers,
Tommi

1 Like
8

I am taking a different approach just using BJS and javascript as a proof of concept. Will have some idea if it works in a few days or so. Will be interested how you get on.

9

Hi, good to hear. It will be useful to have javascript only implementation.

Cheers,
Tommi