SGI Fellows: Kyle Loh, Preet Savalia
SGI Mentors: Sebastien Loriot, Mael Rouxel-Labbé
One may think that the order in which an algorithm processes geometric data should not affect its result. Consider simplifying a triangular mesh by repeatedly collapsing edges. The mesh contains the same numbers of vertices, edges, and faces. The simplification also targets the same final edge count, so one might expect approximately the same amount of computation. In practice, however, layout can significantly affect runtime.
For example, in our experiments, the three locality-aware ordering methods that we tested reduced edge-collapse time by up to 18%.
Processors rely on caches, which are small, fast stores for recently accessed data. If required data is already cached, it can be retrieved quickly; otherwise, the processor must retrieve it from slower main memory, causing a cache miss. An edge collapse accesses the faces, edges, and vertices surrounding the selected edge. When neighboring elements are stored close together in memory, the processor has more opportunities to reuse cached data. When they are scattered, those opportunities decrease, which can increase cache misses and slow the algorithm.
We investigated this effect onlamppost.obj, comparing a randomized ordering baseline against three locality-aware strategies that we re-implemented (Morton ordering [1], Hilbert ordering [2], and Tipsify [3]).

The same connected triangle group is highlighted under random and Morton orderings. Random ordering scatters these faces throughout the face array, with vertices ranging 184,989 indices, whereas Morton ordering places them in a more compact interval with vertices ranging 303 indices.
Edge Collapse: Edge collapse is an operation for reducing the complexity of a triangle mesh [4]. Given an edge connecting two vertices, the operation effectively merges its endpoints and removes triangles that become degenerate. Repeating this process reduces the number of vertices, edges, and faces while approximately preserving the original surface.

Our implementation uses CGAL’s Surface Mesh Simplification package, whoseedge_collapse algorithm iteratively collapses edges until a user-provided stopping condition is satisfied [5]. Each collapse requires information about the selected edge’s neighborhood. In particular, the algorithm accesses the endpoints, adjacent triangles, and nearby edges. Reordering the mesh attempts to assign nearby indices to elements that are likely to be accessed together, increasing the chance that their data remains available in cache.
Methods: We introduce the three locality-aware methods for re-ordering triangles/vertices in a mesh: Morton, Hilbert, and Tipsify. After re-ordering the mesh using these three methods, we compare the runtimes of the edge collapse algorithm on the re-ordered mesh against the mesh generated from randomly ordered vertices.

Morton Sorting: Morton sorting orders triangles according to the positions of their centroids by assigning them a binary number known as the key. The procedure is as follows:
1. Compute the mesh’s bounding box, which is the smallest box containing the entire mesh.
2. Divide the bounding box in half along all three coordinate axes, producing eight smaller boxes called octants.
3. Determine which octant contains each triangle’s centroid and record that octant (after encoding into bits) as the first part of the triangle’s key.
4. Divide the selected octant into eight smaller octants and again record which one contains the centroid.
5 . Repeat this subdivision to the desired level of precision. The resulting sequence of octants forms the key for each triangle.
6. Sort the triangles by their key. Since triangles in the same region begin with similar keys, this tends to place spatially nearby triangles close together in the face array.
Hilbert Curve Sorting: Hilbert sorting also orders triangles according to the positions of their centroids. Like Morton sorting, it repeatedly divides the mesh’s bounding box into octants. The difference is that it visits the octants along a continuous path. The procedure is as follows:
1. Compute the mesh’s bounding box and divide it in half along all three coordinate axes, producing eight octants.
2. Visit the eight octants in an order that moves between adjacent regions.
3. Determine which octant contains each triangle’s centroid and record its position in the traversal as the first part of the triangle’s Hilbert key.
4. Divide each octant into eight smaller octants and repeat the traversal inside it.
5. Rotate or reflect each smaller traversal so that it connects continuously to the regions visited immediately before and after it.
6. Continue subdividing to the desired level of precision. The resulting sequence of visited regions forms a Hilbert key for each triangle.
7. Sort the triangles by their Hilbert keys. Since consecutive portions of the traversal usually correspond to neighboring regions, this tends to place spatially nearby triangles close together in the face array.
Tipsify: Unlike Morton and Hilbert curves, Tipsify does not consider triangle centroid location and looks instead at which triangles share vertices. It walks across the mesh one triangle at a time while keeping track of a small list of the most recently used vertices as well as vertex-to-triangle adjacencies. The traversal proceeds as follows:
(1) For every vertex, record the triangles incident to it and count how many of those triangles have not yet been added to the reordered triangle list.
(2) Choose a current vertex. Add each of its unprocessed incident triangles to the reordered triangle list. Whenever a triangle is added, update the number of unprocessed triangles remaining at each of its vertices and update the simulated vertex-cache state.
(3) From the vertices belonging to the newly added triangles, choose a vertex from which to continue. Prefer a vertex that still has unprocessed incident triangles and is predicted to remain in the simulated cache while those triangles are processed.
(4) If no suitable nearby vertex remains, search recently encountered vertices for one that still has unprocessed incident triangles. If none exists, scan the remaining vertices until such a vertex is found.
(5) Repeat until every triangle has been added exactly once. The order in which the triangles were added becomes the new triangle order.
Remark: While Hilbert and Morton sortings were designed for CPU caches, Tipsify was originally designed for GPU caches. Here, we test whether Tipsify’s connectivity-aware triangle order also benefits a CPU edge-collapse implementation.

Experimental Details: The input lamppost.obj contains 181,850 vertices, 417,689 edges, and 239,720 triangular faces after import and triangulation with the goal of reducing to half the number of edges.
All three (deterministic) locality algorithms produced reductions to 105,303 vertices, 208,844 edges, and 107,748 faces after simplification. The random ordering varied from the deterministic algorithms by at most 3 edges for each of five trials, which is a negligible difference.


Morton sorting.
Results: Table 1 reports mean times and the mean of the five paired speedup ratios. Morton had the lowest simplification and combined times. Tipsify and Hilbert also significantly accelerated simplification, although their preprocessing costs were higher than Morton’s. Nevertheless, all three locality-aware layouts produced a significant improvement over the randomized baseline.

and paired percent reductions over five trials. ACMR is the average number
of simulated vertex-cache misses per triangle. Combined time and reduction
include ordering and simplification.
References:
[1] Fernando Cacciola, Mael Rouxel-Labbé, and Baskın Şenbaşlar. “Triangulated Surface Mesh Simplification.” CGAL User Manual, CGAL 6.2. https://doc.cgal.org/latest/Surface_mesh_simplification/ Accessed August 26, 2026.
[2] G. M. Morton. “A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing.” IBM Ltd., Ottawa, Ontario, Canada, Technical Report, 1966. https://books.google.com/books?id=9FFdHAAACAAJ
[3] Hans Sagan. Space-Filling Curves. Universitext. New York: Springer, 1994. https://doi.org/10.1007/978-1-4612-0871-6
[4] Pedro V. Sander, Diego Nehab, and Joshua Barczak. “Fast Triangle Reordering for Vertex Locality and Reduced Overdraw.” ACM Transactions on Graphics, vol. 26, no. 3, article 89, 2007. https://doi.org/10.1145/1276377.1276489
[5] Peter Lindstrom and Greg Turk. “Fast and Memory Efficient Polygonal Simplification.” In Proceedings of IEEE Visualization 1998, pp. 279–286, 1998. https://doi.org/10.5555/288216.288288








