Implicit fairing of irregular meshes using diffusion and curvature flow

Mathieu DesbrunMark MeyerPeter SchröderAlan H. Barr

article1999SIGGRAPH1,828 citations

Introduces unconditionally stable implicit integration schemes and discrete curvature flow operators for irregular triangle meshes, enabling fast, distortion-free surface smoothing with volume preservation and geometric constraints.

Listen

Generating high-fidelity 3D digital models from real-world range scanning and photography often produces irregular, noisy surface meshes. Existing explicit smoothing techniques suffer from severe step-size limits, high computational overhead on large datasets, object shrinkage, and geometric distortions caused by irregular triangle spacing. The article develops and evaluates an efficient, unconditionally stable mathematical framework for irregular mesh fairing that removes unwanted noise while preserving intrinsic geometric features and volume.

The authors evaluated their approach by integrating backward Euler implicit numerical solvers with new geometric operators on standard irregular 3D meshes ranging from 12,000 to 290,000 faces. They compared this implicit approach against traditional explicit methods and evaluated both a scale-dependent Laplacian operator and an intrinsic curvature flow operator derived from discrete differential geometry.

The analysis yielded four major findings. First, implicit integration achieves unconditional numerical stability, allowing substantially larger time steps and reducing computation time by roughly 60% compared to explicit integration on high-smoothing tasks. Second, the scale-dependent Laplacian accounts for varying edge lengths and eliminates artificial bumps and distortions that standard operators introduce on irregular meshes. Third, the curvature flow operator successfully drives smoothing based solely on local mean curvature, completely preventing vertices from sliding across flat areas or distorting spherical regions. Fourth, an automated post-step scaling step preserves exact 3D volume in linear time, eliminating object shrinkage without requiring manual parameter tuning.

These findings indicate that digital geometry pipelines can process large, scanned datasets significantly faster with substantially higher visual and geometric fidelity. Practitioners no longer need to compromise between numerical stability and processing speed or manually tune anti-shrinkage parameters. For deployment, teams should apply the scale-dependent Laplacian when the objective is to simultaneously smooth shapes and regularize triangle sizes, and deploy the curvature flow operator when only the underlying geometry should be filtered without altering mesh sampling.

The methods rely on local linearizations where edge lengths and angles are treated as constant during each solver iteration, which requires care when handling degenerate zero-area triangles. Overall confidence in the performance and stability gains is high across standard closed and open meshes, though full-scale production adoption could benefit from incorporating multigrid solvers to accelerate convergence on exceptionally massive meshes.

California Institute of Technology 3d graphics adaptive algorithms feature space Curvature Implicit Mesh

Desbrun et al (1999).pdf

Paper: A signal processing approach to fair surface design, Gabriel Taubin (1995). Introduces explicit low-pass geometric filtering and non-shrinking fairing on polyhedral surfaces, establishing the foundational discrete Laplacian formulation that this paper improves with implicit integration and curvature flow.
Paper: Large steps in cloth simulation, D. Baraff et al. (1998). Pioneers the use of implicit numerical integration and large stable time-stepping for stiff differential equations on triangle meshes in computer graphics.
Paper: Scale-Space Filtering, A. Witkin (1983). Formulates continuous diffusion and Gaussian scale-space filtering, providing the conceptual foundation for geometric multiscale smoothing and feature diffusion.
Paper: Shape Modeling with Front Propagation: A Level Set Approach, R. Malladi et al. (1995). Introduces curvature flow and front-propagation techniques for shape evolution and smoothing, which directly motivate the intrinsic curvature-flow fairing operators used on meshes.
Paper: Surface reconstruction from unorganized points, Hugues Hoppe et al. (1992). Details the construction of irregular triangle meshes from raw scan points, representing the exact type of noisy real-world geometry targeted by this fairing method.
Paper: A volumetric method for building complex models from range images, B. Curless et al. (1996). Exemplifies volumetric reconstruction from range data, producing dense, noisy polygonal surfaces that require feature-preserving fairing and smoothing.

Paper: Geometric Deep Learning: Going beyond Euclidean data, Michael M. Bronstein et al. (2016). Surveys geometric deep learning architectures that generalize discrete Laplacian operators, diffusion processes, and non-Euclidean manifold operations to neural network pipelines.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). Applies discrete graph Laplacians and heat diffusion operators to manifold learning, non-linear dimensionality reduction, and spectral data clustering.
Paper: Poisson image editing, P. Pérez et al. (2003). Builds upon discrete differential operators and boundary-constrained elliptic PDE solvers to perform guided Poisson interpolation and seamless editing.
Paper: Image inpainting, Marcelo Bertalmio et al. (2000). Extends continuous PDE-driven diffusion and curvature flow mechanisms to digital inpainting and geometric image structure propagation.
Paper: Reconstruction and representation of 3D objects with radial basis functions, J. Carr et al. (2001). Provides a smooth implicit continuous surface representation for noisy point clouds that contrasts with and complements discrete irregular mesh fairing.

Cover for Implicit fairing of irregular meshes using diffusion and curvature flow

Abstract

In this paper, we develop methods to rapidly remove rough features from irregularly triangulated data intended to portray a smooth surface. The main task is to remove undesirable noise and uneven edges while retaining desirable geometric features. The problem arises mainly when creating high-fidelity computer graphics objects using imperfectly-measured data from the real world.

Our approach contains three novel features: an implicit integration method to achieve efficiency, stability, and large time-steps; a scale-dependent Laplacian operator to improve the diffusion process; and finally, a robust curvature flow operator that achieves a smoothing of the shape itself, distinct from any parameterization. Additional features of the algorithm include automatic exact volume preservation, and hard and soft constraints on the positions of the points in the mesh.

We compare our method to previous operators and related algorithms, and prove that our curvature and Laplacian operators have several mathematically-desirable qualities that improve the appearance of the resulting surface. In consequence, the user can easily select the appropriate operator according to the desired type of fairing. Finally, we provide a series of examples to graphically and numerically demonstrate the quality of our results.

Topics

3d graphics adaptive algorithms feature space optimization problems parameterization

Keywords

Curvature Implicit Mesh Using Meshes Diffusion Fairing Operator Smoothing Implicit Fairing

2 Implicit fairing
1 Introduction
2.1 Notation and definitions
2.2 Diffusion equation for mesh fairing
2.3 Time-shifted evaluation
2.4 Solving the sparse linear system
2.5 Interpretation of the implicit integration
2.5.1 Signal processing
2.5.2 Mass-spring network
2.6 Filter improvement
2.7 Constraints
2.8 Discussion
3 Automatic anti-shrinking fairing
3.1 Volume computation
3.2 Exact volume preservation
3.3 Discussion
4 An accurate diffusion process
4.1 Inadequacy of the umbrella operator
4.2 Simulation of the 1D heat equation
4.3 Extension to 3D
5 Curvature flow for noise removal
5.1 Diffusion vs. curvature flow
5.2 Curvature normal calculation
5.3 Boundaries
5.4 Implementation
5.5 Normalized version of the curvature operator
5.6 Comparison of results
6 Discussion and conclusion
Acknowledgements
References
Appendix A Preconditioned Bi-Conjugate Gradient
A.1 Preconditioning
A.2 Convergence criterion
A.3 Memory requirements
B Curvature normal approximation

Knowls

Knowl 1 — Implicit Backward Euler Integration for Mesh Fairing
model/method
Surface smoothing via diffusion evolves vertex coordinates $X = (x_1, \dots, x_N)^T$ according to the heat-like partial differential equation $\frac{\partial X}{\partial t} = \lambda L(X)$ , where $L$ is a spatial discrete Laplacian operator and $\lambda > 0$ is the diffusion coefficient.

While explicit Euler integration $X^{n+1} = (I + \lambda dt L) X^n$ requires very small time steps for stability (typically $\lambda dt < 1$ for uniform operators, or $dt \le \frac{\min(|e|)^2}{2\lambda}$ based on the minimum edge length $|e|$ ), implicit (backward Euler) integration evaluates the Laplacian at the future time step:

$(I - \lambda dt L) X^{n+1} = X^n$

Because the linear system matrix $A = I - \lambda dt L$ is sparse (averaging six non-zero entries per row for triangular meshes), it is solved iteratively using the Preconditioned Bi-Conjugate Gradient (PBCG) algorithm with a diagonal Jacobi preconditioner $\tilde{A}_{ii} = 1/A_{ii}$ and stopping condition $\|A X^{n+1} - X^n\| < \varepsilon \|X^n\|$ .

In the frequency domain for a 1D spatial frequency $\omega$ , the explicit update acts as a Finite Impulse Response (FIR) filter with transfer function $H_{\text{explicit}}(\omega) = 1 - \lambda dt \omega^2$ , which becomes unstable for large time steps. The implicit scheme acts as an Infinite Impulse Response (IIR) filter with transfer function:

$H_{\text{implicit}}(\omega) = \frac{1}{1 + \lambda dt \omega^2}$

Since $H_{\text{implicit}}(\omega) \in [0, 1]$ for all $\omega$ , the implicit smoothing is unconditionally stable for arbitrarily large time steps $\lambda dt$ , performing global filtering in a single solve.
Knowl 2 — Discrete Mean Curvature Normal via Area Variation
theoretical result
The mean curvature normal vector $\kappa \mathbf{n}$ of a surface (where $\kappa = \frac{\kappa_1 + \kappa_2}{2}$ is the mean curvature and $\mathbf{n}$ is the unit surface normal) equals the normalized gradient of local surface area $A$ with respect to spatial position:

$\frac{\nabla_{x_i} A}{2 A} = \kappa_i \mathbf{n}_i$

For a triangular mesh vertex $x_i$ , letting $A$ denote the total area of the 1-ring adjacent faces $A = \sum_{j \in N_1(i)} A_j$ , differentiation of $A$ with respect to vertex coordinates $x_i$ yields the discrete curvature normal formula:

$-\kappa_i \mathbf{n}_i = \frac{1}{4 A} \sum_{j \in N_1(i)} (\cot \alpha_j + \cot \beta_j)(x_j - x_i)$

where $N_1(i)$ denotes the 1-ring neighbors of $x_i$ , and $\alpha_j, \beta_j$ are the two angles opposite to the shared edge $e_{ij} = (x_i, x_j)$ in the two adjacent triangles containing that edge.

For any vertex lying in the same plane as its 1-ring neighbors, in-plane movement does not change the local area to first order, which achieves a local minimum. Consequently, $\nabla_{x_i} A = 0$ on flat regions regardless of valence, edge lengths, or triangle aspect ratios, ensuring that flat regions produce a zero curvature normal.
Knowl 3 — Curvature Flow for Intrinsic Mesh Noise Removal
model/method
Curvature flow smooths a surface by displacing each point along its outward normal $\mathbf{n}$ with a speed equal to the negative mean curvature $\kappa$ :

$\frac{\partial x_i}{\partial t} = -\kappa_i \mathbf{n}_i$

Unlike Laplacian diffusion operators whose updates contain tangential components that cause vertices to drift across the surface and alter mesh parameterization, curvature flow depends solely on intrinsic geometry. On planar regions where $\kappa = 0$ , vertices remain stationary without tangential sliding, while spherical geometries maintain constant shape.

Using the discrete curvature normal matrix $K$ (where row $i$ computes $-\kappa_i \mathbf{n}_i$ ), the flow is integrated implicitly via:

$(I - \lambda dt K) X^{n+1} = X^n$

Because edge lengths and angles change slowly within a single integration step, the coefficients of $K$ are computed from $X^n$ and held constant during the linear solver iterations (PBCG). Any triangle with zero area is skipped during matrix assembly to prevent division by zero.
Knowl 4 — Scale-Dependent Discrete Laplacian Operator
model/method
The standard uniform umbrella operator $L(x_i) = \frac{1}{m} \sum_{j \in N_1(i)} (x_j - x_i)$ (where $m = \#N_1(i)$ ) assumes unit edge lengths and equal angles, confounding spatial frequency with mesh sampling density and introducing distortion on irregularly sampled meshes.

To account for irregular triangulation, the scale-dependent umbrella operator weights each neighbor difference inversely by edge length:

$L(x_i) = \frac{2}{E_i} \sum_{j \in N_1(i)} \frac{x_j - x_i}{|e_{ij}|}, \quad \text{with } E_i = \sum_{j \in N_1(i)} |e_{ij}|$

where $|e_{ij}| = \|x_j - x_i\|$ is the Euclidean length of edge $e_{ij}$ . When all incident edges have equal length, this operator reduces to the uniform umbrella operator.

In implicit fairing, the coefficients of the matrix $A = I - \lambda dt L$ are initialized from current edge lengths and held constant during Preconditioned Bi-Conjugate Gradient (PBCG) iterations.
Knowl 5 — Exact Volume Preservation for Anti-Shrinking Mesh Fairing
model/method
Pure diffusion and curvature flow contract geometry, shrinking the total volume of closed meshes. To prevent shrinkage automatically without requiring parameter tuning, the original volume is maintained as an exact invariant.

For a closed triangular mesh with faces $k \in \{1, \dots, N_f\}$ and vertex coordinates $(x_1^k, x_2^k, x_3^k)$ , the enclosed volume is computed in $O(N_f)$ time by summing oriented tetrahedra connected to the origin:

$V = \frac{1}{6} \sum_{k=1}^{N_f} g_k \cdot N_k$

where $g_k = \frac{1}{3}(x_1^k + x_2^k + x_3^k)$ is the centroid and $N_k = (x_2^k - x_1^k) \times (x_3^k - x_1^k)$ is the face area normal.

After an integration step produces an evolved mesh with volume $V_n$ , all vertex positions are rescaled by:

$\beta = \left(\frac{V_0}{V_n}\right)^{1/3}$

where $V_0$ is the initial volume. Multiplying all vertex coordinates by $eta$ restores the exact original volume. In the frequency domain, this uniform scaling acts as an amplification that counteracts the low-frequency attenuation of diffusion while preserving high-frequency smoothing.
Knowl 6 — Higher-Order Implicit Fairing with the Squared Laplacian Operator
model/method
Minimizing the thin-plate surface functional leads to fairing using the bi-Laplacian (squared Laplacian) operator $L^2(X) = L \circ L(X)$ .

When integrated implicitly, higher powers of the Laplacian yield frequency transfer functions that approximate an ideal low-pass filter:

$(I + \lambda dt L^2) X^{n+1} = X^n$

The transfer function of the implicit bi-Laplacian filter is $H(\omega) = \frac{1}{1 + \lambda dt \omega^4}$ . Compared to the first-order implicit filter $1/(1 + \lambda dt \omega^2)$ , $L^2$ significantly reduces the attenuation of low and mid frequencies while maintaining strong high-frequency suppression.

Although $L^3$ and $L^4$ provide even steeper cutoffs, they expand the neighborhood stencil beyond the 2-ring, reducing matrix sparsity and increasing solver computation time without substantial visual improvement. Thus, $L^2$ represents the optimal trade-off between computational cost and filtering fidelity.

Knowl 7 — PBCG Iteration Count and Runtime for Implicit Fairing

data/table

Implicit mesh fairing using a Preconditioned Bi-Conjugate Gradient (PBCG) solver converges in few iterations across large irregular meshes, outperforming explicit integration for large time steps $\lambda dt$ .

Mesh	Nb of faces	$\lambda dt = 10$	$\lambda dt = 100$
Horse	42,000	8 iterations (2.86s)	37 iterations (12.6s)
Dragon	42,000	8 iterations (2.98s)	39 iterations (13.82s)
Isis	50,000	9 iterations (3.84s)	37 iterations (15.09s)
Bunny	66,000	7 iterations (4.53s)	35 iterations (21.34s)
Buddha	290,000	5 iterations (13.78s)	28 iterations (69.93s)

These benchmarks were measured on an SGI High Impact Indigo2 (175 MHz R10000 CPU, 128 MB RAM). Because one iteration of PBCG requires only slightly more computation than a single explicit Euler integration step, an implicit solve at $\lambda dt = 100$ requiring approximately 35 PBCG iterations takes ~60% less time than explicit Euler integration, which requires 100 separate steps due to the $\lambda dt \le 1$ stability limit.

Knowl 8 — Positional Constraints and Boundary Handling in Implicit Fairing
model/method
Implicit fairing supports both hard constraints, soft constraints, and boundary conditions during smoothing:
1. Hard Constraints: Vertices can be locked in place by enforcing $L(x_i) = 0$ in the linear system, or by zeroing out their update directions during PBCG solver iterations. Vertices can also be constrained to move only along a line or within a plane.
2. Soft Constraints: A per-vertex scalar factor $s_i \in [0, 1]$ is assigned to modulate the local diffusion coefficient $\lambda_i = s_i \lambda$ , enabling interactive spatial attenuation of smoothing over selected regions.
3. Boundaries on Non-Closed Meshes: For boundary vertices where mean curvature is undefined, 1D curve smoothing is applied along the boundary edge network using the 1D scale-dependent operator restricted to the two adjacent boundary neighbors. Alternatively, a virtual central vertex at the boundary barycenter can be connected to all boundary vertices to close the local neighborhood topology.
When combined with global volume rescaling $\beta = (V_0/V_n)^{1/3}$ , hard constraints maintain their relative spatial configuration rather than absolute coordinates.
Knowl 9 — Normalized Discrete Curvature Operator for Explicit Integration
equation
To enable explicit Euler time integration of curvature-based fairing with normalized time steps ( $dt \le 1$ ), the discrete curvature normal can be normalized so that its eigenvalues remain within $[-1, 0]$ :

$(\kappa \mathbf{n})_{\text{normalized}} = \frac{1}{\sum_{j \in N_1(i)} (\cot \alpha_j^l + \cot \alpha_j^r)} \sum_{j \in N_1(i)} (\cot \alpha_j^l + \cot \alpha_j^r)(x_i - x_j)$

where $N_1(i)$ is the 1-ring neighborhood of vertex $x_i$ , and $\alpha_j^l, \alpha_j^r$ are the two angles opposite to edge $e_{ij} = (x_i, x_j)$ in the adjacent left and right triangles sharing $e_{ij}$ .

Coverage note — None was omitted; all key contributions—including implicit integration, cotangent curvature normal derivation, curvature flow, scale-dependent Laplacian, exact volume preservation, higher-order filtering, constraints, boundary handling, and empirical benchmarks—are fully covered.

References

1.Alan H. Barr. The Einstein Summation Notation: Introduction and Extensions. In SIGGRAPH 89 Course notes #30 on Topics in Physically-Based Modeling, pages J1–J12, 1989.
2.David Baraff and Andrew Witkin. Large Steps in Cloth Simulation. In SIGGRAPH 98 Conference Proceedings, pages 43–54, July 1998.
3.Brian Curless and Marc Levoy. A Volumetric Method for Building Complex Models from Range Images. In SIGGRAPH 96 Conference Proceedings, pages 303–312, 1996.
4.Tom Duchamp, Andrew Certain, Tony DeRose, and Werner Stuetzle. Hierarchical computation of PL harmonic embeddings. Technical report, University of Washington, July 1997.
5.Mathieu Desbrun and Marie-Paule Cani-Gascuel. Active Implicit Surface for Computer Animation. In Graphics Interface (GI’98) Proceedings, pages 143–150, Vancouver, Canada, 1998.
6.Bengt Fornberg. Generation of Finite Difference Formulas on Arbitrarily Spaced Grids. Math. Comput., 51:699–706, 1988.
7.Koji Fujiwara. Eigenvalues of Laplacians on a closed riemannian manifold and its nets. In Proceedings of AMS 123, pages 2585–2594, 1995.
8.Igor Guskov, Wim Sweldens, and Peter Schr¨oder. Multiresolution Signal Processing for Meshes. In SIGGRAPH 99 Conference Proceedings, 1999
9.Leif Kobbelt, Swen Campagna, Jens Vorsatz, and Hans-Peter Seidel. Interactive Multi-Resolution Modeling on Arbitrary Meshes. In SIGGRAPH 98 Conference Proceedings, pages 105–114, July 1998.
10.Leif Kobbelt. Discrete Fairing. In Proceedings of the Seventh IMA Conference on the Mathematics of Surfaces ’97, pages 101–131, 1997.
11.S. Lien and J. Kajiya. A Symbolic Method for Calculating the Integral Properties of Arbitrary Nonconvex Polyhedra. IEEE CG&A, 4(9), October 1984.
12.Roger B. Milne. An Adaptive Level-Set Method. PhD Thesis, University of California, Berkeley, December 1995.
13.Ulrich Pinkall and Konrad Polthier. Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics, 2(1):15–36, 1993.
14.William Press, Saul Teukolsky, William Vetterling, and Brian Flannery. Numerical Recipes in C, second edition. Cambridge University Press, New York, USA, 1992.
15.James A. Sethian. Level-Set Methods: Evolving Interfaces in Geometry, Fluid Dynamics, Computer Vision, and Material Science. Cambridge Monographs on Applied and Computational Mathematics, 1996.
16.Gabriel Taubin. A Signal Processing Approach to Fair Surface Design. In SIGGRAPH 95 Conference Proceedings, pages 351–358, August 1995.
17.Demetri Terzopoulos. The Computation of Visible-Surface Representations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(4), July 1988.
18.Willian Welch and Andrew Witkin. Free-form shape design using triangulated surfaces. In SIGGRAPH 94 Conference Proceedings, pages 247–256, July 1994.

Citation

MLA

Desbrun, M., et al. “Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow”. Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '99, 1999, pp. 317–24, https://doi.org/10.1145/311535.311576.

APA

Desbrun, M., Meyer, M., Schröder, P., & Barr, A. H. (1999). Implicit fairing of irregular meshes using diffusion and curvature flow. Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '99, 317–324. https://doi.org/10.1145/311535.311576

Chicago

Desbrun, M., M. Meyer, P. Schröder, and A. H. Barr. 1999. “Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow”. Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '99, 317–24. https://doi.org/10.1145/311535.311576.

Harvard

Desbrun, M. et al. (1999) “Implicit fairing of irregular meshes using diffusion and curvature flow”, Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH '99. ACM Press, pp. 317–324. Available at: https://doi.org/10.1145/311535.311576.

Vancouver

1. Desbrun M, Meyer M, Schröder P, Barr AH (1999) Implicit fairing of irregular meshes using diffusion and curvature flow. In: Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH '99. ACM Press, pp 317–324

BibTeX

@inproceedings{Desbrun_1999, series={SIGGRAPH ’99}, title={Implicit fairing of irregular meshes using diffusion and curvature flow}, url={http://dx.doi.org/10.1145/311535.311576}, DOI={10.1145/311535.311576}, booktitle={Proceedings of the 26th annual conference on Computer graphics and interactive techniques  - SIGGRAPH ’99}, publisher={ACM Press}, author={Desbrun, Mathieu and Meyer, Mark and Schröder, Peter and Barr, Alan H.}, year={1999}, pages={317–324}, collection={SIGGRAPH ’99} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Implicit fairing of irregular meshes using diffusion and curvature flow

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Implicit Backward Euler Integration for Mesh Fairing

Knowl 2 — Discrete Mean Curvature Normal via Area Variation

Knowl 3 — Curvature Flow for Intrinsic Mesh Noise Removal

Knowl 4 — Scale-Dependent Discrete Laplacian Operator

Knowl 5 — Exact Volume Preservation for Anti-Shrinking Mesh Fairing

Knowl 6 — Higher-Order Implicit Fairing with the Squared Laplacian Operator

Knowl 7 — PBCG Iteration Count and Runtime for Implicit Fairing

Knowl 8 — Positional Constraints and Boundary Handling in Implicit Fairing

Knowl 9 — Normalized Discrete Curvature Operator for Explicit Integration

References

Citation

BibTeX

Access the Paper