Complexity of practical algorithms for Volume Rendering and Computer Graphics

点击翻译按钮获取中文摘要

3D Computer Graphics is a quite new research area when compared to traditional disciplines, and has a wide scope of application, ranging from games and movie effects to scientific visualisation. A crucial issue in computer graphics is that it is tremendously computation intensive, especially at the rendering stage. Once the 3D scene has been modelled in an appropriate way (i.e., voxels, triangular mesh, implicit surfaces, etc...), rendering must then be performed. Rendering involves the crucial operation of being able to determine the visibility between any pair of point within the scene, and the current best computer graphics algorithms can only solve this by performing Log(n) steps on average, where n is the number of elements within the scene (can be as large as a billion).The new algorithm to be developed in this project aims to make the number of required steps independent (i.e., constant) from the number of elements of the 3D world. This will allow, for example, to generate movie pictures quicker than what is currently possible. A speed-up factor between 5 and 10 is expected.