Ray-Tracing Time-Continuous Animations
using 4D KD-Trees

MSc Thesis
Lund University

Jens Olsson
Illuminate Labs


Advisor: Tomas Akenine-Möller

Completed: 2007-02-19



Static acceleration structures are for efficiency reasons the de-facto standard used in high-quality renderers today. Time discretization is vital for performance for such a system, forcing otherwise natural time-dependent phenomena like motion-blur to be accumulated together by multiple rendered images. In this thesis, new methods are presented for storing animation sequences in a time-dependent kd-tree, which includes a pre-processing step, and a modified surface area heuristic (SAH) cost function. A time-dependent distributed ray tracer was implemented as a plugin-in for Softimage|XSI to test the methods in practice. Tests showed that the 4D kd-tree had better adaption to dynamic data compared to the 3D kd-tree even when both had the advantage of pre-processing. Applications of the 4D kd-tree were demonstrated to temporally displace instances of primitives to create the illusion of large groups of independently moving objects.




Head 1 [2.7 Mb]
Head 2 [2.2 Mb]
Armadillo [5.5 Mb]
Propeller 1 [4.0 Mb]
Propeller 2 [3.7 Mb]
10 Bunnies [2.8 Mb]
1001 Bunnies [3.8 Mb]