A Discrete Algorithm For Feature Line Detection On Mesh Surfaces

Mesh surfaces are fundamental shape representation tools for shape modeling and computer graphics. Ridge -valley line calculation is one of the basic problem as well as a hot topic in the fields of geometric processing and computer graphics. Ridge -valley lines serve as basis for surface segmentation, simplification, reconstruction and editing, etc. Feature lines also play important roles in non-photorealistic rendering, computer vision and computational geometry.Feature points on surfaces are often referred to those having local maximum principle curvature along one principle direction, then the judgement of feature points depends on at most fourth order derivative of the surface. However, high order derivatives for mesh surfaces are not always available immediately, they may be unstable or inaccuracy for discrete surfaces. From the traditional definition of feature points we propose new metric measuring the local sharpness of every mesh vertex. The new sharpness metric is defined as the ratio of mean curvature at a vertex and the mean value of normal curvatures at other neighboring vertexes. Then the sign judgement of second order derivatives of curvatures is transformed into the range estimation of curvature ratios. Moreover, the curvature ratios can be further simplified as the ratio of vector projections. When all candidate feature points have been detected, feature lines can be extracted by clustering, connecting, smoothing operations on the surface.The ridge valley line extraction algorithm consists of five main steps:1. Calculate sharpness metric for each vertex on the surface.2. Choose candidate feature points for all feature regions and cluster them.3. Extract initial rough feature line on each feature region by minimum spanning treealgorithm.4. Smooth the initial feature lines.5. Divide each feature line into ridge or valley types.All examples we have experimented show that the new feature line extraction algorithm owns the benefits of simplicity, robustness and efficiency. The method can be used for feature line detection on freeform surfaces as well as CAD models with C~1 discontinuous or C~1 continuous but C~2 discontinuous features.