Bounding volume hierarchies (BVH) for ray tracing with Morton Codes

Demos and projects
1

In this post - short version, code link, question, inspiration, references,problems and to do.

SHORT VERSION
This is the start of an attempt to implement BVH using Morton codes in BJS.
In all examples wait for mesh to load, click to generate BVH (or in one case an Octree), wait for generation, click to intersect ray. Waiting time can be several seconds to load mesh and for generation -please be patient.

https://agitated-sammet-98ab48.netlify.app/ one ray intersects a sphere with 8582 vertices and 17160 triangular facets

the following two demo’s compare 10000 ray intersections using bvh and octree (though I may not be using the octree properly). Times shown at top of page.
https://agitated-sammet-98ab48.netlify.app/helmetbvh
https://agitated-sammet-98ab48.netlify.app/helmetoctree

CODE
github

QUESTION
Is this worth pursuing as an enhancement issue for BJS?

INSPIRATION (for a BJS version)
A @jerome’s to do list

Octree :

B Apparent 150x speed improvement using Rusty Raycast

REFERENCES
Morton Codes | Asger Hoedt
algorithm - How to compute a 3D Morton number (interleave the bits of 3 ints) - Stack Overflow
Bounding Volume Hierarchies
Efficient BVH Construction via Approximate Agglomerative Clustering PDF File
JavaScript BVH

PROBLEMS
The algorithm in the PDF paper was recursive. When I tried recursion anything over about 4500 facets caused too much recursion.
Apparently you can create the BVH using parallel programming in a gpu but this is way beyond my skill level

TO DO
Currently only works with a static mesh that has not been transformed in any way, ie no re-positioning, rotation or scaling. Next task is to deal with this.
Extend to rays hitting multiple meshes, (a) which meshes hit, (b) where the mesh was hit
Extend to rays hitting SPS, ie which particle hit
Exploration of possibilities for use with collisions.

4 Likes
2

In order to check if a task is worth it, I usually try to evaluate its gain whatever the needed refactor work : if all the rest (same language, same API, no breaking changes, etc) keeps the same and the performance gain is at least for 20%, I don’t even hesitate, I try to implement it.
If the expected gain is more than 100%, it’s even more motivating :smiley:

Usually, such gains with the current conditions (nb of meshes, vertices, CPU or GPU current speed, current javascript engine speed) tend to increase with the future improvement of these initial conditions.

2 Likes
3

Completely aligned!

And you seem to be using the octree correctly!