發表文章

目前顯示的是 7月, 2013的文章

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;