Scientific Visualization and Computer Graphics > CS > JBI > FWN > RUG

Project Proposal: Skeleton-based Mesh Segmentation

Background

Curve skeletons are powerful descriptors for 3D shapes. They are thin structures locally centered with respect to an input shape, and capture the part-whole shape structure.

We have used in the past curve skeletons to produce high-quality, robust, and intuitive part-based segmentations of 3D shapes, where one segment is created for each natural part the shapes.

The above work handles voxel models. However elegant, these are problematic in terms of speed and memory consumption.

Goal

Recently, we have perfected a surface-and-curve skeleton extractor from large polygonal meshes. This method is over 100 times faster than the voxel-based method and produces extremely high-quality skeletons.

In this project, we want to study how to apply and adapt the main ideas for part-based segmentation already demonstrated with our voxel method, this time for mesh models. Several algorithmic and implementation challenges exist:

  • do we really need to extract the curve skeleton first, or can we do part-based segmentation directly from the surface skeleton?
  • the part-based segmentation is quite slow, as it requires several topological operations on the surface (connected components, flood-fills, etc). Can we design a computationally faster algorithm that produces the same segmentations, but with less work?
  • can we design better criteria for what a part of an object is, leading us to better segmentations?
  • our mesh-based skeleton framework heavily uses CUDA. How can we optimally parallelize the segmentation algorithm to take most advantage of CUDA?

Requirements

The candidate should have the following skills:

  • (very) good mastery of C/C++
  • familiarity with CUDA programming
  • basic knowledge of OpenGL

Contact

If you are interested in this project, contact Alex Telea. This project is a cooperation with dr. Andrei Jalba, Univ. of Eindhoven.

References

First, check the project pages accessible via links in the above text. Next, have a look at the following papers:

  • Computing Multiscale Curve and Surface Skeletons Using a Global Importance Measure (D. Reniers, J. van Wijk, A. Telea, IEEE TVCG, 2007)
  • Hierarchical Part-type Segmentation using Voxel-based Curve Skeletons

(D. Reniers, A. Telea, The Visual Computer, 2008)

  • Part-type Segmentation of Articulated Voxel-Shapes using the Junction Rule

(D. Reniers, A. Telea, Computer Graphics Forum (Proc. Pacific Graphics), 2008)