Gint — Technical Architecture

Geographic Interleaved Binary Format
interleave (Morton bit-interleaving) · integer (64-bit integer code) · intended (purposefully designed LOD)
Spatial indexing × LOD encoding × GPU rendering — unified in a single pipeline

1. Problems with the Traditional Approach

Most web GIS implementations rely on map tiles (slippy tiles / MVT), where servers pre-generate separate file sets for each zoom level and serve them on demand.

Problem	Root Cause	Cost
Tile count explosion	Total tiles at zoom z = 4z	268 M tiles at z=14
Network on every zoom	Each zoom level requires different tiles	Multiple requests per zoom interaction
CPU triangulation	Concave/holed polygons can't be sent directly to the GPU	earcut O(n²) per frame
Static LOD management	Multiple resolutions pre-generated as separate files	Storage multiplied by number of LOD levels

Gint solves all four problems with one file, zero additional network, no CPU triangulation.

2. Pipeline Overview

3. Stage 1 — Encoding

3.1 Morton Order (Z-order Curve)

A Morton code maps a 2D coordinate (x, y) to a single integer by interleaving the bits of x and y, alternating one bit from each dimension.

// 2D → Morton code (supports 32-bit coordinates)
function morton2D(x, y) {
	let r = 0;
	for (let i = 0; i < 32; i++) {
		r |= ((x >> i) & 1) << (2*i);      // X bit at even positions
		r |= ((y >> i) & 1) << (2*i + 1);  // Y bit at odd positions
	}
	return r;
}

// Viewport feature extraction via bit-mask (zoom level z)
// At z=6, the top 12 bits (2×6) form the tile address
const mask    = ~(0xFFFFFFFFFFFFFFFFn >> BigInt(2*z));
const tileKey = mortonCode & mask;  // features in same tile share the same prefix

3.2 Visvalingam-Whyatt Weight (LOD Tag)

Each vertex is pre-tagged with the area of the triangle it forms with its two neighbors — a measure of how much geometric information would be lost if that vertex were removed. High-weight vertices are always included; low-weight vertices appear only at high zoom levels.

// Compute VW weights for all vertices at encode time
function computeVWWeights(polygon) {
	const n = polygon.length;
	return polygon.map((_, i) => triangleArea(
		polygon[(i - 1 + n) % n],
		polygon[i],
		polygon[(i + 1) % n]
	));
}

// Vertex filter at decode time (per zoom level)
// Physical pixel size in map units at zoom level z
// (Mercator projection, 256px tile size)
const metersPerPx = (40075016 / (256 * Math.pow(2, z)));
const threshold   = metersPerPx * metersPerPx;  // 1px² — sub-pixel vertices are invisible
const activeVerts  = vertices.filter(v => v.weight >= threshold);

4. Stage 2 — GPU VB Write (one-time)

The client receives a GeoPBF from the server and decodes it exactly once into the gint structure (Morton-sorted, VW bits unpacked), uploading all vertices to the GPU vertex buffer in a single call. No additional network requests are ever issued. LOD (vertex culling by VW threshold) is handled by the vertex shader every frame in Stage 3.

4.1 Viewport Query via Morton Bit-Shift

// Find features inside the viewport at zoom level z
// The top 2z bits of a 64-bit Morton code encode the tile address

const tileAddr  = morton2D(tileX, tileY);      // top-left tile of viewport
const shiftBits = 64 - 2 * z;                     // how many bits to shift
const prefix    = tileAddr >> BigInt(shiftBits);   // top 2z bits

// Binary search over the sorted Morton array
const lo      = lowerBound(features, prefix << BigInt(shiftBits));
const hi      = upperBound(features, ((prefix + 1n) << BigInt(shiftBits)) - 1n);
const viewport = features.slice(lo, hi);  // O(log n) — no server round-trip

4.2 Zoom Level to LOD Mapping

Zoom	LOD	VW Threshold (example)	Active Vertices	Tile-based equivalent
z = 2	LOD 0	maxW × 0.50	22 vertices	1 tile fetch
z = 4	LOD 1	maxW × 0.20	44 vertices	4 tile fetches
z = 6	LOD 2	maxW × 0.07	88 vertices	16 tile fetches
z = 8	LOD 3	maxW × 0.018	176 vertices	64 tile fetches
z = 10	LOD 4	0 (all vertices)	352 vertices	256 tile fetches

5. Stage 3 — GPU Stencil Tessellation

Rendering polygons in WebGL normally requires the CPU to triangulate them first (e.g., earcut), before the data can be uploaded to the GPU. Concave polygons and polygons with holes are particularly expensive, making high frame rates difficult.

Stencil tessellation eliminates CPU triangulation entirely, passing the raw vertex sequence directly to the GPU and rendering in exactly two passes.

5.1 Pass 1: Stencil Pass (Even-Odd Count)

// Generate fan triangles from NDC origin (0,0) to every consecutive edge
// An N-vertex polygon produces exactly N triangles — no CPU logic required

for (let i = 0; i < N; i++) {
	drawTriangle(
		[0, 0],          // NDC origin (constant)
		vertices[i],       // current vertex
		vertices[i+1]    // next vertex
	);
}

// WebGL stencil configuration
gl.stencilOp(gl.KEEP, gl.KEEP, gl.INVERT);  // XOR on every overlap (0→1→0→1…)
gl.stencilFunc(gl.ALWAYS, 0, 0xFF);
gl.colorMask(false, false, false, false); // color buffer: writes disabled

Pixels where fan triangles overlap an odd number of times = polygon interior. Pixels with an even count = exterior or hole. The even-odd rule emerges naturally from the stencil XOR accumulation.

5.2 Pass 2: Color Pass

// Only draw where stencil is odd (interior pixels)
gl.stencilFunc(gl.EQUAL, 1, 0x01);  // pass only where bit 0 = 1
gl.colorMask(true, true, true, true);
drawFullscreenQuad(fillColor);     // single quad fill — GPU handles the rest

5.3 Concave Polygons and Holes — Automatic

5.4 Sphere Culling — Horizon-Straddling Polygons

The fan stencil works correctly for 2D flat rendering. On an orthographic globe, a polygon can span the horizon — the visible boundary of the sphere where the surface transitions from front to back. Back-hemisphere vertices have p.z < 0 in eye space: they are invisible but still participate in fan triangles.

The Naive Approach: Collapse Backface Vertices to NDC Origin

// ❌ Creates degenerate triangles at the horizon
if (p.z < 0.0) { gl_Position = vec4(0.0, 0.0, 0.0, 1.0); return; }

Collapsing to the fan pivot creates zero-area (degenerate) triangles for every edge that crosses the horizon:

• EXIT (visible → back): backface endpoint lands on the fan pivot — zero-area triangle.
• BACK-BACK (both back): both endpoints collapse — the horizon arc between them is never filled.
• ENTRY (back → visible): symmetric to EXIT.

The Fix: Push Backface Vertices to the Horizon Circle

Instead, push each backface vertex outward to the horizon circle (the sphere's projected limb, radius u_scale px), preserving its screen-space direction from the globe center:

// ✅ Push to horizon circle — eliminates degenerate triangles
if (p.z < 0.0) {
	vec2 v = p.xy - u_viewport * 0.5;     // direction from globe center
	float d = length(v);
	gl_Position = d < 1e-4                 // guard: vertex exactly at center
		? vec4(0.0, 0.0, 0.0, 1.0)
		: toNDC(u_viewport * 0.5 + v * (u_scale / d));
	return;
}

6. Performance Comparison

Metric	Traditional Tile Approach	Gint
File count	O(4z) tiles	1 file
Initial load	Only tiles needed for current z	Single file containing all LOD levels
Bytes on zoom	Multiple new tile fetches per zoom	+0 bytes
Viewport query	Server request with tile x/y/z	Morton bit-shift O(log n) — local
LOD switching	Re-fetch different tile set	In-memory filter only — instant
CPU triangulation	earcut O(n²) every frame	Not required — GPU stencil
Holed / concave polygons	Special-cased in earcut	Even-odd rule — automatic
Pre-generation cost	All zoom levels × all tiles	One-time encode: Morton sort + VW

7. Design Philosophy

How geographic data is represented is also a choice about which level of detail to treat as "reality." Just as NaturalEarth's physical/cultural distinction organizes phenomena on Earth from a human perspective, gint's LOD design implements the idea that what is visible changes dynamically with scale.

The VW weight quantifies "how much shape information would be lost by removing this vertex." In information-theoretic terms it is a measure of significance — a way to numerically distinguish the essential structure of a coastline or boundary from detail that is only meaningful at finer observation scales.

One other quirk specific to orthographic globe rendering: polygons that cross the antimeridian (±180° longitude) must be split at that boundary before rendering, or they wrap the wrong way around the sphere. Together with sphere culling, these two edge cases are the quietly non-obvious surprises that separate a flat map renderer from a true globe renderer.

---

Demo Files

File	Content	Pipeline Stage
GINT.html	Morton order animation, interactive VW weight visualization	Stage 1 — Encoding
LOD.html	Dynamic LOD: vertex shader discards vertices by VW threshold every frame	Stage 3 — GPU Rendering
ST.html	GPU stencil tessellation vs. CPU earcut comparison	Stage 3 — GPU Rendering