Chapter 6: LOD Control with SSE

Introduction

GIS tile maps switch resolution based on zoom level, but in 3D, SSE (Screen Space Error) automatically determines the appropriate level by evaluating camera distance and on-screen pixel size. This is an industry-standard technique also adopted by Cesium and the OGC 3D Tiles specification.

We also implement 3D-specific optimizations not found in 2D maps, such as horizon culling (excluding tiles behind the horizon) and frustum culling (excluding tiles outside the field of view). Rotate and zoom the camera to observe how the tile color coding changes dynamically.

What You Will Learn

• Geometric Error (tile ground width) definition —— A measure of geometric coarseness that forms the basis for LOD decisions
• Screen Space Error (SSE) concept and formula —— Quantifying how many pixels a tile's coarseness occupies on screen
• Tile selection algorithm via quadtree traversal —— The 3D version of 2D map tile selection
• Frustum culling and horizon culling —— 3D-specific rendering optimizations not found in 2D maps
• Bounding sphere calculation —— Circumscribed sphere approximation using latitude correction (cosLat) and SQRT2
• Efficient scene management through differential updates (add/remove) —— Processing only the differences from the previous frame
• Avoiding unnecessary recalculation by detecting camera matrix changes —— Eliminating wasteful processing when the camera is stationary

Real-Time Statistics

As you rotate and zoom the camera, the tile colors change dynamically in the demo on the left. Observe how areas closer to the camera use higher zoom levels (blue to purple), while distant areas use lower zoom levels (red to yellow).

Why LOD Control Is Necessary

Attempting to display the entire Earth at zoom level 18 would require approximately 68.7 billion tiles. Obviously, loading and rendering all of them simultaneously is impossible.

LOD (Level of Detail) control is a technique that displays areas close to the camera at high resolution and distant areas at low resolution. In WebGIS, this is achieved by "using higher zoom level tiles for regions closer to the camera and lower zoom level tiles for distant regions."

Geometric Error

A tile's Geometric Error represents "how coarsely the tile approximates the ground surface." In this book, we use the tile's ground width at the equator.

/** Tile Geometric Error (ground width in meters) */
export function tileGeometricError(z: number): number {
  // Width of one tile at the equator [m] = 2*PI * R / 2^z
  return (2 * Math.PI * WGS84.a) / (1 << z);
}

1 << z is a bit shift for computing 2^z, which is faster than Math.pow(2, z). The Geometric Error halves with each increase in zoom level.

Why Is It Called "Error"?

Geometric Error is not simply "the ground width of a tile" but rather the error relative to the actual ground surface (an infinitely detailed ideal representation). Mountains, cities, coastlines, and other details that would have been visible with further subdivision represent the ground truth, and approximating them with a single tile introduces positional deviation and omission up to that width.

In other words, Geometric Error is the upper bound on "how far off from the ideal representation we could be when we stop subdividing at this tile."

What Is Screen Space Error (SSE)?

SSE is a metric that converts Geometric Error (ground width in meters) into on-screen pixel count. It represents "how many pixels this tile's error appears as on the user's screen" and is compared against a threshold to decide whether to subdivide or accept the tile. This concept is widely used in 3D Tiles and CesiumJS.

For example, consider a zoom level 4 tile (Geometric Error = 2,505km). The SSE varies significantly depending on the distance from the camera:

• A 2,505km error appears as only 3 pixels on screen → indistinguishable to the human eye → the tile is sufficient
• A 2,505km error appears as 500 pixels on screen → clearly looks blurry → should subdivide into child tiles

In other words, SSE converts Geometric Error, a physical error, into "how coarse it appears to the user's eye," serving as a yardstick for determining whether subdivision is needed.

SSE Formula

A larger SSE means "the error is more noticeable on screen."

/** Compute Screen Space Error */
export function computeSSE(
  geometricError: number,
  distance: number,
  screenHeight: number,
  fovRad: number
): number {
  if (distance <= 0) return Infinity;
  return (geometricError / distance) *
    (screenHeight / (2 * Math.tan(fovRad / 2)));
}

When distance <= 0, Infinity is returned. This safely handles cases where the tile overlaps with the camera or is behind it. If SSE is Infinity, the tile is always subdivided.

Quadtree Traversal Algorithm

The tile coordinate system is essentially a quadtree. Starting from the root tile (0,0,0) at zoom level 0, each tile has four child tiles. SSE-based LOD control traverses this quadtree from the root, determining at each node whether "this tile is sufficient or should be subdivided into child tiles."

           (0,0,0)          z=0
          /   |       (0,0,1) (1,0,1) ...     z=1
    / | (0,0,2) (1,0,2) ...         z=2

export function selectVisibleTiles(
  cameraPosition: { x: number; y: number; z: number },
  fovRad: number,
  screenHeight: number,
  frustumPlanes: FrustumPlane[],
  sseThreshold = 400,
  maxZoom = 6,
  maxTiles = 128
): VisibleTile[] {
  const result: Array<VisibleTile & { dist: number }> = [];

  // Pre-computation for horizon culling (done once outside the loop)
  const camDist = Math.sqrt(
    cameraPosition.x ** 2 +
    cameraPosition.y ** 2 +
    cameraPosition.z ** 2
  );

  function traverse(x, y, z): void {
    const center = tileCenterScene(x, y, z);
    const radius = tileBoundingSphereRadius(x, y, z);

    // 1. Horizon culling (requires only one dot product)
    if (!isAboveHorizon(center, radius, cameraPosition, camDist))
      return;

    // 2. Frustum culling (6-plane test)
    if (!sphereInFrustum(center, radius, frustumPlanes))
      return;

    // 3. SSE evaluation
    const distance = ...; // Distance to camera
    const sse = computeSSE(
      tileGeometricError(z), distance, screenHeight, fovRad
    );

    if (sse <= sseThreshold || z >= maxZoom) {
      result.push({ x, y, z, dist: distance }); // Accept
      return;
    }

    // 4. Subdivide into 4 child tiles and recurse
    traverse(x*2,   y*2,   z+1);
    traverse(x*2+1, y*2,   z+1);
    traverse(x*2,   y*2+1, z+1);
    traverse(x*2+1, y*2+1, z+1);
  }

  traverse(0, 0, 0);
  // When exceeding maxTiles, sort by distance and keep only the closest
  return result;
}

Algorithm Processing Flow

traverse(0,0,0)
  |
  +-- Horizon culling --> Behind the Earth? --> return
  |
  +-- Outside frustum? --> return (culled)
  |
  +-- SSE <= threshold or z >= maxZoom? --> result.push (accept)
  |
  +-- SSE > threshold --> Subdivide into 4 and recurse
       +-- traverse(0,0,1)
       +-- traverse(1,0,1)
       +-- traverse(0,1,1)
       +-- traverse(1,1,1)

The culling execution order is horizon culling → frustum culling → SSE evaluation. Horizon culling requires only a single dot product, so it is executed before the 6-plane frustum culling test to reduce costs.

Meaning of SSE Threshold and maxTiles

sseThreshold = 400 means "accept the tile if its coarseness is 400 pixels or less on screen." A smaller value yields higher quality (more tiles loaded), while a larger value yields lower quality (fewer tiles needed).

maxTiles (default 128) is the maximum number of tiles displayed at once. When the quadtree traversal result exceeds this limit, tiles are sorted by distance from the camera and only the closest ones are kept.

if (result.length > maxTiles) {
  result.sort((a, b) => a.dist - b.dist);
  result.length = maxTiles;
}

This limit serves two purposes:

• GPU resource protection: If tile count grows unbounded, the number of meshes explodes and rendering performance degrades
• Frame rate stabilization: Capping the number of network requests prevents bandwidth saturation

Distance sorting ensures that tiles closer to the camera (the area the user is focusing on) are kept preferentially. Since distant low-resolution tiles are the ones discarded, visual impact is minimal.

Horizon Culling

Because the Earth is a sphere, tiles beyond the horizon as seen from the camera are never visible. Horizon culling is an optimization that efficiently excludes these "far side of the Earth" tiles.

          Camera *
         /       |
        /  Visible|
       /         |
------*----------|---- Horizon
   Tangent   Not visible
   point       *
              Tile

The tangent line from the camera to the Earth forms the horizon. Tiles on the near side of the tangent line may be visible, while tiles beyond the tangent line are occluded by the Earth.

The isAboveHorizon Function

Since the Earth is not a sphere but an oblate ellipsoid, the horizon position varies depending on the camera direction. By dynamically computing the ellipsoid radius in the camera direction, accurate horizon culling on the ellipsoid is achieved.

/** Compute the ellipsoid radius in the camera direction.
 * Ellipsoid equation: (x²+z²)/a² + y²/b² = 1 */
function ellipsoidRadiusInCameraDir(
  dirX: number, dirY: number, dirZ: number
): number {
  const a = WGS84.a;
  const b = WGS84.b;
  return 1 / Math.sqrt(
    (dirX * dirX + dirZ * dirZ) / (a * a)
    + (dirY * dirY) / (b * b)
  );
}

This is the same math as ellipsoidRadiusInDirection from Chapter 2, but here we use a scalar-argument version that does not depend on Three.js.

export function isAboveHorizon(
  tileCenter: { x: number; y: number; z: number },
  tileRadius: number,
  cameraPosition: { x: number; y: number; z: number },
  cameraDistance: number
): boolean {
  // Camera direction unit vector
  const invD = 1 / cameraDistance;
  const camDirX = cameraPosition.x * invD;
  const camDirY = cameraPosition.y * invD;
  const camDirZ = cameraPosition.z * invD;

  // Ellipsoid radius in camera direction (dynamic calculation, not sphere approximation)
  const R = ellipsoidRadiusInCameraDir(
    camDirX, camDirY, camDirZ
  );

  // If camera is inside the ellipsoid, do not cull
  if (cameraDistance <= R) return true;

  // Projection of tile center onto camera direction (dot product)
  const proj = tileCenter.x * camDirX
             + tileCenter.y * camDirY
             + tileCenter.z * camDirZ;

  // Horizon cutoff distance: R^2 / d
  const horizonCut = R * R * invD;

  // If the entire bounding sphere is on the far side, it is invisible
  return proj + tileRadius >= horizonCut;
}

Mathematical Background of Horizon Culling

When the camera is at distance d from the origin, with R being the ellipsoid radius in the camera direction, the tangent point to the ellipsoid lies at a projection distance of R^2 / d along the camera direction. Since R is dynamically computed by ellipsoidRadiusInCameraDir, it correctly reflects different horizon positions for equatorial and polar directions.

        d
*-----------------* Camera
        | R^2/d
        *--- Tangent point
       /
      / R (ellipsoid radius in camera direction)
     /
    * Origin

This R^2/d (the horizonCut in the code) forms the visible/invisible boundary. When the projection of the tile center onto the camera direction proj is less than horizonCut, the tile is beyond the horizon. However, since tiles have size, the bounding sphere radius tileRadius is added to the evaluation:

Only tiles satisfying this condition are determined to be "potentially visible."

Guard for when the camera is inside the ellipsoid: When cameraDistance <= R, the concept of a horizon does not apply, so all tiles are treated as visible.

Frustum Culling

Tiles not within the camera's frustum do not need to be rendered. Frustum culling terminates traversal of off-screen tiles early.

Bounding Sphere Calculation

We compute the bounding sphere (center and radius) for each tile.

export function tileBoundingSphereRadius(
  x: number, y: number, z: number
): number {
  const bounds = tileBounds(x, y, z);
  const latCenter = (bounds.north + bounds.south) / 2;
  const cosLat = Math.cos(degToRad(latCenter));
  return ((tileGeometricError(z) * cosLat) / 2) * Math.SQRT2;
}

Steps for calculating the bounding sphere radius:

1. Tile width at the equator * cos(lat) corrects to the actual width at that latitude
2. Half the width gives half the side of the square
3. * SQRT(2) converts to half the diagonal of the square (= circumscribed circle radius)

Why the cosLat Correction

tileGeometricError(z) is the width of one tile at the equator (in meters). In the Mercator projection, tile images are stretched at higher latitudes, so the actual ground area for the same zoom level is largest at the equator and smallest near the poles. Multiplying by cosLat corrects to the actual tile width at that latitude.

• Equator (lat=0): cosLat = 1.0 → no correction
• Latitude 60 degrees: cosLat = 0.5 → radius is half of equatorial
• Near poles (lat=85 degrees): cosLat = 0.087 → radius is about 1/11 of equatorial

Math.SQRT2 (=SQRT(2)) comes from the fact that the diagonal of a square is SQRT(2) times its side. The circumscribed circle (bounding sphere) radius of a square tile is half the side * SQRT(2).

Frustum Test Implementation

/** Check if a sphere is within the frustum */
function sphereInFrustum(
  center: { x: number; y: number; z: number },
  radius: number,
  planes: FrustumPlane[]
): boolean {
  for (const plane of planes) {
    const dist =
      plane.normal.x * center.x +
      plane.normal.y * center.y +
      plane.normal.z * center.z +
      plane.constant;
    if (dist < -radius) return false;
  }
  return true;
}

A frustum is defined by 6 planes (near, far, left, right, top, bottom). For each plane, if the signed distance from the sphere's center is less than the negative radius, the sphere is completely outside the frustum. If even one plane excludes the sphere, false is returned; if the sphere is inside (or intersecting) all planes, true is returned.

Extracting Frustum Planes

The 6 planes are generated by the extractFrustumPlanes function in tile-layer-utils.ts.

export function extractFrustumPlanes(
  camera: THREE.PerspectiveCamera
): FrustumPlane[] {
  const frustum = new THREE.Frustum();
  const matrix = new THREE.Matrix4().multiplyMatrices(
    camera.projectionMatrix,
    camera.matrixWorldInverse
  );
  frustum.setFromProjectionMatrix(matrix);

  return frustum.planes.map((plane) => ({
    normal: { x: plane.normal.x, y: plane.normal.y, z: plane.normal.z },
    constant: plane.constant
  }));
}

The product of camera.projectionMatrix (projection matrix) and camera.matrixWorldInverse (view matrix) forms the clip matrix. Three.js's Frustum.setFromProjectionMatrix extracts the 6 planes from this clip matrix.

The result is converted to the FrustumPlane type ({ normal: { x, y, z }, constant }) because the core/ layer does not depend on Three.js.

Worked Example: Camera Above Tokyo

z=0 --- SSE high --> Subdivide
  z=1 -+-- Quadrant containing Japan: SSE high --> Subdivide
        |    z=2 --- Near Japan: SSE high --> Subdivide further...
        |           z=3 --- Tokyo: SSE still high --> Subdivide
        |                  z=4 --- SSE <= threshold --> Accept!
        +-- Atlantic: Outside frustum --> Culled
        +-- Antarctica: SSE low --> Accept at z=1
        +-- Pacific: SSE low --> Accept at z=1

As a result, high zoom level (high resolution) tiles are selected for the area near Tokyo close to the camera, while low zoom level (low resolution) tiles are selected for distant locations.

Calling selectVisibleTiles

const tiles = selectVisibleTiles(
  cameraPos,       // Camera position
  fovRad,          // FOV (radians)
  containerHeight, // Render area height (px)
  frustumPlanes,   // 6 planes
  400,             // SSE threshold (px)
  6,               // Max zoom
  128              // Max tile count
);

Differential Updates

Destroying and recreating all tiles every frame is inefficient. Instead, we compare the Map of tiles displayed in the previous frame (activeTiles) with the current frame's selection result, and only process tiles to add and tiles to remove.

Furthermore, when the camera matrix has not changed from the previous frame, tile selection itself is skipped. cameraMatrixChanged() detects changes by comparing all 16 elements of the 4x4 matrix.

// Per-frame processing
camera.updateMatrixWorld();

if (cameraMatrixChanged()) {
  const needed = selectVisibleTiles(...);

  // Remove and dispose of tiles no longer needed
  for (const [key, mesh] of activeTiles) {
    if (!needed.has(key)) {
      scene.remove(mesh);
      mesh.geometry.dispose();
      mesh.material.dispose();
    }
  }

  // Create and add new tiles
  for (const tile of needed) {
    if (!activeTiles.has(key)) {
      // computeTileGeometry + add to scene
    }
  }
}

Key Points for Unit Tests

tile-tree.test.ts comprehensively tests each component of the LOD control. Particularly important is the partition verification.

Partition Verification Test

The test verifying that the quadtree traversal result is "a complete partition with no gaps or overlaps" is an uncommon unit testing technique. For a correct quadtree traversal:

• The selected leaf tiles exactly cover the region of the z=0 root tile without gaps or excess
• If a parent tile is selected, its child tiles are not selected (no overlap)
• There is no region that does not belong to any leaf tile (no gaps)
• Tiles excluded by horizon culling are treated as legitimate gaps

This test is run at multiple camera distances (1.5R, 2.0R, 3.0R, 5.0R), ensuring correctness that is not dependent on camera position.

Summary

In this chapter, we implemented SSE-based LOD control.

• SSE: Geometric Error / distance * screen factor quantifies "on-screen coarseness"
• Geometric Error: Ground width per zoom level (2*PI*R / 2^z)
• Quadtree traversal: Recursively evaluate SSE from root; accept below threshold, subdivide into 4 above
• Horizon culling: Dynamically compute ellipsoid radius R in camera direction, exclude far side of Earth with a single dot product (R^2/d cutoff)
• Frustum culling: Bounding sphere vs. 6 frustum plane intersection test
• Bounding sphere: Latitude correction (cosLat) * SQRT(2) approximates the circumscribed sphere of a square tile
• maxTiles: Distance-sorted tile count limit (default 128) protects GPU resources