Ray Tracing Animated Scenes using Motion Decomposition

Abstract

Though ray trac­ing has re­cently be­come in­ter­ac­tive, its high pre­com­pu­ta­tion time for build­ing spa­tial in­dices usu­ally lim­its its ap­pli­ca­tions to walk­throughs of static scenes. This is a ma­jor lim­i­ta­tion, as most ap­pli­ca­tions de­mand sup­port for dy­nam­i­cally an­i­mated mod­els. In this pa­per, we present a new ap­proach to ray trace a spe­cial but im­por­tant class of dy­namic scenes, namely mod­els whose con­nec­tiv­ity does not change over time and for which all pos­si­ble poses are known in ad­vance.

We sup­port these kinds of mod­els by in­tro­duc­ing two new con­cepts: mo­tion de­com­po­si­tion, and fuzzy kd-trees. We an­a­lyze the an­i­ma­tion and break the model down into sub­meshes with sim­i­lar mo­tion. For each of these sub­meshes and for ev­ery time step, we cal­cu­late a best affine trans­for­ma­tion through a least square ap­proach. Any resid­ual mo­tion is then cap­tured in a sin­gle “fuzzy kd-tree” for the en­tire an­i­ma­tion.

To­gether, these tech­niques al­low for ray trac­ing an­i­ma­tions with­out re­build­ing the spa­tial in­dex struc­tures for the sub­meshes, re­sult­ing in in­ter­ac­tive frame rates of 5 to 15  fps even on a sin­gle CPU.