When intersecting non-matching three-dimensional lattices, one needs to calculate the intersections of tetrahedra. The authors’ previously published two-dimensional triangle–triangle intersection algorithm suggests a novel approach in three dimensions based on parsimony. The algorithm presented here expands on this two-dimensional algorithm and introduces new strategies necessitated by the increase in dimension. An extensive proof is given for the consistency of the algorithm. Thus, the algorithm is shown to be robust to numerical error arising from floating-point arithmetic. Example problems demonstrate its use and effectiveness.

Motivated by the unexpected failure of the triangle intersection component of the Projection Algorithm for Nonmatching Grids (PANG), this article provides a robust version with proof of backward stability. The new triangle intersection algorithm ensures consistency and parsimony across three types of calculations. The set of intersections produced by the algorithm, called representations, is shown to match the set of geometric intersections, called models. The article concludes with a comparison between the old and new intersection algorithms for PANG using an example found to reliably generate failures in the former.

We design and analyze an algorithm with linear complexity to perform projections between 2D and 3D nonmatching grids. This algorithm, named the PANG algorithm, is based on an advancing front technique and neighboring information. Its implementation is surprisingly short, and we give the entire Matlab code. For computing the intersections, we use a direct and numerically robust approach. We show numerical experiments both for 2D and 3D grids, which illustrate the optimal complexity and negligible overhead of the algorithm. An outline of this algorithm has already been presented in a short proceedings paper of the 18th International Conference on Domain Decomposition Methods (see Gander and Japhet [2008]).