In this post - short version, code link, question, inspiration, references,problems and to do.
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.
Is this worth pursuing as an enhancement issue for BJS?
- implement a faster octree selection in the current BJS octree without modify its API.
The faster octree algo is known as the Morton code and is O(n) = log(n) max.
The implementation is very well described here in french : Octree optimisés gràce au code de Morton
english (didn’t read) : Advanced Octrees 2: node representations | The Infinite Loop
Challenge level : hard, maybe very hard
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
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
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.