Ray tracing with kd-trees

OData support
Dr. Szécsi László
Department of Control Engineering and Information Technology

Computer based image synthesis techniques have a great interest from research point of view ever since graphic acceleration cards appeared on the market. More and more methods are developed even nowadays. There is a great variance in performance and in the produced pictures’ quality amongst the developed methods. They can be divided into three major categories: incremental image synthesis methods, ray tracing, and global illumination methods. This thesis concentrates on ray tracing, which is commonly used as a basis for global illumination effects in the present.

Ray tracing in computer graphics has gone through a lot of development over the past thirty years. The rapid growth in computation rates and the appearance of programmable GPUs made it possible to run ray tracing in real-time. In the 90’s the technique was only used by movies with a higher budget and industrial computer aided design softwares, it has changed significantly since than. Nowadays it’s applied by leading 3D real-time graphic engines to make computer games more and more realistic.

The aim of this thesis is to give a brief summary on ray tracing and on the published space partitioning techniques and their use to accelerate the image synthesis. The kd-tree data structure and its efficient implementation will be described in detail, with its appliance in ray tracing implemented on a processor and on a programmable graphic card. Additionally, the performance of the CPU and GPU implementation will be analyzed and further development ideas and optimization possibilities will be provided.


Please sign in to download the files of this thesis.