Tiling a sphere with triangles, and the indexing trap that hid for three days

Every so often you take on something that sounds like a fun math problem and ends up being a three-day exercise in off-by-one errors. Building a planet out of triangles was one of those. The geometry itself is straightforward; the part that ate the time was mapping back and forth between a position in space and the triangle that owns it, with every mapping agreeing with every other mapping.

The geometry: a geodesic sphere is just a subdivided icosahedron

Start with the icosahedron: 12 vertices, 20 faces, all equilateral. That already tiles the sphere perfectly — every triangle is the same shape and size. But 20 triangles is a coarse planet, so you subdivide.

Each of the 20 faces becomes an equilateral triangle in barycentric space, split into a grid. A face of subdivision N becomes N² sub-triangles; the whole sphere gets 20·N². For N=8 that's 1,280 sectors; N=10 gives 2,000. Configurable planet sizes for free.

Each sub-triangle is addressed by two grid coordinates (i, j) plus an orientation flag — each grid cell holds two triangles, a "down" one and an "up" one. Position is the normalized sum of the three base vertices weighted by barycentric coordinates:

P(i, j) = normalize(i·A + j·B + (N - i - j)·C)

That's the whole construction. Fifteen minutes of code. The trap is everything that comes after.

The trap: indexing must match generation exactly

Here's the bug that cost the most time. The grid has a shape you have to respect: cell (i, j) only exists where i + j < N, and while most cells hold two triangles, the last cell of each row holds only one. The "up" triangle at (i, j) needs the corner (i+1, j+1), which is outside the face when i + j = N - 1. Generate it anyway and you get a triangle with a negative barycentric weight — a ghost triangle that silently corrupts everything downstream.

I found and fixed that in the generation loop, and declared victory. Three days of "why is there a hole in the world" later, the unit tests finally said what the editor could not:

Sector 16 has 2 flat neighbors (expected 3)
Sector 2 -> flat pos -> sector 7   (face 0 vs 0)

Two separate indexing bugs, both reverse-mapping functions still written against the assumption that every cell holds two triangles:

  1. Decode (index → grid coordinates) replayed the generation loop but consumed an "up" triangle in the last cell of each row that was never generated. From row three onward, every index was shifted.
  2. Encode (position → index) did the same arithmetic in reverse, adding 2 per cell where the last cell only contributes 1.

The lesson isn't about triangles. It's that when you have a canonical ordering — a loop that emits items — every function that reverses or re-derives that ordering must be written against the same loop, and the fastest way to catch a mismatch is a round-trip test:

for every index i:
    assert(encode(decode(i)) == i)
    assert(decode(encode(corner(i))) == i)

Which brings me to the second indexing trap, subtler than the first.

The axis trap: barycentric coordinates have an order

To find which triangle contains a position, you compute the barycentric coordinates of that position in the base face and convert them to grid coordinates. Barycentric weights come out of a 2×2 solve:

P = FA + U·(FB - FA) + W·(FC - FA)

So U is the weight on vertex B, V = 1 - U - W is the weight on vertex A. Mix those up — map U to the axis that weights A and V to the one that weights B — and every position maps to the transposed triangle. Sector (0, j) round-trips to (j, 0). In game terms: the player stands on one triangle while the code believes they're on another, so the world streams in the wrong place. The gap in front of you is the mapping disagreeing with itself, not the geometry being wrong.

The fix was one swap, and the test that caught it printed the actual answer instead of just pass/fail:

Round-trip failed: sector 2 -> flat pos -> sector 7

"That's a transpose" is only obvious because the diagnostic printed the real numbers. A bare "test failed" would have sent me chasing the wrong thing.

The flat world problem: you can't tile a sphere flat

Separate from the indexing, there's a geometry decision worth understanding. For gameplay, a fully curved spherical surface is a headache (gravity, orientation, movement all become spherical). The pragmatic version: keep the world flat and use the sphere only as the addressing layer — position on the flat plane maps to a direction from the planet center, and that direction picks a triangle.

The naive way to flatten is equirectangular projection (longitude / latitude, like a world map). It works everywhere except it doesn't: at the poles, all longitudes converge, so triangles near the pole collapse to nearly collinear points. A triangle whose three corners share a latitude is a zero-area triangle — invisible, no collision, and you've spawned the player inside it.

The clean alternative is the icosahedron net: unfold the 20 base faces into the plane by reflecting each face across shared edges. Every triangle stays a true equilateral triangle — zero distortion, no pole degeneracy, guaranteed. The cost: the net has a boundary (the cut edges), and walking off it wraps you to the far side. Wrapping is a rigid transform per cut edge, which is exactly the "walk around the planet" behavior you wanted anyway.

The deeper rule here: a sphere cannot be flattened without distortion or seams — that's topology, not a bug. Pick where you want the distortion (equirectangular puts it at the poles) or pick where you want the seams (the net puts them on 11 edges). You don't get both clean.

What the tests were really for

The star of this whole episode was the test suite, and not in the way tests usually are. The pure math — mesh construction, indexing, lookups — runs headless and deterministically. The game itself requires a full editor session to see anything at all. Every time the game showed a gap, the question was "is it the math or the rendering?" and the editor couldn't answer it. The tests could:

  • Round-trip: position → sector → position must return where you started. Catches indexing and axis swaps.
  • Structure: every face placed, no two faces overlapping, every sector's flat neighbors consistent with its geodesic neighbors and symmetric. Catches net-construction bugs.
  • Growth: streaming clusters must grow monotonically with radius. Catches the "loading in big batches" symptom.

Each test isolates one invariant and reports the specific violation, with numbers. That turned "there's a gap somewhere" into "sector 2 maps to sector 7, the axes are swapped" in a single run.

The other thing worth stealing from this: when a debugging session is stuck, stop guessing and make the thing tell you. Add a validation function that walks every sector and reports failures with coordinates. Then run it. The gap that takes a human twenty minutes to reproduce in a game session, a test reproduces in milliseconds.

The Unreal-specific part

Most of this is engine-agnostic math, but a few Unreal details are worth recording:

  • Procedural floor tiles: UProceduralMeshComponent builds a mesh section from vertex/triangle arrays at runtime, with collision. This is how you draw a triangle floor without shipping any geometry assets.
  • Backface culling bites flat triangles: a triangle viewed from above can vanish if its winding points the wrong way. Emitting every triangle twice, once per winding, is the brute-force fix that never fails (better than relying on material two-sided flags or praying about winding order).
  • Headless tests are the fast loop: UnrealEditor-Cmd.exe running Automation RunTests boots, runs, and exits without opening a window — the only sane way to iterate on pure logic. (One warning: the process has a habit of lingering and eating memory after the tests finish; kill it explicitly when done.)
  • The log file is where the answer is: test output goes to the project's Saved/Logs/fightme.log, not to stdout, no matter what -log= argument you pass. Grep for AutomationController lines.

Takeaways

  1. A geodesic sphere is 20 faces, N² sub-triangles each, and nothing else magical. All the hard parts are bookkeeping.
  2. When items come from a loop, every consumer of that ordering must be written against the same loop. Round-trip tests catch the drift.
  3. Barycentric weights come out in a specific order. Write it down, label the variables by the vertex they weight, not by guessable names.
  4. You cannot flatten a sphere cleanly. Choose distortion or seams deliberately.
  5. When stuck, stop guessing: make the system report its own violations, in numbers. A test run reproduces in milliseconds what a game session hides for hours.