Visualization and GraphicsInteractionDept ICSFaculty of ScienceUU

//webspace.science.uu.nl/~telea001/Site/TopBar

Multiscale 3D Skeletonization of Polygonal Models

Skeletonization of 3D shapes is a challenging area of research. Practical applications thereof pose a complex set of requirements, including correctness, completeness, robustness to noise, handling any 3D shape, and computational (memory and speed) efficiency. These requirements, as well as the fundamentals of skeletonization, are described separately in an associated project here.

Polygonal models

3D models come in two main flavors: voxel volumes and polygonal models, or meshes. Meshes have several important advantages: compact surface representation, easy modeling of non-uniform surface detail, and a vast repository of processing tools and available models.

However, computing surface skeletons of complex 3D meshes was still a challenging task. Until now.

3D Mesh Skeletonization Algorithm

We developed a skeletonization algorithm for 3D meshes which

  • can handle very complex shapes such as produced by the 3D modeling industry
  • computes arbitrarily exact, compact, 3D "surface" skeletons (manifolds)
  • produces the skeleton both as a point cloud and a triangle mesh
  • deals with noisy shapes using a multiscale importance metric
  • accurately reconstructs the initial shape in real-time from its skeleton
  • is to our knowledge the world's fastest 3D-mesh surface-skeletonization method
  • runs on commodity graphics PCs with limited memory resources
  • is inherently parallelizable
  • requires no user parameters

Step 1: Skeleton point cloud extraction

First, we extract the skeleton from a given 3D mesh. For this, we use a fast 'ball shrinking' method which reduces balls tangent to each mesh vertex until they contain exactly two points. The centers of such balls are located on the skeleton.

Careful algorithm design, using a bisection-like method, , and parallelization, allow us to deliver high speed. For example, the models below, containing hundreds of thousands of triangles, are skeletonized in sub-minute time on a dual-core MacBook Pro laptop running at 2.5 GHz.

The skeleton points are colored by the well-known feature-vector cosine angle metric (blue points correspond to parallel shape areas, red points to shape convexities).

Step 2: Multiscale importance

For each skeleton point, we compute an "importance metric" which describes the amount of area encoded by that point. For this, we adapt the geodesic-based method described in this paper to polygonal meshes. We compute all geodesics directly using CUDA, which delivers almost two orders of magnitude speed-up as compared to a sequential CPU implementation.

The importance metric is shown below. Red points encode large object areas, such as the rump. Blue points encode small features, such as edges or leg tips.

Thresholding this metric delivers a multiscale of nested skeletons.

Step 3: Splatting reconstruction

We reconstruct the shape from the skeleton point cloud by splatting 'shaded balls' (encoded as luminance-depth textures) on screen-aligned billboards centered at the skeleton points. This delivers a near-pixel-accurate shape reconstruction at several frames per second (left image below). In contrast, rendering 3D polygonal balls delivers less accuracy at around 20 times less speed (see the zoomed-in images below)

Here are the reconstructions for the cow model (left: splats; right: 3D geometric balls):

Step 4: Skeleton reconstruction

We reconstruct the 3D skeleton as a set of intersecting manifolds. Two methods are provided here:

  • a method using Delaunay triangulation of quasi-flat shape projections on the skeleton
  • a method based on an adaption of the ball-pivoting algorithm

The Delaunay method (below left) is fast: 10 seconds for a 300K skeleton point cloud), but delivers more polygons and a less clean mesh. The ball-pivoting method (below right) is slower (40 seconds for the same cloud) but delivers less polygons and a clean mesh.

The image below shows the surface skeleton of a brain surface. Note how the skeletal manifolds nicely capture the anatomical shapes (sulci and gyri) on the cortex surface.

Nonphotorealistic rendering

The skeleton structure can be used to create real-time nonphotorealistic shape renderings (NPR). The example below shows the cow model, rendered with splats whose shape is a prism rather than a sphere. Next, we enhance the contrast of the image to obtain a 'stylized' rendering appearance.

The examples below show a different NPR technique. Here, we

  • select all skeleton points with a lower importance
  • select all shape points corresponding to the above skeleton points
  • for each such point, set its normal to the normal of the closest surface point corresponding to an important skeleton point

This creates a 'faceted' look. Points close to the (implicitly detected) shape edges get their normals from flat neighborhoods. This accentuates the transitions between such flat neighborhoods. Note that the shape is not changed, just its normals.

Comparison

Compared with its closest-resembling skeletonization technique (based on voxels), our method is roughly ten times faster, takes ten times less memory, and captures significantly more detail due to the non-uniform point placement. Practically, you can obtain a surface skeleton of a 3D mesh shape of 1 million points in under a second on a 2014 consumer-grade PC with an NVidia card

Acknowledgements

This method has been developed in collaboration with dr. Andrei Jalba (Univ. of Eindhoven) and Jacek Kustra (Philips Research). Thanks go also to Madalina Florean (Univ. Transilvania, Brasov, Romania) for her MSc work on this topic. This work was partially supported by the grant PN-II-RU-TE-2011-3-2049 Image-assisted diagnosis and prognosis of cutaneous melanocitary tumors offered by ANCS, Romania.

Availability

Coming soon; please contact me (Alex Telea) if you are really interested in this.

Publications

1. A. Jalba, A. Kustra, A. Telea (2013) Surface and Curve Skeletonization of Large 3D Models on the GPU, IEEE TPAMI 35(6), pp. 1495-1508 (PDF)