Integer Traversal and Floating-Point-Free UVW Calculation Based on Hexagonal Grid Coordinate Mapping

1. Common Implementation Challenges in Hexagonal Grid Mapping

In spherical hexagonal grids, discrete global grids, or planar hexagonal tile maps, developers often need to establish stable index relationships among triangular, rhombic, or hexagonal cells. A typical problem occurs when a spherical surface is unfolded into several rectangular strips and each rectangle is split into two triangles: the linearized memory order of grid cells often does not match the geometric traversal direction.

A common approach is to assign a two-dimensional row-column coordinate (row, col) to each cell, then determine, based on the triangle type, whether southward traversal requires a column offset, index reversal, or subtraction. Although this approach works, it tends to introduce the following problems:

1. When row numbers increase southward, column changes are not monotonic, requiring extra branch checks.
2. Some triangular regions rely on negative indices or complement-style offsets, increasing array access complexity.
3. Barycentric coordinate calculation depends on floating-point multiplication, division, or conditional branches, making it difficult to implement consistently in integer environments or GPU kernels.

Therefore, designing a layout where geometric adjacency naturally aligns with array linearization order becomes a key factor in improving hexagonal grid implementation quality.

2. How Alternating △▽ Arrangement Eliminates Southward Traversal Subtraction

Consider splitting a rectangular strip into two triangles along its diagonal. If the first triangle is always a △-shaped triangle with its tip pointing upward and base downward, and the second triangle is always a ▽-shaped triangle with its tip pointing downward and base upward, and they alternate along the row direction, the entire strip forms a stable zigzag arrangement.

In this arrangement, when moving southward from cell (r, c), the natural stepping directions are:

• Lower left: (r+1, c)
• Lower right: (r+1, c+1)

The key point is that row number r and column number c increase together during southward movement. If the normalized vertical position is defined as y = row - N, then:

• The geometric range of a △-shaped triangle is c < y
• The geometric range of a ▽-shaped triangle is c >= y

When moving southward from the current cell to the next row, y increases by 1, while c increases by at most 1. Therefore, the next coordinate still satisfies the original triangle boundary inequality. In other words, traversal does not cross out of the current triangular partition, and there is no need to change the column offset direction.

This is the core benefit of the alternating △▽ arrangement: the geometric adjacency direction of the grid matches the index growth direction of the two-dimensional array. Southward traversal no longer depends on negative indices or complex subtraction-based branching.

3. Unified Derivation of Integer Barycentric Coordinates

In hexagonal grids, barycentric coordinates (u, v, w) usually represent the weights of a point relative to the three vertices of a triangle, satisfying:

u + v + w = N

Here N is the grid resolution or normalization coefficient. When floating-point arithmetic is used, rounding errors may cause the sum of the three weights to not exactly equal N, requiring additional correction. Using integer arithmetic directly avoids this problem.

Based on the △▽ arrangement described above, the monotonic coordinate relationship can be used to derive a purely integer get_uvw(). The basic idea is:

1. Determine whether the current cell belongs to a △ or ▽ region based on the relationship between r and c.
2. In the △ region, directly compute the three integer weights using the difference between y and c.
3. In the ▽ region, reuse the same set of integer formulas through a complementary relationship.
4. Handle polar cells as a special case, treating the pole as one vertex of a degenerate triangle and reusing the same calculation path.

In this way, both the equatorial band and the polar regions can use the same function without maintaining separate branch implementations for different regions.

4. Illustrative Implementation Structure

The following is an abstract implementation structure of this design, independent of any specific platform or language features:

function get_uvw(row, col, N):
    // Handle polar cells separately
    if is_pole(row):
        return pole_weights(row, col, N)
    y = row - N
    c = col
    if c < y:
        // △ region
        u = N - c
        v = c
        w = y - c
    else:
        // ▽ region
        u = N - y
        v = y
        w = c - y
    return (u, v, w)

The key points of this structure are:

• No floating-point multiplication or division appears.
• No negative indices appear.
• All branches only distinguish triangle orientation, not offset direction correction.
• The polar special case only handles degenerate conditions and does not affect the main equatorial path.

For more complex spherical grids, polar cells can also be treated as multiple degenerate triangles sharing the same vertex, allowing the same integer weight calculation to be reused.

5. Impact on Traversal and Cache Friendliness

Aligning geometric traversal direction with array linearization direction not only reduces branching but also improves cache locality. When accessing cells sequentially southward through (r+1, c) or (r+1, c+1), the memory addresses of adjacent cells also tend to be contiguous. For scenarios that require batch grid state updates, adjacency computation, or flow field simulation, this arrangement can reduce the proportion of random access.

In addition, because column offset only has two possible values, 0 or +1, compilers and underlying hardware can perform branch prediction more easily. Even if separate paths need to be kept for the two triangle orientations, the actual executed instruction sequence remains very short.

6. Design Boundaries and Applicability

It should be noted that this alternating △▽ arrangement is suitable for cases where the target region can be divided into regular N × N rectangular blocks, and each rectangular block contains only two triangles. For grids with non-uniform resolution, adaptive subdivision, or hanging nodes, this arrangement may not be directly applicable and may require additional boundary handling or hierarchical indexing.

Furthermore, although the polar special case can reuse the integer weight formulas, geometric degeneration of cells near the poles is more pronounced. If the application does not require high polar accuracy, the unified branch can be used directly. If strict preservation of spherical area or angular properties is required, further adjustment based on the specific projection method is needed.

Overall, the main value of this design is that by adjusting the arrangement order, the grid topology relationship becomes consistent with the array index growth direction. This makes it possible to replace floating-point arithmetic and subtraction-based branching with integer operations, simplifying the implementation complexity of hexagonal grid traversal, indexing, and barycentric coordinate calculation.