A predictor-corrector scheme for approximating signed distances using finite element methods

Amina El Bachari, Johann Rannou, Vladislav A. Yastrebov, Pierre Kerfriden, Susanne Claus · 2025

Read A predictor-corrector scheme for approximating signed distances using finite element methods by Amina El Bachari, Johann Rannou, Vladislav A. Yastrebov, Pierre Kerfriden, Susanne Claus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-17830.txt.

Introduction

Amina El Bachari and co-authors present a two-step method for computing signed distance maps to complex boundaries, in a 2025 paper. Such maps say how far each point sits from a boundary, and on which side. They feed many simulation tools, but sharp or flat starting shapes can break older methods.

The first step solves a smooth spread problem to get a good first guess. The second step corrects that guess by minimizing against the classic distance equation. Tests cover plain shapes plus harder ones, such as star-shaped regions and three-dimensional rings. The authors report that the method stays accurate, fast, and robust across this range of cases.

Catalog record

CREATORAmina El Bachari, Johann Rannou, Vladislav A. Yastrebov, Pierre Kerfriden, Susanne Claus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-17830

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A predictor-corrector scheme for approximating signed distances using finite element methods Amina El Bachari, Johann Rannou, Vladislav A. Yastrebov, Pierre Kerfriden, Susanne Claus Abstract In this article, we introduce a finite element method designed for the robust computation of approximate signed distance functions to arbitrary boundaries in two and three dimensions. Our method employs a novel prediction-correction approach, involving first the solution of a linear diffusion-based prediction problem, followed by a nonlinear minimization-based correction problem associated with the Eikonal equation. The prediction step efficiently generates a suitable initial guess, significantly facilitating convergence of the nonlinear correction step. A key strength of our approach is its ability to handle complex interfaces and initial level set functions with arbitrary steep or flat regions, a notable challenge for existing techniques. Through several representative examples, including classical geometries and more complex shapes such as star domains and three-dimensional tori, we demonstrate the accuracy, efficiency, and robustness of the method, validating its broad applicability for reinitializing diverse level set functions. 1 Introduction The computation of signed distance functions (SDFs) plays a critical role in numerous computational methods, particularly within computational mechanics, computer graphics, and numerical simulations involving interface capturing and tracking [ 21 , 24 ] . Accurate and efficient methods to compute SDFs are crucial for applications such as shape optimization [ 2 , 13 ] , multi-phase flow [ 27 , 16 , 11 ] or image processing [ 28 , 18 ] . The signed distance function is typically defined as the solution of the Eikonal equation, a nonlinear partial differential equation whose numerical solution poses significant computational challenges [ 25 ] . Traditional methods to compute SDFs generally fall into two main categories: geometric algorithms such as fast marching methods [ 9 , 24 , 23 , 17 ] and fast sweeping methods [ 29 , 32 , 22 ] which can be highly efficient but are challenging to parallelize [ 26 ] , extend to unstructered grids [ 8 ] , [ 15 ] or to higher-order geometric representations. PDE-based methods, which solve variants of the Eikonal equation directly using finite element or finite difference discretizations, offer greater flexibility for complex domains but require careful treatment to ensure stability and accuracy [ 21 ] . In this article, we propose a PDE-based finite element approach characterized by a novel prediction-correction strategy. Our method begins with a linear diffusion-based prediction step, efficiently providing a robust initial approximation of the SDF. This is subsequently refined through a nonlinear correction step formulated as a minimization problem derived from the Eikonal equation. This minimization based formulation of the Eikonal equation has first been used in [ 18 ] for the reinitialization of a level set function. As the original method struggles in regions with a gradient norm of the level set function close to zero several modifications of the original problem have been proposed in [ 6 , 31 ] which modify the equations for small norms of the gradient of the signed distance functions. However, these changes are not consistent with the original problem of solving the Eikonal equation. In this article, we propose to leave the minimization based problem unchanged. Instead, we focus on formulating a prediction problem to provide an ideal initial guess to the minimization based formulation of the Eikonal problem. We will demonstrate that this yields a robust predictor-corrector method that can handle initial functions with arbitrary steep and flat regions for complex two- and three-dimensional geometries. We demonstrate the use of our method in the context of meshes that fit to the boundary of the complex geometry to which we want to compute the signed distance function as well as the case in which the boundary is immersed in a background finite element grid. In the case of immersed geometries, we reconstruct the interface and enforce Dirichlet conditions weakly on the unfitted interface using cut integration [ 7 ] . The implementation of our method is done in FEniCSx [ 5 ] and CutFEMx [ 10 ] . We validate our method through extensive numerical experimentation, including classical benchmarks such as circles and tori, as well as challenging test cases featuring noisy data and non-smooth boundaries. Our results highlight the accuracy, computational efficiency, and robustness of the approach, demonstrating its potential as a versatile and reliable tool for reinitializing level set functions in diverse applications within computational mechanics and engineering. The remainder of this article is organized as follows. In Section 2 , we introduce the mathematical formulation of the signed distance function and corresponding signed distance problem. In Section 3 we discuss the minimization-based Eikonal problem and introduce its finite element formulation. Section 4 presents the prediction-correction algorithm and its finite element discretization. In Section 5 , we validate our predictor-corrector scheme on a range of numerical experiments in both two- and three-dimensions. 2 Level set method 2.1 Level sets and signed distance functions. Let’s consider fixed domain D\subset\mathbb{R}^{n} containing implicitly defined domain \Omega . A level set function, \phi:D\rightarrow\mathbb{R} , is used to represent \Omega\subset D such that: \begin{cases}\phi(x)<0&\text{ if }x\in\Omega,\\ \phi(x)=0&\text{ if }x\in\Gamma,\\ \phi(x)>0&\text{ if }x\in D\setminus\left\{{\Omega\cup\Gamma}\right\}\end{cases} (1) with \Gamma=\left\{x\in D\text{ such that }x\in\partial\Omega\setminus\partial D\right\} . A level set function with signed distance property with respect to \phi(x)=0 is defined as: \displaystyle\phi(x)= \displaystyle\begin{cases}-d\left(x,\Gamma\right)&\text{ if }x\in\Omega,\\ d\left(x,\Gamma\right)&\text{ if }x\in D\setminus\left\{{\Omega\cup\Gamma}\right\},\end{cases} (2) where d is the euclidean distance function defined as: \displaystyle d\left(x,\Gamma\right)=\underset{y\in\Gamma}{\inf}d\left(x,y\right). (3) If the domain \Omega\subset\mathbb{R}^{n} has a piecewise smooth boundary, then the signed distance function to domain boundary \Gamma is differentiable almost everywhere, and the equivalent signed distance property (SDP) holds \left|\nabla\phi\right|=1\text{, almost every where in }D, (4) where |\cdot| denotes the Euclidean norm, defined by |x|=\left(\sum_{i=1}^{n}x_{i}^{2}\right)^{1/2}, with x=(x_{1},x_{2},\ldots,x_{n})\in\mathbb{R}^{n} . The normal to the contour lines of locally smooth level set function is given by \bfn_{\phi}=\frac{\nabla\phi}{\left|\nabla\phi\right|}, (5) which can be simplify as \bfn_{\phi}=\nabla\phi , almost every where, for a level set function with signed distance property. 2.2 Need for approximate redistancing In general, the level set method is employed in the context of moving boundary problems. In this framework, an advection equation is used to advect the domain boundary \Gamma in the normal direction \theta=v\bfn_{\phi} . Regardless of the method used for the advection of the level set, the signed distance property |\nabla\phi|=1 is not preserved. Nevertheless, maintaining the signed distance property is essential, as it greatly facilitates the following aspects: (i) to compute normals on \Gamma , \bfn_{\phi}=\nabla\phi/|\nabla\phi| , which becomes inaccurate when |\nabla\phi|\rightarrow 0 ; (ii) for the level set advection, because the term \theta\cdot\nabla\phi=v\left|\nabla\phi\right| becomes difficult to stabilize for steep \phi ; (iii) to reconstruct the interface by linear interpolation, which becomes inaccurate for flat \phi as too small change in \phi values yields a large difference in determining the location of \Gamma . The use of the level set method for numerous moving boundary problem (shape optimization, fluid simulation, propagation phenomena) has led to active research on reinitialization methods to address the diverse needs associated with each application. The need for redistancing extends beyond moving boundary value problems. For instance, solving partial differential equations on domains derived from the semantic segmentation of an image can be made more efficient by redefining the domain’s contour using the zero level-set, rather than

Read the complete text