Hi,

I am trying to code a Lightmapper for my 3D engine, and as such I implemented a TexturePacker/Atlas, and although it's working OK, I find it oddly in-effecient. It mostly packs all to the left and leaves a lot of free space to the right.

Here is the code, can you spot anything wrong, or suggest another way to do it? Cheers. I have a test win.form app if required, I could upload it.

Cheers.

using System.Collections.Generic;

namespace Vivid3D.Util.Texture
{
    public class TexTree
    {
        public static List<TreeLeaf> Leafs = new List<TreeLeaf>();

        public TreeLeaf Root
        {
            get;
            set;
        }

        public Rect RC;

        public TexTree ( int w, int h )
        {
            RC = new Rect ( 0, 0, w, h );
            //Root = ne
            //w TreeLeaf (new Rect(0,0,w,h));
        }

        public TreeLeaf Insert ( int w, int h, int id = -1 )
        {
            //return Root.Insert ( w, h );
            if ( Root == null )
            {
                Root = new TreeLeaf ( new Rect ( 0, 0, w, h ), id )
                {
                    Used = true
                };
                Root.Child [ 0 ] = new TreeLeaf ( new Rect ( 0, h, RC.W, RC.H - h ) );
                Root.Child [ 1 ] = new TreeLeaf ( new Rect ( w, 0, RC.W - w, h ) );
            }
            else
            {
                return Root.Insert ( w, h );
            }
            return Root;
        }
    }

    public class TreeLeaf
    {
        public TreeLeaf[] Child = new TreeLeaf[2];
        public Rect RC = new Rect();
        public int TexID = 0;
        public bool Used = false;

        public TreeLeaf ( Rect s, int id = -1 )
        {
            RC = s;
            TexID = -1;
            Child [ 0 ] = Child [ 1 ] = null;
            TexTree.Leafs.Add ( this );
        }

        public TreeLeaf Insert ( int w, int h )
        {
            if ( Used )
            {
                TreeLeaf rn =  Child [ 1 ].Insert ( w, h );
                if ( rn != null )
                {
                    return rn;
                }
                rn = Child [ 0 ].Insert ( w, h );
                if ( rn != null )
                {
                    return rn;
                }
            }
            else
            {
                if ( w < RC.W && h < RC.H )
                {
                    Used = true;

                    Child [ 0 ] = new TreeLeaf ( new Rect ( RC.X, RC.Y + h, RC.W, RC.H - h ) );
                    Child [ 1 ] = new TreeLeaf ( new Rect ( RC.X + w, RC.Y, RC.W - w, h ) );
                    RC.W = w;
                    RC.H = h;
                    return this;
                }
                else
                {
                    return null;
                }
            }
            return null;
        }

        public bool Fits ( int w, int h )
        {
            return w < RC.W && h < RC.H;
        }
    }

    public class Rect
    {
        public float X,Y,W,H;

        public Rect ( )
        {
            X = Y = W = H = 0;
        }

        public Rect ( float x, float y, float w, float h )
        {
            X = x;
            Y = y;
            W = w;
            H = h;
        }
    }
}

Had an idea, what if you had a next pixel map? it would be slightly fuzzy but.

tex 1 = a atlas,  you insert a image, it finds the first free pixel, then tex 2 on that pixel is a value indicating the next pixel location/offset. could this in theory allow for really high packing or am i not seeing something wrong with the idea? I might try giving it a go, i'll upload any images if anyone is interested, source too.

In your algorithm each time you insert an image, you're always picking a horizontal split. This is why you are only able to fill the space to the right with increasingly smaller < h elements.

Check out this post on using kdtree. The altered idea is to alter the direction of your split depending on which dimension is greater.

http://blackpawn.com/texts/lightmaps/default.html

EDIT: found this link from a forum post on here from 2005!