Octree injection for faster raycasting/raytracing

My version: http://eliashasle.github.io/three.js/examples/raytracing_sandbox.html

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

Rendering times are shown in the console.

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 https://github.com/EliasHasle/three.js/blob/master/examples/js/Mesh_octree_injection.js (based on modifying an 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?

1 Like

hey, great work. You might find these interesting:


2 Likes

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.