OpenGLなどでスプライトの描画をするとき、絵のパターンごとにテクスチャが分かれていると、スプライト1つ1つに対してテクスチャをセットして四角形を描画、次のテクスチャをセットして四角形を描画、というのを繰り返すことになる。しかしそのようなステート変更が増えると非常に負荷がかかる。そこでスプライトシートという方法を使う。

What is a sprite sheet? - The Movie - Performance

あらかじめ複数の画像を組み合わせて1つの大きなテクスチャにまとめてしまう。そうすると実行時にはそのテクスチャを1度セットして、あとは複数のスプライトの四角形をまとめて描画することができるので、負荷を減らすことができる。

問題はそのテクスチャをまとめるツールをどうするかという点。TexturePackerというツールがメジャーなんだけど、7日間の試用期間はあるものの購入には4千円かかる。しかも「1年間のフリーアップデート」と書いてあるので、その後も費用がかかりそう。そりゃたまらん。

というわけでどうにかできないか考えてみた。「texture packing algorithm」でググったところいろいろでてきた。しかしそもそもビンパッキング問題はNP困難とのことで、必ず最適な解が得られるアルゴリズムはないらしい。

Packing Lightmapsには単純な方法のアルゴリズムと疑似コードがのっている。この方法は、四角形の左上隅から詰めていって、詰められた四角形は片方がより大きくなるように分割していく、というもの。

実際に実装してみた。まとめた画像をテクスチャとして使う場合、サイズが2のべき乗になっている必要があるので、そのようにしている:

class RectPacker
  class Rect
    attr_accessor :x, :y, :w, :h
    attr_accessor :object
    def initialize(x, y, w, h)
      @x = x
      @y = y
      @w = w
      @h = h
    end
  end

  class Node
    def initialize(rect)
      @left = @right = nil
      @rect = rect
    end

    def insert(rect, margin)
      if @rect
        return false if rect.w + margin > @rect.w || rect.h + margin > @rect.h

        rect.x = @rect.x
        rect.y = @rect.y
        w = rect.w + margin
        h = rect.h + margin
        dw = @rect.w - w
        dh = @rect.h - h
        if dw > dh
          @left = Node.new(Rect.new(@rect.x, @rect.y + h, w, dh))
          @right = Node.new(Rect.new(@rect.x + w, @rect.y, dw, @rect.h))
        else
          @left = Node.new(Rect.new(@rect.x + w, @rect.y, dw, h))
          @right = Node.new(Rect.new(@rect.x, @rect.y + h, @rect.w, dh))
        end
        @rect = nil
        return true
      else
        return true if @left.insert(rect, margin)
        return @right.insert(rect, margin)
      end
    end
  end

  def pack(image_rects, margin)
    image_rects.sort! {|a, b| [b.w, b.h].sort <=> [a.w, a.h].sort}

    result = nil
    w, h = calc_initial_rect(image_rects)
    loop do
      root = Node.new(Rect.new(0, 0, w, h))
      result = insert_images_to_root(image_rects, root, margin)
      return w, h if result
      # Expand destination size, and retry.
      w > h ? h *= 2 : w *= 2
    end
  end

  def insert_images_to_root(image_rects, root, margin)
    image_rects.each do |image_rect|
      return false unless root.insert(image_rect, margin)
    end
    return true
  end

  def calc_initial_rect(images)
    total_pixel = calc_total_pixel(images)
    w = power_of_2(Math.sqrt(total_pixel).floor) / 2
    h = w
    while w * h < total_pixel
      w > h ? h *= 2 : w *= 2
    end
    return w, h
  end

  def calc_total_pixel(images)
    images.map {|img| img.w * img.h}.inject(&:+)
  end

  def power_of_2(x)
    w = 1
    w *= 2 until x <= w
    return w
  end
end

TexturePackerでは画像を回転させて詰め込んだりするけど、まあそこまでしなくてもいいでしょう。

これを使って、あとは画像を処理するのはRMagickを使ってみた:

require 'rubygems'
require 'optparse'
require 'rexml/document'
require 'RMagick'
require "#{File.dirname(__FILE__)}/rect_packer"
include Magick

module REXML
  class Element
    def tag(key, attr = {}, &block)
      child = REXML::Element.new(key)
      child.add_attributes(attr)
      if block
        result = child.instance_eval(&block)
        if String === result
          child.add_text(result)
        end
      end
      add_element(child)
      return child
    end
  end
end

class RMagickPacker
  def initialize
    @image_base_path = nil
  end

  def set_image_base_path(path)
    @image_base_path = path
  end

  def pack(files, margin, list_file_name, output_format)
    image_fn_map = {}
    images = files.map do |fn|
      path = fn
      if @image_base_path
        path = "#{@image_base_path}/#{fn}"
      end
      img = Magick::ImageList.new(path)
      image_fn_map[img] = fn
      img
    end

    image_rects = images.map do |img|
      rect = RectPacker::Rect.new(0, 0, img.columns, img.rows)
      rect.object = img
      rect
    end

    packer = RectPacker.new
    size = packer.pack(image_rects, margin)
    exit(1) unless size

    w, h = size
    image_file_name = "#{list_file_name}.#{output_format}"
    output_image(image_file_name, w, h, image_rects)
    output_plist("#{list_file_name}.plist", image_file_name, w, h, image_rects, image_fn_map)
  end

  def output_image(file_name, w, h, image_rects)
    packed_image = Image.new(w, h) { self.background_color = 'none' }
    image_rects.each do |image_rect|
      img = image_rect.object
      packed_image.composite!(img, image_rect.x, image_rect.y, CopyCompositeOp)
    end
    packed_image.write(file_name)
  end

  def output_plist(file_name, image_file_name, w, h, image_rects, image_fn_map)
    doc = REXML::Document.new
    doc.add(REXML::XMLDecl.new(version='1.0', encoding='UTF-8'))
    doc.add(REXML::DocType.new('plist', 'PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"'))
    doc.tag('plist', {'version' => '1.0'}) do
      tag('dict') do
        tag('key') { 'frames' }
        tag('dict') do
          image_rects.each do |image_rect|
            img = image_rect.object
            x = image_rect.x
            y = image_rect.y
            w = image_rect.w
            h = image_rect.h
            tag('key') { image_fn_map[img] }
            tag('dict') do
              tag('key') { 'spriteColorRect' }
              tag('string') { "{{0, 0}, {#{w}, #{h}}}" }
              tag('key') { 'spriteOffset' }
              tag('string') { "{0, 0}" }
              tag('key') { 'spriteSize' }
              tag('string') { "{#{w}, #{h}}" }
              tag('key') { 'spriteSourceSize' }
              tag('string') { "{#{w}, #{h}}" }
              tag('key') { 'spriteTrimmed' }
              tag('false')
              tag('key') { 'textureRect' }
              tag('string') { "{{#{x}, #{y}}, {#{w}, #{h}}}" }
              tag('key') { 'textureRotated' }
              tag('false')
            end
          end
        end
        tag('key') { 'metadata' }
        tag('dict') do
          tag('key') { 'version' }
          tag('string') { '0.1' }
          tag('key') { 'format' }
          tag('integer') { '3' }
          tag('key') { 'size' }
          tag('string') { "{#{w}, #{h}}" }
          tag('key') { 'name' }
          tag('string') { image_file_name }
          tag('key') { 'textureFileName' }
          tag('string') { image_file_name }
          tag('key') { 'premultipliedAlpha' }
          tag('false')
        end
      end
    end

    formatter = REXML::Formatters::Pretty.new(2)
    formatter.compact = true
    output = ''
    formatter.write(doc, output)
    open(file_name, 'w') do |out|
      out.print(output.gsub("'", '"'))
    end
  end
end

def main
  list_file_name = 'images'
  output_format = 'png'
  image_base_path = nil
  margin = 0

  opt = OptionParser.new
  opt.on('-o filename') {|v| list_file_name = v}
  opt.on('-f format') {|v| output_format = v}
  opt.on('-i image-base-path') {|v| image_base_path = v}
  opt.on('-m margin') {|v| margin = v.to_i}
  opt.parse!(ARGV)

  files = []
  while gets
    files.push($_.chomp)
  end

  packer = RMagickPacker.new
  if image_base_path
    packer.set_image_base_path(image_base_path)
  end
  packer.pack(files, margin, list_file_name, output_format)
end

if $0 == __FILE__
  main
end

  元の画像をどのようにパックしたかの情報は、cocos2dではplistというxmlフォーマットをサポートしている:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
  <dict>
    <key>frames</key>
    <dict>
      <key>pattern1.png</key>
      <dict>
        <key>spriteColorRect</key>
        <string>{{0, 0}, {80, 112}}</string>
        <key>spriteOffset</key>
        <string>{0, 0}</string>
        <key>spriteSize</key>
        <string>{80, 112}</string>
        <key>spriteSourceSize</key>
        <string>{80, 112}</string>
        <key>spriteTrimmed</key>
        <false/>
        <key>textureRect</key>
        <string>{{0, 0}, {80, 112}}</string>
        <key>textureRotated</key>
        <false/>
      </dict>
      ...

ランダムな大きさの四角形で試した結果:

random-packed-rects

まあいい感じじゃないでしょうか。

  • nVidiaのImprove Batching Using Texture Atlasesに、テクスチャをパックしたときにミップマップで問題が起きることが書いてあるが、難しいことはよくわからない。
  • 上記のアルゴリズムで木構造を使ってるけど、挿入先の四角形の探索は全探索で最初に見つけたところなので、あまり意味がないと思う。
  • Greedyなアルゴリズムなので挿入する四角形を与える順番が大事だと思う。縦横どちらかの長い辺順にしてみた。
  • TexturePackerでは元画像が余白を含んでいる場合その領域は削ったりするんだけど、その辺は今後の課題。