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 :

- 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

**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.