Enhanced Ray Tracing Algorithm for Depth Image Generation
Hanan Ahmed *
Department of Scientific Computing, Faculty of Computer and Information Systems 6, Ain Shams University, 11566, Cairo, Egypt.
Howida A. Shedeed
Department of Scientific Computing, Faculty of Computer and Information Systems 6, Ain Shams University, 11566, Cairo, Egypt.
Doaa Hegazy
Department of Scientific Computing, Faculty of Computer and Information Systems 6, Ain Shams University, 11566, Cairo, Egypt.
*Author to whom correspondence should be addressed.
Abstract
Ray tracing is a method to convert 3D image to high quality 2D realistic image. In traditional Ray tracing technique generating an image is an expensive process due to the large number of transmitted rays and the intersection tests of these rays with the scene primitives. This paper introduces an enhanced ray tracing (Enhanced RT) algorithm. In the proposed algorithm, merge sort algorithm is used to order triangles according to the minimum x coordinate. Then Binary Search algorithm is used to find the end index of the first triangle that has minimum x coordinate greater than the pixel x coordinate. This search limits the subset of the triangles that may intersect the ray, and hence, reduces the intersection calculation time. Experimental results show that the proposed algorithm decreased the execution time by 99.8% than the traditional ray tracing algorithm with high quality for the produced depth images for a standard Benchmark models. The implementation was done on an ordinary hardware without need to use the highly expensive parallel architecture hardware (as GPUs or Clusters) as in the other research in the same application. The proposed algorithm also achieved the highest successful hit rate in comparing to the most recent ray tracing algorithms.
Keywords: Depth images, ray tracing, merge sort algorithm, binary search algorithm.