Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes

Abstract

We present a highly parallel, linearly scalable technique of kd-tree construction for ray tracing of dynamic geometry. We use conventional kd-tree compatible with the high performing algorithms such as MLRTA or frustum tracing. Proposed technique offers exceptional construction speed maintaining reasonable kd-tree quality for rendering stage. The algorithm builds a kd-tree from scratch each frame, thus prior knowledge of motion /deformation or motion constraints are not required. We achieve nearly real-time performance of 7-12 FPS for models with 200K of dynamic triangles at 1024x1024 resolution with shadows and textures.