Python Script to build a Texture Page or Sprite Sheet

Why pack textures/images?

If you’re making a game then it’s more efficient to tell the hardware:

1
2
3
4
use packed texture 1
draw primitive 1,2,3,4,5,6
use packed texture 2
draw primitive 7,8,9,10

than to

1
2
3
4
5
use texture 1
draw primitive 1
use texture 2
draw primitive 2
...

The less you do, the more efficient rendering is.

If you’re making a website then again it’s quicker to ask the client browser to load one large image (often called a sprite sheet) than to ask it to load many more smaller textures.

Algorithm

The algorithm we are going to use in called Bin Packing. We want to pack the textures in to one larger texture with the minimum of wasted space. Note that there will always be some wasted space, this is an NP complete problem and Bin Packing just gives you a very good solution not a perfect one

2D bin packing works by using the source images to subdivide the destination image creating a tree of ‘used’ areas of the destination image. This sounds a little complication but it’s actually pretty simple.

Code Overview

class BinPackNode

BinPackNode does the work of subdividing space and recording the tree structure of subdivisions creating left and right children. The BinPackNode has:

  • area which represent the sub rectangle of this image this node covers

  • leftchild, rightchild if this node has been subdivided leftchild and rightchild are BinPackNodes representing the split of this node.

    1
    leftchild.area + rightchild.area == self.area
    
  • filled is a boolean indicating that this node has been filled with an image and can’t be subdivided.

def pack_images

pack_images is a function that does the grunt work of trawling through the images, sorting them in to size order (largest to smallest) and the iteratively adding them to the BinPackNode tree.

class Rect

Rect is a utility class that represents a rectangle. I used this just to make the logic within BinPackNode.insert more concise and easier to follow.

How does it work

The psuedocode for pack_images is:

1
2
3
sort the images in to size order
create a root BinPackNode with an initial size of the target image
for each image insert it to the root BinPackNode

The pseudocode for BinPackNode.insert is:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
if the node has children then
    ask the left child to insert the new image
    if the left child cant fit the image in then
        ask the right child
    if the right child can't fit the image in then
        we can't find the image in to this node
    return

if this node is filled or the new image is bigger than this node then
    we can't fit the image in this node
    return

if the image is the size of this node then
    mark this node as filled
    return

split this node in to a left and right node based on the image
ask the left node to insert the new image
return

Usage

The python code can be run from the command line to pack a set of PNGs that are in a directory:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
usage: txtrpacker.py [-h] [-v] [-pad PAD] [-sort SORT] [-maxdim MAXDIM]
                 [--log LOG]
                 src dst

A utility to take a set of png images and pack them in to a power of two image
with pading. The placements of the source images is printed to stdout in the
format: "filename x y x2 y2"

positional arguments:
  src             src directory
  dst             dest png file

optional arguments:
  -h, --help      show this help message and exit
  -v              enable verbose mode
  -pad PAD        padding on each side of the texture (default: 2)
  -sort SORT      sort algorithm one of maxheight,maxwidth,maxarea (default:
                  maxarea)
  -maxdim MAXDIM  maximum texture size permissable.
  --log LOG       Logging level (INFO, DEBUG, WARN) (default: INFO)

using the example data you could enter:

1
./txtrpacker.py -pad 4 ./testart output.png

Code

This code can be downloaded from this gzip along with some test art from our iOS game Max Astro and our upcoming game (which isn’t public yet). I’ve used to code for a few years so I am pretty confident that it works.

rect.py

 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
__all__ = ['Rect']


class Rect(object):
    """Represent a rectangle in the BinPack tree."""
    def __init__(self, x1, y1, x2, y2):
        self.x1 = x1
        self.y1 = y1  # bottom
        self.x2 = x2
        self.y2 = y2  # top

    def get_width(self):
        return abs(self.x2 - self.x1)

    def set_width(self, w):
        self.x2 = self.x1 + w

    def get_height(self):
        return abs(self.y2 - self.y1)

    def set_height(self, h):
        self.y2 = self.y1 + h

    def get_left(self):
        return self.x1

    def set_left(self, l):
        w = self.get_width()
        self.x1 = l
        self.x2 = l + w

    def get_top(self):
        return self.y2

    def set_top(self, t):
        h = self.get_height()
        self.y2 = t
        self.y1 = t - h

    def get_right(self):
        return self.x2

    def get_bottom(self):
        return self.y1

    def set_bottom(self, y1):
        h = self.get_height()
        self.y1 = y1
        self.y2 = self.y1 + h

    def offset(self, x, y):
        self.left = self.left + x
        self.top = self.top + y
        return self

    def inset(self, d):
        """return a rect which is this rect inset by d in each direction"""
        return Rect(self.x1 + d, self.y1 + d,
                    self.x2 - d, self.y2 - d)

    def inside(self, r):
        """return true if this rectangle is inside r"""
        return self.x1 >= r.x1 and self.x2 <= r.x2\
               and self.y1 >= r.y1 and self.y2 <= r.y2

    width = property(fget=get_width, fset=set_width)
    height = property(fget=get_height, fset=set_height)
    left = property(fget=get_left, fset=set_left)
    top = property(fget=get_top, fset=set_top)
    right = property(fget=get_right)
    bottom = property(fget=get_bottom, fset=set_bottom)

    def __str__(self):
        return "[%f, %f, %f, %f]" % (self.x1, self.y1, self.x2, self.y2)

    def __repr__(self):
        return "Rect[%s]" % str(self)

txtrpacker.py

  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#!/usr/bin/env python
import argparse
import Image
import logging
from copy import copy
from os.path import join
from glob import glob

from rect import Rect

log = logging.getLogger(__name__)


class BinPackNode(object):
    """A Node in a tree of recursively smaller areas within which images can be placed."""
    def __init__(self, area):
        """Create a binpack node
        @param area a Rect describing the area the node covers in texture coorinates
        """
        #the area that I take up in the image.
        self.area = area
        # if I've been subdivided then I always have a left/right child
        self.leftchild = None
        self.rightchild = None
        #I'm a leaf node and an image would be placed here, I can't be suddivided.
        self.filled = False

    def __repr__(self):
        return "<%s %s>" % (self.__class__.__name__, str(self.area))

    def insert(self, newarea):
        """Insert the newarea in to my area.
        @param newarea a Rect to insert in to me by subdividing myself up
        @return the area filled or None if the newarea couldn't be accommodated within this
            node tree
        """
        #if I've been subdivided already then get my child trees to insert the image.
        if self.leftchild and self.rightchild:
            return self.leftchild.insert(newarea) or self.rightchild.insert(newarea)

        #If my area has been used (filled) or the area requested is bigger then my
        # area return None. I can't help you.
        if self.filled or newarea.width > self.area.width or newarea.height > self.area.height:
            return None

        #if the image fits exactly in me then yep, the are has been filled
        if self.area.width == newarea.width and self.area.height == newarea.height:
            self.filled = True
            return self.area

        #I am going to subdivide myself, copy my area in to the two children
        # and then massage them to be useful sizes for placing the newarea.
        leftarea = copy(self.area)
        rightarea = copy(self.area)

        widthdifference = self.area.width - newarea.width
        heightdifference = self.area.height - newarea.height

        if widthdifference > heightdifference:
            leftarea.width = newarea.width
            rightarea.left = rightarea.left + newarea.width
            rightarea.width = rightarea.width - newarea.width
        else:
            leftarea.height = newarea.height
            rightarea.top = rightarea.top + newarea.height
            rightarea.height = rightarea.height - newarea.height

        #create my children and then insert it in to the left child which
        #was carefully crafted about to fit in one dimension.
        self.leftchild = BinPackNode(leftarea)
        self.rightchild = BinPackNode(rightarea)
        return self.leftchild.insert(newarea)


def _imagesize(i):
    return i.size[0] * i.size[1]

#table of heuristics to sort the list of images by before placing
# them in the BinPack Tree NOTE that they are compared backwards
# as we want to go from big to small (r2->r1 as opposed to r1->r2)
sort_heuristics = {
    "maxarea": lambda r1, r2:  cmp(_imagesize(r2[1]), _imagesize(r1[1])),
    "maxwidth": lambda r1, r2: cmp(r2[1].size[0], r1[1].size[0]),
    "maxheight": lambda r1, r2: cmp(r2[1].size[1], r1[1].size[1]),
}


def pack_images(imagelist, padding, sort, maxdim, dstfilename):
    """pack the images in image list in to a pow2 PNg file
    @param imagelist iterable of tuples (image name, image)
    @param padding padding to be applied to all sides of the image
    @param dstfilename the filename to save the packed image to.
    @return a list of ( rect, name, image) tuples describing where the images were placed.
    """

    log.debug("unsorted order:")
    for name, image in imagelist:
        log.debug("\t%s %dx%d" % (name, image.size[0], image.size[1]))

    #sort the images based on the heuristic passed in
    images = sorted(imagelist, cmp=sort_heuristics[sort])

    log.debug("sorted order:")
    for name, image in images:
        log.debug("\t%s %dx%d" % (name, image.size[0], image.size[1]))

    #the start dimension of the target image. this grows
    # by doubling to accomodate the images. Should start
    # on a power of two otherwise it wont end on a power
    # of two. Could possibly start this on the first pow2
    # above the largest image but this works.
    targetdim_x = 64
    targetdim_y = 64
    placement = []
    while True:
        try:
            placement = []
            tree = BinPackNode(Rect(0, 0, targetdim_x, targetdim_y))

            #insert each image into the BinPackNode area. If an image fails to insert
            # we start again with a slightly bigger target size.
            for name, img in images:
                imsize = img.size
                r = Rect(0, 0, imsize[0] + padding * 2, imsize[1] + padding * 2)
                uv = tree.insert(r)
                if uv is None:
                    #the tree couldn't accomodate the area, we'll need to start again.
                    raise ValueError('Pack size too small.')
                uv = uv.inset(padding)
                placement.append((uv, name, img))

            #if we get here we've found a place for all the images so
            # break from the while True loop
            break
        except ValueError:
            log.debug("Taget Dim [%dx%d] too small" % (targetdim_x, targetdim_y))
            if targetdim_x == targetdim_y:
                targetdim_x = targetdim_x * 2
                if targetdim_x > maxdim:
                    raise Exception("Too many textures to pack in to max texture size %dx%d\n" % (maxdim, maxdim))
            else:
                targetdim_y = targetdim_x

    #save the images to the target file packed
    log.info("Packing %d images in to %dx%d" % (len(imagelist), targetdim_x, targetdim_y))
    image = Image.new("RGBA", (targetdim_x, targetdim_y))
    for uv, name, img in placement:
        image.paste(img, (uv.x1, uv.y1))
    #image.show()
    image.save(dstfilename, "PNG")

    return placement

if __name__ == "__main__":
    _description = """A utility to take a set of png images and pack them in to
    a power of two image with padding. The placements of the source images is
    printed to stdout in the format: "filename x y x2 y2"
    """

    _epilog = " example: txtrpacker.py hud/images data/hud/texturepage.png"

    parser = argparse.ArgumentParser(description=_description, epilog=_epilog)
    parser.add_argument("-v", action="store_true",
                        help="enable verbose mode",
                        default=False)
    parser.add_argument("-pad", type=int,
                        help="padding on each side of the texture (default: 2)",
                        default=2)
    parser.add_argument("-sort", type=str, default="maxarea",
                        help="sort algorithm one of %s (default: maxarea)" % ",".join(sort_heuristics.keys()))
    parser.add_argument("-maxdim", type=int, default=4096,
                        help="maximum texture size permissable.")
    parser.add_argument("--log", type=str,
                        help="Logging level (INFO, DEBUG, WARN) (default: INFO)",
                        default="INFO")
    parser.add_argument("src", type=str, help="src directory")
    parser.add_argument("dst", type=str, help="dest png file")

    args = parser.parse_args()
    numeric_level = getattr(logging, args.log.upper(), None)
    if not isinstance(numeric_level, int):
        log.error('Invalid log level: %s' % args.log)
        exit(-1)
    logging.basicConfig(level=numeric_level)

    if args.sort not in sort_heuristics:
        log.error("Uknown sort parameter '%s'" % args.sort)
        exit(-1)

    #get a list of PNG files in the current directory
    names = glob(join(args.src, "*.png"))
    #create a list of PIL Image objects, sorted by size
    images = [(name, Image.open(name)) for name in names]

    placements = pack_images(images, args.pad, args.sort, args.maxdim, args.dst)
    for area, name, im in placements:
        print("%s %d %d %d %d" % (name, area.x1, area.y1, area.x2, area.y2))

Comments