Texture packing algorithm

將小圖合併成大圖是最佳化的一種技巧，合併的時機可以是在程式編譯時期，透過工具或者是人工方式作到。或者也能在程式執行時期，由程式自動將小圖合併。這牽涉到怎麼將小圖合併成大圖的演算法，同時在繪圖時也需要支援怎麼從大圖裡抽取出原本是小圖的相關資訊等等。

這裡只對小圖合併大圖作簡介，提供一個簡單的演算法。

首先想到的是很直接的作法：

假設大圖是一張矩形，而小圖也都是矩形。一開始有張空白的大圖，當第一張小圖要擺進大圖時，先確認這張小圖是否可以放進這張空白的大圖裡，如果答案是可以的話，則將這張小圖擺進大圖的左上角位置。接著將空白大圖剩下來的空白區域切割成二塊空白矩形。切割的方法是，小圖以右及小圖以下作分界。

如圖所示，把1號小圖放進大圖後，剩下來的空白區域可以依小圖位置往右往下切成AB二塊較小的空白區塊。

接下來繼續同樣的步驟依序再擺入其它的小圖，如下圖所示。2號小圖可以擺的進去原來切出來的A號空白區塊，把2號小圖放進去後，剩下來的空白區域再以同樣的方法再切成AB二塊空白區塊。

依此累推，將各小圖一個一個塞進去，如果某張小圖找不到可以塞的進去的空白區塊，則再新開另一張空白大圖即可。

因為每次會把剩餘的空白區域切割成二塊，所以很自然的在實作上可以應用一個二元樹的結構，將每個節點分成左右二個子樹，底下列出主要的虛擬碼。

Node::Add(Image)
{
  if (NotImageAdded()) {
    if (IsImageFit(Image)) {
      AddImage(Image);
      Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundTop + ImageHeight);
      Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundRight, BoundBottom);
      return true;
    }
    return false;
  }
  if (Left->Add(Image)) {
    return true;
  }
  if (Right->Add(Image)) {
    return true;
  }
  return false;
}

如上圖，是依此演算法實作出來的一個測試程式的結果。隨機產生100個15x15~165x165之間的小圖，想辨法擺進一張1024x1024的大圖。
　
可以看到結果有22張小圖放不進去大圖裡，但從結果的顯示來看，這張大圖裡似乎有太多空白區域因為切割的方式，造成太多小碎片以致於浪費了，很難再塞入大一點的小圖。所以這個演算法，有很大的改進空間。

;

上一個演算法裡面，切割剩餘空白區域的方式很簡單的只根據加入的小圖的大小，切成右及下二塊，很容易造成小碎片。所以如果改善切割的方式，減少碎片的話，就可以塞入更多的小圖到大點裡去。

原來的方法一律都是以小圖的底的延長線當作是切割線，切出在小圖右及下的二塊區域。現在改善切割的方法，切割時同時還要考慮切的方向。改善方法以計算小圖的寬高及區塊的寬高差異量來決定切割線是水平或垂直方法。

改良後的演算法如下。

Node::Add(Image)
{
  if (NotImageAdded()) {
    if (IsImageFit(Image)) {
      AddImage(Image);
      if (BoundWidth - ImageWidth > BoundHeight - ImageHeight) {
        Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundBottom);
        Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundLeft + ImageWidth, BoundBottom);
      } else {
        Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundTop + ImageHeight);
        Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundRight, BoundBottom);
      }
      return true;
    }
    return false;
  }
  if (Left->Add(Image)) {
    return true;
  }
  if (Right->Add(Image)) {
    return true;
  }
  return false;
}

只需一點點改善，就可以得到更好的結果，可以在同一張大圖裡塞入更多的小圖。如下圖所示，是改良後的一個測試結果。