Categories
Research

Locality in Geometric Algorithms

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.

Figure 2: Three stages of an edge collapse: (1) selecting an edge and its local neighborhood, (2) merging the edge’s endpoints, and (3) updating the resulting connectivity.

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.

Figure 3: Small 2-dimensional example with (a) Morton ordering; (b) Hilbert ordering; (c) Tipsify ordering.

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.

Figure 4: The lamppost mesh under random, Morton, Hilbert, and Tipsify face orderings. Color indicates each triangle’s normalized position in the corresponding face array.

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.

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.

Table 1: Mean timing, simulated average cache miss ratio (ACMR),
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

Categories
Research

Self-Rectifying Textures

By: Kyle Loh, Mahlet Girma, Max Dunitz

If you have ever had to flatten out a bag of chips so the checkout scanner would finally read it, you already understand the problem we worked on this week. A code printed on a surface that bends, folds, or curves is hard to read, and QR codes and barcodes carry one disadvantage here: they are obvious. In supply-chain tracking, that single visible code can be tampered with, causing a product to be moved into a market it was not meant for. Our project examines self-rectifying textures, which are patterns that look like random noise, but their autocorrelation contains a regular lattice. By measuring how that lattice bends in a photo, we can recover how the surface was deformed, without printing a single visible marker.

A self-rectifying texture and a QR code printed on paper folded across an edge. The fold makes the QR code unreadable, but the texture reader still recovers the deformation and decodes the tracking information (Bencheikh et al., WACV 2026).

The usual way to undo a perspective distortion is to find distinct points (for example, the three eyes of a QR code) and use their pixel positions to solve for a homography. To stay hidden, self-rectifying textures move the landmarks into the autocorrelation of the image.

Definition of Autocorrelation: The autocorrelation measures how much an image resembles a shifted copy of itself. It is basically a dot product. For a 2D image f:ℝ2→ℝf: \mathbb{R}^2 \rightarrow \mathbb{R}, the autocorrelation is defined as follows:

Rf,f(τ)=∫ℝ2f(x)f(x+τ)dx R_{f,f}(\tau) = \int_{\mathbb{R}^2} f(x)\, f(x + \tau)\, dx

where xx is a pixel position and the lag (or shift) τ∈ℝ2\tau \in \mathbb{R}^2. A peak is defined as the τ\tau where Rf,f(τ)R_{f,f}(\tau) attains a local maximum. This operation is translation-invariant.

As autocorrelations are computationally expensive (𝒪(N2))(\mathcal{O}(N^2)), we never compute them directly. Instead, we invoke the Wiener-Khinchin theorem, allowing us to compute the autocorrelation in terms of Fourier transforms (ℱ\mathcal{F}): R=ℱ−1(|ℱ(f)|2)R = \mathcal{F}^{-1}(|\mathcal{F}(f)|^2) in 𝒪(Nlog⁡N)\mathcal{O}(N\log N).

Task 1 – Constructing Textures: We used a grayscale-version of Steamboat Willie with a fronto-parallel view as our base image.

The base image (left) and its autocorrelation plot (right) with unshifted copy τ=0.\tau=0. A plain image with no modifications give one peak at the center corresponding to τ=0\tau=0.

Next, we superimposed three copies of the image, each offset by shift vectors 0,+u,+v∈ℝ20, +u, +v \in \mathbb{R}^2, using zero-padding. We call the superimposed image the base texture. The following autocorrelation plot would have six peaks, at {±u,±v,±(u−v)}\{ \pm u, \pm v, \pm (u-v)\} . This is known as the Fundamental Hexagon. Then, we apply a deformation AA to the superimposed image, causing the fundamental hexagon to become {±Au,±Av,±A(u−v)}.\{ \pm Au, \pm Av, \pm A(u-v)\}.

The superimposed texture (left) and its six-peak fundamental hexagon (right).
The deformed texture (left) and its warped hexagon (right).

The Assignment Problem: Suppose you know the original shifts {±u,±v,±(u−v)}\{ \pm u, \pm v, \pm (u-v)\} and have access to the base texture, but not the deformation. Unfortunately, the deformed hexagon {±Au,±Av,±A(u−v)}\{ \pm Au, \pm Av, \pm A(u-v)\} alone does not tell you which peak corresponds to AuAu and which to AvAv, or their signs. However, if you can figure out this assignment problem, then you can immediately solve for AA with some linear algebra.

Given the symmetries, there are eight sign-and-order combinations. Using certain invariance properties, this can be reduced to six combinations. We find and apply six candidate inverse maps A−1A^{-1} and select the inverse map with the highest normalized cross-correlation score against the base texture. This is a computationally expensive solution, and for future work, we will explore more efficient methods for the assignment problem.

Task 2 – Full Rectification Pipeline: We introduce a method that no longer assumes a uniform linear deformation. Our goal is to recover a global inverse map ϕ−1\phi^{-1} that maps the observed texture back to a fronto-parallel image.
For this experiment, we used blurred Gaussian white noise as our base image, constructing a texture by superimposing it with two shifted copies of itself and zero-padding. We then apply a homography deformation AA.

Methodology: We sample small square patches from the grid. Then, we compute each patch’s autocorrelation and patches with “unreliable measurements” are discarded — criteria include: no valid fundamental hexagon detected or the inverse Jacobian’s determinant is a statistical outlier). For each patch, we detect the warped fundamental hexagon in each patch’s autocorrelation. Comparing these peaks with the known original shifts provides six candidates for the local inverse Jacobian Dϕ−1(yi)D\phi^{-1}(y_i).

Then, we construct a Delaunay triangulation mesh of the center points of the remaining patches. Two measurements are treated as neighbors when their centers share an edge in the mesh. To select on candidate Jacobian at each vertex, we assume that the physical deformation varies smoothly, so the correct matrices at neighboring vertices should be similar.

We resolve the candidate ambiguity using Minimum Spanning Tree propagation. First, we use a phase correlation on one patch with the original template to select one initial vertex and its actual local Jacobian Dϕ−1(yi)D\phi^{-1}(y_i). Suppose vertex ii has been already assigned the matrix Gi∗G_i^\ast while an adjacent vertex jj remains unassigned. For each of the six candidates at jj, we compute the mismatch

dij(k)=‖Gi∗−Gj(k)‖Fd_{ij}^{(k)} = \| G_i^\ast – G_j^{(k)} \|_F

and take the candidate with the minimum Frobenius norm. All edges from assigned vertices to unassigned vertices are stored in a priority queue, and we iteratively assign matrices to unassigned vertices adjacent to vertices with assignment.
Finally, we use a finite-element method that reconstructs a global inverse map whose gradient best matches the selected local Jacobians:

ϕ^−1=arg minψ∈Vh⁡∫Ω‖∇ψ(y)−A−1(y)‖Fdy.\hat{\phi}^{-1} = \argmin_{\psi \in V_h} \int_\Omega \| \nabla \psi(y)- A^{-1}(y)\|_F dy.

This determines the map up to a constant translation (the +C in integration), so we anchor the reconstructed mesh to the image boundary. We then regrid the deformed pixel values through the recovered map to produce a rectified image. For validation, we compare this result with the original template using the absolute error |rectified−template||rectified – template|.

Task 3 – Non-Planar Texture Rectification via Cylindrical Mapping: We extend our rectification pipeline to non-planar surfaces (particularly, a homography-deformed white-noise texture wrapped around a cylinder) utilizing the same MST and Finite Element Method pipeline from Task 2 to recover a global inverse deformation map.

Flattened base texture (left) and cylindrically warped base texture (right).

Note: To model deformations on cylindrical geometry, spatial coordinates (X,Y)(X,Y) in the planar texture domain are mapped to 3D surface coordinates (X,Y,Z)(X,Y, Z) for a cylinder of radius R=260px. To unroll or warp texture fields back into the reference domain, we map the angular coordinates θ=atan2(Y,X)\theta = \text{atan2}(Y,X) back into 2D planar coordinates (X,Y)(X,Y).

Flattened deformed texture (left) and cylindrically warped deformed texture (right)
The resultant unrolled rectified texture (left), cylindrically warped rectified texture (center), and the absolute error against template (right).

Conclusion: Our rectification pipeline has a clear strength: most internal vertices (from the Delaunay triangulation) have sub-pixel error in the rectification and are accurate intensity-wise. However, the pipeline also has two clear weaknesses: (1) there are larger intensity errors at the edges and corners, most likely from our failure to collect as many “good” observations near the edges and corners of the texture. However, because of the robustness properties of a self-rectifying texture, we need only small portions of the image to capture to “important information” from this deformed image. For this reason, we seldom need the area around the edges of corners of the image. (2) the dependency on accessing the template at least once in the process. Future work would entail resolving these second issue.

References:
[1] Bencheikh, Ismail, et al. “Autocorrelation-based Fiducial Markers for Traceability.” Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision. 2026.