
A while back I explained a fast way to construct a kdtree using SAH on this forum. I'm not sure if it's easy to find that topic though.
If you want to take a look at my implementation, just drop me a line, I'll gladly send you some source code.
Basically, what I do is this:
The slowest part of the SAH kdtree construction is finding the best split position, as each split position (in each of the orientations, x/y/z) has a approximated cost, based (a.o.) on the number of primitives to the left and to the right of the split plane candidate. Counting these primitives makes the algorithm very slow, especially during the initial splits. To solve this, I store all split plane candidates in a linked list (sorted). Once this is done, I walk this list from left to right, counting primitives and storing the count in each split plane candidate. For the 'right count' I do something similar. This runs in O(n). It is possible to build a kdtree for 200k polygons, using SAH, in about 30 seconds if you implement the compiler well (mine is not that fast, but still reasonably fast, 1 or 2 minutes for 200k triangle scenes).
