<p>There appears to be a solution used by game programmers that both optimizes graphics hardware cache utilization and facilitates mesh connectivity compression. It is Tom Forsyth's Linear-Speed Vertex Cache Optimisation described here: <a href="https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html" rel="nofollow">https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html</a> </p>

<p>The algorithm uses a heuristic based on modeling the GPU vertex cache to produce a sequence of triangles with high locality and vertex reuse. The pattern produced is reportedly not unlike the Hilbert curve. The algorithm has linear time complexity.</p>

<p>The master thesis "Efficient Triangle Reordering for Improved Vertex Cache Utilisation in Realtime Rendering" (<a href="http://www.martin.st/thesis/" rel="nofollow">http://www.martin.st/thesis/</a>) contains a C++ implementation and also seems to describe an improved algorithm.</p>

CC BY-SA 3.0
2016-09-23T09:06:53.767Z
This is interesting. I guess you could reorder the faces quickly using these algorithms, and then resort the vertices by the min-face-index of each vtx (and correct the faces with the reshuffled vtx-indices). This way the vtx order is induced by the face order which in turn is induced by minimizing the vtx cache/access counts.
Adi Shavit
CC BY-SA 3.0
2016-09-23T09:27:11.357Z
The algorithm also produces a vertex ordering. Every time a vertex is first assigned a score it can also be assigned a new index. People who do mesh compression seem to use this property for delta coding of the vertices.
jcerveny
CC BY-SA 3.0
2016-09-23T09:36:56.487Z
I haven't dug too deep into the algorithm and implementations yet but the code samples I looked at from the links don't even look at the vertices, only at the indices themselves. But delta coding is indeed one of my goals, so I'll look into the optional vtx ordering too. Thanks!
Adi Shavit
CC BY-SA 3.0
2016-09-23T07:46:56.360Z
2016-09-23T07:46:56.360Z
jcerveny
<p>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).<br>
The mesh is represented as an array of triangles. Assume that I know the indices of each triangle's neighbors.</p>

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

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

<p>Here's what I found but all seem unsatisfactory:</p>

<p><strong><a href="https://en.wikipedia.org/wiki/Hilbert_curve" rel="nofollow">Space-filling Hilbert-like curves</a></strong> (e.g. for <a href="https://ideophilus.wordpress.com/2012/09/06/a-triangular-space-filling-curve/" rel="nofollow">triangular grids</a>).<br>
Even if I could generate such a curve for arbitrary topology (non-regular) meshes, these <a href="https://en.wikipedia.org/wiki/Hilbert_curve#Applications_and_mapping_algorithms" rel="nofollow">do not preserve or minimize overall locality</a>: </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>What is guaranteed, is that close points <em>on the 1D curve</em> 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 .</p>

<p><strong><a href="https://en.wikipedia.org/wiki/Band_matrix#Band_form_of_sparse_matrices" rel="nofollow">Adjacency Matrix Bandwidth Reduction</a></strong><br>
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.<br>
The adjacency matrix is symmetric very sparse since each node has (at most) 3 neighbors.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Band_matrix#Band_form_of_sparse_matrices" rel="nofollow"><em>matrix bandwidth reduction</em></a>, and is an NP-complete problem, but it has several well known algorithms such as <a href="https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm" rel="nofollow">the reverse Cuthill–McKee algorithm (RCM)</a>. This algorithm and its variants are essentially variants of the breadth-first-search algorithm.  </p>

<p>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. </p>

<p>I prefer fewer long non-local hops to many shorter non-local hops.</p>

<p>Am I missing anything? Is there another approach I could take?</p>

CC BY-SA 3.0
2016-07-14T11:55:40.173Z
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
<graph-algorithms>
Triangular Mesh Reordering - Huddling Triangles
Adi Shavit
# Triangular Mesh Reordering - Huddling Triangles

(Asked by: username_0 on 2016-07-14)

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](https://en.wikipedia.org/wiki/Hilbert_curve)** (e.g. for [triangular grids](https://ideophilus.wordpress.com/2012/09/06/a-triangular-space-filling-curve/)).  
Even if I could generate such a curve for arbitrary topology (non-regular) meshes, these [do not preserve or minimize overall locality](https://en.wikipedia.org/wiki/Hilbert_curve#Applications_and_mapping_algorithms):

> 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 .

**[Adjacency Matrix Bandwidth Reduction](https://en.wikipedia.org/wiki/Band_matrix#Band_form_of_sparse_matrices)**  
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*](https://en.wikipedia.org/wiki/Band_matrix#Band_form_of_sparse_matrices), and is an NP-complete problem, but it has several well known algorithms such as [the reverse Cuthill–McKee algorithm (RCM)](https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm). 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?

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-09-23. Score: 3

There appears to be a solution used by game programmers that both optimizes graphics hardware cache utilization and facilitates mesh connectivity compression. It is Tom Forsyth's Linear-Speed Vertex Cache Optimisation described here: <https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html>

The algorithm uses a heuristic based on modeling the GPU vertex cache to produce a sequence of triangles with high locality and vertex reuse. The pattern produced is reportedly not unlike the Hilbert curve. The algorithm has linear time complexity.

The master thesis "Efficient Triangle Reordering for Improved Vertex Cache Utilisation in Realtime Rendering" (<http://www.martin.st/thesis/>) contains a C++ implementation and also seems to describe an improved algorithm.

> **Comments:**
> **username_0**: This is interesting. I guess you could reorder the faces quickly using these algorithms, and then resort the vertices by the min-face-index of each vtx (and correct the faces with the reshuffled vtx-indices). This way the vtx order is induced by the face order which in turn is induced by minimizing the vtx cache/access counts.  
> **username_2**: The algorithm also produces a vertex ordering. Every time a vertex is first assigned a score it can also be assigned a new index. People who do mesh compression seem to use this property for delta coding of the vertices.  
> **username_0**: I haven't dug too deep into the algorithm and implementations yet but the code samples I looked at from the links don't even look at the vertices, only at the indices themselves. But delta coding is indeed one of my goals, so I'll look into the optional vtx ordering too. Thanks!  

---

