关键词: 计算机图形显示学, 算法, 光线跟踪, 算法复杂性

Abstract: Kay tracing can produce very high quality and extremely realistic images in computer graphics. However, the computational expense of ray tracing algorithm is very high. Up to 75% total operation in ray tracing are consumed in searching interse?ting objects. This algorithm has the advantages of generality because it can produce accurate images regardless of the position of the originating points of rays, and optimal expected time complexity because it properly divides the object space into small cubes and realizes the optimal expected time searching by checking only the cubes on the path of the ray.

Key words: computer graphics, algorithm, ray tracing, computational complexity