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