Acceleration of regular grid traversals using extended chessboard distance transformation on GPU

In the recent years graphics processing units (GPU) have evolved into general purpose programmable streaming parallel processors. This evolution makes it possible to implement high quality photo realistic rendering techniques on graphics processors. There have been a few studies to show how to map ray tracing to the GPU. Since graphics processors are not designed to process complex data structures, it is crucial to explore data structures and algorithms for efficient stream processing. In particular ray traversal is one of the most time consuming parts of ray tracing methods. In this work we focus on the efficient ray traversals on GPU. Several known techniques have been redesigned and adapted to the GPU programming model. Also a new traversal method based on extended anisotropic chessboard distance metric has been introduced.