2D Bin Packing: Why are my images overlapping?

Question

I ported this 2D bin-packing algorithm from JavaScript to PHP and I'm using it to lay out some images in a sprite map.

It works for regularly shaped images (e.g., all squares) but it's producing slightly broken results for larger, more complex data sets.

You can see that 16 is a long, thin image, and 118 fits snugly underneath it. Then 57 is a bit taller, but then 121 and 126 get placed inline with 118/just below 16 which overlaps 57. Not sure why it's doing this.

Anyone know where I might be going wrong?

<?php

class Block {
    /** @var int */
    public $width;
    /** @var int */
    public $height;

    public function __construct($width, $height) {
        $this->width = $width;
        $this->height = $height;
    }
}

class Sprite extends Block {
    /** @var int */
    public $x;
    /** @var int */
    public $y;
    /** @var bool */
    public $used ;
    /** @var Sprite  */
    public $down;
    /** @var Sprite  */
    public $right;

    public function __construct($x, $y, $width, $height, $used=false, $down=null, $right=null) {
        $this->x = $x;
        $this->y = $y;
        $this->width = $width;
        $this->height = $height;
        $this->used = $used;
        $this->down = $down;
        $this->right = $right;
    }

    public function __toString() {
        return "$this->x $this->y $this->width $this->height";
    }
}

class Image extends Block {
    /** @var string */
    public $filePath;
    /** @var Sprite */
    public $fit;

    public function __construct($filePath, $width, $height) {
        $this->filePath = $filePath;
        $this->width = $width;
        $this->height = $height;
    }
}

class Packer {
    /** @var Sprite */
    public $root;

    /**
     * @param Image[] $images
     */
    public function fit($images) {
        $len = count($images);
        $w = $len > 0 ? $images[0]->width : 0;
        $h = $len > 0 ? $images[0]->height : 0;
        $this->root = new Sprite(0,0,$w,$h);
        foreach($images as $img) {
            if($node = $this->findNode($this->root, $img->width, $img->height)) {
                $img->fit = $this->splitNode($node, $img->width, $img->height);
            } else {
                $img->fit = $this->growNode($img->width, $img->height);
            }
        }
    }

    /**
     * @param Sprite $node
     * @param int $w
     * @param int $h
     *
     * @return Sprite
     */
    private function findNode($node, $w, $h) {
        if($node->used) {
            return $this->findNode($node->right, $w, $h) ?: $this->findNode($node->down, $w, $h);
        } elseif($w <= $node->width && $h <= $node->height) {
            return $node;
        }
        return null;
    }

    /**
     * @param Sprite $node
     * @param int $w
     * @param int $h
     *
     * @return Sprite
     */
    private function splitNode($node, $w, $h) {
        $node->used = true;
        $node->down = new Sprite($node->x, $node->y + $h, $node->width, $node->height - $h);
        $node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $node->height);
        return $node;
    }

    private function growNode($w, $h) {
        $canGrowDown = $w <= $this->root->width;
        $canGrowRight = $h <= $this->root->height;

        $shouldGrowDown = $canGrowDown && $this->root->width >= ($this->root->height + $h);
        $shouldGrowRight = $canGrowRight && $this->root->height >= ($this->root->width + $w);

        if($shouldGrowRight) {
            return $this->growRight($w, $h);
        } elseif($shouldGrowDown) {
            return $this->growDown($w, $h);
        } elseif($canGrowRight) {
            return $this->growRight($w, $h);
        } elseif($canGrowDown) {
            return $this->growDown($w, $h);
        }
        throw new Exception("Could not grow");
    }

    /**
     * @param int $w
     * @param int $h
     *
     * @throws Exception
     * @return Sprite
     */
    private function growRight($w, $h) {
        $node = new Sprite($this->root->width, 0, $w, $this->root->height);
        $this->root = new Sprite(0, 0, $this->root->width + $w, $this->root->height, true, $this->root, $node);
        return $this->splitNode($node, $w, $h);
    }

    /**
     * @param int $w
     * @param int $h
     *
     * @throws Exception
     * @return Sprite
     */
    private function growDown($w, $h){
        $node = new Sprite(0, $this->root->height, $this->root->width, $h);
        $this->root = new Sprite(0, 0, $this->root->width, $this->root->height + $h, true, $node, $this->root);
        return $this->splitNode($node, $w, $h);
    }
}

class Program {

    private static function imageCreateFromAny($filename) {
        return imagecreatefromstring(file_get_contents($filename));
    }

    private static function imageCreateTrueColorTransparent($width, $height) {
        $im = imagecreatetruecolor($width, $height);
        imagesavealpha($im, true);
        $transColor = imagecolorallocatealpha($im, 0, 0, 0, 127);
        imagefill($im, 0, 0, $transColor);
        return $im;
    }

    public static function main() {
        /** @var Image[] $images */
        $images = array();
        $di = new DirectoryIterator('test/7');
        foreach($di as $f) {
            /** @var $f DirectoryIterator */
            if(!$f->isFile()) continue;
            $filePath = $f->getPathname();
            list($w, $h) = getimagesize($filePath);
            if(!$w || !$h) {
                echo "could not get width/height for $filePath -- skipping\n";
                continue;
            }
            $images[] = new Image($filePath, $w, $h);
        }
        usort($images, function($a, $b) {
//            return max($a->width, $a->height) < max($b->width, $b->height) ? 1 : -1;
            if($a->width > $a->height) {
                $aMax = $a->width;
                $aMin = $a->height;
            } else {
                $aMin = $a->width;
                $aMax = $a->height;
            }
            if($b->width > $b->height) {
                $bMax = $b->width;
                $bMin = $b->height;
            } else {
                $bMin = $b->width;
                $bMax = $b->height;
            }
            if($aMax > $bMax) return -1;
            if($aMax < $bMax) return 1;
            if($aMin > $bMin) return -1;
            if($aMin < $bMin) return 1;
            return strcmp($a->filePath, $b->filePath);
        });
        $packer = new Packer();
        $packer->fit($images);
        $spritesheet = self::imageCreateTrueColorTransparent($packer->root->width, $packer->root->height);
        $black = imagecolorallocate($spritesheet, 0, 0, 0);
        foreach($images as $i=>$img) {
            $r = mt_rand(0, 255);
            $g = mt_rand(0, 255);
            $b = mt_rand(0, 255);
            imagefilledrectangle($spritesheet, $img->fit->x, $img->fit->y, $img->fit->x+$img->width, $img->fit->y+$img->height, imagecolorallocatealpha($spritesheet, $r, $g, $b, 64));
            imagerectangle($spritesheet, $img->fit->x, $img->fit->y, $img->fit->x+$img->width, $img->fit->y+$img->height, imagecolorallocate($spritesheet, $r, $g, $b));
            imagestring($spritesheet, 5, $img->fit->x + 2, $img->fit->y + 2, $i, $black);
//            imagecopy($spritesheet, self::imageCreateFromAny($img->filePath), $img->fit->x, $img->fit->y, 0, 0, $img->width, $img->height);
        }
        imagepng($spritesheet, 'spritesheet.png');
        echo "done!\n";
    }
}


if(php_sapi_name() === 'cli' && __FILE__ == realpath($argv[0])) {
    Program::main();
}

Update: Noticed a couple places the code should never be able to hit and threw exceptions instead; realized that findNode will always find the newly created node and there's no sense searching for what we already have. Cleaned up a little, but it's still exhibiting the exact same behaviour. Beginning to think this algo is unworkable.

Answer 1

The problem is in the splitNode function:

private function splitNode($node, $w, $h) {
        $node->used = true;
        $node->down = new Sprite($node->x, $node->y + $h, $node->width, $node->height - $h);
        $node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $node->height);
        return $node;
}

in particular the height of the new node on node->right should be the height of the new block not the height of the node, so this line is wrong:

$node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $node->height);

and this is the correction:

$node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $h);

Otherwise the new node would be bigger of the actual space it has and it will eventually overlap with other nodes.

Here some info on this algorithm and the original javascript implementation: http://codeincomplete.com/posts/bin-packing/

This is my php implementation (using also sort maxside on the blocks before starting the algorithm).

class Node {
    public $x;
    public $y;
    public $w;
    public $h;
    public $used;
    public $right;
    public $down;

    public function __construct($x, $y, $w, $h, $used=false, $right=null, $down=null) {
        $this->x = $x;
        $this->y = $y;
        $this->w = $w;
        $this->h = $h;
        $this->used = $used;
        $this->right = $right;
        $this->down = $down;        
    }
}


class BinTreePacking {
    public $root;

    public function __construct($w, $h) {
        $this->init($w, $h);
    }

    public function init($w, $h) {        
        $this->root = new Node(0, 0, $w, $h);        
    }

    public function fit($blocks) {

        $blocks = $this->sortMaxside($blocks);

        foreach($blocks as &$block) {

            $block['fit'] = null;

            if($node = $this->findNode($this->root, $block['w'], $block['h'])) {
                $block['fit'] = $this->splitNode($node, $block['w'], $block['h']);
            } 
        }

        return $blocks;        
    }

    public function findNode($node, $w, $h) {
        if($node->used) {
            return $this->findNode($node->right, $w, $h) ?: $this->findNode($node->down, $w, $h);            
        }
        else if($w <= $node->w && $h <= $node->h) {       
            return $node;
        }
        return null;        
    }

    public function splitNode($node, $w, $h) {  
        $node->used = true;      
        $node->down = new Node($node->x, $node->y + $h, $node->w, $node->h - $h);
        $node->right = new Node($node->x + $w, $node->y, $node->w - $w, $h);
        return $node;
    }

    public function sortMaxside($blocks) {
        usort($blocks, function($a, $b) {
            $a_maxside = max($a['w'], $a['h']);
            $b_maxside = max($b['w'], $b['h']);
            return $a_maxside < $b_maxside;
        });
        return $blocks;
    }
}

Answer 2

A better bin-packing is from blackpawn:http://www.blackpawn.com/texts/lightmaps/. It doesn't uses a grow-function. There is another example in JS: http://incise.org/2d-bin-packing-with-javascript-and-canvas.html and the repository: https://github.com/mackstann/binpack.