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.