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.