Feature Line Extraction on Triangle Meshes in C++

Feature lines are among the most expressive descriptors of surface geometry. They reveal sharp bends, concentrated curvature, and the paths the eye naturally follows across a shape. In scientific visualization, CAD inspection, and non-photorealistic rendering, they offer a compact, meaningful summary of the underlying surface.

This article builds on the curvature-estimation pipeline developed in the previous installment. Using the MeshExplicit representation, we computed per-vertex principal curvatures and principal directions, producing a local geometric field that describes how the surface bends.

Here, we use that field to extract three important classes of feature lines:

• Ridges — regions where the maximum principal curvature \(k_{max}\) is strongly positive
• Valleys — regions where \(k_{max}\) is strongly negative
• Sharp creases — hard edges where adjacent faces meet at a large dihedral angle

Together, these feature types cover both smooth and piecewise-smooth geometry. Ridges and valleys appear naturally on anatomical models, scanned objects, and sculpted meshes, while creases capture the hard edges common in CAD models, mechanical parts, and stylized assets.

We continue using MeshExplicit, extended with a lightweight adjacency module. This keeps the implementation approachable and consistent with the curvature article. Later, when we introduce half-edge meshes and segmentation, we will revisit feature lines with more advanced tools; for now, MeshExplicit is more than sufficient.

By the end of this article, you will have a complete C++ implementation for extracting feature lines from any triangle mesh, ready for visualization or integration into downstream tools.

Feature lines are surface curves that reveal meaningful geometric behavior. Rather than arbitrary polylines, they are defined by specific mathematical conditions that identify curvature extremes, sharp transitions, or visually important structure.

2.1 Ridges and Valleys

Ridges and valleys are derived from the principal curvature field. At each vertex, the curvature estimation step provides four key quantities:

• \(k_{max}\) — maximum principal curvature
• \(k_{min}\) — minimum principal curvature
• \(d_{max}\) — principal direction associated with \(k_{max}\)
• \(d_{min}\) — principal direction associated with \(k_{min}\)

A ridge follows points where \(k_{max}\) is strongly positive and reaches a local extremum along its principal direction. In practical mesh processing, this is approximated with a simple threshold test.

• \(k_{max}\) is greater than a positive threshold
• \(k_{max}\) changes consistently along the direction \(d_{max}\)

A valley is the corresponding negative feature: \(k_{max}\) is strongly negative, indicating a concave curvature concentration.

For discrete triangle meshes, the article uses a robust and easy-to-implement criterion:

• Ridge vertex: \(k_{max} > {threshold}\)
• Valley vertex: \(k_{max} < -{threshold}\)

Once candidate vertices are identified, the extractor traces polylines by walking along the principal direction \(d_{max}\).

This simplified approach is robust, efficient, and well suited to practical geometry-processing workflows.

2.2 Sharp Creases

Sharp creases are detected independently of curvature. They occur where two adjacent faces meet at a large dihedral angle:

\[\theta =\arccos\left(\left\langle n_{0}^{\prime },\; n_{1}^{\prime }\right\rangle \right)\]

Here, the face normals are projected onto the plane orthogonal to the shared edge before the angle is measured. This makes the crease test more stable on irregular meshes.

If the angle \(\theta\) exceeds a user-defined threshold, such as 35°, the edge is classified as a crease. Connected crease edges are then assembled into crease polylines.

This method is especially effective for CAD models, mechanical parts, and meshes with deliberately hard edges.

2.3 Why Feature Lines Matters

Feature lines provide a compact, intuitive description of mesh structure. They are useful in several common workflows:

• Shape analysis — identifying the main geometric structure of a model
• Mesh segmentation — finding meaningful boundaries between regions
• Non-photorealistic rendering — drawing silhouettes, contours, and stylized edges
• Scientific visualization — emphasizing curvature patterns and structural features
• Quality inspection — detecting unwanted sharp edges, dents, or smoothing artifacts

In short, feature lines turn dense surface data into a readable geometric summary that supports analysis, visualization, and downstream processing.

3.1 Recap: MeshExplicit

The MeshExplicit structure keeps the mesh data direct and easy to inspect. It stores the core geometric information needed by the feature-line extractor:

• vertices — 3D positions
• faces — triangle index triples
• normals — per-face or per-vertex normal vectors
• curvature data — \(k_{max}, k_{min}, d_{max}, \text{ and } d_{min}\) from the previous article

This layout is intentionally simple: it is readable, easy to debug, and well suited to teaching, experimentation, and incremental development.

3.2 Why Add Adjacency?

Feature-line extraction depends on fast local neighborhood queries. Different feature types need different forms of connectivity:

• Ridges and valleys
  • find each vertex’s 1-ring neighbors
  • trace along the principal curvature direction
• Creases
  • find the faces adjacent to each edge
  • compute the dihedral angle between those faces
  • connect crease edges into ordered polylines

MeshExplicit was enhanced to include adjacency. We added VertexAdjacency that holds which vertices and which vertices are adjacent to each vertex. We also added FaceAdjacency to hold the three faces adjacent to each face. N ext we enhanced the EdgeExplicit struct to hold the two faces on its sides;

• VertexAdjacency.neighbor_vertices — each vertex’s 1-ring neighbors
• VertexAdjacency.incident faces — faces incident to each vertex
• edges — the unique list of mesh edges
• EdgeExplicit.incident_faces — the faces adjacent to each edge

The adjacency data is built once, then reused throughout ridge, valley, and crease extraction, or any other calculation.

3.3 Building the Adjacency Structure

The adjacency builder constructs the required connectivity in a single pass over the triangle faces. Its main responsibilities are:

• Deduplicate edges with a 64-bit packed key: (min(v0,v1) << 32) | max(v0,v1)
• Preserve deterministic ordering by storing edges in discovery order
• Handle boundaries by marking edges with one adjacent face as boundary
• Keep complexity linear: O(F) time and O(V + E) memory

With this functionality in place, MeshExplicit remains lightweight while still supporting all neighborhood operations required for feature-line extraction.

Feature lines are stored as polylines: ordered sequences of mesh vertices and corresponding 3D points. To keep the implementation modular, configurable, and easy to extend, we organize the data into three small structures.

4.1 FeatureLine: The Extracted Polyline

A FeatureLine represents one extracted ridge, valley, or crease. It stores the line in two complementary forms:

• Vertex indices — preserve mesh connectivity and allow the line to be related back to the original mesh.
• 3D points — provide ready-to-render positions and support later interpolation or smoothing.

Keeping both representations gives the extractor flexibility: the indices preserve topology, while the points make visualization and post-processing straightforward.

4.2 FeatureLineParameters: Extraction Controls

Feature-line extraction depends on a small set of user-controlled thresholds and limits. Grouping them into one parameter structure keeps the extractor clean and makes experiments easier to reproduce.

• Curvature thresholds — determine which vertices qualify as ridge or valley candidates.
• Dihedral-angle threshold — determines which edges are classified as creases.
• Minimum polyline length — filters out short, noisy fragments.
• Maximum tracing steps — limits how far ridge and valley tracing can travel from a seed vertex.
• Optional smoothing parameters — control any post-processing applied to extracted polylines.

Together, these controls make it easy to tune the extractor for smooth scans, CAD-like models, or stylized assets without changing the core algorithm.

4.3 FeatureLineExtractor: The Main Interface

FeatureLineExtractor is the central class in this article. It combines the mesh, curvature data, and extraction parameters into one workflow.

• MeshExplicit with adjacency — supplies geometry and neighborhood connectivity.
• CurvatureField — provides \(k_{max}, k_{min}, d_{max}, \text{and } d_{min}\) for ridge and valley detection.
• FeatureLineParameters — defines thresholds, tracing limits, and optional smoothing behavior.

The class exposes four public extraction methods:

• extractRidges() — extracts curvature ridges.
• extractValleys() — extracts curvature valleys.
• extractCreases() — extracts sharp dihedral-angle creases.
• extractAll() — returns ridges, valleys, and creases as one combined feature-line set.

Internally, the extractor separates the main algorithmic steps into focused helper routines:

• ridge and valley candidate tests
• principal-direction tracing
• dihedral-angle computation
• crease polyline assembly

This design keeps the public interface small while making the implementation easier to read, test, and extend in later sections.

Ridges and valleys are the primary feature lines on smooth surfaces. They show where curvature concentrates and how the surface bends along its principal directions. This section builds a practical extraction pipeline using the curvature fields from the previous article and the adjacency data introduced earlier.

The pipeline has three main stages:

1. Classify candidate vertices as ridges or valleys.
2. Trace polylines along the maximum-principal-curvature direction.
3. Assemble and filter the resulting feature lines to remove noise.

Each stage is simple in isolation, but together they produce a robust algorithm that works well on real triangle meshes.

5.1 Classifying Ridge and Valley Vertices

At each vertex, we use the maximum principal curvature \(k_{max}\) and its associated direction \(d_{max}\). The sign and magnitude of \(k_{max}\) determine whether the vertex is a ridge or valley candidate:

• Ridge vertex: \[k_{max} \gt {\tau}_{ridge}\]
• Valley vertex: \[k_{max} \lt -{\tau}_{valley}\]

The ridge and valley thresholds are user-controlled parameters. They help the extractor:

• suppress low-curvature noise
• avoid tracing from weak or unstable curvature estimates

On smooth geometry, \(k_{max}\) varies continuously; on triangle meshes, however, discretization can introduce local fluctuations. Thresholding keeps the extractor conservative and prevents noisy features from becoming lines.

In code, these criteria become two small boolean checks:

bool FeatureLineExtractor::isRidgeVertex(int v) const
{
    double k = m_curvature.kmax[v];
    return std::abs(k) > m_params.ridgeKappaThreshold && k > 0.0;
}

bool FeatureLineExtractor::isValleyVertex(int v) const
{
    double k = m_curvature.kmax[v];
    return std::abs(k) > m_params.valleyKappaThreshold && k < 0.0;
}

This intentionally conservative test traces only through vertices where the curvature signal is clearly significant.

5.2 Tracing Along the Principal Direction

After a ridge or valley seed is found, the extractor grows a polyline by walking through neighboring vertices in the principal direction d₁. This directional walk is the core of the ridge/valley algorithm.

auto traceOneSide = [&](int startVertex, bool forward) -> std::vector<int>
{
    std::vector<int> path;
    int current = startVertex;
    int steps = 0;

    while (steps < m_params.maxTraceSteps)
    {
        if (!isRidgeVertex(current)) break; // or isValleyVertex for valleys

        path.push_back(current);

        // Find the next vertex in the principal direction
        int next = findNextVertex(current, forward);
        if (next == -1) break; // No valid next vertex

        current = next;
        ++steps;
    }

    return path;
};

5.3 Assembling and Filtering Feature Lines

The final stage turns traced segments into a usable set of feature lines. It removes duplicates, filters out tiny fragments, and stores each accepted result as a FeatureLine.

std::vector<FeatureLine> FeatureLineExtractor::extractRidges()
{
    std::vector<FeatureLine> lines;
    std::vector<bool> visited(V, false);

    for (int v = 0; v < V; ++v)
    {
        if (!isRidgeVertex(v) || visited[v])
            continue;

        FeatureLine line = traceCurvatureLine(v, true);
        if (!line.empty())
        {
            for (int idx : line.vertices)
                visited[idx] = true;

            lines.push_back(std::move(line));
        }
    }

    return lines;
}

5.4 Summary

Ridge and valley extraction combines curvature thresholding with directional tracing. The algorithm proceeds as follows:

1. Identify ridge and valley candidates using \(k_{max}\) thresholds.
2. Trace forward and backward along principal direction \(d_{max}\).
3. Merge the two halves into one ordered polyline.
4. Discard short or noisy lines.
5. Use a visited mask to prevent duplicate extraction.

This method is conservative, easy to implement, and effective on both smooth and moderately noisy meshes.

Ridges and valleys describe curvature-driven features on smooth surfaces. Many meshes, however, also contain piecewise-smooth geometry: hard edges, chamfers, CAD-style corners, and manually sculpted creases. These features are not curvature extrema; they are discontinuities in the surface normal field.

To detect these discontinuities, crease extraction uses the dihedral angle between adjacent faces. Unlike ridge and valley tracing, it does not need curvature fields or principal directions. It works directly from mesh adjacency and face normals, making it fast, robust, and applicable to any triangle mesh.

6.1 Computing the Dihedral Angle

For an edge shared by two faces, the dihedral angle measures how sharply those faces meet along the edge. The calculation starts from the two adjacent face normals and produces an angle θ that describes crease sharpness.

A simple normal-to-normal comparison would compute:

\[\theta =\arccos⁡\left(\left\langle n_{0},\; n_{1}\right\rangle \right)\]

That direct comparison can be unstable because it does not isolate rotation around the shared edge. To measure crease sharpness more consistently, we first project both normals onto the plane orthogonal to the edge direction.

Let the edge be defined by its two endpoint vertices:

\[e=p_{1}-p_{0},\ \widehat{e}=\frac{e}{\parallel e\parallel }\]

Next, remove from each normal the component parallel to the edge direction:

\[n_{0}^{\prime }=n_{0}-\widehat{e}\text{\,}\left\langle n_{0},\; \widehat{e}\right\rangle\]

\[n_{1}^{\prime }=n_{1}-\widehat{e}\text{\,}\left\langle n_{1},\; \widehat{e}\right\rangle\]

Normalize the projected normals:

\[{\widehat{n}}_{0}^{\prime }=\frac{n_{0}^{\prime }}{\parallel n_{0}^{\prime }\parallel },\ {\widehat{n}}_{1}^{\prime }=\frac{n_{1}^{\prime }}{\parallel n_{1}^{\prime }\parallel }\]

Finally, compute the projected angle:

\[\theta =\arccos⁡\left(\left\langle {\widehat{n}}_{0}^{\prime },\; {\widehat{n}}_{1}^{\prime }\right\rangle \right)\]

The resulting angle is expressed in degrees and remains stable even on irregular meshes.

6.2 Marking Crease Edges

Once each dihedral angle is available, crease detection becomes a simple filtering pass over the edge list:

• iterate over every mesh edge
• compute its dihedral angle
• mark the edge as a crease when the angle exceeds the threshold

The marked edges form a graph on the mesh. The next step is to convert that graph into ordered polylines.

6.3 Building Crease Polylines

Crease edges usually form connected chains. To make them useful for rendering and downstream processing, the extractor assembles them into maximal polylines: the longest connected crease paths that can be traced without reusing an edge.

6.4 Summary

Crease extraction is a direct and robust process:

1. Compute dihedral angles for all mesh edges.
2. Mark edges whose angle exceeds the crease threshold.
3. Assemble connected crease edges into ordered polylines.
4. Filter out short or insignificant line fragments.
5. Convert accepted polylines into FeatureLine objects.

Unlike ridge and valley extraction, crease detection does not depend on curvature fields. It works directly from connectivity and face normals, making it broadly applicable and especially effective for CAD models, mechanical parts, and stylized assets.

So far, we have handled ridges, valleys, and creases as separate feature types, each with its own detection criteria and traversal strategy. In practice, these lines are most useful when combined. A unified feature-line set gives a compact summary of the mesh by bringing together smooth curvature-driven features and sharp normal discontinuities.

The FeatureLineExtractor class supports this workflow directly. It exposes dedicated methods for each feature type and a unified extractAll() method that gathers all extracted lines into one collection.

7.1 Why Use a Unified Interface?

A unified interface makes the extractor easier to use, easier to maintain, and easier to extend:

7.2 Implementing extractAll()

The unified method is intentionally small. It calls each extractor, reserves enough space for the combined output, and appends the results in sequence:

std::vector<FeatureLine> FeatureLineExtractor::extractAll()
{
    std::vector<FeatureLine> all;

    auto ridges  = extractRidges();
    auto valleys = extractValleys();
    auto creases = extractCreases();

    all.reserve(ridges.size() + valleys.size() + creases.size());
    all.insert(all.end(), ridges.begin(),  ridges.end());
    all.insert(all.end(), valleys.begin(), valleys.end());
    all.insert(all.end(), creases.begin(), creases.end());

    return all;
}

This method performs three simple steps:

1. Run the ridge, valley, and crease extractors independently.
2. Append their outputs into one vector.
3. Return the combined collection as FeatureLine objects.

No additional filtering or merging is applied here. Each feature type remains distinct, and the caller decides how to visualize, group, or post-process the results.

7.3 Example Workflow

A typical workflow loads the mesh, prepares normals and adjacency, computes curvature, configures thresholds, and then runs unified extraction:

MeshExplicit mesh = loadMesh("model.obj");
mesh.buildAdjacency();
mesh.computeNormals();

CurvatureField curvature = computeCurvature(mesh);

FeatureLineParameters params;
params.ridgeKappaThreshold   = 0.05;
params.valleyKappaThreshold  = 0.05;
params.dihedralAngleThreshold = 35.0;

FeatureLineExtractor extractor(mesh, curvature, params);

auto lines = extractor.extractAll();

The resulting lines vector contains all three feature types:

• ridge polylines
• valley polylines
• crease polylines

They are ready for visualization, analysis, segmentation, or any other downstream processing step.

Feature-line extraction is lightweight compared with curvature estimation, remeshing, or segmentation, but its runtime and stability still matter for large meshes, interactive visualization, and downstream tools. This section summarizes the algorithm’s complexity, practical performance, memory use, and robustness on noisy or irregular input.

8.1 Complexity Analysis

The full pipeline has three main computational stages:

1. Adjacency construction
2. Ridge and valley tracing
3. Crease detection and polyline assembly

Each stage has predictable behavior and scales linearly with mesh size.

8.2 Robustness Considerations

Feature line extraction is sensitive to mesh quality, curvature noise, and threshold selection. Below are the main robustness factors and how the algorithm handles them.

8.3 Summary

Feature line extraction is:

• linear time
• memory efficient
• robust on real meshes
• fast enough for interactive use

Its simplicity and performance make it an ideal complement to curvature estimation and a natural precursor to more advanced topics such as half edge meshes, segmentation, and non photorealistic rendering.

Feature-line extraction is a natural continuation of the curvature-estimation pipeline developed earlier in this series. By combining curvature fields, adjacency information, and simple geometric criteria, we can analyze and visualize the structure of triangle meshes in a compact, expressive way.

Ridges and valleys reveal how a surface bends, while creases highlight sharp geometric transitions. Together, these feature types summarize both smooth and piecewise-smooth shape behavior.

• adjacency construction is linear and fast
• ridge and valley tracing follows intuitive directional rules
• crease detection relies on stable normal projections
• unified extraction produces a clean, consistent output format

The approach remains practical because each component is simple, efficient, and easy to reason about:

The result is a feature-line extractor that works across a wide range of meshes, from smooth scanned geometry to CAD models with hard edges, and fits naturally into TheMeshProject ecosystem.

9.1 Why Move Beyond MeshExplicit?

This article also marks an architectural turning point. MeshExplicit remains useful for geometry storage, curvature estimation, and feature-line extraction, especially when paired with lightweight adjacency. However, more advanced operations require a richer representation.

Tasks such as mesh editing, segmentation, remeshing, and topological manipulation benefit from explicit edge orientation and more efficient local traversal. That leads directly to the next major topic in the series: half-edge mesh representation.

• explicit edge orientation
• constant-time traversal of local neighborhoods
• robust handling of boundaries and non-manifold configurations
• a foundation for mesh editing and segmentation algorithms

9.2 Next Topic: Half-Edge Mesh Representation

The half-edge structure provides the connectivity tools needed for more advanced mesh-processing algorithms:

It is the natural next step in the evolution of this mesh-processing framework.

9.3 Looking Ahead: Mesh Segmentation

After introducing half-edge meshes, the series will move into mesh segmentation. Segmentation uses geometric cues—such as curvature, feature lines, and dihedral angles—to divide a mesh into meaningful regions. The feature lines extracted in this article will provide important boundary cues for that process.

1. Curvature Estimation — robust per-vertex curvature fields using MeshExplicit.
2. Feature-Line Extraction — ridges, valleys, and creases using curvature and adjacency.
3. Half-Edge Mesh Representation — a more powerful mesh structure for advanced algorithms.
4. Mesh Segmentation — using curvature, feature lines, and half-edge traversal to identify meaningful regions.

This progression keeps the learning curve smooth while gradually introducing more advanced concepts, algorithms, and data structures.

9.4 Closing Remarks

Feature lines are more than polylines drawn on a surface. They are geometric fingerprints: they reveal structure, highlight transitions, and guide higher-level algorithms. With the tools developed in this article, readers now have a complete pipeline for extracting and visualizing ridges, valleys, and creases.

The next article will introduce the half-edge mesh, a key structure in modern geometry processing. From there, the series will move naturally into segmentation and other higher-level operations, continuing to build a cohesive, modular, and educational framework for mesh-based computation.