# Kd-tree based ray tracing acceleration

OData: XML JSON What's this?Ray tracing is a rendering technique based on physical models. It's base idea is to take the light rays entering the camera, trace them backwards, and calculate their color like that.

The scenes are made up from models made from triangles, so the most critical part of the program, as far as performance goes, is finding the first triangle which the ray intersects. The naiv algorithm, which tests each triangle, whether they intersect or not, is very slow, as the computational requirement scales with the product of the number of triangles, light sources and pixels. The solution to this is spatial partitioning, with a KD tree, which allows us to quickly determine of a group of triangles whether collision is possible or not. The algorithm basically puts triangles in boxes, and only calculates intersection with the triangles, whose boxes the ray intersects, this was we can calculate first intersection a lot faster.

The program will be able to read textured models, and render images of them, using algorithms found in modern graphical programs, like normal map, super sampling, mip map etc.

Ray tracing is an algorithm that's easy to run in paralel environments, the data structures need to be created only once, then each ray can be traced independently. Because of this, I will try to implement the program on the CUDA platform too, to utilize the computing power of graphics cards.