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

Thanks guys!