How do you mesh and re-mesh a surface (2-manifold) in 4D?

Question

For ease of explanation, suppose that you began with a two-dimensional surface in (x1, x2, x3, x4)-space, and the surface begins as a flat planar region in the (x1, x2)-plane. The boundaries of this flat region is not that important to resolve, but it would have a closed boundary. Pretend it is a square. So this surface might be specified by a triangular mesh, so a listing of points and their neighbours.

Through some operation, the plane now gets deformed into 4D. So for instance, I might assign +(0, 0, 1, 0) for some points and -(0, 0, 0, 1) for other points. At this point, you have a 2-manifold in 4D.

The problem is that I need to remesh this surface. I'd like to capture things like folds in the surface, and I'd like to remesh so that triangles that get stretched out are subdivided, and to avoid things like skinny triangles.

I understand that there is a lot of info on how this is done for two-dimensional planar surfaces in 2D, like Shewchuk's Triangle program. I've read Persson and Strang's article on simple meshing in 2D, but I don't think this is generalizable to 2-manifolds in 4D.

Ultimately, I'm looking for a more-or-less simple algorithm (or program). The need for accuracy is not terribly high, and the boundary regions of my surface are not important to accurately resolve.

Can anybody suggest literature I can refer to? There is a startlingly large amount of work done on meshing and remeshing, so it's difficult to see what is applicable for my problem.

Answer 1

You can use a 2D anisotropic mesh generator (see e.g. H. Borouchaki, George, P. L. , F. Hecht , P. Laug and E. Saltel, Delaunay mesh generation governed by metric specifications. Part 1: Algorithms, Finite Elements in Analysis and Design, Vol. 25, pp. 61-83, 1997).

Such a 2D anisotropic mesh generator takes as input:

• a 2D domain to be meshed

• a metric $G(x,y)$

The metric is a function that associates a $2\times 2$ symmetric positive definite matrix with each point of the domain. This metric specifies the desired edge length as follows: suppose you have an edge $(x_1, y_1) - (x_2, y_2)$, then what you want is $e^t G(x,y) e = 1$, where e = $(x_2, y_2) - (x_1, y_1)$ and where $x=(x_1 + x_2)/2, y = (y_1 + y_2)/2)$. Intuitively, the squared norm of $e = \| e \|^2 = e^t e$ is replaced with $e^t G e$. This provides a means of "shearing" and "scaling" the definition of distances.

In practice, the metric can be stored at the vertices of an input background mesh and linearly interpolated over the triangles of the background mesh. Then the anisotropic mesh generator will create a new triangulation of the input geometry where all the edges are (mostly) of length 1 with respect to the metric.

In your case, you can see your 4D input domain as a 2D domain transformed into 4D with a (vector-valued) function $\Phi(x,y)$. Now if you generate a 2D mesh deformed in such a way that it will exactly counterbalance the deformation created by the mapping $\Phi$, then you will have mostly equilateral triangles in 4D. This can be achieved by using for $G(x,y)$ the pullback metric of $\Phi$, given by $G(x,y) = J^t J$, where $J$ denotes the Jacobian matrix of $\Phi$. This technique is used for tesselating parametric surfaces (Splines, Nurbs ...) using a 2D anisotropic mesh generator.

If a mapping $\Phi$ and its Jacobian cannot be computed, there is an alternative method that we used (in 6D in our case), that directly optimizes and computes the mesh in high dimensional space: http://www.imr.sandia.gov/papers/abstracts/Le621.html (but it is much more costly, the anisotropic meshing steered by $J^tJ$ is probably much better in most cases).