Algorithms for Computer Graphics

New generation of graphics hardware improve the real-time rendering of more complex 3D scenes. However, highly detailed scenes of 3D-CAD models can still exceed the abilities of current hardware. Therefore, rendering-algorithms have been developed in the area of computer graphics, to exploit the special properties of scene and hardware in order to reduce the amount of data to be displayed without considerably reducing the image quality.

Multi-algorithm-rendering

A virtual 3D scene can consist of data from different sources; for example of CAD data (e.g. of complex machines), data from laser scans (of factory buildings, art objects etc.), data from architecture programs (e.g. planned factory buildings) or data from 3D modeling programs. Especially when data from heterogeneous sources is combined in a virtual scene, very inhomogeneously structured data comes about. The following problem poses for the real-time rendering of such scenes: a single algorithm is often capable of rendering just one particular scene type in good quality. If it is utilized in an unfavorable scene, either the image quality or the running time can become arbitrarily poor. Therefore, occlusion-culling techniques qualify outstandingly for scenes, in which a high occultation predominates. But if a large proportion of the scene is visible, it can also generate an additional overhead, which decreases the frame rate. For a heterogeneous scene it can be difficult to choose a single algorithm, which is generally suited for rendering. Therefore we have developed a method, which displays the scene's different sections with different rendering algorithms in one image. Initially, during preprocessing, the complete scene is therefore automatically divided into sections with homogeneous characteristics. Then, it is measured, how good the single algorithms perform for the sections. Criteria for this are running time, as well as the quality of the resulting image.
Since these values depend strongly on the observer's position in the scene, they are determined for many positions within the scene via a sampling process and are saved in a data structure. When the observer moves through the scene, an optimization problem can be defined for the current position, which maximizes the resulting image's quality within a given maximum duration for image reconstruction. The procedure allows for scenes, which consist of hundreds of millions of triangles, to be automatically processed and rendered.

PADrend

For this and other rendering algorithm's development, we develop and employ a software platform, which is especially tailored to the particular demands in this branch: "PADrend: Platform for Algorithm Development and Rendering". Based on a modular and platform-independent plug-in system, algorithms and data structure can be variably adapted and combined. Especially in the new development of algorithms, the possibility to substitute the program code during runtime, offers great advantages; equally, the different possibilities to systematically determine different parameters (algorithm running time, image quality etc.). For the evaluation of new algorithms, PADrend offers a wide selection of already existing implementations for many algorithms and data structures from literature as a reference. This allows for a fair comparison of algorithms, since the same foundation is used for all algorithms and therefore, differences in running time due to diverging implementations are minimized.

back to overview