Last update: Feb. 18, 2004

BACK

Publications by INRIA projects on 3D Shape Analysis & Metamorphosis :

• Level Set Diagrams of Polyhedral Objects, F.Lazarus & A.Verroust, 1998 & 1999.
• Extracting skeletal curves from 3D scattered data, A.Verroust & F.Lazarus, 2000, 1999 & 1997.
• Metamorphosis of Cylinder-like Objects, F.Lazarus & A.Verroust, 1997.
• Axial Deformations: An Intuitive Deformation Technique, F.Lazarus et al., 1994.

BibTeX references.

URL's:

• IMEDIA : Image and Multimedia indexing, browsing and retrieval
• 3D Morphing and skeletal curves

Shape descriptors and feature-based representations are of primary interests in the area of solid modeling. They allow us for easier storage, recognition and general treatments of objects. Axial structures such as skeletons are popular shape descriptors which have been widely studied. Most of the studies focus on a particular type of skeleton called the Medial Axis. Medial Axes can be extracted from discrete volumetric data as well as boundary-based representations. In the later case, however, no algorithm is known to perform well and accurately.

We propose a new paradigm for constructing 1D axial structures associated with a polyhedral object. These structures, called the level set diagrams, are associated with scalar functions defined over the set of vertices of a polyhedron. We study in details the level set diagram associated with the shortest path distance to a source point. This particular association fits nicely into a theoretical framework and presents interesting properties for the purpose of shape description.

Keywords : Skeleton, Cylindrical decomposition, Euler formula, Dijkstra's algorithm.

New paradigm for constructing 1D axial structures, the Level Set Diagram (LSD) associated to a polyhedral object. It capture the overall shape (geometry) as well as the topology of an object. It can be used for deformation and animation purposes. It is much simpler than algorithms that compute the Medial Axes of polyhedral objects. The latter start with adding points on the object's boundary and compute their Delaunay triangulation. The resulting Medial axes need to be prunned.

LSDs are simple 1D graphs which relate to the level sets of scalar function defined over the vertices of a polyhedral surface. The points of an LSD correspond to "average points" associated with the connected components of the level sets of a given scalar function, f . Branches of the LSD are connected through virtual links with critical vertices of the surface P of the object.

The function f is often taken to be the height function relatively to a given orientation of the object. This is particularly meaningful for terrain data as critical points of f (i.e., points where the gradient is null) correspond to peaks, pits & passes. However, it is proposed that the shortest path distance to a source point is a often a better choice of function, especially for describing the geometry of tubular and branching objects.

Level Sets of Functions

Only LSDs of triangulated polyhedra, P, are considered here. Let f be a function over the vertices of P (v1, ..., vn) s.t. 2 adjacent vertices are given 2 different values. All that is needed is to tell which of any such 2 adjacent vertices gets the smaller values (ordering); vertices who get identical values can be ordered arbitrarily.

Cross-edge:

• An edge (vi, vj), relatively to level l, is a cross-edge if: f(vi) < l < f(vj)

Cross-face:

• A face (vi, vj, vk), relatively to level l, is a cross-face if the 3 values of its vertices encompass l, i.e.:

  f(vi) < l < f(vj) < f(vk)

  or

  f(vi) < f(vj) < l < f(vk)

• NB: a cross-face has exactly 2 cross-edges.

Cross-adjency graph (Dual graph of P):

• Graph whose vertices are the faces of P and whose edges correspond to pairs of incident faces.
• NB: A cross-face (relatively to level l ) is adjacent to exactly 2 cross-faces in the dual graph.

Property 1 - Cross-faces cycles

• For any level l, distinct from the values f(v1), ..., f(vn), the set of cross-faces constitutes a set of disjoint cycles in the dual graph.
• NB: This is comparable to the property of Morse functions that level sets on a closed smooth surface are composed of disjoint closed curves (as long as a level set does not contain any critical point).
• These cycles of cross-faces define closed polygonal contours on the polyhedron P.
• Associate with each cross-edge (vi, vj) the point:

  

Geometric realization of a level-set, C(l) :

• Set of polygonal contours obtained by tracing the lines (pij(l) pik(l)) in every cross-faces (vi, vj, vk).
• These polygonal contours are not necessarily planar.

Vertex Index & Euler Formula

Index of a vertex:

• Let w1, w2, ..., wk be the k neighbors of v enumerated counterclockwise around v. Consider the number of sign changes, Sgcf(v), in the sequence of differences of the pairs: f(w1)-f(v), f(w2)-f(v), ..., f(wk)-f(v). Then, the index of v is:

  Indf(v) = 1 - 0.5 Sgcf(v)

• This index summarizes how f is changing around v. It also records part of the topology of P itself.

Euler formula :

Where X(P) = nV - nE + nF, is the classic Euler characteristic of P, in terms of the number of vertices, edges & faces of P.

Relation with the Morse theory: Critical points of a vector field.

In Morse theory, one may speak of the index of a critical point of a gradient vector field , i.e. at a point where the vector field is null: one measures the number of revolutions made by the vector field while turning around that point. The analogy with the above vertex index can be made where one first orient the edges according to the f-values of their endpoints. This orientation corresponds to the gradient of f along the edges.

A triangle must have 2 edges oriented the same way and 3rd one oriented the other way. Then, in each triangle of P, we can draw a continuous vector field, s.t. the direction of the vector field on the boundary agrres with the orientation of its edges. The vertices of P are the critical points of this (induced) vector field. The (Morse) index of this critical points corresponds the vertex index introduced above.

The vertex index thus describes how the level set realization, C(l), is modified around any given vertex, v, as the level l is raised from f(v) - e to f(v) + e , for a sufficiently small e. Note: This is similar to the construction of Dupin's indicatrix.

Regular vertex :

• Vertex with a null index; its function value f(v) is also said to be regular.

If Indf(v) is null, then the neighbors of v are partitioned into 2 connected sets {v- : f(v-) < f(v)}and {v+ : f(v+) > f(v)}.

Critical vertex :

• Vertex with non-null index; its associated function value, f(v), is also said to be critical.
• A positive index (+1) indicates a local extremum. A critical vertex which is not an extremum is a saddle.
• When traversing a critical value, the topology of the level set is changing; hence the evolution of the level set depends on the index of this critical value.
• The precise topological change, however, depends also on the whole configuration of the level set. But these changes can be deduced directly from the vertex indices, when considering the shortest path distance to a source point on a genus-0 polyhedron (sphere-like).

The Choice of f : The Shortest Path Distance to a Source Point

While a choice of f as the height function is relevant for terrain-like surfaces (see Shinagawa et al.), a better choice to obtain level sets of tubular objects following their "natural" axes, is provided with the moving front of some flow emanating from the tip of a given tube. Such fronts corresponf to the geodesic distance to a tip of a tube.

As an approximation to the geodesic distance, it is proposed to compute the shortest path distance, ds, relatively to the graph induced by the edges of the polyhedron.

Property of sphere-like triangulated shapes (genus-0) : No loops

• The set of cross-faces incident to v for a level l lower than ds(v) belong to a unique cycle (front).
• This prevents the LSD from having loops; hence the LSD of genus-0 shapes is a tree-like structure.

Tree structure of the LSD :

The tree structure of the LSD is recorded into a tree Ts(P) whose root, internal nodes and leaves are respectively the source s, the saddle vertices and the local maxima. The lines of Ts(P) link critical vertices and correspond to cylindrical parts of P.

Algorithms to compute Ts(P) and its associated LSD

Assumptions :

• No 2 vertices of P are at the same distance from the source, s ; otherwise, order the vertices according to their order of processing.
• Ngbs. of a vertex, incident faces to an edge and edges & vertices of a face can be accessed in constant time O(1); e.g. use the winged-edge datastructure of Weiler.

To construct the LSD, we need to sweep the level from zero to its maximum value max ds and compute "average" points of various level set cycles. Ts(P) provides an efficient tool to determine a starting edge in each cycle of any level set. For each line (si, sj) of Ts(P) we compute a starting cross-edge in any cycle contained in the associated cylindrical part, for a decreasing path (from sj ).

Computing Ts(P) - based on Dijkstra's algorithm

Ts(P) is constructed while traversing the adjency graph of P, where shortest path distance ds of the visited vertices, as well as the pointer pi to the preceding ngb on a shortest path, are computed. A priority queue with respect to distance is maintained (a la Dijkstra), which contains the adjacent vertices to already visited ones, but whose distance have not yet been fixed.

1. Starting from the root, s, visit vertices of P until a singular one is found (critical vertex).
2. Create a line (s, v) of Ts(P) :
   • if v is a local max, stop
   • else, v is a saddle: split the priority queue into 1-Ind_ds(v) queues corresponding to the branches of Ts(P) related to the saddle v.
3. Recursively go through steps 1 & 2 above for each branch (queue), until all maxima are reached.

The complexity of each loop (cylindrical branch) reduces to Dijkstra's (O(n log n) using a Fibonacci heap, for a polyhedron made of n vertices). The total time spent splitting queues is bounded by ns.Lmax, where ns counts the number of saddles, and Lmax is the largest number of cross-edges in a level-set. Thus, the computation of Ts(P) requires time O(n log n + ns.Lmax).

Computing the LSD

The LSD is a geometric embedding of Ts(P).

1. In practice, the level interval [0, ..., max ds] is discretized into a set {l1, l2. ..., lr} of r levels.
2. Compute the average point of each cycle of the level set realizations C(l1), ..., C(lr), as the barycenter of each curve C (approximated by a polygon or through a curve fitting process):
   • If C = (p1, p2, ..., pk), then :

     

3. Virtual links are kept between the branches according to the tree structure of Ts(P), to preserve the branching information.

Results

The LSD can handle self-intersections, which would not have been the case had a height function been used. Also, the Medial Axis Transform would fail (? not clear why ... ?).

N.B.: The LSD may lie outside of the object (see bowl above).

Usefulness of the LSD:

• The LSD provides a set of tubular parametrizations together with articulations, usable for animation systems.
• Such axial structure is also helpful for the extraction of surfaces from scattered point sets (see [Verroust97Extracting] and its application to medical data, such as blodd vessels).

Question :

• Does not deal with scale/noise. The number of critical vertices (local max and saddles) should explode then). Even in the results presented it is not explained how scale is dealt with. The use of very few level sets smoothes the final results enormously.

We introduce a method for the construction of skeletal curves from an unorganized collection of scattered data points lying on a surface. These curves may have a tree like structure to capture branching shapes such as blood vessels. The skeletal curves can be used for different applications ranging from surface reconstruction to object recognition. As an input, the algorithm takes a set of 3D points. It returns a set of curves arranged in a tree structure. The only interaction needed is the selection of a data point which represents the root of the tree. A neighborhood graph is constructed over the set of points to compute geodesic distances between the root point and the other points. Connected level sets of the distance map are then extracted and organized in a tree structure. The centers of these levels sets constitute the skeletal curves.

As opposed to most other approaches, which start from voxelized data to compute 3D medial axes, here one starts from an unorganized cloud of points sampled on a surface.

The computation of the axes is based on a cylindrical decomposition of the surface representing the set of 3D points. It is composed of 4 steps:

1. Construction of a neighborhood graph of order n.
   • A non-oriented graph whose vertices are the input data points.
   • Edges are pairs (v, v'), where v (v') is one of the n nearest negihbors of v' (v).
   • Not possible in general to determine a suitable polygonal surface from this graph as it may be non-planar.
2. Construction of distance map & an oriented subgraph called geodesic graph .
   • From the neighborhood graph & a source point (user provided).
   • Compute shortest paths of the neighborhood graph between all vertices & source.
3. Construction of k level sets of the distance map using the geodesic graph.
   • k is a user-defined value.
   • The level sets are composed of points at a constant distance from the source.
   • Connect (join) these points on the basis of a proximity criterion and identify the connected components.
   • Compute the centroids of every connected component.
4. Construction of axes by joining the centroids of successive levels.
   • If a level contains more than one connected component, the connection of the centroids is based upon the paths of the geodesic graph.

The choice of k (level sets) is based on the number an locations of branches as well as the smoothness of the desired skeletal curves.

Each axis of the tree structure correspond to a tubular part of the surface. Their union forms a decomposition of the surface.

Compute continuous shape transformations between polyhedral objects that are star-shaped around an axis (i.e., a generalised cylinder).

The user controls the global evolution of the deformation by specifying 2 corresponding skeletal structures in 3D, from which parametrizations of the sampling meshes are built.

The class of object considered, the star-shaped (cross-section) around an axis (3D axial curve), are split in 3 sheets: 2 hemispherical parts for the 2 end-points of the axis and 1 cylindrical part in between.

Many discretization aspects are treated by ad-hoc methods. For ecample, the recovery of "edge" (ridge) features of the original shape is done manually (it seems), which is deemed necessary to obtain reasonable cross-sections.

Our current research efforts focus on providing more efficient and effective design methods for broadcast modeling systems. This paper is a revised version of Interactive axial deformations. It presents an interactive deformation technique called AxDf for Axial Deformations. Based on the paradigm of modeling tool, the Axial Deformations technique allows an easy specification of deformations that can be controlled with a 3D axis, such as bending, scaling, twisting and stretching. Moreover, AxDf can easily be combined with other existing deformation techniques.

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