Parallel SAH Based KD Tree Construction Algorithm
Cheng Ma · Advanced materials research · 2012
The best method to construct a high quality KD tree is by using Surface Area Heuristic[1][4] (SAH). However, the computation involved in SAH is expensive. Wald and Havran[2] introduced a sequential algorithm of O(NlogN) complexity, which reached the lower bound of constructing a binary tree. In this paper, we will introduce a parallel SAH KD tree construction algorithm based on the O(NlogN) sequential algorithm. We proposed data structure for parallel constructing process which can minimize the communication among working threads, and a load balance strategy for evenly distributing work load. Our algorithm can achieve 4x speed up on 8-core CPUs architecture.