Feb. 11, 2004

Publications in Graphics on the use of Skeletons for Shape Reconstruction and Animation :

• Fu-Che Wu et al.:
  • Skeleton Extraction of 3D Objects with Visible Repulsive Force, 2003.
  • Skeleton Extraction of 3D Objects with Radial Basis Functions, 2003.
• J. P. Lewis et al.:
  • Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, 2000.
• S.Pontier et al.:
  • Implicit Surface Reconstruction from 2D CT Scan Sections, 1998.
  • Weighted Skeleton for Implicit Object Reconstruction, 1998.
• C.van Overveld & B.Wyvill:
  • Polygon Inflation for Animated Models: A Method for the Extrusion of Arbitrary Polygon Meshes, 1997.

BibTeX references.

Skeleton is a lower dimensional shape description of an object. The requirements of a skeleton differ with applications. For example, object recognition requires skeletons with primitive shape features to make similarity comparison. On the other hand, surface reconstruction needs skeletons which contain detailed geometry information to reduce the approximation error in the reconstruction process. Whereas many previous works are concerned about skeleton extraction, most of these methods are sensitive to noise, time consuming, or restricted to specific 3D models.

A practical approach for extracting skeletons from general 3D models using radial basis functions (RBFs) is proposed. Skeleton generated with this approach conforms more to the human perception. Given a 3D polygonal model, the vertices are regarded as centers for RBF level set construction. Next, a gradient descent algorithm is applied to each vertex to locate the local maxima in the RBF; the gradient is calculated directly from the partial derivatives of the RBF. Finally, with the inherited connectivity from the original model, local maximum pairs are connected with links driven by the active contour model (snake). The skeletonization process is completed when the potential energy of these links is minimized.

Color plates:

Pose space deformation generalizes and improves upon both shape interpolation and common skeleton-driven deformation techniques. This deformation approach proceeds from the observation that several types of deformation can be uniformly represented as mappings from a pose space, defined by either an underlying skeleton or a more abstract system of parameters, to displacements in the object local coordinate frames. Once this uniform representation is identified, previously disparate deformation types can be accomplished within a single unified approach. The advantages of this algorithm include improved expressive power and direct manipulation of the desired shapes yet the performance associated with traditional shape interpolation is achievable. Appropriate applications include animation of facial and body deformation for entertainment, telepresence, computer gaming, and other applications where direct sculpting of deformations is desired or where real-time synthesis of a deforming model is required

In this paper a new method, using skeleton-based implicit model, is introduced for shape reconstruction of objects from a set of data points organized in parallel sections. To reduce complexity and computation time, the objects are described by a uniform field function and a "3D weighted skeleton". The 3D skeleton is composed of planar elements and is deduced from the 2D Voronoi skeleton of each section. The weigths are distances creating a non uniform offset of the skeleton.

In this paper, a method is proposed to reconstruct the shape of deformable objects from 2D parallel sections. For this, we use the skeleton-based implicit model, which defines objects with a skeleton and a set of field functions. To simplify the computation, in our methodology only one field function is associated with the totality of the skeleton. To reconstruct complex shapes, this function is combined with a weighted skeleton composed of triangles whose vertices are weighted in function of a distance. These weights define a non uniform offset of the skeleton which gives a coarse description of the object. The skeleton itself is automatically deduced from the 2D Voronoi skeletons of the sections.

Goal : Designing 3D free-form polyhedral objects.

Solution : Polygonal skeleton consisting of a few geometrical primitives which can be interpreted as a distribution of (electrical) charges in space; the equi-potential surfaces at a given fixed potential value for a geometrical object. Each polygon of the skeleton is annotated with 2 (possibly different) extrusion distances.

Disadvantages of Implicit Surfaces Modeling (ISM) for this task :

• Unwanted blending
• Bulging
• Deformation and motion leads to unpredictable behavior of the surface modeling, since the implicit representation is not attached (un-related) to the skeleton (or shape of the object).

Requirements to deriving closed manifold models (in 3D) from simple piecewise polygonal skeletons:

• Similarity : The 3D model should be bear ressemblance with the skeleton.
• Simplicity & flexibility : The skeleton should have few dof for ease of animation. A 3D model is usually to complex to animate directly; a derived shape representation such as the skeleton is preferable. However, the skeleton should allow for widely varying angles between adjacent polygons.
• Smoothness : Smooth blends between segments resulting from inflating several adjacent polygons is required.
• Robustness : The inflation process should be stable w/r to the angles between adjacent polygons. Self-intersection should be avoided.
• Versatility : The inflation process should be aplicable to polygonal networks of arbitrary topology.

Inflating Polygons

Different steps are possible, increasing in complexity but leading to better results. These steps are illustrated via a human figure, in Fig.1.

1. Uniform extrusion : The distance associated to all skeletal polygon patches is fixed (a global parameter) and used to inflate the skeleton (follows the similarity requirement, but works agains flexibility) - Fig.1b.
2. Non-uniform extrusion : Distance can vary from polygon to polygon - Fig.1c.
3. Non-uniform 2-sided extrusion : Each polygon is extruded in 2 directions where the (dilation) distance can take 2 different values - Fig.1d.
4. Cº non-uniform 2-sided extrusion : 1st attempt at introducing smoothness: For 2 adjacent polygonsm the dilation distance for a vertex is set to the average value of extrusion distances of each polygon. The resulting piecewise polygonal object (3D) surface becomes Cº - Fig.1e.
5. Trapezoidal Cº non-uniform 2-sided extrusion : Instead of a purerly parallel extrusion, allow growth to be non-uniform along polygonal shared edges, thus producing wedge-shaped area in between 2 adjacent trapezoids giving space for rotations - Fig.1f,g&h.
                
   
6. Trapezoidal Cº non-uniform 2-sided extrusion with provision for shared edges : Instead of "shrinking" each polygonal trapezoid independently, which gives gaps, the wedge-shape indents should be filled in with additional polygons - Fig.2a&b.
7. Trapezoidal Cº non-uniform 2-sided extrusion with provision for shared edges and non-planar input meshes : To achieve greater degrees of realism, it is necessary to permit the skeletal meshes to be non-planar. A normal vector field needs to be defined over the each patch.

Correcting self-intersection

Self-intersection cannot be avoided globally with the proposed method. On a local basis, however, one can define "safe" regions bordered by separator planes, such that most self-intersection can be avoided. This is illustrated in Fig.3.

Dealing with arbitrary toppological configurations

For an edge with more than 2 incident edges, a more elaborate approach is required; it consists of 4 phases. This is illustrated in Fig.4.

Problems

There are still 2 cases which can be problematical:

1. The self-intersection correction works only locally between adjacent polygons.
2. The overlap correction can make a point translate to the wrong side of a separator plane.

Comparison with Implicit Surface Modeling (ISM)

Table 1 below summarizes the comparison between the 2 methods.

The computational complexity of polygon inflation is proportional to the number of generated polygons, which in practice seems to be an order of magnitude lower than with ISM techniques, for a similar accuracy (of the resulting 3D mesh). Interactive manipulation of the skeleton vertices and change of the extrusion distance is directly available. Topological changes however remain difficult as they require the calculation ot the mesh topology.

Results

To illustrate the usefuulness of the proposed modelling technique, which starts from simple polygon skeletons and derives a full 3-D polygon mesh from them, see Fig. 5 & 6.

Page created & maintained by Frederic Leymarie, 1998-2004.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu