@Vilem Otte But the longest axis is that in image (horizontal). The middle is also marked. The problem is that all centroids are on left half (one by a bit). So I don't understand ur solution.

If all centroids are on the left, the average of all those centers is on the left too so some end up right of that..

The point is to take the average of all centroids, not the center of the single bound.

@JoeJ Could you briefly explain SAH?

@JoeJ

JoeJ said:

If all centroids are on the left, the average of all those centers is on the left too so some end up right of that..

The point is to take the average of all centroids, not the center of the single bound.

I dont get your point here. Could you illustrate or show some math?

The math is simply: sum of all orange centers / number of objects

This will create a number at the drawn red line and divide the objects into two groups.

Notice, even if you use only the center of the bounding box, you could still successfully subdivide by putting any 2 bodies on the left and the other two on the right, until a required maximum of bodies per leaf node remains.

SAH = surface area heuristic, tries to minimize the surface area of the bounding boxes. That's good for RT. For a point search or range query minimizing the volume of boxes might work better.
Algorithm is: Sort along longest axis, partition in two halfs, test if putting the dividing object on left / right side improves the heuristic, and continue moving the split until no more improvement can be found.

But those things have high cost on tree building and may not be worth it for dynamic scenes.

Alright … Now, this is going to be a bit image heavy now (but the illustrations might help you out a bit):

You start off with a scene.

Your scene with AABB.

Then you generate AABBs for each primitive in your scene.

Calculate centroid positions for your primitives.

And build both child nodes:

Thanks guys!