Home > Research Groups > Algorithms and Complexity > Research > Algorithms for Computer Graphics

Algorithms for Computer Graphics

In 3D assisted simulation and test environments, it is often required to interactively navigate in highly complex 3D scenes that are partly generated at run time. To render such 3D scenes in real time, we develop rendering algorithms that reduce the amount of data to be processed in such a way that fluent navigation is possible.

Mesh clustering based on progressive sampling

Clustering of 3D surfaces is an important technique in computer graphics with many applications. The goal is to divide the triangles of a 3D surface mesh into several small, connected groups of triangles (clusters), so that each group is as compact as possible. Based on our progressive sampling technique, we have developed a clustering technique that allows to compute such a clustering efficiently on the graphics card. We take advantage of the uniform point distribution on 3D surfaces of our sampling technique and assign each triangle to the nearest sample point. This gives us an equally uniform subdivision of the 3D surface mesh.

The stanford bunny model clustered using our method.

Hybrid point-based and clustered rendering

In the past, we have developed a highly efficient, point-based rendering method based on our progressive sampling technique. One problem so far was that geometry in the nearby range was rendered in full complexity, which strongly influenced the runtime. Now, we have combined our rendering method with our clustering method to solve this problem as well. In the close range, whole groups of triangles (clusters) can now be culled away in a simple way, which greatly increases the rendering performance.

Automatic generation of landscapes based on road data

For virtual simulation environments, it is often necessary to create large, complex 3D landscapes. The manual creation of such landscapes is often very time consuming and expensive. In cooperation with dSPACE GmbH by the Software Innovation Lab of Paderborn University, we develop methods for automatically generating landscapes for driving simulations. The goal is to generate fitting, plausible landscapes based on raw road data that can be used for virtual driving simulations.

Terrain automatically generated from the road data.

Project Partners:

  • SICP – Software Innovation Campus Paderborn,
  • dSPACE GmbH