TUD Logo

TUD Home » ... » Results of student work » Minor Theses » Thomas Räckel

Computer Graphics

Minor thesis of Thomas Räckel

Surface Reconstruction from Point Clouds using Hierarchical Clustering

Lehrstuhl für Computergraphik und Visualisierung

Student: Thomas Räckel
Betreuer: Dipl.-Medieninf. Sören König
Verantwortlicher Hochschullehrer: Prof. Dr. Stefan Gumhold


Technology for the acquisition of a 3D model gets cheaper each day. Hence, having your own 3D scanner at home might be as common in the near future as having a document scanner today. Therefore, the need to process the acquired data increases. Since 3D scanners typically produce point clouds, the acquired data must be processed further for efficient representation, rendering, and computations. One task is the reconstruction of a surface from the acquired points. Reconstructing such a surface is a challenging problem because the data produced by 3D scanners is always noisy and a point cloud can consist of a few hundred thousand up to more than one million points. Other issues for reconstruction are holes that might be found in the data, along with outliers and undersampled areas.


Starting from a point cloud, the data is first clustered into smaller pieces. To do that, diffrent methods can be used, like a standard Lloyd approach up to a split plane clustering. A proxy is associated with each cluster to capture the local shape of the surface. Those proxy are then composed to a gloabl surface. Therefore, we define support spheres an blend the proxies using a partition of unity approach.


We developed a software system to reconstruct the surface from a point cloud. We showed that a divide and conquer approach is necessary, to handle the high amount of data produced by a 3D scanner. The local shape of the surface can be capture using planes or bivariate polynomials as proxy objects. The clustering stage results in a binary tree, which can be saved and used in other applications. Despite that, the final surface can be rendered using a standard raytracing approach.

Clustering result

Visualization of proxy objects

Visualization of support spheres

rendered surface

Future Work

The first restriction of our software system is the fact that it uses only a single thread. With dualcore or even quadcore systems becoming common these days, making the program multithreaded would increase the performance significantly. Especially the clustering process is an ideal candidate for multithreaded computations. The analysis of other proxy object may also be an important improvment which can be made. Additionally, other clustering approaches like Fuzzy C-Means may lead to better clustering results. For the visualization, the standard raytracing approach to visualize the final surface may be substituted by a GPU based approach.


Last modified: 1st Feb 2010, 2.40 PM
Author: Dipl.-Medieninf. Sören König