Sprite Sheet Packing: MaxRects Algorithms, Texture Atlases & Memory Optimization

The Catastrophic Cost of Individual Image Files

Novice web developers frequently load visual assets as standalone PNG or WebP files: hero_idle_01.png, hero_run_01.png, bullet.png, coin.png. When rendered in WebGL, this introduces severe performance penalties:

• Network HTTP Waterfall: Discarding packing forces the browser to open hundreds of concurrent HTTP requests, stalling asset loading pipelines and triggering cold-boot delays.
• GPU Texture Binding Overhead: A WebGL context cannot draw a sprite without binding its texture using gl.bindTexture(gl.TEXTURE_2D, texture). Swapping textures flushes the GPU instruction pipeline, forcing a distinct draw call per sprite and destroying batch rendering.
• VRAM Fragmentation: Allocating hundreds of small 32x32 textures leads to severe video memory fragmentation, preventing the GPU memory allocator from maintaining contiguous memory pages.

The MaxRects Bin-Packing Algorithm

Packing dozens of irregular rectangular sprites into a single minimum-area bounding container is an instance of the 2D Bin Packing Problem, which is mathematically NP-hard.

Developed by Jukka Jylänki, the Maximal Rectangles (MaxRects) algorithm is widely acknowledged as the gold standard packing architecture in video game engineering. MaxRects maintains a comprehensive list of all overlapping "maximal free rectangles" within the bin.

The placement pipeline operates through four discrete algorithmic phases:

1. Candidate Selection: Sort all unpackaged sprites by area, perimeter, or max side length descending.
2. Placement Heuristic: Evaluate where to place the sprite among all available free rectangles using a heuristic:
   • BSSF (Best Short Side Fit): Places the sprite into the free rectangle where the smaller remaining edge is minimized.
   • BAF (Best Area Fit): Minimizes the total wasted residual area of the free rectangle.
   • BL (Bottom-Left): Favors packing tightly toward the bottom-left coordinate of the container.
3. Splitting Intersecting Rectangles: Once placed, any free rectangle that intersects the newly placed sprite is split into up to four smaller maximal rectangles along the sprite edges.
4. Redundancy Pruning: Traverse the free list and prune away any rectangle that is completely contained within another larger free rectangle.

export interface SpriteInput {
  id: string;
  width: number;
  height: number;
}

export interface PackedRect {
  x: number;
  y: number;
  width: number;
  height: number;
}

export class MaxRectsBinPacker {
  private binWidth: number;
  private binHeight: number;
  private freeRects: PackedRect[] = [];

  constructor(width: number, height: number) {
    this.binWidth = width;
    this.binHeight = height;
    this.freeRects.push({ x: 0, y: 0, width, height });
  }

  public insert(width: number, height: number): PackedRect | null {
    let bestNode: PackedRect | null = null;
    let bestShortSide = Infinity;
    let bestIdx = -1;

    // Evaluate Best Short Side Fit (BSSF)
    for (let i = 0; i < this.freeRects.length; i++) {
      const r = this.freeRects[i];
      if (r.width >= width && r.height >= height) {
        const leftoverH = Math.abs(r.width - width);
        const leftoverV = Math.abs(r.height - height);
        const shortSide = Math.min(leftoverH, leftoverV);

        if (shortSide < bestShortSide) {
          bestNode = { x: r.x, y: r.y, width, height };
          bestShortSide = shortSide;
          bestIdx = i;
        }
      }
    }

    if (!bestNode) return null;

    this.splitFreeRectangles(bestNode);
    this.pruneRedundantRectangles();
    return bestNode;
  }

  private splitFreeRectangles(placed: PackedRect): void {
    const nextFree: PackedRect[] = [];
    for (const free of this.freeRects) {
      if (!this.intersects(placed, free)) {
        nextFree.push(free);
        continue;
      }

      // Generate 4 prospective split rectangles
      if (placed.x < free.x + free.width && placed.x + placed.width > free.x) {
        if (placed.y > free.y && placed.y < free.y + free.height) {
          nextFree.push({ x: free.x, y: free.y, width: free.width, height: placed.y - free.y });
        }
        if (placed.y + placed.height < free.y + free.height) {
          nextFree.push({ x: free.x, y: placed.y + placed.height, width: free.width, height: free.y + free.height - (placed.y + placed.height) });
        }
      }
      if (placed.y < free.y + free.height && placed.y + placed.height > free.y) {
        if (placed.x > free.x && placed.x < free.x + free.width) {
          nextFree.push({ x: free.x, y: free.y, width: placed.x - free.x, height: free.height });
        }
        if (placed.x + placed.width < free.x + free.width) {
          nextFree.push({ x: placed.x + placed.width, y: free.y, width: free.x + free.width - (placed.x + placed.width), height: free.height });
        }
      }
    }
    this.freeRects = nextFree;
  }

  private pruneRedundantRectangles(): void {
    for (let i = 0; i < this.freeRects.length; i++) {
      for (let j = i + 1; j < this.freeRects.length; j++) {
        if (this.isContained(this.freeRects[i], this.freeRects[j])) {
          this.freeRects.splice(i, 1);
          i--;
          break;
        }
        if (this.isContained(this.freeRects[j], this.freeRects[i])) {
          this.freeRects.splice(j, 1);
          j--;
        }
      }
    }
  }

  private intersects(a: PackedRect, b: PackedRect): boolean {
    return a.x < b.x + b.width && a.x + a.width > b.x && a.y < b.y + b.height && a.y + a.height > b.y;
  }

  private isContained(a: PackedRect, b: PackedRect): boolean {
    return a.x >= b.x && a.y >= b.y && a.x + a.width <= b.x + b.width && a.y + a.height <= b.y + b.height;
  }
}

Eliminating Texture Bleeding via Pixel Extrusion

When a GPU renders a sprite from an atlas, floating-point camera positions, zoom scaling, and mipmapping cause the texture sampler to interpolate across texel boundaries.

If sprites are packed edge-to-edge with 0 padding, bilinear filtering samples color values from adjacent unrelated sprites, causing faint colored lines or seams (texture bleeding).

To solve this, professional texture atlas pipelines apply two defenses:

1. 1-Pixel Border Padding: Inserts transparent space between packed rectangles.
2. 1-Pixel Edge Extrusion: Duplicates the outermost colored texels of each sprite outward into the border margin. When bilinear filtering samples outside the sprite boundary, it samples matching color data, completely eliminating seams.

Whitespace Trimming and Source Offsets

Animation sequences authored in graphics software often contain vast expanses of transparent pixels to maintain a uniform canvas size. Packing these transparent pixels wastes valuable VRAM.

The packing engine crops away transparent borders, recording the trimmed dimensions alongside the original source offset:

{
  "frame": { "x": 128, "y": 64, "w": 48, "h": 72 },
  "trimmed": true,
  "spriteSourceSize": { "x": 16, "y": 8, "w": 48, "h": 72 },
  "sourceSize": { "w": 80, "h": 80 }
}

The WebGL rendering engine uses these offsets to reconstruct the original registration point at runtime, achieving up to 50% higher packing density with zero visual discrepancy.

Comparative Architectural Matrix: Texture Atlas Approaches

Analyzing packing strategies across 2D game pipelines:

Conclusion

Texture atlas optimization is essential for web game performance. Implementing the MaxRects bin-packing algorithm with whitespace trimming and edge extrusion eliminates texture swap draw calls, prevents sub-pixel edge bleeding, and ensures silky 60 FPS WebGL rendering on all gaming devices.