Second order meshes interpolation error

I simulate ALE FSI problem in 3D with 2nd order meshes. In my framework, a remeshing process is needed to interpolate data from the old mesh to the new mesh in every several steps. Here a strange interpolation result is presented and seek for help on solving this issue.

To demonstrate this issue, two test sets of meshes (mesh1_order[1|2].bp and mesh2_order[1|2].bp) are provided – https://drive.google.com/file/d/1YjC6tCtiJaxQ7Sg7FVakZ8or23QNNMAc/view?usp=sharing. The MWE below interpolates function f1 on mesh1 to f2 on mesh2. The problem occurs on the interpolated result f2.

In the mesh.bp files, mesh and cell tags are stored. The mesh is a cubic domain ranging from [-1, -1, -1] to [1, 1, 1]. A sphere with radius 0.5 is centered at [0, 0, 0]. The cell tags for the sphere and the rest part are 0 and 1 to represent solid and fluid tags, respectively.

The result can be found in the attached figure. I tested it on DOLFINx v0.9.0. The original function f1 is all 0 around and with [0, 1] value in the spherical solid part. To compare the interpolation performance, 1st order and 2nd order meshes are used. I can sense that the wiggling result in 1st order (figure g,h) is due to numerical error with lower resolution on the sphere. But it seems a mistake is in 2nd order result (figure c,d) as [-0.12, 0] values on f2 is computed in the halo region of the sphere. I have no clue why there is a miscalculation on the second order meshes interpolation.

MWE:

# interpolation.py
# Run with `mpirun -n 3 python interpolation.py`
# Test on DOLFINx v0.9.0

import os
os.environ['OMP_NUM_THREADS'] = '1'

from mpi4py import MPI
from dolfinx import mesh, io, fem
import adios4dolfinx
import numpy as np

def assign_xyz(submesh, xyz) -> None:
    xlims = []
    xmins = []
    for d in range(ndims):
        geom = submesh.geometry.x[:, d]
        xmin = geom.min() if len(geom) > 0 else 1e6
        xmax = geom.max() if len(geom) > 0 else -1
        xmin = comm.allreduce(xmin, op = MPI.MIN)
        xlim = comm.allreduce(xmax, op = MPI.MAX) - xmin
        xmins.append(xmin)
        xlims.append(xlim)

    def exp_xyz(x):
        r = []
        for d in range(ndims):
            r.append((x[d]-xmins[d])/xlims[d])
        return r

    xyz.interpolate(exp_xyz)

def nonmatching_meshes_interpolation(dest: fem.Function, src: fem.Function):
    V_dest = dest.function_space
    V_src = src.function_space
    tdim = V_src.mesh.topology.dim
    dest_mesh_cell_map = V_dest.mesh.topology.index_map(tdim)
    num_cells_on_proc = dest_mesh_cell_map.size_local + dest_mesh_cell_map.num_ghosts
    cells = np.arange(num_cells_on_proc, dtype = np.int32)
    interpolation_data = fem.create_interpolation_data(V_dest, V_src, cells, padding=1e-8)
    dest.interpolate_nonmatching(src, cells, interpolation_data=interpolation_data)
    dest.x.scatter_forward()


comm = MPI.COMM_WORLD
ndims = 3
order = 2 # 1 or 2
file1 = f"mesh1_order{order}.bp"
file2 = f"mesh2_order{order}.bp"

mesh1 = adios4dolfinx.read_mesh(file1, comm, engine="BP4")
mesh2 = adios4dolfinx.read_mesh(file2, comm, engine="BP4")

celltags1 = adios4dolfinx.read_meshtags(file1, mesh1, meshtag_name = "celltags", engine = "BP4")
celltags2 = adios4dolfinx.read_meshtags(file2, mesh2, meshtag_name = "celltags", engine = "BP4")

V1 = fem.functionspace(mesh1, ("Lagrange", order, (ndims,)))
V2 = fem.functionspace(mesh2, ("Lagrange", order, (ndims,)))

f1 = fem.Function(V1)
f2 = fem.Function(V2)

submesh1, cellmap1, _, _ = mesh.create_submesh(mesh1, ndims, celltags1.find(0))
submesh2, cellmap2, _, _ = mesh.create_submesh(mesh2, ndims, celltags2.find(0))

xyz1 = fem.Function(fem.functionspace(submesh1, ("Lagrange", order, (ndims,))))
xyz2 = fem.Function(fem.functionspace(submesh2, ("Lagrange", order, (ndims,))))

# make functions on submesh1 and mesh1
assign_xyz(submesh1, xyz1)
n = len(cellmap1)
f1.interpolate(xyz1, cells0=np.arange(n), cells1=cellmap1)
f1.x.scatter_forward()

# interpolate into f2 with nonmatching meshes interpolation
nonmatching_meshes_interpolation(f2, f1)

# make function on submesh2 with identical mesh interpolation
n = len(cellmap2)
xyz2.interpolate(f2, cells0=cellmap2, cells1=np.arange(n))
xyz2.x.scatter_forward()

# visualization
with io.XDMFFile(comm, f"f1_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(mesh1)
    xdmf.write_function(f1)

with io.XDMFFile(comm, f"f2_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(mesh2)
    xdmf.write_function(f2)

# assistant visualization
with io.XDMFFile(comm, f"xyz1_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(submesh1)
    xdmf.write_function(xyz1)

with io.XDMFFile(comm, f"xyz2_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(submesh2)
    xdmf.write_function(xyz2)

This is a problem with your mesh.
If you inspect the files f1_order2.xdmf and f2_order2.xdmf carefully, you will observe that the geometry of f1_order2.xdmf has a weird kink in the offending cell


This causes interpolation for that node to happen in the cell that is on the outside of the sphere, yielding a negative value.
Here is the script Im running (in serial) with DOLFINx main branch:

# interpolation.py
# Run with `mpirun -n 3 python interpolation.py`
# Test on DOLFINx v0.9.0

import os

os.environ["OMP_NUM_THREADS"] = "1"

from mpi4py import MPI
from dolfinx import mesh, io, fem
import adios4dolfinx
import numpy as np


def assign_xyz(submesh, xyz) -> None:
    xlims = []
    xmins = []
    for d in range(ndims):
        geom = submesh.geometry.x[:, d]
        xmin = geom.min() if len(geom) > 0 else 1e6
        xmax = geom.max() if len(geom) > 0 else -1
        xmin = comm.allreduce(xmin, op=MPI.MIN)
        xlim = comm.allreduce(xmax, op=MPI.MAX) - xmin
        xmins.append(xmin)
        xlims.append(xlim)

    def exp_xyz(x):
        r = []
        for d in range(ndims):
            r.append((x[d] - xmins[d]) / xlims[d])
        return r

    xyz.interpolate(exp_xyz)


def nonmatching_meshes_interpolation(dest: fem.Function, src: fem.Function):
    V_dest = dest.function_space
    V_src = src.function_space
    tdim = V_src.mesh.topology.dim
    dest_mesh_cell_map = V_dest.mesh.topology.index_map(tdim)
    num_cells_on_proc = dest_mesh_cell_map.size_local + dest_mesh_cell_map.num_ghosts
    cells = np.arange(num_cells_on_proc, dtype=np.int32)
    interpolation_data = fem.create_interpolation_data(
        V_dest, V_src, cells, padding=1e-8
    )
    dest.interpolate_nonmatching(src, cells, interpolation_data=interpolation_data)
    dest.x.scatter_forward()


comm = MPI.COMM_WORLD
ndims = 3
order = 2  # 1 or 2
file1 = f"mesh1_order{order}.bp"
file2 = f"mesh2_order{order}.bp"

mesh1 = adios4dolfinx.read_mesh(file1, comm, engine="BP4")
mesh2 = adios4dolfinx.read_mesh(file2, comm, engine="BP4")

celltags1 = adios4dolfinx.read_meshtags(
    file1, mesh1, meshtag_name="celltags", engine="BP4"
)
celltags2 = adios4dolfinx.read_meshtags(
    file2, mesh2, meshtag_name="celltags", engine="BP4"
)

V1 = fem.functionspace(mesh1, ("Lagrange", order, (ndims,)))
V2 = fem.functionspace(mesh2, ("Lagrange", order, (ndims,)))

f1 = fem.Function(V1)
f2 = fem.Function(V2)

submesh1, cellmap1, _, _ = mesh.create_submesh(mesh1, ndims, celltags1.find(0))
submesh2, cellmap2, _, _ = mesh.create_submesh(mesh2, ndims, celltags2.find(0))

xyz1 = fem.Function(fem.functionspace(submesh1, ("Lagrange", order, (ndims,))))
xyz2 = fem.Function(fem.functionspace(submesh2, ("Lagrange", order, (ndims,))))

# make functions on submesh1 and mesh1
assign_xyz(submesh1, xyz1)
sub_to_parent1 = cellmap1.sub_topology_to_topology(
    np.arange(
        submesh1.topology.index_map(submesh1.topology.dim).size_local
        + submesh1.topology.index_map(submesh1.topology.dim).num_ghosts,
        dtype=np.int32,
    ),
    inverse=False,
)
n = len(sub_to_parent1)
f1.interpolate(xyz1, cells0=np.arange(n, dtype=np.int32), cells1=sub_to_parent1)
f1.x.scatter_forward()

# interpolate into f2 with nonmatching meshes interpolation
nonmatching_meshes_interpolation(f2, f1)

# make function on submesh2 with identical mesh interpolation
sub_to_parent2 = cellmap2.sub_topology_to_topology(
    np.arange(
        submesh2.topology.index_map(submesh2.topology.dim).size_local
        + submesh2.topology.index_map(submesh2.topology.dim).num_ghosts,
        dtype=np.int32,
    ),
    inverse=False,
)
n = len(sub_to_parent2)
xyz2.interpolate(f2, cells0=sub_to_parent2, cells1=np.arange(n, dtype=np.int32))
xyz2.x.scatter_forward()

# visualization
with io.XDMFFile(comm, f"f1_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(mesh1)
    xdmf.write_function(f1)

with io.XDMFFile(comm, f"f2_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(mesh2)
    xdmf.write_function(f2)

# assistant visualization
with io.XDMFFile(comm, f"xyz1_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(submesh1)
    xdmf.write_function(xyz1)

with io.XDMFFile(comm, f"xyz2_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(submesh2)
    xdmf.write_function(xyz2)

Could you please point out which point causes the problem? For me, gmsh is used in a normal way to generate this 2nd order mesh. Still lost in how to improve it.

My question is why a cell with all greater than 0 nodes could result in a negative interpolated node in 2nd order meshes interpolation. This situation does not happen in 1st order interpolation. Is that because a quadratic basis function of P2 element has negative values, which could cause the point just outside the solid to be evaluated as a negative one?

Yes, the values of basis functions for a second order basis function is not necessarily bounded by the values at the degrees of freedom.
For instance, if we just inspect f1 after interpolating from xyz1 to f1 with scifem.compute_extrema, we get:

import scifem

extrema, node = scifem.compute_extrema(f1.sub(0), min)
(Pdb++) extrema
np.float64(-0.14891819580613833)
(Pdb++) node
array([ 0.10721618, -0.09852694, -0.54036315])

which is at:


We can even do this without having a submesh to mesh interpolation by calling:

import os

os.environ["OMP_NUM_THREADS"] = "1"

from mpi4py import MPI
from dolfinx import io, fem, mesh
import adios4dolfinx
import numpy as np
import scifem


def assign_xyz(domain, xyz, cells0=None) -> None:
    xlims = []
    xmins = []
    for d in range(ndims):
        if cells0 is not None:
            nodes = np.unique(
                mesh.entities_to_geometry(domain, domain.topology.dim, cells0).flatten()
            )
            geom = domain.geometry.x[nodes, d]
        else:
            geom = domain.geometry.x[:, d]
        xmin = geom.min() if len(geom) > 0 else 1e6
        xmax = geom.max() if len(geom) > 0 else -1
        xmin = comm.allreduce(xmin, op=MPI.MIN)
        xlim = comm.allreduce(xmax, op=MPI.MAX) - xmin
        xmins.append(xmin)
        xlims.append(xlim)

    def exp_xyz(x):
        r = []
        for d in range(ndims):
            r.append((x[d] - xmins[d]) / xlims[d])
        return r

    xyz.interpolate(exp_xyz, cells0=cells0)
    xyz.x.scatter_forward()


comm = MPI.COMM_WORLD
ndims = 3
order = 2
file1 = f"mesh1_order{order}.bp"

mesh1 = adios4dolfinx.read_mesh(file1, comm, engine="BP4")

celltags1 = adios4dolfinx.read_meshtags(
    file1, mesh1, meshtag_name="celltags", engine="BP4"
)

V1 = fem.functionspace(mesh1, ("Lagrange", order, (ndims,)))

f1 = fem.Function(V1)

assign_xyz(mesh1, f1, cells0=celltags1.find(0))

extrema, node = scifem.compute_extrema(f1.sub(0), min, num_candidates=10, p=1)
print(extrema, node)

# visualization
with io.XDMFFile(comm, f"f1_order{order}.xdmf", "w") as xdmf:
    xdmf.write_mesh(mesh1)
    xdmf.write_function(f1)

Good to know this improved way to fastly assign the whole function with the use of mesh.entities_to_geometry and contrain interpolation region with cells0 in xyz.interpolate.

Thanks for confirming this. I believe this is the reason to cause the negative interpolated node in my application above. The following validation code shows a simple test, which maybe useful for the prospective people: a mesh with only one single triangle cell is made and a P2 function with all greater than 0 values is built on it. Several points inside the mesh are evaluated to be negative values as interpolated points on the new mesh:

# P2_eval.py
# $ python P2_eval.py
# Test on DOLFINx v0.9.0

import numpy as np
from mpi4py import MPI
from dolfinx import fem, mesh, io, geometry

import basix.ufl
import dolfinx
import ufl
import matplotlib.pyplot as plt

def evaluate_at_points(_mesh, f, points):

    if points.shape[1] == 2:
        z_coords = np.zeros((points.shape[0], 1))
        points = np.hstack([points, z_coords])

    bb_tree = geometry.bb_tree(_mesh, _mesh.topology.dim)
    cell_candidates = geometry.compute_collisions_points(bb_tree, points)
    colliding_cells = geometry.compute_colliding_cells(_mesh, cell_candidates, points)

    cells = []
    points_on_proc = []
    for i, point in enumerate(points):
        if len(colliding_cells.links(i)) > 0:
            cells.append(colliding_cells.links(i)[0])
            points_on_proc.append(point)

    values = f.eval(np.array(points_on_proc), np.array(cells))
    
    return values, np.array(points_on_proc)

comm = MPI.COMM_WORLD
nodes = np.array(
    [[0,   0  ],
     [1,   1  ],
     [0,   2  ],
     [0.5, 1.5],
     [0,   1  ],
     [0.5, 0.5],
    ],
    dtype=np.float64,
)

connectivity = np.array([[0, 1, 2, 3, 4, 5]], dtype=np.int64)

c_el = ufl.Mesh(basix.ufl.element("Lagrange", "triangle", 2, shape=(nodes.shape[1],)))
_mesh = dolfinx.mesh.create_mesh(MPI.COMM_SELF, cells=connectivity, x=nodes, e=c_el)

Q = fem.functionspace(_mesh, ("Lagrange", 2))
f = fem.Function(Q)

def x_tip(x):
    return x[0] > 0.9

corner_point = mesh.locate_entities_boundary(_mesh, 0, x_tip)
dof = fem.locate_dofs_topological(Q, 0, corner_point)
f.x.array[dof] = 1

n = 100
points = np.ones((n, 2))
points[:, 0] = np.linspace(0, 1, n)
vals, _ = evaluate_at_points(_mesh, f, points)

fig = plt.figure()
plt.plot(points[:, 0], vals, "o-")
plt.xlabel("x")
plt.ylabel("value")
plt.legend("y = 1 probe")
plt.grid("on")
plt.savefig("evals.png", dpi = 300)

with io.XDMFFile(comm, "f.xdmf", "w") as xdmf:
    xdmf.write_mesh(_mesh)
    xdmf.write_function(f)

Yielding

Sorry to bother in this thread again. Still be confusing with interpolation result. I tried to catch a specific error from my simulations. The problem does not come in every time. But when it comes, the task is likely to fail.

Fig (a) shows that a very negative value as marked in the new mesh, which was interpolated from all positive surronding cells of old mesh. The old and the new mesh were both stored to reproduce this error. To simplify the problem, only limited regions were extracted from the two meshes respectively as shown in fig (b). The (sub)meshes can be found in interpolation_error_meshes - Google Drive . The MWE below shows that if I have a field with random values ranged [0, 1] in u_1, then there is a very huge point (>100) in the u_2 as shown in fig (c). This definitely causes error accumulation for the following steps.

To me, the old and new mesh look reasonable in terms of quality, and the values in the old mesh is also OK. Any recommended practice I can do to avoid this kind of error?

MWE:

# interpolation_error.py, run with 
# python interpolation_error.py
# tested on v 0.9.0 and v 0.10.0.post2

import numpy as np
from dolfinx import fem, io, mesh
from dolfinx.fem.petsc import LinearProblem
from petsc4py.PETSc import ScalarType
from mpi4py import MPI

def nonmatching_meshes_interpolation(
    dest: fem.Function, src: fem.Function):
    
    V_dest = dest.function_space
    V_src = src.function_space
    
    tdim = V_src.mesh.topology.dim
    dest_mesh_cell_map = V_dest.mesh.topology.index_map(tdim)
    num_cells_on_proc = dest_mesh_cell_map.size_local + dest_mesh_cell_map.num_ghosts
    cells = np.arange(num_cells_on_proc, dtype = np.int32)

    interpolation_data = fem.create_interpolation_data(V_dest, V_src, cells, padding=1e-8)
    dest.interpolate_nonmatching(src, cells, interpolation_data=interpolation_data)
    dest.x.scatter_forward()
    

mesh_1 = io.XDMFFile(MPI.COMM_WORLD, "submesh_1.xdmf", "r").read_mesh()
mesh_2 = io.XDMFFile(MPI.COMM_WORLD, "submesh_2.xdmf", "r").read_mesh()

V_1 = fem.functionspace(mesh_1, ("Lagrange", 2))
V_2 = fem.functionspace(mesh_2, ("Lagrange", 2))

u_1 = fem.Function(V_1)
u_2 = fem.Function(V_2)

# Option 1: u_2 behaves well as u_1
# u_1.interpolate(lambda x: x[0])

# Option 2: u_2 behaves poorly
u_1.x.array[:] = np.random.rand(u_1.x.array.size)

nonmatching_meshes_interpolation(u_2, u_1)

with io.XDMFFile(MPI.COMM_WORLD, "u_1.xdmf", "w") as file:
    file.write_mesh(mesh_1)
    file.write_function(u_1)

with io.XDMFFile(MPI.COMM_WORLD, "u_2.xdmf", "w") as file:
    file.write_mesh(mesh_2)
    file.write_function(u_2)

Since you are using a random set of numbers, you should set the random seed to make it reproducible.
Let’s consider a specific random seed (for serial computations)

rng = np.random.default_rng(2021)
u_1.x.array[:] = rng.random(u_1.x.array.size)

Then, as we are running in serial, lets inspect what coordinates you get negative values in u_2.

import dolfinx
negative_points =  V_2.tabulate_dof_coordinates()[pos]
num_cells = mesh_1.topology.index_map(mesh_1.topology.dim).size_local
bb_tree = dolfinx.geometry.bb_tree(mesh_1, mesh_1.topology.dim, padding=0.0, entities=np.arange(num_cells, dtype=np.int32))
candidates = dolfinx.geometry.compute_collisions_points(bb_tree, negative_points)
closest_cells = dolfinx.geometry.compute_colliding_cells(mesh_1, candidates, negative_points)
closest_cell = closest_cells.array[closest_cells.offsets[:-1]]
u1_at_u2 = u_1.eval(negative_points, closest_cell).flatten()
np.testing.assert_allclose(u_2.x.array[pos], u1_at_u2)
print("u_1 at interpolation points of u_2",u1_at_u2)

as you observe, simply evaluating u_1 at the interpolation points of u_2 gives the exact negative values one would observe in Paraview.

This again highlights the problem that even if all dofs in a second order discretization is positive, you can’t guarantee positivity within the whole cell.

I made some test and please correct me. Many thanks.

By checking the point-cell ownership info, I examined the problematic cell (id 842) from the old mesh and the evalation point. The weights of basis function at the evaluation point and DOF values are extracted as follows, and the check np.dot(weight, dofs)returns value 27.781290. The weight of basis function at that point goes insane.

Node | Weight   | DOF Value
------------------------------
   0 |  43.7148 | 0.837484
   1 |  99.9177 | 0.487535
   2 | 227.4921 | 0.841392
   3 |   2.2353 | 0.567598
   4 |  58.3611 | 0.663984
   5 | -36.4690 | 0.930795
   6 | -297.9587| 0.484501
   7 | -23.6899 | 0.892946
   8 | -193.5505| 0.684937
   9 | 120.9471 | 0.356007
------------------------------

The evaluation point indeed lies in the cell via fem.create_interpolation_data(...) (bb_tree + compute_collisions_points). However, I found that the reference coordinate is (xi, eta, zeta): [-6.82257897 10.91810998 1.33633645] with cmap.pull_back(eval_point, coords), which causes an extrapolation situation and overshooting for high order elements.

Hence, I use the following steps to make a robust interpolation (only works for serial version). Please also comment on this:

  1. Use bb_tree + compute_collisions_points to get several candidate cells
  2. With cmp.pull_back, examine the valid candidate cell to avoid extrapolation situation
  3. use f.eval to manually assign every interpolation point
  4. use np.clip to constrain the value

MWE:

# python this_file.py
# tested on v 0.9.0

import numpy as np
from mpi4py import MPI
import dolfinx
from dolfinx import fem, io, mesh, geometry
import sys

def robust_interpolate_logic(src_u, pt, tree, mid_tree):
    """
    Robust interpolation logic for a single point (Serial usage).
    """
    m_src = src_u.function_space.mesh
    tdim = m_src.topology.dim
    cmap = m_src.geometry.cmap
    
    # Find all colliding candidate cells
    candidates = geometry.compute_collisions_points(tree, pt[None, :])
    candidate_cells = candidates.array[candidates.offsets[0]:candidates.offsets[1]]
    
    if len(candidate_cells) == 0:
        # Fallback to closest entity if no direct collision is found
        try:
            res = geometry.compute_closest_entity(tree, mid_tree, m_src, pt[None, :])
            candidate_cells = [res[0]]
        except:
            return 0.0

    best_val = 0.0
    min_violation = 1e10
    
    # Iterate through candidates to find the most geometrically valid cell
    for c in candidate_cells:
        g_idx = mesh.entities_to_geometry(m_src, tdim, np.array([c], dtype=np.int32))[0]
        coords = m_src.geometry.x[g_idx]
        try:
            # Pull back to reference space to check for extrapolation violation
            ref = cmap.pull_back(pt[None, :], coords)[0]
            violation = np.sum(np.maximum(-ref, 0)) + max(0, np.sum(ref) - 1.0)
            if violation < min_violation:
                min_violation = violation
                # Only evaluate if the violation is within acceptable tolerance (e.g., slight extrapolation)
                if violation < 0.2:
                    best_val = src_u.eval(pt[None, :], [c])[0]
                # Break early if a perfect match is found
                if violation < 1e-8: break
        except:
            continue
    return best_val

def solve():
    comm = MPI.COMM_WORLD
    if comm.size > 1:
        print("This script is intended for serial testing purposes only.")
        return

    # 1. Load meshes
    try:
        with io.XDMFFile(comm, "submesh_1.xdmf", "r") as f:
            m_src = f.read_mesh()
        with io.XDMFFile(comm, "submesh_2.xdmf", "r") as f:
            m_dest = f.read_mesh()
    except Exception as e:
        print(f"Error loading meshes: {e}. Ensure submesh_1.xdmf and submesh_2.xdmf are present.")
        return

    V_src = fem.functionspace(m_src, ("Lagrange", 2))
    V_dest = fem.functionspace(m_dest, ("Lagrange", 2))

    # 2. Initialize source function with RNG for reproducibility
    u_src = fem.Function(V_src)
    rng = np.random.default_rng(2021)
    u_src.x.array[:] = rng.random(len(u_src.x.array))
    u_src.x.scatter_forward()

    # 3. Standard Interpolation (manually bypassing potential library SEGV)
    print("Running standard interpolation...")
    u_std = fem.Function(V_dest)
    dest_pts = V_dest.tabulate_dof_coordinates()
    tree = geometry.bb_tree(m_src, m_src.topology.dim)
    
    for i in range(len(u_std.x.array)):
        pt = dest_pts[i]
        candidates = geometry.compute_collisions_points(tree, pt[None, :])
        if len(candidates.array) > 0:
            c = candidates.array[0] # Standard strategy: pick the first candidate
            try:
                u_std.x.array[i] = u_src.eval(pt[None, :], [c])[0]
            except:
                pass
    u_std.x.scatter_forward()

    # 4. Robust Interpolation (manual logic with geometric filtering)
    u_rob = fem.Function(V_dest)
    dest_pts = V_dest.tabulate_dof_coordinates()
    tree = geometry.bb_tree(m_src, m_src.topology.dim)
    entities = np.arange(m_src.topology.index_map(m_src.topology.dim).size_local, dtype=np.int32)
    mid_tree = geometry.create_midpoint_tree(m_src, m_src.topology.dim, entities)

    print("Running robust interpolation...")
    for i in range(len(u_rob.x.array)):
        u_rob.x.array[i] = robust_interpolate_logic(u_src, dest_pts[i], tree, mid_tree)
    
    # 5. Final Physical Clipping
    u_clipped = fem.Function(V_dest)
    s_min, s_max = np.min(u_src.x.array), np.max(u_src.x.array)
    u_clipped.x.array[:] = np.clip(u_rob.x.array, s_min, s_max)

    print("\n" + "="*60)
    print(f"Source Mesh RNG Range: [{s_min:.6f}, {s_max:.6f}]")
    print(f"Standard Interpolated Max: {np.max(u_std.x.array):.6f} (Overshoot expected)")
    print(f"Robust Filtered Max: {np.max(u_rob.x.array):.6f} (After geo-filtering)")
    print(f"Final Clipped Max: {np.max(u_clipped.x.array):.6f} (Physically constrained)")
    print("="*60)

if __name__ == "__main__":
    solve()

This is quite suprising, as this indicates that the point is not within the cell, as the reference coordinate should be within the reference tetrahedron.

This is due to the fact that you only compute the distance to the bounding box, and not the convex hull of the cell, i.e.

should be

    candidates = geometry.compute_collisions_points(tree, pt[None, :])
    candidate_cells = geometry.compute_colliding_cells(m_src, candidates, pt.reshape(-1, 3))
    candidate_cells = candidate_cells.array[candidate_cells.offsets[0]:candidate_cells.offsets[1]]

Furthermore, by inspecting the distance to the function in reference space, you get:

    best_val = 0.0
    max_ref_distance = 0.01
    import basix
    ref_geom = basix.geometry(m_src.basix_cell())
    # Iterate through candidates to find the most geometrically valid cell
    for c in candidate_cells:
        print(geometry.compute_distance_gjk(m_src.geometry.x[m_src.geometry.dofmap[c]], pt))
        g_idx = mesh.entities_to_geometry(m_src, tdim, np.array([c], dtype=np.int32))[0]
        coords = m_src.geometry.x[g_idx]
        try:
            # Pull back to reference space to check for extrapolation violation
            ref = cmap.pull_back(pt[None, :], coords)[0]
            dist = np.linalg.norm(geometry.compute_distance_gjk(ref, ref_geom))

            if dist > max_ref_distance:
                breakpoint()


as you can observe, the node lies within the convex hull of the cell, but not the cell itself.
It should lie within another cell:

I’ve made a PR to fix this: Improve non-matching interpolation for non-affine grids. by jorgensd · Pull Request #4127 · FEniCS/dolfinx · GitHub
where the undershoot reduces from -0.47 to -0.09, which is more expected as you are interpolating data that might be negative with a cell.

2 Likes

Many thanks. I’d like to take a try. How can we use FEniCSx with the latest modifications? My thought would be:

  1. Use docker image dev-env(or test-env?)
  2. Git clone the repo and checkout the main branch
  3. Install FEniCSx from source

Either of those envs would work nicely. You would also have to install ufl, basix and ffcx from source.
Alternatively you can use the nightly image, and reinstall the branch from DOLFINx on top of it, then you dont have to deal with the other dependencies.

The nightly image has been upgraded to version 0.11.0.dev. Should I use the main branch in the image or your dokken/pull_back_scratch_memory branch?

You need to use the branch:

I have taken a try. With your branch:

python -c "import dolfinx; print(dolfinx.git_commit_hash)"

returns

d4956db474042268827d486cbab629cb07055a07

with the reproduce command rng = np.random.default_rng(2021), I see the improvement: the minimum value reduces from -0.446 to -0.10764921, which is slightly different to yours. However, the most severe point-cell ownership issue is still not covered by the modification. Here is my walkthrough, and hope this info can further help improve FEniCSx’s robustness:

The most severe case is the very positive value, but not the negative one. We get ~27 interpolated from a field with [0, 1] value (mesh_1). The point-cell relation is shown in the following figure:

Two MWEs are attached. MWE1 finds the extreme positive and negative values and point-cell relation. MWE2 reproduces the single-cell function evaluation and examines the mesh quality.

MWE1:

# dolfinx.git_commit_hash: d4956db474042268827d486cbab629cb07055a07
# python this_file.py

import numpy as np
import dolfinx
from dolfinx import fem, io, mesh
from dolfinx.fem.petsc import LinearProblem
from petsc4py.PETSc import ScalarType
from mpi4py import MPI

def nonmatching_meshes_interpolation(
    dest: fem.Function, src: fem.Function):
    
    V_dest = dest.function_space
    V_src = src.function_space
    
    tdim = V_src.mesh.topology.dim
    dest_mesh_cell_map = V_dest.mesh.topology.index_map(tdim)
    num_cells_on_proc = dest_mesh_cell_map.size_local + dest_mesh_cell_map.num_ghosts
    cells = np.arange(num_cells_on_proc, dtype = np.int32)

    interpolation_data = fem.create_interpolation_data(V_dest, V_src, cells, padding=1e-8)
    dest.interpolate_nonmatching(src, cells, interpolation_data=interpolation_data)
    dest.x.scatter_forward()
    
# Load the meshes
mesh_1 = io.XDMFFile(MPI.COMM_WORLD, "submesh_1.xdmf", "r").read_mesh()
mesh_2 = io.XDMFFile(MPI.COMM_WORLD, "submesh_2.xdmf", "r").read_mesh()

V_1 = fem.functionspace(mesh_1, ("Lagrange", 2))
V_2 = fem.functionspace(mesh_2, ("Lagrange", 2))

u_1 = fem.Function(V_1)
u_2 = fem.Function(V_2)

rng = np.random.default_rng(2021)
u_1.x.array[:] = rng.random(u_1.x.array.size)

nonmatching_meshes_interpolation(u_2, u_1)

with io.XDMFFile(MPI.COMM_WORLD, "u_1.xdmf", "w") as file:
    file.write_mesh(mesh_1)
    file.write_function(u_1)

with io.XDMFFile(MPI.COMM_WORLD, "u_2.xdmf", "w") as file:
    file.write_mesh(mesh_2)
    file.write_function(u_2)

# Find the extreme values
pos = np.where(u_2.x.array == np.max(u_2.x.array))[0]
very_positive_point = V_2.tabulate_dof_coordinates()[pos]

print("The very positive value", u_2.x.array[pos])
print("The negative value", u_2.x.array[np.where(u_2.x.array == np.min(u_2.x.array))[0]])

# Even if the function is evaluated normally in a cell, it will produce very strange results
num_cells = mesh_1.topology.index_map(mesh_1.topology.dim).size_local
bb_tree = dolfinx.geometry.bb_tree(mesh_1, mesh_1.topology.dim, padding=0.0, entities=np.arange(num_cells, dtype=np.int32))
candidates = dolfinx.geometry.compute_collisions_points(bb_tree, very_positive_point)
closest_cells = dolfinx.geometry.compute_colliding_cells(mesh_1, candidates, very_positive_point)
closest_cell = closest_cells.array[closest_cells.offsets[0]] # Just take the first colliding cell
u1_at_u2 = u_1.eval(very_positive_point, [closest_cell]).flatten()
np.testing.assert_allclose(u_2.x.array[pos], u1_at_u2)
print("u_1 at interpolation points of u_2", u1_at_u2)

# Extract cell info for reproduction
cell_geom_indices = mesh_1.geometry.dofmap[closest_cell]
cell_coords = mesh_1.geometry.x[cell_geom_indices]
print("\n--- Reproduction Data ---")
print(f"problematic_point = np.array({very_positive_point.tolist()})")
print(f"cell_coords = np.array({cell_coords.tolist()})")

# Get DOFs for the function on this cell
dofs = V_1.dofmap.cell_dofs(closest_cell)
cell_values = u_1.x.array[dofs]
print(f"cell_values = np.array({cell_values.tolist()})")
print("--------------------------\n")

MWE2:

import numpy as np
import dolfinx
from dolfinx import fem, mesh, io
from mpi4py import MPI
import ufl
import basix

problematic_point = np.array([[0.5920964741183606, 0.7784909024954635, 0.0760893759006711]])

cell_coords = np.array([
    [0.6210342830629921, 0.7130886075697652, 0.08535278979841678], 
    [0.5897009907801825, 0.7817623179610342, 0.07777225396692372], 
    [0.6163326081106263, 0.7599823011151882, 0.06999672067488931], 
    [0.5812509453350484, 0.7665364480265131, 0.03620476065405204], 
    [0.5983808025811516, 0.7633307128793245, 0.05310084774660532], 
    [0.5849672878699544, 0.7740814303588602, 0.05698859022652897], 
    [0.6026809405096305, 0.7711469582865065, 0.07196483547790937], 
    [0.6023762196105121, 0.7399338746252635, 0.06077855760134429], 
    [0.6188050511380555, 0.7353222257315518, 0.07393261786005173], 
    [0.6038786191530268, 0.745720310535569, 0.07226986483687235]
], dtype=np.float64)

# 10 nodal values for the P2 function on this cell
cell_values = np.array([
    0.837484251520003, 0.4875351573013783, 0.8413916593920271, 
    0.5675978795177005, 0.663983629844943, 0.930794602477507, 
    0.48450071806840367, 0.8929458162743907, 0.6849371844003903, 
    0.3560069051691127
], dtype=np.float64)

# --- Mesh and Function Construction ---
# Create a single cell mesh
gdim = 3
coord_element = basix.ufl.element("Lagrange", "tetrahedron", 2, shape=(gdim,))
msh_ufl = ufl.Mesh(coord_element)
cells = np.array([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]], dtype=np.int32)
msh = mesh.create_mesh(MPI.COMM_WORLD, cells, msh_ufl, cell_coords)

# Create P2 FunctionSpace and Function
V = fem.functionspace(msh, ("Lagrange", 2))
u = fem.Function(V)
u.x.array[:] = cell_values

print(f"DOLFINx Version: {dolfinx.__version__}")  # 0.11.0.dev0
print(f"Problematic Point: {problematic_point.flatten()}")
print(f"Nodal range of the cell: [{np.min(cell_values):.4f}, {np.max(cell_values):.4f}]")

# Perform evaluation
res = u.eval(problematic_point, [0])
print(f"Evaluation results array: {res}")
# Flatten and take the first value
res_val = res.flatten()[0]
print(f"Final evaluation result: {res_val:.8e}")

if not np.allclose(res_val, 27.78, atol=1.0):
    print("WARNING: Could not reproduce the high value exactly! Value found:", res_val)
else:
    print("SUCCESS: Reproduced the high value.")

try:
    cell_nodes = msh.geometry.x[msh.geometry.dofmap[0]]
    map_obj = msh.geometry.cmap
    
    # Check pull-back again
    point_ref = map_obj.pull_back(problematic_point, cell_nodes)
    print(f"Reference coordinates (xi): {point_ref.flatten()}")
    
    # Check if xi is inside the reference tetrahedron [0, 1]
    xi_sum = np.sum(point_ref)
    is_inside = np.all(point_ref >= -1e-10) and xi_sum <= 1.0 + 1e-10
    print(f"Is point inside reference cell? {is_inside}")
    if not is_inside:
        print("CRITICAL: The point is mapped to a location OUTSIDE the reference cell.")
        print(f"Sum of xi: {xi_sum:.4f} (should be <= 1.0)")

except Exception as e:
    print(f"\nAnalysis failed: {e}")

# Save single-cell mesh
with io.XDMFFile(MPI.COMM_WORLD, "single_cell.xdmf", "w") as file:
    file.write_mesh(msh)

But that evaluation point seems to be within the cell, no?

As a side-note, I am working on a more elaborate way of finding the owners, ref: Closest point projection · Issue #198 · scientificcomputing/scifem · GitHub

The general problem here is that your cell i very non-convex, meaning that collision detection is quite hard.