Using Binary Space Subdivision to Optimize Primary Ray Processing in Ray-Tracing Algorithms

摘要

Ray-tracing algorithms have the potential to create extremely realistic three-dimensional computer graphics. The basic idea is to trace light rays from the user through the computer screen into the hypothetical three-dimensional world. This is done to determine what objects should be displayed on the screen. Furthermore, these rays are traced back to the light sources themselves to determine shading and other photorealistic effects. However, without optimization these algorithms are slow and impractical. This paper explores the use of the classic binary space subdivision algorithm in order to speed up the process. Binary space subdivision is the use of binary trees to recursively partition the screen into rectangular areas which are then rendered separately. The algorithms were implemented using C++. The use of binary space subdivision dramatically improved the speed of the implementation in most cases, resulting in a doubled or tripled frame rate under favorable circumstances.