A Solid 32³ Cube: 196,608 Quads or 6? — Greedy Meshing

▶ Live demo · Source

The working code for the article "A Solid 32³ Cube: 196,608 Quads or 6? Greedy Meshing in TypeScript". A single 32³ voxel chunk goes through three separate meshers:

1. Naive (src/voxel/naive.ts) — all six faces of every solid voxel, no questions asked.
2. Culled (src/voxel/culled.ts) — never emit a face whose neighbor is solid.
3. Greedy (src/voxel/greedy.ts) — sweep slice by slice per axis, build a 2D mask, merge neighboring faces under the same key into rectangles.

All three return the same Quad type; the comparison rests on that. The proof of correctness is not the quad count but the equality of the set of unit faces expanded by faceKeys() — because a bug that emits the same number of quads while covering a different surface really is possible (see tests/transpose-trap.test.ts).

No assets are downloaded; the chunk is generated from a seed (mulberry32 + value noise + fBm). None of the tests or the bench opens a browser.

Versions

Package	Version
three (+ @types/three)	0.185.1
vite	6.4.3
vitest	2.1.9
typescript	5.9.3

Install

npm install

Test (no browser needed)

npm test

31 tests should be green (7 files, ~1 s):

File	Tests	What it proves
tests/surface-equality.test.ts	14	5 seeds × {greedy ≡ culled set equality, Σ w·h = culled quad count} · culled ⊂ naive · naive = 6 × solidCount · on a solid 32³ cube 196,608 / 6,144 / 6 · single voxel 6/6/6 · empty chunk 0/0/0
tests/winding.test.ts	3	the triangle normal of every greedy quad points the same way as axis/dir · all six faces of a single voxel point OUTWARD · culled follows the same rule
tests/merge-key.test.ts	3	a material change stops merging · adding light to the key raises the quad count without changing the surface (ceiling = culled) · single-material chunk ≤ multi-material
tests/boundary.test.ts	3	under the solid policy a solid chunk gives 0 quads · under both policies culled ≡ greedy · air > solid
tests/geometry.test.ts	3	the index type switching Uint16 → Uint32 · attribute sizes · normals unit length, axis-aligned, no NaN
tests/transpose-trap.test.ts	3	the backbone of the article — see below
tests/index-order.test.ts	2	chunk.index() addresses the same cell as get/set · index is one-to-one

The last two files do not appear as code blocks in the article; they are the repo-side guards for the article's claims (why each of them was added is written in the mutation table below).

Why transpose-trap exists

The article says "filling the mask as mask[j + i*s] instead of mask[i + j*s] is a silent bug". The test turns that from a claim into proof: the file contains a one-character broken copy of meshGreedy and shows three things:

1. On a solid 16³ cube the two versions are identical — the quad count and the surface set alike. The sentence "I tested it with a solid cube and it held" sees nothing of this bug.
2. On an asymmetric shape the broken version emits THE SAME NUMBER of quads while covering a DIFFERENT surface (expect(bad.length).toBe(good.length) green, set equality red). Comparing counters is not proof.
3. Set equality established against the culled reference catches the broken version.

Mutation run — are the tests really guards?

I verified with mutations that no test is a tautology: make a change that breaks the claim, watch the suite go red, revert it. 15 of the 16 mutations were caught on the first pass; the single mutation that survived (M15) is the reason tests/index-order.test.ts was written.

#	Mutation	Result	File(s) that caught it
M1	greedy: transposed mask (x[u] / x[v] loops swapped)	RED	transpose-trap, boundary, surface-equality
M2	greedy: mask sign -b → b	RED	transpose-trap, winding, boundary, surface-equality
M3	greedy: x[axis]++ BEFORE the mask	RED	transpose-trap, merge-key, winding, surface-equality, boundary
M4	greedy: consumed mask cells not zeroed	RED	transpose-trap, merge-key, boundary, surface-equality
M5	greedy: height growth disabled (h always 1)	RED	transpose-trap, merge-key, boundary, surface-equality
M6	greedy: width growth disabled (w always 1)	RED	transpose-trap, merge-key, boundary, surface-equality
M7	quad: AXIS_U / AXIS_V swapped	RED	winding
M8	quad: quadTriangleIndices CCW in both directions	RED	winding
M9	culled: neighbor check removed (no culling)	RED	transpose-trap, merge-key, surface-equality, boundary
M10	culled: boundary policy ignored (always air)	RED	boundary
M11	geometry: index type always Uint16Array	RED	geometry
M12	geometry: normal component dir * 0.5 instead of dir	RED	geometry
M13	naive: the -1 face skipped on one axis	RED	surface-equality
M14	greedy: options.mergeKey ignored	RED	merge-key
M15	chunk: index() axes reversed (x + z*S + y*S²)	GREEN on the first pass	(none) → index-order was written, RED on the second pass
M16	greedy: quad material always 1	RED	transpose-trap, boundary, surface-equality

M7 and M8 turning only winding red is the expected behavior: a winding bug does not change the surface set, only the rotation direction of the triangles. The set equality test sees nothing of that bug — that is exactly why winding has a test of its own.

There is one more gap that stays open, and I am writing it down honestly: a mutation that breaks the noise functions in generate.ts does not turn the suite red. The tests are deliberately relational (greedy ≡ culled ⊂ naive); no test nails down the quad count of a particular seed, because that number is a property of the terrain generator, not of the algorithm. Change the chunk generator and the numbers in the table change while the tests stay green.

Measurement

npm run bench        # 4 tables + bench-results.json

The measurement conditions (the run the article's tables came out of): Apple M2 Pro (macOS 26.5.1), Node v22.22.2, three@0.185.1, chunk terrainChunk(1337) (32³, 4 materials, 17,191 solid voxels). The quad/vertex/triangle columns are deterministic; the ms columns are 20 warmups per mesher + the median of 11 runs, and on top of that npm run bench itself was run 11 times and the median of those 11 medians is what went into the article:

Stage	Median (ms)	Band across 11 runs	Spread
Naive	5.60	5.12 – 6.30	21%
Culled	2.06	2.03 – 2.13	5%
Greedy	1.74	1.71 – 1.76	3%

The naive column is visibly jumpy — it allocates hundreds of thousands of quad objects and the GC steps in. The dirty edit scenario (1 voxel changes, one single remesh) gave naive 4.72 ms · culled 2.10 ms · greedy 1.73 ms over 8 runs.

The measurement was taken with Chrome and desktop apps open on the machine (1-minute load average ~6.8). In the first assessment we wrote that this did not visibly inflate a single-threaded measurement — that was wrong. After the audit the same npm run bench was run back to back under load and the naive median came out 4.911 · 5.670 · 7.197 · 8.722 ms; the greedy median climbed as high as 1.930. So the time bands hold only for a QUIET machine, and the naive column can go to twice its band.

What is portable? The count columns (quad / vertex / triangle) are deterministic — identical on every run, on every machine. The ordering of the three stages also held on every run we tried. Absolute times are NOT portable; measure them yourself on your own machine, preferably with nothing else running.

The core of the expected output (count columns identical on the same machine, ms columns different):

1. TERRAIN CHUNK (policy: air)
  Naive   103,146 quad · 412,584 vertex · 206,292 triangle
  Culled    6,654 quad ·  26,616 vertex ·  13,308 triangle
  Greedy    2,416 quad ·   9,664 vertex ·   4,832 triangle

2. DATA MODEL EXPERIMENT (same solid/empty pattern, culled = 6,654 quads)
  single material, key = material         → 2,129 quads  (32.0% of culled)
  4 materials,     key = material         → 2,416 quads  (36.3% of culled)
  4 materials,     key = material + light → 6,262 quads  (94.1% of culled)

3. BOUNDARY POLICY
  air   → culled 6,654 · greedy 2,416
  solid → culled 3,578 · greedy 2,171

For the time columns I do not lean on the decimals of a single run; the table in the article carries the median of 11 runs and the run-to-run spread is written out plainly in the article too.

Demo (light)

npm run dev          # → http://localhost:5217/

Do NOT open it with file://. Double-click index.html and the ES modules will not resolve and you will see a blank screen. The Vite dev server is mandatory.

The demo is deliberately light: the scene holds a single 32³ chunk. No world, no chunk streaming, no LOD, no post-processing, no shadows, no automatic sweep. The render loop only draws; a remesh is triggered by a key press only.

Key	What it does
1 2 3	NAIVE · CULLED · GREEDY — one single remesh
4	merge key: MATERIAL ↔ MATERIAL + LIGHT
W	quad outline wireframe on/off
B	boundary policy AIR ↔ SOLID
E	carve a random sphere out of the chunk + one single remesh
R	advance the seed, generate a new chunk

The wireframe has a threshold: if the quad count goes past 25,000 the wireframe is not drawn and the HUD says OUTLINE OFF (TOO MANY QUADS: …). No silent skipping.

HUD: the MEASURED / STRUCTURAL split

The two sections sit under separate headings, because collecting them into a single list is the easiest way to show a computed value as if it had been measured:

• MEASURED — what was actually measured in that run: REMESH and GEOMETRY BUILD (performance.now()), QUADS, VERTICES (position.count), TRIANGLES and DRAW CALLS (renderer.info.render, that is, three's own counter), GEOMETRY BYTES, FPS.
• STRUCTURAL — what comes from the model, unmeasured: CHUNK, SOLID VOXELS, MASK CELLS, MODE, MERGE KEY, BOUNDARY, INDEX TYPE.

MASK CELLS shows a number in GREEDY mode only (air → 3 × 33 × 32² = 101,376, solid → 3 × 31 × 32² = 95,232); in naive and culled mode there is no such thing as a mask, so it prints —.

The HUD labels are written already in uppercase in the source and CSS does not use text-transform: combine text-transform: uppercase with a Turkish locale (lang="tr") and the browser applies the Turkish rule to the English letter i, turning it into İ, so you get TRİANGLES instead of TRIANGLES.

Build

npm run build        # tsc && vite build
npm run preview

File layout

src/
  voxel/
    chunk.ts       # CHUNK_SIZE · BoundaryPolicy · VoxelChunk (index/get/set/solidCount)
    generate.ts    # mulberry32 · makeFbm · solidChunk · terrainChunk
    quad.ts        # Axis · AXIS_U/AXIS_V · Quad · makeQuad · faceKeys · quadTriangleIndices
    naive.ts       # meshNaive — 6 quads per voxel
    culled.ts      # meshCulled — never emit a face whose neighbor is solid
    greedy.ts      # meshGreedy — slice mask + rectangle merging (MergeKey)
    geometry.ts    # MATERIAL_COLORS · quadsToGeometry · quadUVs · quadsToOutline
  view/
    main.ts        # demo: one chunk, 6 keys, manually triggered remesh
    hud.ts         # the MEASURED / STRUCTURAL split
    carve.ts       # carveSphere — the E key
    style.css      # dark cinematic + neon; NO text-transform
bench/
  remesh.ts        # 4 tables + bench-results.json (warmup 20, measure 11, median)
tests/             # 7 files, 31 tests — none of them opens a browser

Known traps (commented in the code, nailed down in the tests)

1. The transposed mask is silent — a symmetric chunk hides it, an asymmetric chunk catches it. tests/transpose-trap.test.ts.
2. The AXIS_U / AXIS_V order is not arbitrary — it is what makes (û × v̂) = +axis; swapping it flips the normals and, with a FrontSide material, shows the model from the inside. tests/winding.test.ts.
3. Where the x[axis]++ line goes — the mask is built from x[axis] and x[axis]+1, the face sits BETWEEN the two. The increment goes after the mask, before quad emission.
4. Uint16 index overflow — quads × 4 vertices, at 16,384 quads 65,535 is full; naive mode blows well past that on terrain. tests/geometry.test.ts.
5. Mixing boundary policies — both meshers have to be handed the same policy; in the demo the policy is held in a single variable.
6. computeVertexNormals() is not called — the normals are written by hand; an averaging version would round off the voxel corners.
7. The mask is allocated ONCE per chunk (Int32Array(s*s), 4 KB) and reused across all 33 slices.
8. Vitest's toEqual tells -0 apart from 0 — the cross product can produce -0, which is why winding.test.ts uses the round0 helper.

License

MIT — LICENSE.