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

Figure 1: Dynamic scenes ray traced using parallel fast construction of kd-tree. The scenes were rendered with shadows, 1 reflection (except HAND) and textures at 512x512 resolution on a 2-way Intel R○Core TM 2 Duo machine. a) HAND- a static model of a man with a dynamic hand; 47K static and 8K dynamic triangles; 2 lights; 46.5 FPS. b) GOBLIN- a static model of a hall with a dynamic model of a goblin; 297K static and 153K dynamic triangles; 2 lights; 9.2 FPS. c) BAR- a static model of bar Carta Blanca with a dynamic model of a man; 239K static and 53K dynamic triangles; 2 lights; 12.6 FPS. d) OPERA TEAM- a static model of an opera house with a dynamic model of 21 men without instancing; 78K static and 1105K dynamic triangles; 4 lights; 2.0 FPS. 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. Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensiona