Dynamic Virtual Environments
Principal Investigators: John Hart
Real-time online virtual worlds (e.g. World of Warcraft and Second Life) have transformed the internet into an immersive space for social interaction, but the visuals and simulations of these online collaborative environments lag well behind those of stand-alone video games. Modern video games (like Halo 3) achieve cinematic photorealism and fluid motion by limiting the set of viewpoints and configurations of the game environment, and precomputing its lighting and animation over this limited set (via, e.g., the GPU-assisted precomputed radiance transfer used in the Xbox 360), essentially encoding the visuals into a massive high-dimensional multiple-viewpoint movie. This precomputation requires careful gameplay coordination (which makes game development expensive and time consuming), and does not support user interaction (e.g., building in an online virtual environment). The increased computational power of future multicore processors can overcome the need for precomputation, making videogames cheaper and faster to produce and online virtual environments more realistic.
The performance of shape modeling, scene rendering, physical simulation or any cyber-physical application requires the ability to efficiently find data points nearby a given query point in space. The efficiency of these nearest neighbor queries relies on spatial data structures, and the fundamental challenge for multicore processing of these visual applications will be the development of efficient parallel algorithms for processing a shared spatial data structure. To achieve a goal of realistic rendering and animation of fully dynamic user-reconfigurable virtual worlds, we need new multicore algorithms to efficiently maintain kinetic spatial data that support insertion, deletion, motion, and rebalancing operations.
