BVH creation time?

[Jarred-Sumner]

How long does it take to construct the BVH? Would it be usable for many meshes with ~100k vertices (constructed in a worker and allocated using SharedArrayBuffer if available)?

Its super cool that you implemented all this. It looks like a ton of work.

[Usnul]

I haven't actually tested performance specifically for a long while. Last I checked the numbers for BinaryNode-based BVH (main bvh module) construction were like this:

• 10K boxes - 19.371ms
• 100K boxes - 240.267ms
• 1M boxes - 3.134s

this is using z-filling curve. If you don't care about the quality of BVH at all, you can do that much faster. Also, there are serializers, so you could cache the BVH.

A BVH leaf (a box in the numbers above) is really anything you want. You can group a number of adjacent vertices or triangles into a single leaf if you wanted, this would give you some speedup too. Another option is to use IndexedBinaryBVH, which is perfect for those ShaderArrayBuffer situations. In fact, terrain system works on that principle, terrain tile geometry is built along with geometry's BVH in a worker thread and then shipped over to the main thread.

IndexedBinaryBVH is also optimized for build speed, so you should expect to see significantly lower numbers than those posted above.

relevant files:

BVHFromBufferGeometry
IndexedBinaryBVH
BinaryNode
TerrainTileManager

also, here's a super-old historical post from back when the BVH stuff was being started, that's where the numbers are pulled from:
mrdoob/three.js#5571 (comment)

I should say that the numbers should be better, both because BVH has been worked on a lot since that time, as well as general improvements in JS engines.