# Triangular Mesh Reordering - Huddling Triangles

I am given a 3D model represented by its outside surface as a triangular mesh (hollow inside). The model is mostly 2-manifold, so that each triangle edge is shared by exactly 2 triangles. This, naturally, means that every triangle has exactly 3 neighbors (except at non-manifold bare edges, but we can ignore this case for now).
The mesh is represented as an array of triangles. Assume that I know the indices of each triangle's neighbors.

Is there an algorithm for reordering the triangles such that most triangles are very close to all 3 their neighbors in this 1D ordering?

I suspect this is an NP complete problem, but I wonder if there are approximation algorithms.

Here's what I found but all seem unsatisfactory:

Space-filling Hilbert-like curves (e.g. for triangular grids).
Even if I could generate such a curve for arbitrary topology (non-regular) meshes, these do not preserve or minimize overall locality:

Both the Hilbert curve and its discrete approximations are useful because they give a mapping between 1D and 2D space that fairly well preserves locality. If (x,y) are the coordinates of a point within the unit square, and d is the distance along the curve when it reaches that point, then points that have nearby d values will also have nearby (x,y) values. The converse can't always be true. There will sometimes be points where the (x,y) coordinates are close but their d values are far apart.

What is guaranteed, is that close points on the 1D curve will tend to be close in 2D space, but the converse is not true (i.e. close points in 2D space will not necessarily be close on the 1D curve) and that is what I want .

Another approach I considered was creating the adjacency matrix for the triangle neighborhood graph where each node in the graph is a triangle and there is an edge between each pair of neighboring triangles.
The adjacency matrix is symmetric very sparse since each node has (at most) 3 neighbors.

I'd like an algorithm to reorder the columns and rows of the matrix such that most of the sparse entries are as close to the diagonal as possible. This is called matrix bandwidth reduction, and is an NP-complete problem, but it has several well known algorithms such as the reverse Cuthill–McKee algorithm (RCM). This algorithm and its variants are essentially variants of the breadth-first-search algorithm.

However, IIUC, in my case the graph is mostly locally planar, so the algorithm will essentially generate a spiral of interleaved triangles from and around the start node. This spiral will cause each triangle to get farther and farther away from at least 1 but sometimes all 3 of its immediate neighbors by a distance that is proportional to the circumference of the spiral at that point.

I prefer fewer long non-local hops to many shorter non-local hops.

Am I missing anything? Is there another approach I could take?

• This isn't a fully formed answer at all, but as far as possible other approaches you could try to recurse by splitting the triangles into two regions (finding a small cut in the triangle adjacency graph), sorting the triangles in each region recursively and concatenating the lists. – Mikhail Rudoy Jul 14 '16 at 11:55