光线跟踪的最佳期望时间搜索算法

 在计算机图形显示学中,采用光线跟踪(ray tracing)算法能够生成质量很高的、非常逼真的图象,但机时花费太高。据统计,在光线跟踪算法中花费在搜索与光线相交的物体及计算出交点所用的时间大约占75％。本文提出一种用于光线跟踪的与始点无关的搜索算法。此算法不管光线在物空间的始点位置如何,都能生成精确的图象,因此具有通用性;此算法将物空间适当地划分为小立方体,通过只检测光线路径上的立方体,以实现最佳期望时间搜索,所以具有最佳期望时间的复杂性。

AN OPTIMAL EXPECTED TIME SEARCH ALGORITHM FOR RAY TRACING

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.