Complexity of practical algorithms for Volume Rendering and Computer Graphics

与传统学科相比，3D计算机图形学是一个相当新的研究领域，具有广泛的应用范围，从游戏和电影效果到科学可视化。计算机图形学的一个关键问题是它是非常密集的计算，特别是在渲染阶段。一旦3D场景以适当的方式建模（例如，体素，三角网格，隐式表面等），就必须执行渲染。渲染涉及到能够确定场景中任意对点之间可见性的关键操作，目前最好的计算机图形算法只能通过平均执行Log(n)步来解决这个问题，其中n是场景中元素的数量（可以大到十亿）。在这个项目中开发的新算法旨在使所需的步骤数量独立于3D世界的元素数量（即恒定）。例如，这将允许比目前可能的更快地生成电影图片。预期的加速系数在5到10之间。

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.