Chinese Journal of Computers   Full Text
Title	Ray Tracing of Dynamic Scenes by Managing Empty Regions in Adaptive Boxes
Authors	LI Jing1) WANG Wen-Cheng1) WU En-Hua1),2)
Address	1)(State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190) 2)(Department of Computer and Information Science, University of Macau, Macao)
Year	2009
Issue	No.6(1172—1182)
Abstract &   Background	Abstract This paper presents a new ray-tracing technique to efficiently speed up ray traversal in empty regions. It first produces grid cells in a new method, and then aggregates empty cells adaptively into fewer empty boxes, so that much acceleration can be obtained by reducing computation on ray going through empty regions. The new acceleration structure can be constructed in O(n) time, and its storage complexity is also O(n). By such a structure, rays can be traced in O(logn) time, similar to ray tracing via a kd-tree . When this structure is integrated with existing acceleration structures, large dynamic scenes can be efficiently rendered. For instance, a dynamic scene with multiple buddha models in up to 6G triangles can be interactively rendered in high photorealism on a common PC, where rays are traced individually and second rays are also computed. Keywords acceleration; ray tracing; grid cell; secondary ray; dynamic scene Background Ray tracing is one of the main approaches for photorealistic rendering of 3D scenes. It can achieve high realistic rendering effects, because the rendering process of ray tracing is physically correct. However, high computation cost prevents ray tracing from practical application. Considering this, researchers have been developing spatial acceleration structures and ray traverse algorithms to improve its efficiency. In particular, ray tracing dynamic scenes has attracted much attention from the computer graphics association in recent years, due to its great demand in many applications such as virtual reality and games. As far as we know, the advanced ray tracing techniques can render a dynamic scene in several hundred thousands polygonal facets in several frames per second. But this is still far below the requirements in real applications. In this paper, we design a novel structure for speeding up ray traversal in empty regions, and it is also very efficient for fast ray tracing dynamic scenes. Its basic idea is to produce big empty boxes to gather neighboring empty grid cells and associate the boxes with grids. Due to the uniform grids, these boxes can be built fast. Meanwhile, these boxes provide an approximation of empty regions in fewer partitions so that rays can traverse fast in empty regions via the boxes. Experimental results have shown the advantages of our new method over existing techniques, to be able to interactively ray trace large dynamic scenes, even in over 1G polygonal facets.