Linear Storage and Integer Barycentric Coordinates for Hexagonal Grids

I. The Engineering Challenge of Hexagonal Grid Coordinate Systems

In game development, Geographic Information Systems (GIS), and data visualization, hexagonal grids are widely favored due to their uniform adjacency and isotropic distance metrics. However, when traditional Cube Coordinates map three-dimensional coordinates to a two-dimensional array, they often introduce negative indices, division operations, or lookup tables. This leads to fragmented traversal logic and frequent CPU pipeline stalls. Particularly when a grid extends from the equatorial band into the polar caps, transformation formulas must be switched based on location, causing both code maintenance costs and performance overhead to rise. Therefore, designing a unified storage scheme for the entire grid that relies solely on integer addition and subtraction is a core challenge for high-performance hexagonal grid systems.

II. Achieving Coordinate Monotonicity via Alternating △/▽ Partitioning

2.1 From Rectangular Blocks to Triangular Partitions

Consider an N×N 2D array as the rectangular projection area for the equatorial band. Using the diagonal as the boundary, the upper region (denoted as △) covers coordinate points satisfying c < y, where y = row - N and c is the column index. The lower region (denoted as ▽) covers the area where c ≥ y. The Face ID mapping is defined as follows: odd-numbered faces (e.g., Face 5, 7, 9) map to the △ region, while even-numbered faces (e.g., Face 6, 8, 10) map to the ▽ region—meaning the triangle type is assigned alternately based on row parity. This definition provides a clear prerequisite for subsequent coordinate closure proofs.

2.2 Coordinate Monotonicity and Subtraction-Free Traversal

In a standard 2D array, the two natural steps for moving downwards from (r, c) are bottom-left (r+1, c) and bottom-right (r+1, c+1).

For the △ region: Assuming the current point satisfies c < y, after moving left, y' = y+1 and c' = c, so c' < y' naturally holds. After moving right, c' = c+1 ≤ y', which still satisfies the condition. The same applies to the ▽ region: c ≥ y remains true under both steps because c and y grow synchronously. Thus, a single if (row >= N) check is sufficient to distinguish the triangle type, requiring no subdivided logic internally. This is the mathematical foundation for eliminating complex subtraction branches.

III. Implementing Float-Free Integer Barycentric Coordinates

3.1 Definition and Geometric Meaning of UVW Coordinates

In the △ region, we define u = c (horizontal offset), v = y - c (vertical projection difference), and w = N - y (distance to the top edge). All three are integers from 0 to N and satisfy u + v + w = N. In the ▽ region, to maintain consistency with the array vertex order, an offset adjustment is required: u = c - 1, v = y - c + 1, and w = N - y - 1, where their sum becomes N - 1. This difference requires the caller to explicitly agree on a coordinate normalization strategy to avoid mixed usage.

3.2 Core Code and Overflow Protection

#include <array>
#include <algorithm>
#include <climits>
struct HexGridCoord {
    int row, col;
    int N; // Rectangular block side length. N <= 46340 is recommended to avoid int overflow
    std::array<int, 3> get_uvw() const {
        // Integer overflow note: When N > 46340, (c-1)+(y-c+1)+(N-y-1) remains within int range
        // but if used for subsequent multiplications, upgrade to int64_t
        if (row < 0 || row >= 2 * N) {
            int r = std::clamp(row, 0, 2 * N - 1);
            if (r < N) return {0, 0, N};       // Near the North Pole
            else       return {N, 0, 0};       // Near the South Pole
        }
        const int y = row - N;
        const int c = col;
        if (c < y) {
            // △ region: u+v+w = N
            return {c, y - c, N - y};
        } else {
            // ▽ region: u+v+w = N-1, caller must handle normalization
            return {c - 1, y - c + 1, N - y - 1};
        }
    }
};

3.3 Polar Region Reuse and Performance Notes

For Cap vertices near the poles, the implementation unifies the return value to the nearest triangle vertex combination via row clamping, avoiding independent branches. Under specific test conditions (observed via general performance counters, non-vendor-specific data), this unified approach shows a throughput improvement trend in high-frequency graphics pipeline calls, though exact values vary by hardware and scenario. Developers are advised to set up their own benchmarks before integration to obtain quantitative data applicable to their specific environments.

IV. Operational Benefits and Engineering Validation

4.1 Scheme Comparison

Scheme	Operations	Conditional Branches	Float Division	Applicable Scenarios
Classic Cube Coordinates	3 assignments + 2 comparisons	Required	0	General but fragmented logic
Lookup Table Mapping	2 memory accesses	Optional	0	Static grids
Proposed △/▽ Arrangement	2 add/sub + 1 branch	Only 1	0	Streamed traversal / Real-time pathfinding

This scheme minimizes branching and operates with zero floating-point operations, making it highly suitable for SIMD or GPU shader batch execution.

4.2 Applicable Boundaries and Validation Recommendations

Any engineering innovation must pass both mathematical verification and performance benchmarking. This scheme is universally applicable under any positive integer N, proven by coordinate monotonicity. However, note that integer overflow risks exist for excessively large N; selecting 32-bit or 64-bit integers based on the target platform is recommended. The characteristic of the ▽ region’s coordinate sum being N-1 requires the caller to unify normalization conventions. Developers should complete migration verification from cube coordinates to this scheme before integration and conduct independent performance benchmarks on target hardware.

V. Extended Applications and Migration Guide

This scheme offers advantages in the following scenarios: A* neighbor generation in pathfinding can directly utilize the increment/decrement relationships of (u,v,w), reducing precomputed table memory; texture mapping and terrain LOD can use integer barycentric coordinates to obtain interpolation weights, avoiding seams caused by floating-point errors; collision detection can be simplified to solving integer inequalities, improving physics engine determinism.

Migration Checklist from Cube Coordinates:

1. Determine the target grid’s N value (recommended not to exceed 46340);
2. Convert cube coordinates (q, r, s) to row row = r + N and column col = q + N;
3. Evaluate col < (row - N) to determine the △/▽ region;
4. Call get_uvw() to retrieve barycentric coordinates, normalizing the results for the ▽ region as needed;
5. Check for common errors: row out of bounds, N value overflow, and ▽/△ confusion.

Conclusion

The linearized design of hexagonal grid coordinates is a systematic practice of “translating mathematical properties into code efficiency.” Starting from the geometric foundation of alternating △/▽ arrangements, this article clarified the internal logic of eliminating subtraction and branching, provided a corrected integer implementation, and outlined a complete migration guide. When facing similar mapping challenges, it is often worthwhile to first examine the inherent monotonicity of the geometry—the answer frequently lies within the most fundamental mathematical properties.