Study On Ray Tracing Acceleration Technique

Ray tracing is a widely used photorealistic image synthesis technique in the realm of computer graphics,which was first introduced by Turner Whitted.As Whitted reported that over 95%of time is spent on ray-objects intersection calculations,the importance of studying the algorithm and data structures to reduce the number of intersection tests is quite obvious.Binary space partitioning(BSP)trees is one of the space subdivision technique used for accelerate the ray tracing process in modern ray tracer system.For the purpose of efficiently searching the primitives in the scene,it's basic idea is to successively subdividing a scene space to render into two smaller subspace with an arbitrarily oriented hyperplane.One of special cases of BSP trees is kd-tree which use axis aligned hyperplanes in its system.In practice,kd-trees is widely used in most ray tracer for the arbitrarily oriented BSP trees is considered to be inefficient to traverse,unstable.But these ideas are not completely true.This article shows that with carefully refinement of the build process,a BSP tree is as good or even better than a kd-tree.The major tasks of the article is as follows:1.In order to marry the advantages of both kd-tree and BSP tree,a new BSP tree is proposed.In this combined BSP tree,the nodes which near root of tree are more likely to use kd-tree splits while the leaf nodes use BSP tree split.The rendering tests show that the performance of this combined BSP tree beats standard BSP tree.2.When building a combined BSP tree,since directly using SAH algorithm of kd-tree will result in much more BSP tree nodes than kd-tree nodes,SAH for combined BSP tree is required.The SAH method mentioned in this article making the cost of BSP tree node traversal to be linear correlated with the number of triangles in it.As experiment shows,this refined SAH works much better in building BSP tree.