Kd tree for triangle meshes is too slow

Question

The Kd algorithm starts with the creation of a root BSP node by partitioning an array of primitives (triangles, spheres, ...) in order to create two new arrays (left and right primitives) used for the creation of its two subtrees.

The left and right primitives are calculated by partitioning a given primitives array into two arrays. The partitioning plane position is calculated by taking the median of the middelpoints of the interval (projected onto a given axis (x,y or z)) of each triangle.

For example a triangle with x-coordinates: 1, 2, 3 has a middelpoint 1=(3-1)/2 (along the x-axis) A triangle with x-coordinates: 2, 3, 8 has a middelpoint 3=(8-2)/2 (along the x-axis) A triangle with x-coordinates: 4, 3, 8 has a middelpoint 2.5=(8-3)/2 (along the x-axis) The primitive array containing these three triangles is partitioned by a plane through x=2.5 (median) parallel to the yz-plane. The resulting left primitives array contains the three triangles, the resulting right primitives array contains the three triangles.

The two resulting arrays with the left and right primitives are used to construct the left and right subtree of a Kd node (primitives are only stored at leaf nodes).

For the left subtree:

If (the left primitives are empty) then the left subtree points to NULL
else if (the number of left primitives is smaller than the minimal number || the depth == 1) then the left subtree is a leaf node
else the left subtree is another tree.

create the left subtree with the left primitives along the axis (++axis % 3) with --depth as depth and the same minimal number.

Analoguous for the right subtree.

The algorithm implemented works, but it's very slow because the tree is not very well partitioned. When ray-tracing a bunny of 5500 triangles, there are a lot of leaf nodes of 1 triangle and the last leaf node still contains 762 triangles.

Is there a better partitioning algorithm (because mine is just an implementation of a Kd tree for single points converted to surfaces), that balances the tree?

UPDATE: I searched for an algorithm or heuristic that can partition an array of intervals [t0,t1] into two arrays of intervals according to a cutting point. The left array contains the intervals to the left of the cutting point and those that contain the cutting point. Analoguous for the right array. Both arrays must have approximately the same number of intervals and the number of duplicate intervals must be as least as possible. This algorithm may not be of complexity O(n^2).

Answer 1

The computation of the middlepoints looks incorrect. For the triangle with x coordinates 2,3,8, the middlepoint should be 2 + (8-2)/2 = 5. The triangle with x coordinates 1,2,3 should have middlepoint 1 + (3-1)/2 = 2. This could explain the unbalanced leaves.

Answer 2

I'd suggest you to use Surface Area Heuristic (SAH) for finding optimal split.

The probability of intersection of the ray with subtree - is proportional to the surface area of the bounding box of that subtree.

But, if leaf-subtree contains lots of triangles - it means that we have to traverse them all.

So, the main idea of SAH is to minimize both: surface areas of subtrees and number of polygons inside of them.

Lets look at small 2D example:

Also, using of SAH - helps to determine terminate condition during the building of kd-tree:

1) At each step of building of kd-tree, before the splitting of subtree - you have to calculate SAH of current subtree

SAH_initial = number_of_polygons * area_of_subtree

2) Aftre that you have to find SAH of the most optimal split of current subtree

SAH_optimal = min(S_left * N_left + S_right * N_right)

3) Aftre that you have to compare:

define some split_cost
...

if( SAH_optimal + split_cost < SAH_initial ) { 
   it would be optimal to split that subtree
} else {
   you don't have to split current subtree
}

Here is another answer on Stackoverflow, which contains referebces to the articles, about SAH.