TexturePackerを自作した

2013-10-05

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

What is a sprite sheet? - The Movie - Performance

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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を使ってみた:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
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フォーマットをサポートしている:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<?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では元画像が余白を含んでいる場合その領域は削ったりするんだけど、その辺は今後の課題。