Kd-tree

due to its adaptive division

low memory consumption and fast traversal

has become the most widely used accelerating structure of the virtual scenes.A fast and optimal kd-tree construction method for virtual scenes is proposed in this paper.By analyzing the SAH function of the scene

simulated annealing is used in the optimal split plane search procedure so as to speed up this procedure.In this way

the kd-tree construction is finally accelerated.Experimental results show that the construction of kd-tree is efficiently accelerated with no loss of kd-tree quality.Furthermore

a multi-core parallel computing extension is implemented in this paper

and with the use of multi-core CPU's parallel processing capabilities

the kd-tree construction is further accelerated.