BH

@JoeJ Hi again nice to hear back

In terms of the triangles it loops through all of the 3d coordinates of the model based on the shader position attribute, applies the position of each vertex based on the world matrix of the current objects, and adds a triangle for every 3vertices, then splits everything and creates bounding boxes for each level etc

const positionAttribute = geometry.getAttribute( 'position' );

for ( let i = 0; i < positionAttribute.count; i += 3 ) {

const v1 = new THREE.Vector3().fromBufferAttribute( positionAttribute, i );

const v2 = new THREE.Vector3().fromBufferAttribute( positionAttribute, i + 1 );

const v3 = new THREE.Vector3().fromBufferAttribute( positionAttribute, i + 2 );

v1.applyMatrix4( obj.matrixWorld );

v2.applyMatrix4( obj.matrixWorld );

v3.applyMatrix4( obj.matrixWorld );

this.addTriangle( new THREE.Triangle( v1, v2, v3 ) );

}

Also the blender file is only around 2mb but that's before all of the array modifiers are applied, afterwards it's at least 4 times more and I think even more then they after some new edits

Is there a better way to load it? I'll try to take a look at that article also

Awtsmoos said:
Also the blender file is only around 2mb but that's before all of the array modifiers are applied, afterwards it's at least 4 times more and I think even more then they after some new edits

Ah ok, then i guess the blender file is smart enough to use instancing, by listing vertices of a duplicated stairs model just once. I have not thought about that.
Then maybe we are back at the beginning, suggesting to support instancing for the acceleration structure as well.

To clarify, you could tell the number of total triangles of the scene. Or export a less smart wavefront obj file from blender, to see how things change if we prevent instancing optimizations.

B"H

@JoeJ Yeah I tried exporting it as a glb after applying the modifiers and joining the geometry https://drive.google.com/file/d/1K7r7saSqa6gKlBdlJno5FIFjdhk6xVf0/view I think it's around 40k vertices but it might be more since I checked last

Instancing would seem good for this model, but there should also be a way to do it for models that aren't symmetrical

Also I was reading that article and now I understand, I think, what was earlier meant regarding accessing the indecies of the triangles, meaning the indicies of each coordinate in the model data itself:

“ first improvement is switching from pointers to indices. For triangles we use their indices in the triangle array; for child node pointers we can do something similar if we pre-allocate all nodes that we ever need in a BVHNode pool. ”

Not sure if this can be used in an octree, however, or of it would save size.

Hypothetically if I'm not transforming the actual model itself it might be unnecessary to apply the world matrix to every vertex individually, maybe that would save time, or maybe the transformation could simply be applied to each raycast which might be quicker , not sure

Oh, there is one more important thing i have forgotten to mention about trees in general.

Usually the most memory is taken by child pointers (aside bounds, if so). Two basic options again:
Store 8 child pointers per node, some may be null. (octree has a branching factor of 8, because it has 8 children per node at most)
Or - if we can make sure children are in sequence in memory - we need only one pointer to the first child. Plus a number telling how many children there are, which would be just 3 bits.

The latter is a bit more involved to build, but beside space optimization it also reduces random memory access during traversal, so it's often faster as well.
My BVH8 code example i have linked before would be an example. It works by processing stuff in Morton code order, which usually is the default anyway, we just need to be aware.

Ofc. this optimization only makes sense for trees with a higher branching factor, like octrees. BVH for example is mostly implemented as a binary tree (just two children).

If we raise the branching factor even higher, e.g. 64, so each cell has a 4x4x4 grid of children, this reduces our node count by an extreme, exponential amount, so for compression that's very interesting.
4x4x4 is sometimes called a 'sparse grid', e.g. in fluid sim community. Algorithm and code is pretty much the same as standard octree.
Downside is less fine grained culling during traversal, so we process more nodes. But iterating nodes which are in sequence is super fast because no cache misses.

Awtsmoos said:
Not sure if this can be used in an octree, however, or of it would save size.

Yes it can and should be used.

Hypothetically if I'm not transforming the actual model itself it might be unnecessary to apply the world matrix to every vertex individually, maybe that would save time, or maybe the transformation could simply be applied to each raycast which might be quicker , not sure

That's where the extra complexity of supporting instances is:

You need raw vertex positions in object space. You build ‘sub’ or ‘bottom level’ acceleration structure for that in said object space.

To get a single acceleration structure for the whole scene, each instance of an object needs a transform matrix to support scaling, rotation, translation, sheer, and eventually even mirroring (mirroring flips winding order and breaks some assumptions!)

This is general for any kind of acceleration structures.
We then use the inverse of our transform matrix to transform our ray or query region from world to object space.
Notice, if we support nesting, this gives as a transform hierarchy which needs to be added to our traversal stack. That's not for free, so we support instancing only if we really have to.