hide
Free keywords:
-
Abstract:
Our main goal is to create realistically looking animation in real-time. To
that end, we are interested in fast ray tracing. Ray tracing recursively traces
photon movement from the camera (backward) or light sources (forward). To find
where the first intersection between a given ray and the objects in the scene
is we use acceleration structures, for example kd-trees. Kd-trees are
considered to perform best in the majority of cases, however due to their large
construction times are often avoided for dynamic scenes. In this work we try to
overcome this obstacle by building the kd-tree in parallel on many
cores of a GPU.
Our algorithm build the kd-tree in a top-down breath-first fashion, with many
threads processing each node of the tree. For each node we test 31 uniformly
distributed candidate split planes along each axis and use the Surface Area
cost function to estimate the best one. In order to reach maximum performance,
the kd-tree construction is divided into 4 stages. Each of them handles tree
nodes of different primitive count, differs in how counting is resolved and how
work is distributed on the GPU.
Our current program constructs kd-trees faster than other GPU implementations,
while maintaining competing quality compared to serial CPU programs. Tests have
shown that execution time scales well in respect to power of the GPU and it
will most likely continue doing so with future releases of the hardware.
