Octree injection for faster raycasting/raytracing

**NEW update: I never really established a proper repository for this, and it seems I have let through some serious bugs. I refer to corrected versions by @Nick_Drobchenko here: Octree injection for faster raycasting/raytracing - #7 by Nick_Drobchenko

Update: I had some struggles with properly monkey-patching the mixed module-based and WebWorker solution, but eventually succeeded with a messy setup. New demo is running here: three.js - raytracing renderer with web workers

Outdated, but kept for future reference**NOTE: This does not currently work (if it ever did), but I do not have the time to fix it right now. I will (one day) make a new version that includes the new raycast method in the build instead, because there are problems with either injecting in the module or forcing the example module to use the non-module build.**

Compare with the original: https://threejs.org/examples/raytracing_sandbox.html

Rendering times are shown in the console. With 11 workers, the time appears to be reduced by 40-50 % on my system.

My contribution is injecting the usage of a per-mesh face octree for raycasting to mesh. This reduces the dependence of the rendering time on the complexity of meshes. See three.js/Mesh_octree_injection.js at otnode-mess · EliasHasle/three.js · GitHub (based on modifying a possibly outdated version of the rayast method. Must be brought up to date.)

The octree representation is very simple and object-oriented, and contains only methods for locating and inserting data by bounding boxes. I think returning an array of objects found in ray-intersected cells would be a natural first extension (as it is needed for all raycasting applications). Corresponding methods for other shapes, such as frusta, boxes and spheres, can also be created. See https://github.com/EliasHasle/three.js/blob/master/examples/js/OTNode.js

The cost of octrees is increased memory consumption of geometries, and of course the octree generation/updating, which must be repeated if the geometry is modified. In many cases, geometries are static, though. The geometry octrees are invariant to object transforms.

It is a work in progress. Namely, only BufferGeometry is supported right now (can be easily extended to Geometry, and it would be very useful to support instancing, which is one of the fields where raytracing may excel). Further optimization is likely to be possible by doing the right choices for content (face) representation in the octree, as well as the right juggling of preallocation and cloning. Also, the approach will work equally well for point clouds, if the points are stored by their bounding box.

I welcome contributions.

Is there any interest for incorporating some of this in the main repository/core? If doing multiple renderings of a dynamic geometry, the octree must also be updated accordingly (along with positions/indices etc.). Raycasting is used for things such as tracking consequences of bullets in games etc. too. I know three.js is not really a game engine, but maybe such optimizations could be interesting anyway, if the changes are modest and non-breaking?

Update: Replaced queue with stack, to spare memory.


hey, great work. You might find these interesting:


They are very interesting. I have focused on face indexing within geometries, but the same octree implementation (or another, faster one!), may indeed be applied to object indexing in a scene. Or different indexing methods for objects and faces.

@EliasHasle I’ve spent some days trying to get why your code not building the tree and pushing all the vertices into the first root element.
It appears that there’s a bug in OTNode.js. They try to use not root’s BB but elements…

Please find attached “diff”.

When fixed works like a charm.
Without this fix there was no benefit of the octree - raycaster checked all the faces because they all were in the root of the tree.

PS sorry for my “English” :slight_smile:


Thanks for taking the time to investigate this and report your finding! And sorry for taking several days of your time. I hope you got something out of it.

I cannot independently verify the bug right now (as I am away from a proper computer), but you give me no reason to doubt it. (Hmm, I thought I would have defined bb without this as a local shorthand, but somehow it must have been defined globally instead?)

Do you get faster raytracing?

Would you mind submitting a PR with the fix?

No thank you :slight_smile: It’s a great function!

It should be taken from the recursion while you are going down to the leaf of the tree.

I use it for supports generation, and it gives super-fast results
17 seconds compared 47 seconds for this model:

And 4 seconds compared to eternity for this model (the size of the model is about 38Mb). In fact, I have not ever waited for the final result for this model without octree - right now it’s about 10 minutes running, and it has not done even a half.

1 Like

Found another bug.

If you are working with Geometry (not BufferedGeometry) raycasting fails because indexes are not stored in the octree.
This will store the indexes (a b c - are undefined, should be face.a, face.b,face.c):

< 					let faceIndices = [a, b, c];
> 					let faceIndices = [face.a, face.b, face.c, f];

Also I’ve added storing of the face index. For BufferedGeometry it’s basically faceIndex = a, which is not for just Geometry, so:

< 				for (let [a,b,c] of otn.content) {
> 				for (let [a,b,c,f] of otn.content) {
< 							intersection.face = face;
> 							intersection.face = geometry.faces[f];

please find the attached fixed files.
OTNode.js (2.6 KB)
Mesh_octree_injection.js (9.1 KB)