Vilem Otte said:
As for your problem - you have a scene with geometry and huge amount of surfels (millions). From those millions you pick few hundred thousand for given frame, and now for geometry you need to find 4 closest surfels for each pixel and interpolate between them (to get F.e. indirect light or something … not that different from how generic final gathering works for photon mapping). Do I understand your problem correctly?

Yes.

The difference to PM or FG is that i should not need to do any kind of searching or clustering work at runtime, because preprocessing tools already have exact knowledge which N texels belong to which point on a certain triangle.

BTW, N does not necessarily need to be exactly 4. It would be an option to link only one closest surfel - i could find neighbors from adjacency information present in the tree, eventually.
But the plan is that each surfel corresponds to one texel of a lightmap. It's a bit more complicated: Becasue real LOD can change the topology and even genus of geometry. So i can not rely on one UV map and mips of texture as usual. Actually i need different UVs per lod and mip, and i need to match LOD mechanisms for both the surfels and the visible geometry. This is what makes my work so hard and success appears far fetched : )
But i hope there could be a solution to this ‘simple’ indirection problem which is unrelated to all this complexity.

@JoeJ @Vilem Otte Im having hard time implementing the light BHV (packing the lights into the BHV, testable on GPU). Do you know some good code examples / repos / in depth papers for me as reference? ?

I do understand octree very well, but can't bite into BHV stuff :D

BVH seems alien to me. I don understand the splitting rules. For example pic below. Why left and middle combined in B, but not middle and right.

Again, why is C alone, not bounded in 2 node with A and B?

This is kind of dummy explanation I wanted > https://www.haroldserrano.com/blog/visualizing-the-boundary-volume-hierarchy-collision-algorithm, but does cover only ideal cases where splitting in middle doesn't overlap objects.

trsh said:
Why left and middle combined in B, but not middle and right.

Because this is a binary tree. (would write BVH2, where the number means the maximum children a node can have, also called ‘branching factor’)

Binary is used always when trying to explain things, but it's not a must. I can make sense to even have BVH64 on GPU.

Personally i consider binary trees as often inefficient on GPU, because it means you have more tree levels. Often there is a need for a barrier between levels, so one dispatch per level, causing execution bubbles and smaller workloads. It also causes more traversal steps to get to the goal (but less complexity per step, so it depends… as always)

trsh said:
Again, why is C alone, not bounded in 2 node with A and B?

Seems the splitting happens at the center, exactly like in my example, so BVH4 similar to quadtree. Top right has nothing, and bottom right (C) just has no more children.
Resulting balance is not great, but improving this has a cost, e.g. sorting all children along one or multiple axis at each split when building the tree.

@JoeJ I like the idea of splitting longest bounding axis at mid-point. But what do in this case, where all centroids are one side. This would en up in never ending loop trying to split to leafs.

@trsh You need to get bounds of centroids and then split in the middle of longest axis to avoid the problem you described.

Another common option is to sort the objects along the axis so you can get exactly balanced halfs. (But a balanced tree is not necessarily the most efficient. For raytracing, SAH ist mostly used instead.)

Additionally, to prevent infinite loop in any case just stop adding nodes after a maximum of tree levels like 20.

Also, e.g. if all objects have the exact same center, make it a special case and use their memory indices instead geometric coordinates to split them.

I remember this project https://github.com/sideeffects/WindingNumber has BVH implementation with many splitting options like simple center, SAH, equalize volume etc. Maybe a nice example.