Emmanuel

Posted on Jan 11

O(1) Country Selection on a 3D Globe with GPU Picking and Hemisphere Detection

#threejs #angular #performance #algorithms

How we achieved 99.5% faster country selection using ID textures and fixed the "clicking Asia selects Argentina" bug

Problem: Selecting countries on our 3D globe took 45ms using CPU raycasting against 241 meshes. Worse, clicking on a visible country sometimes selected one on the opposite side of the globe.

Solution: Replaced O(n) raycasting with O(1) GPU pixel reading using a pre-generated ID texture where each country has a unique RGB color. Added dot product hemisphere detection to ensure only front-facing countries respond to clicks.

Result: Selection time dropped from 45ms to <1ms (99.5% faster), and the "see-through globe" bug is completely fixed.

Role: Solo Full-Stack Engineer | Timeline: 3 days | Team: 1 (me)

Impact: Reduced country selection latency from 45ms to <1ms (99.5% improvement), eliminated a confusing UX bug where users could accidentally select countries on the opposite hemisphere, and established a pattern for GPU-accelerated picking that scales to any number of selectable objects.

The Problem: Two Bugs, One Globe

Our 3D Global Dashboard lets users click countries to explore facts, play quizzes, and view bird migration paths. Two issues made this interaction frustrating:

Bug 1: Slow Selection (45ms per click)

The standard Three.js approach uses raycasting:

// Traditional approach: O(n) raycasting
const raycaster = new Raycaster();
raycaster.setFromCamera(mouse, camera);

// Test ray against ALL 241 country meshes
const intersects = raycaster.intersectObjects(countries.children, true);

if (intersects.length > 0) {
  return intersects[0].object.name;  // First hit wins
}

With 241 country meshes (each with complex polygon geometry), this took 45ms per click on average. Users felt the lag.

Bug 2: See-Through Selection (The Niger/Nigeria Problem)

Raycasting returns all intersections along the ray, sorted by distance. But on a sphere, a ray can pass through both the front and back surfaces:

Camera → [Front: Nigeria] → [Back: Argentina]
         ↑ User sees this   ↑ Ray hits this too!

If the front mesh had a gap (between Nigeria and Niger, for example), the ray would pass through and hit Argentina on the back of the globe. Users clicking on Africa would suddenly see South American country data.

Investigation: Finding the Bottlenecks

Profiling the Raycasting

Chrome DevTools Performance panel revealed the issue immediately:

Click Event Timeline:
├── Event dispatch:        2ms
├── Raycaster setup:       1ms
├── intersectObjects():   41ms  ← BOTTLENECK
├── Process result:        1ms
└── Total:                45ms

The intersectObjects() call with recursive: true was testing the ray against every triangle in every country mesh. With 241 countries averaging ~500 triangles each, that's ~120,000 triangle intersection tests per click.

Reproducing the See-Through Bug

User reports said "I clicked on Nigeria but got Argentina." Debug logging revealed the issue: multiple intersections for a single click—one on the visible country, another on the opposite hemisphere. When the front mesh had gaps (between Niger and Nigeria), the ray passed through and selected Argentina on the back of the globe.

Understanding the Geometry: Why Rays Pierce Spheres

A ray from the camera can intersect a sphere at two points: entry and exit.

        Camera
           \
            \  Ray
             \
              ↘
         ┌─────────┐
        /   GLOBE   \
       /      ●      \    ← Entry point (front)
      │    Center    │
       \      ●      /    ← Exit point (back)
        \           /
         └─────────┘

Three.js raycasting returns both intersections; gaps in front-facing meshes allow rays to hit the back of the globe geometrically correct, but UX-incorrect.

The Math Behind It

For a ray R(t) = origin + t * direction and a sphere centered at C with radius r:

|R(t) - C|² = r²

Solving for t gives 0, 1, or 2 solutions:
- 0 solutions: ray misses sphere entirely
- 1 solution: ray tangent to sphere (rare edge case)
- 2 solutions: ray enters AND exits sphere (common case)

When clicking on a globe, we almost always get two intersection points. The question becomes: which one did the user intend to click?

Solution 1: GPU-Based ID Texture Picking

Instead of testing a ray against 241 meshes, we render a special "ID texture" where each country is a unique solid color. Then we simply read the pixel under the mouse.

How It Works

1. Pre-generate a texture where each country = unique RGB color
2. Load texture and build color→country lookup map
3. On click: read the pixel at mouse position
4. Decode RGB → country ID (O(1) lookup)

Generating the ID Texture

We pre-generate a 2048x1024 equirectangular texture where each country is filled with a unique color. The generation script:

// scripts/generate-country-id-map.ts

interface CountryIdData {
  metadata: {
    generatedAt: string;
    totalCountries: number;
    encoding: string;
  };
  countries: Record<string, {
    name: string;
    index: number;
    encodedColor: { r: number; g: number; b: number; hex: string };
  }>;
}

function generateCountryIdMap(geojson: FeatureCollection): CountryIdData {
  const countries: CountryIdData['countries'] = {};
  let index = 1;  // Start at 1, reserve 0 for "no country"

  for (const feature of geojson.features) {
    const countryCode = feature.properties.ISO_A3;

    // Encode index as RGB (24-bit color = 16.7M unique values)
    const r = (index >> 16) & 0xff;
    const g = (index >> 8) & 0xff;
    const b = index & 0xff;

    countries[countryCode] = {
      name: feature.properties.NAME,
      index,
      encodedColor: {
        r, g, b,
        hex: `#${index.toString(16).padStart(6, '0')}`
      }
    };

    index++;
  }

  return {
    metadata: {
      generatedAt: new Date().toISOString(),
      totalCountries: index - 1,
      encoding: 'RGB24'
    },
    countries
  };
}

This produces two files:

country-id-map.png — The texture with unique colors per country
country-id-lookup.json — The mapping from RGB values to country codes

Each country rendered as a unique RGB color for O(1) GPU picking

The TypeScript Interface

// src/lib/services/country-id-texture.service.ts

export interface CountryLookupData {
  metadata: {
    generatedAt: string;
    totalCountries: number;
    encoding: string;
    format: string;
  };
  countries: Record<string, {
    name: string;
    index: number;
    encodedColor: {
      r: number;
      g: number;
      b: number;
      hex: string;
      css: string;
    };
    properties: {
      iso_a3?: string;
      name_long?: string;
      continent?: string;
      region?: string;
      subregion?: string;
    };
  }>;
}

The Service Implementation

// src/lib/services/country-id-texture.service.ts (simplified)

@Injectable({ providedIn: 'root' })
export class CountryIdTextureService {
  private indexToIdMap = new Map<number, string>();

  decodeCountryId(r: number, g: number, b: number): string | null {
    const index = (r << 16) | (g << 8) | b;
    return this.indexToIdMap.get(index) ?? null;
  }
}

The full service handles asset loading, adaptive resolution (2048x1024 for desktop, 1024x512 for mobile), and selection mask generation. The key insight is the constant-time RGB → ID decode using bit shifting.

Texture Configuration: Required Settings

The ID texture requires specific WebGL settings to preserve exact color values:

// Required for correctness:
this.countryIdTexture.format = RGBAFormat;
this.countryIdTexture.minFilter = NearestFilter;  // Prevents color blending
this.countryIdTexture.magFilter = NearestFilter;
this.countryIdTexture.wrapS = ClampToEdgeWrapping;
this.countryIdTexture.wrapT = ClampToEdgeWrapping;
this.countryIdTexture.generateMipmaps = false;    // Mipmaps blend colors

Important: Using LinearFilter instead of NearestFilter would interpolate colors at country borders, corrupting the encoded IDs. This is the most common mistake when implementing GPU picking.

Reading the Pixel on Click

selectCountryAtPoint(x: number, y: number): string | null {
  // Render ID texture to offscreen buffer
  this.renderer.setRenderTarget(this.pickingTexture);
  this.renderer.render(this.pickingScene, this.camera);
  this.renderer.setRenderTarget(null);

  // Read single pixel (flip Y for WebGL coordinates)
  const pixelBuffer = new Uint8Array(4);
  this.renderer.readRenderTargetPixels(
    this.pickingTexture,
    x,
    this.pickingTexture.height - y,
    1, 1,
    pixelBuffer
  );

  return this.countryIdTextureService.decodeCountryId(
    pixelBuffer[0], pixelBuffer[1], pixelBuffer[2]
  );
}

Why This Is O(1)

Operation	CPU Raycasting	GPU Picking
Per-click work	Test ray vs 241 meshes	Read 1 pixel
Complexity	O(n) where n = meshes	O(1) constant
Time	45ms	<1ms
Scales with mesh count	Yes (linear)	No (constant)

The GPU has already rasterized the scene. Reading a pixel is a single memory lookup, regardless of how many countries exist.

Selection Mask: Visual Feedback for Selections

When a user selects a country, we need to highlight it visually. Rather than modifying mesh materials (expensive), we use a second texture as a "selection mask."

Internally, we generate the mask by scanning the ID texture and painting white pixels for selected countries. This avoids per-mesh material updates and keeps selection rendering GPU-bound.

The selection mask is then blended with the globe material in the shader:

// In globe fragment shader
uniform sampler2D selectionMask;

void main() {
  vec4 baseColor = texture2D(baseMap, vUv);
  vec4 selection = texture2D(selectionMask, vUv);

  // Blend selection highlight
  vec3 finalColor = mix(baseColor.rgb, vec3(0.2, 0.8, 0.4), selection.r * 0.5);

  gl_FragColor = vec4(finalColor, 1.0);
}

Solution 2: Front-Facing Hemisphere Detection

GPU picking solves the performance problem, but we still use raycasting for some interactions (hover tooltips, quiz mode). The see-through bug needed a geometric fix.

The Insight: Dot Product

A point on the globe is "front-facing" if it's on the same hemisphere as the camera. We can test this with a dot product:

Camera direction: normalize(camera.position)
Point direction:  normalize(intersection.point)

dot(camera_dir, point_dir) > 0  →  Same hemisphere (front)
dot(camera_dir, point_dir) < 0  →  Opposite hemisphere (back)
dot(camera_dir, point_dir) = 0  →  On the "equator" (edge case)

Why Dot Product Works

The dot product of two unit vectors equals the cosine of the angle between them:

dot(A, B) = |A| * |B| * cos(θ) = cos(θ)  (when A and B are normalized)

cos(0°) = 1      → Vectors point same direction (front-facing)
cos(90°) = 0     → Vectors perpendicular (edge of visible hemisphere)
cos(180°) = -1   → Vectors point opposite directions (back-facing)

For our globe centered at origin:

The camera position vector points FROM the globe center TO the camera
The intersection point vector points FROM the globe center TO the clicked point
If both vectors point "outward" in roughly the same direction, the point is front-facing

Note: This approach assumes the globe is centered at the origin and the camera orbits around it, which is typical for planetary visualizations.

Hemisphere Detection Diagram

                    Camera
                      ◉
                     /|
                    / |
         cameraDir/  |
                 /   |
                ↙    |
          ┌─────────────────┐
         /    FRONT          \
        /   (dot > 0)    ●A   \    A: Front-facing (✓ selectable)
       │        ↗              │       dot(cameraDir, pointA) > 0
       │   Globe               │
       │   Center              │
       │        ↘              │
        \   (dot < 0)    ●B   /    B: Back-facing (✗ filtered out)
         \    BACK           /        dot(cameraDir, pointB) < 0
          └─────────────────┘

The Implementation

// src/app/pages/globe/services/globe-interaction.service.ts

/**
 * Check if a point on the globe is facing the camera (front hemisphere)
 * Uses dot product: positive = front-facing, negative = back-facing
 *
 * @param point The intersection point on the globe surface
 * @param camera The camera to check against
 * @returns true if the point is on the camera-facing side
 */
private isPointFrontFacing(
  point: Vector3,
  camera: PerspectiveCamera,
): boolean {
  // Globe is centered at origin (0, 0, 0)
  // Vector from globe center to intersection point (normalized)
  const pointDirection = point.clone().normalize();

  // Vector from globe center to camera position (normalized)
  const cameraDirection = camera.position.clone().normalize();

  // Dot product > 0 means the point is on the same hemisphere as the camera
  return pointDirection.dot(cameraDirection) > 0;
}

Integrating with Raycasting

async handleCountrySelection(
  event: MouseEvent,
  renderer: { domElement: HTMLCanvasElement },
  camera: PerspectiveCamera,
  countries: Group,
): Promise<string | null> {
  // Get mouse coordinates and convert to normalized device coordinates
  const canvas = renderer.domElement;
  const rect = canvas.getBoundingClientRect();
  const mouse = new Vector2(
    ((event.clientX - rect.left) / canvas.width) * 2 - 1,
    -((event.clientY - rect.top) / canvas.height) * 2 + 1
  );

  // Setup raycaster
  const raycaster = new Raycaster();
  raycaster.near = 0.1;
  raycaster.far = 10;  // Limit ray distance for performance
  raycaster.setFromCamera(mouse, camera);

  const intersects = raycaster.intersectObjects(countries.children, true);

  // Find FIRST intersection that is front-facing
  for (const intersect of intersects) {
    const obj = intersect.object;

    // Skip border lines and non-country meshes
    if (obj.name === 'unified-borders' || obj.userData?.['isUnifiedBorder']) {
      continue;
    }

    if (obj.name.startsWith('selection-mesh-') && obj.type === 'Mesh') {
      // Important: Only accept front-facing intersections
      if (!this.isPointFrontFacing(intersect.point, camera)) {
        continue;
      }
      return this.extractCountryName(obj);
    }
  }

  return null;
}

Applying to Hover Detection Too

The same fix applies to hover tooltips:

async handleCountryHover(
  event: MouseEvent,
  camera: PerspectiveCamera,
  countries: Group,
): Promise<string | null> {
  // Early exit if in quiz mode (different hover behavior)
  if (this.interactionModeService.isQuizMode()) return null;

  const intersects = raycaster.intersectObjects(countries.children, true);

  for (const intersect of intersects) {
    // Same front-facing check
    if (!this.isPointFrontFacing(intersect.point, camera)) {
      continue;
    }

    // Return country name for tooltip
    return this.extractCountryName(intersect.object);
  }

  return null;
}

Visual Explanation

Before fix:
  User views Africa → Click gap between Niger/Nigeria
                   → Ray passes through gap
                   → Hits Argentina on back
                   → Shows Argentina data ❌

After fix:
  User views Africa → Click gap between Niger/Nigeria
                   → Ray passes through gap
                   → Hits Argentina on back
                   → Argentina fails dot product (back-facing)
                   → Returns null (no selection) ✓

  User rotates globe → Views South America → Click Argentina
                    → Argentina passes dot product (front-facing)
                    → Shows Argentina data ✓

Why Not Just...?

Why not limit ray distance?

Setting raycaster.far = 2 (just past the globe surface) doesn't work because:

The exact distance varies with camera zoom
The back of the globe might still be within range at certain angles
You'd miss legitimate clicks on countries at the "edges" of visibility

Why not use backface culling?

Three.js meshes have a side property (FrontSide, BackSide, DoubleSide). Setting material.side = FrontSide makes back-facing triangles invisible, but:

Raycasting still hits back-facing triangles (culling is render-time only)
Country meshes need DoubleSide for proper rendering from all angles

Even if back-facing triangles aren't rendered, raycasting operates on geometry, not fragments—so invisible faces still participate in intersection tests.

Why not just take the first intersection?

We do take the first intersection—but only after filtering out back-facing ones. The key insight is that "first by distance" isn't the same as "first that's visible to the user."

Performance Results

Selection Latency

Method	Time	Complexity
CPU Raycasting (before)	45ms	O(n)
GPU Pixel Read (after)	<1ms	O(1)
Improvement	99.5% faster	—

Bug Fix Verification

After the fix:

Visible countries are always selectable
Back-facing countries are never selectable (until you rotate to face them)
Gaps between borders no longer cause incorrect picks
Hover tooltips follow the same front-facing rule

Memory Overhead

Asset	Size	Notes
ID Texture (desktop)	~8MB	2048x1024 RGBA
ID Texture (mobile)	~2MB	1024x512 RGBA
Lookup JSON	~50KB	Gzipped to ~15KB
Selection Mask	~8MB	Same size as ID texture

The ~16MB GPU memory overhead is acceptable for the performance and UX gains.

How to Verify

# In Chrome DevTools Performance panel:
1. Start recording
2. Click 10 countries rapidly
3. Stop recording
4. Expand "Event Log" → filter for "click"
5. Check "Total Time" for each click event

# Expected:
# Before: 40-50ms per click
# After: <5ms per click (including render)

Tradeoffs and Gotchas

When GPU Picking Works Best

Large number of selectable objects: The more objects, the bigger the win over raycasting
Simple selection (point picking): More complex queries (area selection, proximity) still need CPU
Static or infrequently changing scenes: Regenerating the ID texture is expensive
Known set of selectable objects: IDs must be pre-assigned

When to Stick with Raycasting

Few objects (<50): Raycasting is fast enough, GPU picking adds complexity
Dynamic scenes: Objects added/removed frequently make ID texture maintenance costly
Need intersection details: Raycasting gives you the exact point, normal, UV coordinates
Complex queries: "Find all objects within radius" requires CPU

Common Mistakes

Forgetting to flip Y coordinates: WebGL's origin is bottom-left, DOM's is top-left

// ❌ Wrong: DOM coordinates directly
renderer.readRenderTargetPixels(texture, x, y, 1, 1, buffer);

// ✅ Correct: Flip Y for WebGL
renderer.readRenderTargetPixels(texture, x, texture.height - y, 1, 1, buffer);

Using wrong texture filters: ID textures need NearestFilter to prevent color interpolation

// ❌ Wrong: Linear filtering blends colors at edges
texture.minFilter = LinearFilter;

// ✅ Correct: Nearest filtering preserves exact colors
texture.minFilter = NearestFilter;
texture.magFilter = NearestFilter;

Not handling edge case: index 0: Reserve RGB(0,0,0) for "no country" (ocean, background)

decodeCountryId(r: number, g: number, b: number): string | null {
  const index = (r << 16) | (g << 8) | b;
  if (index === 0) return null;  // Background/ocean
  return this.indexToIdMap.get(index) ?? null;
}

Enabling mipmaps: Mipmaps blend colors at lower detail levels, corrupting IDs

// ❌ Wrong: Mipmaps blend colors
texture.generateMipmaps = true;

// ✅ Correct: No mipmaps for ID textures
texture.generateMipmaps = false;

The Dot Product Edge Case

At exactly 90 degrees (dot product = 0), the point is on the "equator" between hemispheres. We use > 0 rather than >= 0 to be conservative—if you're looking edge-on at a country, you probably didn't mean to click it.

Key Takeaways

GPU picking trades memory for speed: An extra texture gives O(1) selection regardless of mesh count
Encode IDs in RGB channels: 24 bits = 16.7 million unique IDs, more than enough for most applications
Dot product solves hemisphere visibility: Simple vector math prevents "see-through" selection bugs
Use NearestFilter for ID textures: Linear filtering corrupts the encoded colors
Always flip Y for WebGL: DOM and WebGL coordinate systems have opposite Y directions
Adaptive resolution matters: Mobile devices need smaller textures to stay within memory budgets
Selection masks provide efficient feedback: Update a texture instead of modifying mesh materials

The 3D Global Dashboard now responds to clicks in under 1ms, and users can only select countries they can actually see. The Niger/Nigeria bug is gone.